| paper | Gibbard-Satterthwaite games for k-approval voting rules |
| authors | Umberto Grandi, Daniel Hughes, F. Rossi, A. Slinko |
| venue | MSS 2019 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Neither anchor is a named computational result under the stated gate: Theorems 11 and 12 establish structural equilibrium existence or nonexistence, but not computation or computational hardness. Independently, the proposed population repair makes each positive-mass type a coordinated weighted player, while independent high-multiplicity voters lose the pivotality required by the paper's GS-manipulation model. Thus no anchor supplies both a computational result and a faithful continuous-population question.
fails bit a — no named computational result to mirror
The proposed mirror addresses only Theorems 11 and 12; it does not cover the paper's \(2\)-by-\(2\) game classifications, realizability results, or other equilibrium statements.
The strongest positive case is a cohort-level continuous mirror of the paper’s equilibrium problem. It is an extension rather than a literal atomless reinterpretation, and that distinction matters.
My lead anchor is Theorem 12, proved in this paper. It states that there is a \(4\)-Approval GS-game with six voters \(u_1,u_2,u_3,v_1,v_2,v_3\), eight candidates \(w,d_1,d_2,d_3,d,e,c,x\), and tie-breaking order
\[
w\succ d_1\succ d_2\succ d_3\succ c\succ d\succ e\succ x,
\]
whose sincere scores are \(4\) for \(w,d_1,d_2,d_3\), \(3\) for \(c,d\), and \(1\) for \(e,x\). Thus \(w\) wins sincerely. Only \(v_1,v_2,v_3\) are GS-manipulators, and each has exactly one available manipulation in addition to sincerity:
\[
i_1=v_1[w;c],\qquad
i_2=v_2[wd_1;cd],\qquad
i_3=v_3[wd_2d_1;dxe].
\]
These are all minimal GS-manipulations. The resulting eight-profile game has no pure Nash equilibrium: every profile has a profitable deviation. For example,
\[
(s_1,s_2,s_3)\to(i_1,s_2,s_3)\to(i_1,s_2,i_3)
\to(i_1,i_2,i_3)\to(s_1,i_2,i_3)\to\cdots
\]
is part of the improvement cycle displayed in the paper. This is a theorem proved here, not a cited result.
I would mirror it as follows.
Continuous Cohort-\(k\)-Approval GS Equilibrium. An instance consists of candidates \(C\), a fixed tie-breaking order, a finite set \(T\) of voter-cohort types, and rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\). A type \(t\) contains a complete ranking \(\succ_t\), a sincere ballot \(s_t\), and an allowed action set \(A_t\) containing \(s_t\). Nonstrategic types have \(A_t=\{s_t\}\); strategic types have the GS-manipulations permitted by the paper, with the relevant soundness or minimality restriction.
A pure population action profile chooses \(a_t\in A_t\) for each type. Every unit of mass of type \(t\) casts the integral ballot \(a_t\). The \(k\)-Approval score is
\[
\operatorname{sc}_{\mu,a}(c)
=
\sum_{t\in T}\mu_t\,
\mathbf 1[c\in\operatorname{top}_k(a_t)],
\]
and the winner is the highest-scoring candidate under the fixed tie-break. A cohort \(t\) prefers one action profile to another according to \(\succ_t\) applied to the resulting winner. The question is whether there is a pure equilibrium: no type may replace its cohort’s ballot by another allowed ballot and obtain a winner it prefers.
The natural regime is a large election composed of a small number of organized constituencies: party blocs, unions, professional associations, or electoral districts whose members share a ranking, bounded-rationality rule, and manipulation menu. There may be millions of voters but only a modest number \(\tau\) of complete cohort types. Thus \(\mu_t\) is genuinely the percentage of the electorate represented by a type, not a disguised list of named voters. The output remains a deterministic candidate; only the population is continuous.
Theorem 12 gives an immediate rational continuous instance: take the six types in the construction with \(\mu_t=1/6\). The normalized scores and all eight action-profile outcomes are exactly the same, so the same improvement cycle survives. Hence the continuous question “does every \(4\)-Approval minimal-manipulation population game have a pure equilibrium?” has a negative answer for the same structural reason as the finite theorem. This is a Class-B-style transfer of the finite obstruction, not continuum-specific hardness. The paper does not contain an NP-hardness theorem, so I would not claim more than that.
A useful second anchor is Theorem 11, also proved here: under the Minimality Assumption, every \(3\)-Approval GS-game has a pure Nash equilibrium. The assumption is that every strategy in every action set is a minimal GS-manipulation: Type 1 moves only the desired candidate into the approval set, while Type 2 moves down the smallest possible number of approved candidates and moves up the best previously unapproved candidates. Its continuous counterpart is the same population problem with \(k=3\), rational type masses, and only minimal actions. I would expect this weighted version to be tractable, probably by adapting the paper’s constructive proof after sorting candidate score margins by cohort mass. The \(3\)- versus \(4\)-Approval boundary would then become a genuine continuous-population research question rather than a cosmetic replacement of \(n_t\) by \(\mu_t\).
The weakest point is unavoidable: in a literal nonatomic game of uncoordinated individual voters, one voter has measure zero and cannot change the winner. Ordinary unilateral Nash deviations then lose the pivotality on which GS-manipulation is based, and the game may become vacuous. My mirror therefore treats a type as a coordinated electoral cohort whose mass acts as one strategic unit. That is a substantive extension of the paper’s “no coordination devices” model. It is nevertheless recognizable as the authors’ problem: the same rankings, approval rule, manipulation sets, ordinal utilities, tie-breaking, and equilibrium question remain; only the paper’s individual players are interpreted as large, strategically coherent voter blocs. If that cohort interpretation is rejected, this paper has no convincing direct atomless mirror.
The negative case starts one level earlier: this paper does not actually contain a computational-complexity result. Its numbered results classify realizable games or prove existence/nonexistence of pure Nash equilibria. They do not give a complexity classification, an algorithmic problem, or an optimization formulation. A continuous version could therefore be interesting game theory, but it is not naturally a ChoCo computational mirror. Even granting that equilibrium existence counts as computational, both proposed anchors run into the same obstruction.
Theorem 12 does not survive high multiplicity while preserving the paper’s game. The proposed instance with \(\mu_t=1/6\) works only if each of the six types controls its entire mass as one strategic player. That is just the original six-player game with weighted votes. The fractions rescale scores; they do not make the population continuum.
Replicate each named voter \(N\) times instead. Now a type consists of \(N\) independently acting voters, as required by the paper’s explicit “no coordination devices” assumption. The profile in which all copies of a type play \(s_j\) or \(i_j\) is not a closed eight-profile game: one copy can deviate without the other \(N-1\) copies doing so. Its score change is \(1/N\) of the cohort’s change, and the improvement cycle in Theorem 12 is no longer a cycle of unilateral deviations by the relevant players. In the nonatomic limit, a single voter’s deviation has measure zero and cannot change the winner at all. The GS-manipulator set consequently disappears, so pure equilibrium becomes vacuous.
The exact ties in Theorem 12 do not rescue this. Finite cloned elections can have knife-edge pivotal voters, but an “infinitesimal voter breaks a tie” convention is an atomic convention smuggled back into the continuum. At the limit, changing a null set leaves every score unchanged. Preserving pivotality requires either positive atoms or coordinated blocs.
The proponent’s cohort repair is the strongest available rescue, but it changes the object materially. A bloc that moves all of its mass together is not a GS-manipulator in the paper’s sense; it is a coalition or an atomic weighted player. The paper’s central phenomenon is interaction among individually boundedly rational voters who cannot coordinate. Once each type is a coordinated player, the relevant question is a weighted finite normal-form game with \(\tau\) players. The population mass is merely a weight in the payoff map, not the continuous society whose multiplicity is being exploited. That could support a new paper on bloc manipulation, but it is not a continuization of this one.
Theorem 11 has the same problem. Its proof relies on unit ballot changes: candidates differ by one approval point, a Type 1 or Type 2 manipulation changes selected scores by exactly one, and the sets of manipulable candidates are controlled by those unit margins. For a coordinated type of mass \(\mu_t\), the corresponding change is \(\mu_t\), and the whole classification must be rebuilt around weighted coalitional deviations. For independent nonatomic voters, no type can make that change unilaterally. Thus the suggested “sort candidate score margins by cohort mass” is not an adaptation of the proof; it defines a different weighted game.
Allowing only a fraction of a type to manipulate does not provide a faithful third option. If individuals choose independently, the aggregate is a nonatomic mixed-strategy population and unilateral deviations remain ineffectual; the paper explicitly avoids this lottery setting because ordinal preferences do not compare lotteries. If a fraction of a type may coordinate its move, the deviation is again a coalition deviation, requiring a new equilibrium concept and new strategic assumptions.
So the proposed mirrors face a trilemma:
The honest weakness of the negative case is that a deliberately organized-bloc model could be worthwhile in its own right. But that is an extension motivated by this paper, not a continuous mirror of its problem. Under the ChoCo gate—population continuization while preserving the authors’ recognizable computational question—neither Theorem 12 nor Theorem 11 supplies a worthwhile anchor.
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.