| paper | Trembling Hand Equilibria of Plurality Voting |
| authors | S. Obraztsova, Zinovi Rabinovich, Edith Elkind, M. Polukarov, N. Jennings |
| venue | IJCAI 2016 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | low |
| authors would recognise it | unclear |
Both anchors have genuine computational character, and the proposed cohort problem is precise and potentially worthwhile. However, an atomless individual-voter limit removes pivotality and the finite-order tremble effects, while the proposed fix makes each type a coordinated strategic bloc. That is a plausible extension the authors might recognise, but it is not clearly a population-only continuization of their equilibrium game.
fails bit b-changes — the continuum limit changes the question
The cohort map \(b:T\to C\) treats an entire type mass as one strategic player, so the individual-voter pivotality and \(\varepsilon^k\) tremble comparisons in Theorems 1 and 7 are not obtained as a genuine high-multiplicity limit.
fatal: False
It is undecided whether coordinated positive-mass cohorts count as permissible high-multiplicity types or instead change the strategic players and solution concept. Accepting the bloc interpretation gives a viable mirror; rejecting it leaves only a degenerate nonatomic game.
The proposed mirror covers Theorems 1 and 7, but leaves the structural equilibrium results in Theorems 2–6 and the paper's parity-sensitive claims unaddressed.
The strongest positive mirror is a mean-field, bloc-voting version of the paper’s strategic plurality game. The population is continuous, but pivotality is retained by making the strategic units positive-mass cohorts rather than infinitesimal individuals.
A type \(t\) contains the complete utility vector \(\delta_t:C\to\mathbb{N}\), not merely a ranking, since trembling-hand utilities depend on expected cardinal utility under ties. A society is a rational distribution \(\mu\) over finitely many types. A plausible regime is a national or shareholder election with millions of voters but perhaps tens or hundreds of recurring utility-and-coordination types: party constituencies, unions, investor classes, or institutional delegations. Members of a type receive the same ballot instruction, while independent implementation errors affect their individual ballots.
The action is a ballot map \(b:T\to C\): all mass of type \(t\) intends ballot \(b_t\). For \(0<\varepsilon<1/(m-1)\), define
\[ p_\varepsilon(c\mid d)= \begin{cases} 1-(m-1)\varepsilon,&c=d,\\ \varepsilon,&c\neq d. \end{cases} \]
When type \(t\) considers deviating to \(a\), the other cohorts contribute actual ballot mass
\[ q^{\varepsilon,t,a}_c = \mu_t\mathbf{1}[c=a] + \sum_{u\neq t}\mu_u p_\varepsilon(c\mid b_u). \]
This is the continuum, law-of-large-numbers counterpart of the paper’s independent trembles. Let \(W^{\varepsilon,t}(a)\) be the candidates with maximum \(q^{\varepsilon,t,a}_c\), with uniform tie-breaking, and let
\[ U_t^\varepsilon(a\mid b_{-t}) = \frac{1}{|W^{\varepsilon,t}(a)|} \sum_{c\in W^{\varepsilon,t}(a)}\delta_t(c). \]
Call \(a\) a cohort trembling-hand best response if, for some \(\varepsilon_0>0\), it maximizes this quantity against every alternative for all \(0<\varepsilon<\varepsilon_0\). A continuous cohort THE is a ballot map in which every positive-mass type plays such a best response.
This is a genuine population continuization: candidates, ballots, utilities, and tie-breaking remain discrete, while the electorate is represented by mass. It is not outcome-space continuity or a noise model imposed on a finite profile. The cohort assumption is also substantively plausible in settings where voting instructions are issued collectively.
The lead anchor is Theorem 7, proved in this paper. It states:
Given a candidate set \(C\), a voter set \(V\), a utility function \(\delta_v\) for every voter \(v\), and a distinguished candidate \(a\in C\), it is NP-hard to decide whether the associated Plurality voting game admits a trembling hand equilibrium \(b\) with \(a\in W(b)\).
The corresponding continuous problem is:
\[ \textsc{Continuous-Cohort-THE-Membership}. \]
Given \(C\), a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), integer utility vectors \(\delta_t\), and a target candidate \(a\), decide whether there exists a ballot map \(b:T\to C\) such that every positive-mass type is a cohort TH best responder and \(a\in W^0(b)\), where
\[ W^0(b)= \arg\max_{c\in C} \sum_{t\in T}\mu_t\mathbf{1}[b_t=c]. \]
A solution is the ballot map \(b\), not merely the winning candidate.
I would expect this problem to be Class B: hardness should often transfer, because the strategic choices \(b_t\in C\) remain indivisible and the winner condition remains a discrete plurality comparison. Rational population masses do not automatically convexify the equilibrium-profile search. The key research question is whether the paper’s hardness construction can be reorganized so that many voters share a small number of complete types. If it can, the result would demonstrate hardness in a genuinely high-multiplicity strategic electorate. If not, the problem may become tractable for bounded \(\tau=|T|\), since one can enumerate \(m^\tau\) cohort profiles.
The second useful anchor is Theorem 1, also proved in this paper. It states:
Given a voter \(v\) with an ordinary utility function \(\delta_v\) and a ballot profile \(b_{-v}\) of the remaining voters, a TH best response of \(v\) can be found in polynomial time.
Here “ordinary” means that, for every three distinct candidates \(a,b,c\) and \(0\le k\le n+m\),
\[ (m+n-k)(\delta_v(a)-\delta_v(b)) \neq \delta_v(b)+\delta_v(c), \]
and, for every distinct \(a,b\), every \(C'\subseteq C\setminus\{a,b\}\), and \(0\le k\le n\),
\[ \sum_{c\in C'}\delta_v(c)-\delta_v(a) \neq (m+n-k)(\delta_v(b)-\delta_v(a)). \]
Its continuous counterpart is:
\[ \textsc{Continuous-Cohort-TH-Best-Response}. \]
Given \(C\), a finite type distribution \(\mu\), ordinary utility type \(t\), and the intended ballots of all other cohorts, output a ballot \(a\in C\) that is a cohort TH best response for \(t\).
I would expect this problem to be Class A. For each candidate action, every perturbed aggregate score is affine in \(\varepsilon\); the eventual winner set can therefore be determined by comparing the constant and first nonzero coefficient of finitely many score differences. One can test all \(m\) actions using polynomially many rational arithmetic operations in \(m\), \(\tau\), and the input bit length. This preserves the paper’s local strategic question while exploiting the continuous population’s aggregate structure.
These mirrors cover only the paper’s computational results in Theorems 1 and 7. I would not claim that the parity-sensitive consensus result in Theorem 2 transfers unchanged: parity is precisely the kind of finite-population feature that should disappear in a continuum.
The weakest point is pivotality. If the model instead treats every voter as infinitesimal and permits unilateral deviations by zero-mass individuals, no deviation changes plurality scores, so every ballot becomes a best response and the equilibrium question collapses. The cohort interpretation is therefore essential, not cosmetic. A referee who rejects coordinated positive-mass cohorts would reject this particular mirror. But that objection targets one modelling regime, not the possibility of a continuous mirror altogether: bloc voting is a natural high-multiplicity scenario, and the resulting questions retain the paper’s candidates, utilities, plurality winner, trembles, and equilibrium concept while making the society itself continuous.
The main follow-up questions are whether Theorem 7’s hardness persists with \(\tau\ll N\), whether finite elections with many clones converge to the cohort equilibrium defined above, and what happens in a hybrid model with a continuous electorate plus finitely many genuinely pivotal individual voters.
The strongest negative case is that both anchors depend on the same feature that a genuine population continuum removes: one voter’s ballot can change the winning set, and the probability of exactly \(k\) other voters trembling determines the comparison between actions.
Let \(N\) identical voters represent a type of mass \(\mu_t\). A unilateral deviation changes a normalized plurality score by only \(1/N\). In the atomless limit it changes the score by zero, so it cannot change the winner or the tie set. Every ballot therefore gives the same payoff to an individual type. Trembling-hand best response becomes vacuous, and so does equilibrium membership.
The trembles themselves also lose the paper’s meaning. For finite \(N\), the probability of a particular \(k\)-voter error is of order \(\varepsilon^k\), and the smallest \(k\) that changes the outcome determines the best response. In a continuum, independent individual errors average out almost surely: aggregate ballot masses are deterministic. The \(\eta\)-trembling structure disappears. Preserving it requires retaining a finite population scale, an infinitesimal lexicographic scale, or a specified stochastic fluctuation model. None is determined by \(\mu\) alone.
The proposed cohort construction avoids this collapse only by changing the strategic player. If all mass \(\mu_t\) acts as one unit, then a deviation changes plurality scores by \(\mu_t\). This is a weighted finite-player game with one player per type, not the high-multiplicity limit of the paper’s voter game. Repeated voters with the same utility vector are not automatically a coalition: in the paper each may deviate separately, and their ballots need not remain identical. Treating a party constituency or shareholder class as a single strategic bloc may be a sensible new model, but it is a model of bloc voting, not a continuous version of trembling-hand equilibria among voters.
The proposed formula also mixes two incompatible error levels. The deviating type moves as one coordinated mass, while other types’ members tremble independently and their errors disappear by the law of large numbers. If types are truly bloc players, their trembles should move whole masses; if they are populations of independent voters, the deviating type should not be able to move its whole mass. Either consistent choice produces a different game.
This defeats Theorem 7 as a mirror. Its input permits arbitrary voter-specific utility vectors and its existential object is a profile \(b\in C^n\) of individual ballots. Preserving the instance exactly by making each utility vector a type gives \(\tau\) as large as \(n\), so there is no high-multiplicity regime. Collapsing repeated utility vectors into a ballot map \(b:T\to C\) imposes coordinated bloc behavior and changes the equilibrium problem before complexity is considered. Whether the resulting weighted-bloc problem is hard or easy is beside the point: it is not the paper’s problem in continuous form.
The same objection defeats Theorem 1. An atomless individual has no nontrivial best-response calculation at all; every action leaves the aggregate outcome unchanged. A positive-mass type’s “best response” is instead a coalition deviation in a weighted plurality game. The paper’s four-candidate characterization relies on a single ballot changing integer score gaps and on the first nonzero \(\varepsilon^k\) term. Those mechanisms have no counterpart in the atomless model. Reintroducing them through infinitesimal tie-breaking simply reintroduces the discarded finite-unit information.
Thus the paper has genuine computational anchors—there is no “no named result” objection—but neither survives as a population-only continuization while retaining the paper’s strategic meaning. A hybrid model with a continuous background electorate and finitely many pivotal blocs could be worthwhile, but its computational content comes from the retained atomic players, not from continuizing the society. The honest limitation is that the universal negative is not mathematically airtight: a researcher could reasonably choose to study bloc trembling-hand equilibria as a new weighted-game model. It is nevertheless a weak mirror of this paper, and the proponent has not shown a genuine high-multiplicity continuization of either theorem.
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.