| paper | Some results on approximating the minimax solution in approval voting |
| authors | Rob LeGrand, E. Markakis, Aranyak Mehta |
| venue | ATAL 2007 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: A polynomial-time factor-\(3\) approximation exists. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
Given \(q\) candidates, committee size \(k\), a finite approval-type set \(T\subseteq\{0,1\}^q\), and a rational distribution \(\mu\) over \(T\), output an integral committee \(S\subseteq[q]\) with \(|S|=k\) satisfying \(R_\mu(S)\le 3\min_{|S'|=k}R_\mu(S')\), where \(R_\mu(S)=\max_{\mu_b>0}H(S,b)\).
Types are approval vectors \(b\in T\), masses are \(\mu_b\), the decision variable is an integral committee \(S\) of size \(k\), and the objective is worst-type Hamming dissatisfaction \(R_\mu(S)=\operatorname*{ess\,sup}_{b\sim\mu}H(S,b)\).
The proponent answers the mass-insensitivity objection as a fidelity point, but the remaining concern is that the continuum contributes only support compression and no substantive mass-sensitive computation.
fatal: False
The mirror covers Theorem 1 and its \(3\)-approximation algorithm. It leaves the heuristic framework, empirical evaluation, manipulation discussion, and unnumbered or cited hardness results outside the mirror.
The strongest honest case is a modest one built around the paper’s Theorem 1, proved in the paper. The paper does discuss NP-hardness, but only in unnumbered prose and by citing earlier work; I therefore would not use it as a qualifying hardness anchor.
The paper’s underlying problem is Fixed-size Minimax, \(FSM(k)\): there are \(n\) candidates, ballots \(v_i\in\{0,1\}^n\), and the output is a committee-vector \(u\) of Hamming weight \(k\). Its objective is
\[ \operatorname{maxscore}(u)=\max_i H(u,v_i). \]
Theorem 1 states that the following algorithm is a \(3\)-approximation: choose any ballot \(v_j\), output a \(k\)-completion \(u\) of \(v_j\), meaning a weight-\(k\) vector at minimum Hamming distance from \(v_j\). The theorem proves
\[ \operatorname{maxscore}(u)\le 3\,\operatorname{OPT}. \]
The paper proves this by two applications of the triangle inequality; it also observes that the algorithm takes \(O(n)\) time once the ballot has been selected. This is a genuine computational result proved in the paper, not merely a cited fact. [Original paper](https://www.cs.angelo.edu/~rlegrand/research/legrand2007fsm.pdf)
My mirror would be Continuous Fixed-Size Minimax Approval, \(\mathrm{CFSM}_\infty\). An instance consists of \(q\) candidates, a committee size \(k\), and a rational distribution
\[ \mu=(\mu_b)_{b\in T} \]
over a finite set \(T\subseteq\{0,1\}^q\) of \(\tau\) approval-ballot types. A type \(b\) is complete: every voter of that type has the same approved candidates and evaluates a committee \(S\) through the same Hamming loss
\[ H(S,b)=\left|\{j\in[q]:\mathbf 1[j\in S]\ne b_j\}\right|. \]
The mass \(\mu_b\) is the fraction of society of type \(b\). The decision remains an integral committee \(S\subseteq[q]\) with \(|S|=k\); only the population is continuized. Define
\[ R_\mu(S)=\operatorname*{ess\,sup}_{b\sim\mu}H(S,b) =\max_{\mu_b>0}H(S,b). \]
The problem is to output a committee \(S^\star\) minimizing \(R_\mu(S)\). Its theorem-facing approximation version asks for a committee \(S\) satisfying
\[ R_\mu(S)\le 3\min_{|S'|=k}R_\mu(S'). \]
This is a sensible high-multiplicity regime for, for example, a large professional or standards association electing a committee from a common slate of candidates. Millions of members may follow a few hundred institutional, disciplinary, or organizational approval templates: \(N\gg\tau\). The type is not “a named voter with an invented common price”; it is precisely the full approval behavior relevant to this paper’s rule.
The authors should recognize this as their problem. The committee remains integral, the Hamming-distance compromise criterion is unchanged, and the only replacement is the electorate list by its distribution over indistinguishable ballot types. For a finite election with ballot counts \(n_b\), setting
\[ \mu_b=\frac{n_b}{N} \]
gives exactly the same objective. Conversely, a rational distribution can be expanded into a finite election. Thus this is the paper’s high-multiplicity version, not a fractional-committee or outcome-space relaxation.
Theorem 1 lifts immediately. Choose any positive-mass type \(b_j\), output a \(k\)-completion \(S\), and evaluate its radius over the \(\tau\) types. The same proof gives
\[ R_\mu(S)\le 3R_\mu^\star. \]
The running time is polynomial in \(q\), \(\tau\), and the encoding length of \(\mu\), and independent of the potentially enormous population size \(N\). I would classify the approximation problem as Class A. The exact optimization problem is more likely Class B: the discrete \(FSM(k)\) problem embeds by normalized ballot counts, so candidate-side combinatorics and the paper’s hardness do not disappear merely because duplicate voters are compressed.
The weakest point is that the minimax objective is a maximum. Once a type has positive mass, its precise mass is irrelevant; \(\mu\) matters mainly through the support. An opponent can fairly call this “continuous deduplication” rather than a mass-sensitive optimization problem. But making the objective depend substantively on masses—for example through a weighted or quantile minimax criterion—would create a different problem. The support-based essential maximum is therefore the faithful continuization of the paper’s stated objective, even if it is not the programme’s most powerful example.
I would cover only Theorem 1. Natural follow-up questions are whether exact \(\mathrm{CFSM}_\infty\) is NP-hard when parameterized by \(\tau\), whether a mass-sensitive weighted-minimax variant has a richer continuum landscape, and how coalition manipulation behaves when a positive-mass type rather than one named voter changes its report.
The proponent’s construction is formally valid, but it does not produce a worthwhile continuous-population mirror. The obstruction is that the theorem’s objective annihilates population mass.
For every committee \(S\),
\[ R_\mu(S)=\max_{\mu_b>0} H(S,b). \]
Hence, whenever two societies have the same support,
\[ \operatorname{supp}(\mu)=\operatorname{supp}(\nu), \]
they induce exactly the same objective for every \(S\), regardless of their proportions. A society with masses \((0.999,0.001)\), one with \((0.5,0.5)\), and a finite election containing one voter of each type are indistinguishable to \(FSM(k)\). The probability simplex has collapsed to its support face.
This is not an objection that high multiplicity is implausible. A large association with many repeated approval ballots is perfectly sensible. The problem is that multiplicity has no semantic role in this particular result. Replacing the voter list by \(\mu\) merely deletes duplicate rows from a finite robust-optimization instance. The relevant parameter is the number \(\tau\) of distinct ballots, not population mass, density, or proportions. No continuous optimization, mass transfer, or high-multiplicity phenomenon is exposed.
No choice of a richer type space repairs this while preserving the theorem. Refining a type by identity, institution, or location changes nothing because Hamming loss does not see those attributes. Allowing continuous approval intensities or weighting dissatisfaction by mass changes the problem.
The obvious mass-sensitive repairs are different objectives. Expected Hamming loss,
\[ \sum_b \mu_b H(S,b), \]
is an approval-frequency objective, not minimax dissatisfaction; indeed it reduces to selecting candidates by marginal approval probabilities. Quantiles, CVaR, or mass-weighted maxima would be legitimate new research questions, but they either ignore small minorities or replace the paper’s worst-voter criterion. They are not continuous versions of Theorem 1.
Thus the theorem does lift exactly, but only because the proposed “society” is observationally equivalent to a finite support set. The proponent has established a valid deduplication reformulation, not a substantive continuization. If support compression alone counts as worthwhile, this anchor survives; under the programme’s stronger standard—where population mass should be the object of computation—it should be rejected.
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.