| paper | d4-conf-aaai-2014-0060 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: For every fixed \(0<\varepsilon<1\), achieving a \(\tau^{1-\varepsilon}\)-approximation is NP-hard; no algorithm polynomial in \(m,\tau,L\) achieves this guarantee unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 16
statement extracted from the paper’s text layer
Given candidates \(C\) and a rational mass distribution \(\mu\) over supported complete rankings \(T\), choose retained masses \(0\leq \nu_t\leq\mu_t\) to maximize \(\sum_{t\in T}\nu_t\), subject to this condition: for every candidate mapping \(\xi\) and every \(\Phi\in\Gamma_{\rm sp}\), at least one condition \(\phi\in\Phi\) has zero retained mass, \(\sum_{t\in T:t\models_\xi\phi}\nu_t=0\).
A society is a rational mass distribution \(\mu\) over complete ranking types \(T\) on \(C\). The decision chooses how much of each type to retain, \(\nu_t\in[0,\mu_t]\); the objective is maximum retained mass, and feasibility means the retained society contains no occurrence of either single-peakedness-forbidden configuration in \(\Gamma_{\rm sp}\).
The mirror covers Corollary 16 for \(\Gamma_{\rm sp}\)-VDEL\(^{-}\). It leaves the paper’s candidate-deletion results, other preference domains, approximation algorithms, and parameterized results aside.
The strongest mirror is the paper’s voter-deletion problem for single-peakedness. Picture a large public consultation on a fixed set of alternatives: many respondents submit complete rankings, but the number \(\tau\) of distinct rankings is modest compared with the population \(N\). A ranking is a complete type, and its mass \(\mu_t\) is the fraction of respondents who submitted it. The question is then how large a share of the society can be retained while making the retained profile exactly single-peaked.
Call this problem SP-MaxRetain\(_\infty\). An instance is a candidate set \(C\) and a list of supported rankings \(t\), each with binary rational mass \(\mu_t>0\), with \(\sum_t\mu_t=1\). A solution is a retained-mass vector \(\nu\), where \(0\leq\nu_t\leq\mu_t\); maximize \(\sum_t\nu_t\), subject to the retained society containing no single-peakedness-forbidden configuration.
Precisely, the paper characterizes single-peakedness by \(\Gamma_{\rm sp}=\{\Phi_\alpha,\Phi_W\}\). The conditions of \(\Phi_\alpha\) are \(abc\land db\) and \(cba\land db\); those of \(\Phi_W\) are \(ac\land bc\), \(ab\land cb\), and \(ba\land ca\). Here, for example, \(abc\) means \(a\succ b\succ c\), and \(db\) means \(d\succ b\). For every candidate mapping \(\xi\) and every \(\Phi\in\Gamma_{\rm sp}\), the retained society must have zero mass in at least one of the condition classes of \(\Phi\) under \(\xi\). Equivalently, the retained rankings must contain no occurrence of either forbidden configuration.
The hardness anchor is Corollary 16, proved here: for each \(\Gamma\in\{\Gamma_W,\Gamma_B,\Gamma_M,\Gamma_C,\Gamma_{\rm sp},\Gamma_{\rm scv},\Gamma_{\rm gs}\}\), \(\Gamma\)-VDEL\(^{-}\) cannot be approximated within \(n^{1-\epsilon}\), for any \(\epsilon>0\), unless \(P=NP\). I rely on its \(\Gamma_{\rm sp}\) case: given an election with \(n\) voters, maximizing the number of surviving voters whose profile avoids the forbidden configurations has that inapproximability. The paper derives the corollary from its approximation-preserving reduction in Theorem 15 and cited Independent Set inapproximability results.
This is a natural high-multiplicity mirror of that problem. For a finite profile with \(n_t\) voters of ranking \(t\), set \(\mu_t=n_t/N\), where \(N=\sum_t n_t\). Feasibility depends on which rankings remain present: keeping any positive number of voters of a type gives the same support, while keeping more of them improves the objective. Thus an optimum can retain either all or none of each type, and maximizing retained mass gives exactly the finite optimum divided by \(N\). Cloning every voter any number of times leaves \(\mu\) and the continuous instance unchanged, so the same instance can represent populations with \(N/\tau\) arbitrarily large. The authors could reasonably recognize this as their voter-deletion question expressed as the share of a society to retain.
I expect hardness to transfer for exact optimization. In fact, the forbidden-pattern constraints depend only on whether each type has positive retained mass. If \(0<\nu_t<\mu_t\), raising \(\nu_t\) to \(\mu_t\) changes no configuration, so there is always an all-or-none optimum by type. The problem is therefore a weighted selection problem over the supported rankings, not a linear program made easy by fractional masses. The corollary’s approximation threshold in \(n\) should not be claimed unchanged as a bound in \(\tau\) or the bit length \(L\); that would need its own analysis.
This case covers the paper’s \(\Gamma_{\rm sp}\)-VDEL\(^{-}\) result, not its candidate-deletion results or every domain it studies. Its weakness is also its boundary: continuization gives a convincing population model and a clean normalized objective, but it does not dissolve the configuration-selection combinatorics. Natural next questions are whether useful approximation guarantees can be stated in \(m,\tau,L\), and how parameterized algorithms change when type masses are binary rationals rather than voter counts.
The anchor I can challenge is Corollary 16 for \(\Gamma_{\rm sp}\)-VDEL\(^{-}\). The proposed consultation scenario is credible, and rankings are complete types for this problem. I don’t see a sound way to argue that high multiplicity is meaningless here.
The strongest case against the mirror is that exact forbidden-configuration avoidance depends only on which types have positive retained mass. For a fixed candidate mapping and forbidden configuration, an occurrence exists precisely when every condition class has positive mass. Because the configurations are exact, those classes cannot be supplied by the same ranking type. If a feasible solution retains some positive amount of a type, raising that amount to its full input mass does not change the retained support or create a new occurrence. So an optimum can retain each type either wholly or not at all.
That reduces SP-MaxRetain\(_\infty\) to maximum-weight selection of a subset of supported rankings that contains no forbidden hyperedge, with the type masses as weights. It is a sensible weighted high-multiplicity problem, but it has no fractional optimum for the exact objective and no evident opening for the continuous-optimization machinery that motivates much of the programme.
There is also a gap in the hardness claim. Corollary 16 gives an inapproximability bound in the number \(n\) of explicitly listed voters. It does not by itself give the corresponding bound in \(m,\tau,L\) for binary-rational type masses. Expanding a weighted type into repeated voters may take time proportional to its multiplicity, which can be exponential in the mass’s bit length. The proponent correctly avoids claiming that the paper’s approximation threshold transfers to the continuous input parameters. The resulting weighted problem may still be hard, but that is a separate result to establish.
The better version of the mirror—retaining arbitrary fractions of each type—does not fix the issue: fractions strictly between zero and the full mass leave support unchanged. One could instead limit the mass of forbidden patterns or study an approximate notion of structure, where fractional decisions matter. But that changes the exact voter-deletion question, so it is not a stronger mirror of this anchor.
This makes the case against the anchor a case about fit: it is a weighted combinatorial reformulation, rather than a problem whose exact continuization exposes a new continuous-optimization question. That could make it a weaker flagship for ChoCo. It is not enough to establish that the mirror is unworthy, though. The paper’s result and the consultation regime make a legitimate, recognizable high-multiplicity problem, and the programme explicitly values identifying where continuization stops helping. The honest negative case is therefore weak: this anchor likely survives, as a possible boundary case rather than a tractability opportunity.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.