| paper | d4-conf-atal-2015-0263 |
| 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: \(\mathrm{NP}\)-complete, even with dyadic masses and threshold \(\rho=m/2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a candidate set \(A\), a finite support \(\mathcal T\subseteq 2^A\), positive binary-rational masses \(\mu_P\) summing to \(1\), and a threshold \(\rho\), with \(\sum_{P\ni a}\mu_P=\tfrac12\) for each \(a\in A\), is there a committee \(S\subseteq A\) such that \(\max_{P\in\mathcal T} d_H(P,S)\le\rho\)?
A finite-support distribution \(\mu\) over approval-ballot types \(P\subseteq A\); the decision variable is a committee \(S\subseteq A\), and the objective is to minimize the worst Hamming distance \(\max_{P:\mu_P>0}d_H(P,S)\), subject to balanced approval mass for every candidate.
The mirror covers Theorem 1’s balanced MINIMAX hardness result; it leaves the other OWA complexity, approximation, and manipulability results unaddressed.
The lead mirror is continuous-population MINIMAX approval voting. A type is an approval ballot \(P\subseteq A\), completely describing how an agent evaluates the candidates or issues. A society is a finite-support distribution \(\mu\) over those types: each listed type has positive rational mass, and the masses sum to \(1\). The regime is a large electorate in which many residents share one of a relatively small number \(\tau\) of ballot patterns. That fits, for example, a city choosing a common bundle of policies when its residents’ approval patterns recur. Replicating every voter in a discrete profile increases the headcount without increasing \(\tau\), so the model does not depend on treating each resident as a separate type.
The anchor is Theorem 1, which states that the decision version of MINIMAX is NP-complete even for balanced elections, where every candidate is approved by exactly half the voters. The paper asserts this result; it omits the proof for space and describes it as a reduction from a balanced variant of 3-SAT cited as [4]. It is therefore a result of this paper, not merely a citation of prior MINIMAX hardness.
Here is the continuous decision problem I would hand to a prover:
Balanced Continuous MINIMAX Approval. An instance consists of a candidate set \(A\), a finite listed support \(\mathcal T\subseteq 2^A\), positive binary-rational masses \(\mu_P\) summing to \(1\), and a threshold \(\rho\). Require that \(\sum_{P\ni a}\mu_P=\tfrac12\) for every \(a\in A\). Is there a committee \(S\subseteq A\) such that
\[ > \max_{P\in\mathcal T} |P\triangle S|\le \rho? > \]
A solution is such a set \(S\).
This is the population-distribution version of the paper’s underlying winner-determination problem: choose the common committee that minimizes the worst Hamming distance from any represented voter type. The masses are binary rationals and the input size is measured in \(|A|\), \(\tau\), and their bit length. For every balanced discrete profile in Theorem 1, set \(\mu_P\) to the fraction of voters with ballot \(P\). The resulting instance has the same feasible committees and the same maximum distance. Thus the theorem’s NP-hardness transfers to this continuous problem; membership in NP follows by checking a proposed committee against the listed types. I expect this mirror to be Class B: hardness transfers. The hard choices remain in the candidate and ballot-pattern structure, not in the number of copies of each voter.
The authors should recognize this as their problem: the objective and committee decision are unchanged, and the society is what has been represented by type masses. The normative setting matters, though. The paper itself questions whether MINIMAX is appropriate for large electorates because a single very unhappy voter can exert substantial influence. A plausible continuous application must deliberately want a worst-represented-type guarantee—for example, a policy designer who wants no resident group with a positive share of the population to be more than \(\rho\) issues away from the selected bundle.
My weakest point is that mass magnitude barely affects the objective: every positive-mass type counts fully in the maximum, however small its share. The problem uses the masses for the balance condition and the support for the minimax score; it does not get a new tractable optimization landscape from fractional population sizes. The score is also sensitive to a type’s mass reaching zero, when that type leaves the support. That makes this a credible continuous mirror of the paper’s MINIMAX result, but a boundary case for the programme’s hoped-for computational gains, rather than evidence that its broader OWA family becomes easier.
This case covers Theorem 1 only. It raises two natural follow-up questions: how does the problem behave when parameterized by support size \(\tau\), and what happens if worst-case distance is replaced by a mass-sensitive quantile objective? The latter could produce a richer continuous OWA mirror, but it is not the anchor claimed here.
The strongest case against the anchor is that Theorem 1’s continuous version barely uses the population measure. For a committee \(S\), its score is
\[
F_\mu(S)=\max_{P:\mu_P>0} d_H(S,P).
\]
Once the support is fixed, changing the masses does not change the score. A type with mass \(10^{-100}\) counts just as much as one with mass \(1/2\). Balance depends on the masses, but winner determination within the balanced instances depends only on which ballots occur. The resulting problem is therefore a worst-case optimization over a list of ballot types, with a population distribution attached to the input.
That also makes the large-electorate interpretation unstable at the boundary. If \(\mu_\epsilon=(1-\epsilon)\delta_P+\epsilon\delta_Q\), then for every \(\epsilon>0\), \(F_{\mu_\epsilon}(S)=\max\{d_H(S,P),d_H(S,Q)\}\); at \(\epsilon=0\), the \(Q\)-type vanishes and the score becomes \(d_H(S,P)\). So a tiny positive faction can determine the result no matter how small its share, exactly the concern the paper raises about MINIMAX in large electorates. This is the best reason to doubt that this anchor will illuminate population-scale computation: its distinctive feature is insensitivity to population shares, and its decision question does not bring mass-based optimization into play.
But that does not defeat the mirror. The theorem is a named computational result, its balanced condition transfers to rational population proportions, and finite-support ballot distributions are a sensible model for repeated approval patterns. A policymaker could deliberately want a worst-case guarantee for every represented preference type, regardless of its share. Nor does the discontinuity make the question ill-posed; it identifies what the rule is choosing to protect.
A stronger, mass-sensitive extension is also available: replace the maximum by a weighted integral of the distance quantiles, such as \(J_g(S,\mu)=\int_0^1 g(u)Q_{\mu,S}(u)\,du\). That is a natural continuous-rank analogue of the paper’s OWA family, though it requires choosing a weight function and is not Theorem 1’s MINIMAX problem. It could open its own computational questions.
So the negative case is real but narrow: this particular mirror may offer little population-mass structure, and its large-electorate rationale is normatively fragile. I cannot honestly sustain the requested universal claim that no worthwhile mirror exists in any scenario. Theorem 1 survives the objections; under the programme’s stated gate, the proponent has the stronger case.
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.