| paper | Equilibria of plurality voting with abstentions |
| authors | Y. Desmedt, Edith Elkind |
| venue | SIGECOM 2010 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorem 3 is a genuine computational hardness anchor, and the proposed mass problem is stated concretely. Under the direct nonatomic interpretation, each voter has zero influence on \(v_c\), making all-abstention an equilibrium, while the proposed \(\delta\)-mass repair introduces coalition-style stability. The cases do not settle whether the authors would recognise that repair as their problem, so green is premature, but the opponent has not ruled it out strongly enough for red.
fails bit b-changes — the continuum limit changes the question
Under the ordinary nonatomic interpretation, every individual is non-pivotal, so the all-abstain allocation is always a PNE; the proposed \(\delta\)-deviation is a coalition-style convention that the paper does not define.
fatal: False
It is undecided whether stability against infinitesimal same-type mass deviations is an admissible high-multiplicity continuation of the paper's unilateral PNE notion or a new coalition-stability problem. Author acceptance of that solution concept would support green; rejection would leave only the trivial nonatomic game and support red.
The proposed mirror covers only Theorem 3's simultaneous PNE-existence hardness; it leaves the structural simultaneous results and the sequential voting results, including Theorems 6 and 7, unaddressed.
My strongest case is a mirror of the paper’s simultaneous-voting result, not its sequential model.
The anchor is Theorem 3, proved in this paper by reduction from Exact Cover by 3-Sets: given voters \(V\), candidates \(C\), and utility vectors \(u_1,\ldots,u_n\), it is NP-complete to decide whether there exists a ballot vector \(b\in(C\cup\{\bot\})^n\) that is a pure Nash equilibrium of the simultaneous Plurality game with abstention. The utilities rank candidates and tied winner sets by expected utility, and voting incurs the paper’s arbitrarily small positive cost. Thus the theorem concerns existence of an equilibrium, not merely computing one.
My lead mirror would be Mass-PNE Existence for Plurality with Abstention. An instance contains candidates \(C\), a finite set of complete utility types \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), and utilities \(u_t(c)\). A type includes everything relevant to the game: its cardinal utilities, its preferences over tied winner sets, and the common abstention-cost convention.
Let \(B=C\cup\{\bot\}\). A candidate-level strategy is a mass allocation \(x_{t,b}\ge0\) satisfying \(\sum_{b\in B}x_{t,b}=\mu_t\). Candidate \(c\) receives vote mass \(v_c=\sum_t x_{t,c}\), and the winner set is
\[ W(x)=\{c\in C:v_c=\max_{d\in C}v_d\}. \]
For a nonempty set \(S\), type \(t\)'s utility is \(u_t(S)=|S|^{-1}\sum_{c\in S}u_t(c)\), and voting for a candidate costs \(\varepsilon>0\).
Because an ordinary atomless voter has zero influence on \(v\), I would define equilibrium using the natural pivotal-mass limit of the paper’s one-voter deviation. For every positive-support pair \((t,b)\), move an arbitrarily small mass \(\delta\) from \(b\) to some \(b'\), recompute the winner set, and compare
\[ u_t(W(x'))-\varepsilon\mathbf{1}[b'\ne\bot] \]
with
\[ u_t(W(x))-\varepsilon\mathbf{1}[b\ne\bot]. \]
A solution is an allocation \(x\) for which no sufficiently small positive-mass deviation is strictly profitable. The decision question is whether such an \(x\) exists, together with the allocation as a witness.
This is recognisably the authors’ problem: same candidates, same simultaneous ballots, same Plurality rule, same abstention motive, same utility over tied outcomes, and the same equilibrium-existence question. Only the population representation changes: named voters become a distribution over complete voter types, and vote counts become vote masses. A large electorate with repeated utility profiles—say, a national election whose voters fall into many stable policy-and-intensity segments—is a convincing high-multiplicity regime. Replicating every type \(K\) times makes the number of voters arbitrarily large without changing the continuous instance or the equilibrium constraints.
I would expect hardness to transfer, placing this mirror in Class B. The paper’s X3C construction already has the right form. For a ground set of size \(N\) and \(M\) feasible triples, use candidates \(d_i\) and \(e_j\). Give each element type mass \(2/(2N+3M)\), corresponding to the two voters associated with \(g_i\), and each set-incidence type mass \(1/(2N+3M)\), corresponding to the three voters associated with \(E_j\). The utility rankings are exactly those in the proof of Theorem 3.
If an exact cover \(F\) exists, take the winner set to be all \(d_i\) together with the \(e_j\) for \(E_j\notin F\). Every surviving \(e_j\) receives mass \(3/(2N+3M)\). Every \(d_i\) receives its baseline mass \(2/(2N+3M)\) plus one unit from the selected set covering \(g_i\), hence the same total. The paper’s preference argument then rules out every infinitesimal deviation. Conversely, the three-case argument in the proof of Theorem 3 applies to these masses: an equilibrium winner set must make all surviving candidates receive equal top-vote mass, and that equality forces the deleted \(e_j\)'s to encode an exact cover.
The continuous question therefore retains the reduction’s real combinatorics. The hardness lives in choosing a candidate winner set and satisfying equal-support constraints, not in the identities or multiplicity of voters. The continuous version may still reveal useful tractable subcases—for example, fixed \(m\), bounded type structure, or restricted utility rankings—but the unrestricted problem should remain hard.
The mirror deliberately covers only Theorem 3 and the simultaneous model. I would not stretch it to Theorems 6 and 7: their sequential algorithms depend essentially on the finite order of individual voters and the resulting history space, so a continuous analogue would require an additional model of voter order or a distribution over positions.
The weakest point is the equilibrium convention. Under standard nonatomic-game Nash equilibrium, one individual cannot change the aggregate vote mass, so voting-cost considerations largely collapse the model: voters abstain and pivotality disappears. The infinitesimal mass-deviation definition is therefore a genuine co-modification, though one forced by the paper’s reliance on a one-vote change at a tie. If the authors reject that pivotal-mass interpretation, this mirror becomes weak. If they accept it, Theorem 3 is an unusually good candidate for continuization because its hardness already resides in aggregate candidate-selection structure rather than in population granularity.
The strongest objection targets the proponent’s equilibrium convention, not the X3C reduction itself.
Under the standard nonatomic interpretation, the mirror collapses. A single voter has zero mass, so changing her ballot does not change any \(v_c\). Since voting costs \(\varepsilon>0\), abstention strictly dominates every non-pivotal vote. In particular, the all-abstain allocation is always a Nash equilibrium: every candidate has vote mass \(0\), and one individual cannot alter the winner set. Existence is therefore trivial, so Theorem 3’s NP-completeness disappears.
The proposed repair—moving an arbitrarily small mass \(\delta\)—is not a unilateral deviation by a voter. It is a coordinated deviation by a coalition of same-type voters, or by a “representative mass” with no counterpart in the paper. Making each type an atomic weighted player changes the game in the same way; retaining finite atoms merely keeps discrete voter granularity. Thus the nontrivial version is not the high-multiplicity limit of the paper’s PNE notion, but a new coalition-stability notion.
There is also no canonical limiting argument that forces this repair. In a finite election, a one-vote perturbation has size \(1/n\); after normalization it vanishes, while its effect on a tied Plurality outcome remains discontinuous. Unique-winner equilibria with one supporting voter converge to the all-abstain allocation, which is an equilibrium under the ordinary nonatomic model but not under the proposed pivotal-mass model. Different orders of taking the population limit and evaluating pivotality therefore produce different games.
That said, this is not enough to defeat the anchor under ChoCo’s permissive modelling standard. If the authors explicitly accept “infinitesimal coalition” equilibrium as their intended question, the X3C construction probably does lift: equilibrium forces equal support mass among co-winners, and the masses \(1/(2N+3M)\) reproduce the integer equalities in the reduction. My honest assessment is therefore that the negative case is weak. It can reject the standard continuous-game interpretation, but it cannot honestly establish that no worthwhile pivotal-mass mirror exists.
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.