| paper | The Proportional Veto Principle for Approval Ballots |
| authors | Daniel Halpern, Ariel D. Procaccia, Warut Suksompong |
| venue | IJCAI 2025 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.4
Given \(M\) with \(|M|=m\), fixed \(k,t\), and an explicitly listed rational distribution \(\mu=(\mu_A)_{A\subseteq M}\) over approval-set types, output \(W\in\binom{M}{k}\) such that for every \(\ell\in\{1,\ldots,m\}\), \(\sum_{A:\,|A|\ge\ell,\ |A\cap W|<t}\mu_A\le H(m,\ell,k;t-1)\); equivalently, compute the mass version of Algorithm 1 and certify its FVR envelope.
Approval-set types \(A\subseteq M\) carry rational masses \(\mu_A\); the decision variable is a discrete committee \(W\in\binom{M}{k}\), computed by mass-weighted Algorithm 1, with FVR violation mass as the guarantee.
The displayed theorem proves FVR-optimality of a rule rather than explicitly classifying a search problem as polynomial-time, and the continuous execution is essentially grouped weighted execution.
fatal: False
The mirror covers the algorithmic guarantees of Theorems 3.4 and 2.5, with Theorem 3.1 providing the sharpness envelope; it leaves Theorems 2.6, 2.7, 3.5, and 3.6 as structural results.
The strongest positive case is a direct Class-A mirror, led by Theorem 3.4. This is not a claim that the paper develops a complexity landscape: it is primarily an axiomatic and guarantee paper. But its polynomial-time committee rule survives as an exact high-multiplicity computation, and the population-continuized version is both natural and author-recognizable.
A plausible regime is large participatory budgeting or project-selection elections. There may be millions of residents, a moderate menu \(M\) of \(m\) projects, and a committee of \(k\) projects to fund. Residents belonging to the same neighbourhood, occupation, institution, or issue coalition may submit the same approval ballot. A type is therefore an approval set \(A\subseteq M\), which is complete for this paper: the rule uses only \(A\), its size \(|A|\), and intersections with committees. The society is a rational distribution \(\mu=(\mu_A)_{A\subseteq M}\), with \(q=|\operatorname{supp}\mu|\ll n\). Mass \(\mu_A\) is the fraction of residents with ballot \(A\). This is a genuine high-multiplicity regime: clearing denominators produces an ordinary election with many cloned voters, while the continuous input can be much shorter than the expanded electorate.
My lead anchor is Theorem 3.4, proved by the authors here, with the omitted proof in the full version. The theorem states that the committee rule induced by Algorithm 1 is FVR-optimal for every flexibility threshold \(s\), once \(k\) and \(t\) are fixed. The surrounding text explicitly identifies this as a polynomial-time algorithmic result. Strictly speaking, the theorem statement is not written as “the problem is in P”; this is the closest named P-side computational anchor in the paper.
I would call the mirror Continuous Sharp-FVR Committee. An instance consists of \(m,k,t\), and a rational distribution \(\mu\) over approval types \(A\subseteq M\), with \(1\le t\le k<m\). For a committee \(W\in\binom{M}{k}\), define its violation mass at approval threshold \(\ell\) by
\[ V_{\mu,W}(\ell) = \sum_{\substack{A\subseteq M\\ |A|\ge \ell\\ |A\cap W|<t}}\mu_A. \]
This is exactly the mass of voters who are \(\ell/m\)-flexible but \(t\)-disapprove \(W\). Let
\[ B_{m,k,t}(\ell) = H(m,\ell,k;t-1) = \sum_{r=0}^{t-1} \frac{\binom{\ell}{r}\binom{m-\ell}{k-r}}{\binom{m}{k}}. \]
The task is to output a committee \(W\) satisfying
\[ V_{\mu,W}(\ell)\le B_{m,k,t}(\ell) \qquad \text{for every }\ell\in\{1,\dots,m\}. \]
A valid solution is therefore a committee, together with the finite list of inequalities above as a certificate. Theorem 3.1 supplies the matching worst-case lower bound, so this is the sharp FVR envelope rather than an arbitrary relaxation.
The continuous Algorithm 1 is obtained by replacing voter sums with mass sums. At stage \(j\), with current committee \(C\), define for every \(a\notin C\)
\[ S_C(a) = \sum_{\substack{A\setminus C\neq\varnothing\\a\in A}} \mu_A \frac{ h\!\left(m-j-1,\ |A\setminus C|-1,\ k-j;\ t-1-|A\cap C|\right) }{ H(m,|A|,k;t-1) }, \]
omitting types for which the denominator is zero. Add a candidate maximizing \(S_C(a)\), and repeat until \(|C|=k\). This uses polynomially many exact rational operations, roughly \(O(kmq)\), with bit complexity polynomial in the mass encoding length. It does not enumerate the \(\binom{m}{k}\) committees from Theorem 3.3, nor does it depend on the potentially enormous number of cloned voters. I would classify this mirror as tractable, Class A.
The match to the original problem is unusually strong. Approval sets remain indivisible approval sets; candidates and committees remain discrete; only the voter multiplicities become rational masses. Clearing denominators reproduces the finite election and preserves all approval counts, flexibility thresholds, ties, and FVR inequalities. This is a direct mirror, not outcome-space continuity or fractional committee selection.
A useful secondary anchor is Theorem 2.5, proved in the paper. It states that the single-winner rule \(R_{\mathrm{OPT}}\), which scores an approved candidate using weight \(1/(1-f_i)\), is FVR-optimal. Its continuous counterpart is Continuous-\(R_{\mathrm{OPT}}\). Given \(m\) and rational masses \(\mu_A\), put \(f_A=|A|/m\), ignore the universal type \(A=M\), and define the weighted disapproval burden
\[ \Phi_\mu(a) = \sum_{\substack{A\subsetneq M\\a\notin A}} \frac{\mu_A}{1-f_A}. \]
The task is to output a candidate
\[ a^\star\in\arg\min_{a\in M}\Phi_\mu(a), \]
along with its exact score. Since the average burden is at most \(1\),
\[ \frac{1}{m}\sum_{a\in M}\Phi_\mu(a) = \sum_{A\subsetneq M}\mu_A \le 1, \]
so \(\Phi_\mu(a^\star)\le1\). For any \(s\)-flexible types disapproving \(a^\star\), each contributes at least \(1/(1-s)\), yielding
\[ \sum_{\substack{A:a^\star\notin A\\ |A|/m\ge s}}\mu_A \le 1-s. \]
Thus the continuous rule achieves exactly the lower-bound guarantee from Theorem 2.2. It is computable in \(O(mq)\) exact operations and is again Class A. This is a companion algorithmic mirror rather than an independent complexity theorem.
The scope should remain narrow. These mirrors cover Theorem 3.4 and Theorem 2.5, with Theorem 3.1 serving as the sharpness benchmark. They do not claim to continuize every uniqueness or incompatibility statement in Theorems 2.6, 2.7, 3.5, and 3.6; those are primarily structural or axiomatic results. Theorem 3.5 could be transferred to rational mass profiles, but it is not needed for the positive computational case.
The weakest point is source discipline: if “named computational anchor” is interpreted literally as a theorem statement saying “in P,” “NP-hard,” or similar, this paper has no such theorem. Theorem 3.4 is a named algorithmic result whose polynomial-time status is stated in the surrounding prose, not in the displayed theorem statement. A second weakness is that the continuous algorithms are relatively straightforward weighted restatements, so they may be judged as modest Class-A mirrors rather than a deep new complexity frontier. Nevertheless, the mirror is honest and strong on fidelity: it preserves the paper’s approval ballots, flexibility notion, FVR objective, and discrete committee action while gaining exactly the high-multiplicity compression that continuization is meant to expose.
The strongest negative case is that this paper does not really contain a computational result for ChoCo to continuize. Theorem 3.1 is a worst-case counting bound, Theorem 2.5 characterizes a scoring rule, and Theorem 3.4 proves that a particular greedy rule has a guarantee. None formulates an optimization, decision, approximation, or parameterized-complexity problem whose input is a society. The paper’s objects are rules and axioms; the proposed mirrors turn the execution of those already-given rules into the “computational problem.”
Theorem 3.4 is the best anchor, and it is not vulnerable to objections about identity or multiplicity. An approval set \(A\subseteq M\) is a perfectly legitimate complete voter type, and participatory budgeting can plausibly have many voters sharing such types. But that makes the continuization almost entirely mechanical. If \(\mu_A\) is the mass of type \(A\), every sum in Algorithm 1 is obtained by the substitution
\[ \sum_{i=1}^n g(A_i) \;=\; N\sum_{A\subseteq M}\mu_A g(A), \]
after clearing denominators. The committee produced is exactly the same committee as in the corresponding weighted finite election. The continuous algorithm is therefore not a new algorithmic result about a distributional society; it is Algorithm 1 with equal approval ballots grouped together.
The claimed \(O(kmq)\) implementation does provide compression when the support \(q\) is small, but that is an encoding benefit, not a new computational question exposed by the paper. If the support is explicitly listed, this is simply a weighted approval election. If the distribution is given implicitly, then the complexity depends on the chosen representation or oracle, none of which is specified by the paper. The proposed “sharp-FVR committee” feasibility problem also adds little: the theorem already supplies a greedy committee satisfying all \(m\) inequalities. If one instead asks for a committee minimizing a weighted or worst-threshold violation for a particular \(\mu\), that could be an interesting new problem, but it is no longer the paper’s FVR-optimality theorem; it is an invented profile-specific objective.
Theorem 2.5 is weaker still as a computational anchor. The proposed quantity
\[ \Phi_\mu(a) = \sum_{A:a\notin A} \frac{\mu_A}{1-|A|/m} \]
is just a weighted approval tally, computable by scanning the listed types. Clearing denominators again gives an ordinary finite electorate. There is no continuous optimization, separation problem, or nontrivial high-multiplicity phenomenon. Nor does the factor \(1/(1-f)\) create a meaningful continuum singularity: for approval ballots, \(f\) lies on the finite grid \(\{0,1/m,\ldots,1\}\), and the \(f=1\) type contributes the same amount to every candidate and can be ignored. Treating \(f\) as an arbitrary real parameter would change the ballot model, rather than improve its population continuization.
Theorem 3.1 cannot rescue the case. Its hypergeometric term
\[ H(m,\ell,k;t-1) \]
comes entirely from sampling committees from the finite candidate set. It is independent of the population representation. Replacing voter counts by masses leaves the averaging argument unchanged, and the matching worst-case profiles are already obtainable by cloning voters. Thus the theorem gives neither a computational task nor a continuum-specific boundary.
No alternative author-recognizable type space fixes this problem. The paper uses only approval sets, so adding identities, arrival times, prices, or private parameters would create a different problem. Keeping only approval sets makes \(\mu\) a sufficient statistic and turns both proposed mirrors into exact weighted-profile restatements. The paper contains no bribery, control, robustness, or other intervention axis where mass transfer or continuous optimization could expose a new complexity landscape.
The honest limitation is that this does not prove that no formal mirror exists. A genuine high-multiplicity version of Theorem 3.4 is natural and correct. The negative claim is narrower: it is not a worthwhile ChoCo mirror in the programme’s computational sense. Theorem 3.4 is the one serious surviving anchor, but its continuous version is a compressed implementation of an already explicit greedy rule, not a new computational problem. If ChoCo counts such exact weighted-election translations as sufficient, then the universal negative case cannot honestly win.
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.