| paper | d4-conf-aaai-2017-0205 |
| 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: NP-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given \(C\) with \(|C|=m\), a committee size \(k\), a distance bound \(d\), and a support \(\mathcal A\subseteq 2^C\) of \(\tau\) approval types with positive binary-rational masses \(\mu_A\) summing to \(1\), is there a committee \(K\subseteq C\), \(|K|=k\), such that \(\max_{A\in\mathcal A}|A\triangle K|\le d\)?
The society is a distribution over approval-set types; each type \(A\) has mass \(\mu_A\). The decision is one integral size-\(k\) committee, and the objective bounds the worst approval mismatch over all positive-mass types, equivalently the essential supremum of \(|A\triangle K|\).
A positive-mass type can constrain the radius even when its mass is arbitrarily small, then disappear as masses converge to zero; the proposed model retains that type explicitly in its support.
fatal: False
The mirror covers the decision problem and the ETH lower bound in Theorem 3.3. It leaves the approximation results in Theorems 4.1, 5.1, and 5.4 unclaimed.
The strongest case I believe is a literal continuous-population version of Minimax Approval Voting, anchored on Theorem 3.3. The authors prove that, assuming ETH, Minimax Approval Voting has no algorithm running in \(2^{o(d\log d)}\operatorname{poly}(n,m)\) time, where \(n\) is the number of votes, \(m\) the number of candidates, and \(d\) the maximum allowed Hamming distance. The proof is in this paper: it reduces from \(k\times k\)-Clique using Lemma 3.1 and the ETH lower bound cited as Theorem 3.2. This is my lead anchor because it is a hardness result, and the reduction gives a direct route into the continuous setting.
Call the mirror Continuous Minimax Approval Voting. An instance consists of a candidate set \(C\) of size \(m\), a committee size \(k\), a nonempty support \(\mathcal A\subseteq 2^C\) of \(\tau\) approval types, a positive binary-rational mass \(\mu_A\) for each \(A\in\mathcal A\), with \(\sum_{A\in\mathcal A}\mu_A=1\), and a distance bound \(d\). A type \(A\) means that fraction \(\mu_A\) of the population approves exactly the candidates in \(A\). The question is whether there is a committee \(K\subseteq C\), \(|K|=k\), such that every positive-mass type satisfies \(|A\triangle K|\le d\). A solution is the committee \(K\); equivalently, the optimization version minimizes \(R_\mu(K)=\max_{A:\mu_A>0}|A\triangle K|\).
A plausible regime is a large approval election or recurring public consultation in which many participants reuse a relatively small set of ballot patterns: \(N\) people, but \(\tau\ll N\) distinct approval sets. Agents with the same approval set are indistinguishable for this rule, and their mass is their fraction of the population. The committee is a single decision for everyone; its objective is to bound the worst individual’s approval mismatch. That worst-case criterion is exactly what makes a small but present group count fully. This is a natural continuum analogue of the paper’s egalitarian objective.
Theorem 3.3 transfers to this problem: assuming ETH, there is no \(2^{o(d\log d)}\operatorname{poly}(\tau,m,L)\)-time algorithm, where \(L\) is the encoding length of the masses. Map each vote type in a discrete instance to its fraction of the electorate. Conversely, for this maximum-distance objective, any continuous instance has the same answer as the discrete instance containing one vote of each supported type. In particular, the paper’s reduction can be represented by a continuous society with positive rational mass on each constructed type, preserving its yes/no answer and its parameters up to polynomial input size. I expect this problem to be Class B: hardness transfers. The reduction’s combinatorics live in the candidate agenda and committee choice—the construction has \(m=\Theta(k^2)\) and \(d=\Theta(k)\)—rather than in the number of repeated voters.
This mirror covers the paper’s ETH lower bound, not its approximation results. I would not count the PTAS results as additional anchors here: their continuous versions would use the same support-based objective and add no distinct case.
The weakest point is substantial: the masses do not affect the answer except by determining which types have positive mass. The continuous formulation therefore adds a population interpretation, but does not create a new optimization landscape or a tractability gain. Still, the authors could plausibly recognize it as their problem over a nonatomic population: Minimax Approval Voting minimizes the worst individual mismatch, and its continuous form is the essential supremum of that same quantity. The further questions are whether useful restrictions on the approval-type support make the problem tractable, and how its complexity changes under parameters such as \(\tau\) or structured approval sets. Those are follow-up questions about this mirror; changing the objective to depend on group mass would be a different problem.
The strongest objection to Theorem 3.3 is that its natural continuous version has no population weights in it. For a committee \(K\), the continuous worst-case radius is
\[ R_\mu(K)=\operatorname*{ess\,sup}_{A\sim\mu}|A\triangle K| =\max_{A:\mu_A>0}|A\triangle K|. \]
So any two societies with the same support have exactly the same feasible committees and objective, however differently their mass is distributed. Conversely, any finite set of approval types can be given uniform positive masses. The continuous problem is therefore precisely Minimax Approval Voting on the deduplicated set of ballot types. Theorem 3.3 transfers, but only by this direct identification: neither its parameter \(d\) nor its optimization problem acquires a population-mass dimension.
The problem is not that the transferred hardness result is dull; the programme explicitly allows that outcome. It is that there is no substantive population question for the weights to pose here. Duplicate voters were already irrelevant to a maximum-over-voters objective. A continuous encoding makes the electorate a distribution syntactically, while the computation sees only which types occur. The usual population-limit intuition is also unstable for this objective: if one type has mass \(1/N\), it constrains the radius for every finite \(N\), but disappears from the limiting distribution when \(N\) tends to infinity. Keeping it in the limit requires retaining extra support information; using a mass-sensitive tail radius instead changes the objective.
That tail-radius variant could be worth studying: for example, minimize \(r\) such that at least \(1-\alpha\) of the population has approval distance at most \(r\). But it tolerates an \(\alpha\) fraction of voters, so it is a different rule, not a continuous formulation of the paper’s minimax result. It supplies no reason to treat Theorem 3.3 as its anchor.
This is the best case against the mirror, but it is weak under the programme’s stated gate. A distribution over approval types is a sensible high-multiplicity regime, and the paper’s authors could readily recognize essential-supremum Minimax Approval Voting as their problem. Since an unchanged answer is not itself an objection, the support-only dependence may be judged an immediate Class B mirror rather than a reason to reject it. I cannot honestly claim this argument defeats the anchor outright.
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.