| paper | Impact of Tie-Breaking on the Manipulability of Elections |
| authors | — |
| venue | AAMAS 2024 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Under the explicit test, Theorems 4.2 and 3.7 assert exact PoA values, not hardness, algorithms, or complexity of a named problem, so bit (a) fails. The proposed high-multiplicity reporting games are intelligible, but their equilibria depend on a finite replication scale: an atomless unilateral deviation is ineffectual, while replication changes the game or restores the discrete instance. The paper is therefore red, although these newly formulated models could motivate separate ChoCo work.
fails bit a — no named computational result to mirror
The proposed mirrors attempt to cover Theorem 4.2 and Theorem 3.7 only; they leave the other PoA theorems, equilibrium propositions, and discussion of tie-breaking untouched.
The strongest positive case is real, but qualified: this paper has no theorem explicitly classifying a problem as NP-hard, polynomial-time, FPT, or similar. Its named results are exact price-of-anarchy theorems. If those count as computational anchors—as results about computing a manipulation-impact objective—then two particularly good mirrors are available. Under a strict complexity-only reading, I would report that the paper has no qualifying computational anchor.
My lead anchor is Theorem 4.2, proved in this paper: the normalized PoA of plurality with random-candidate tie-breaking is exactly \(m\), for both Spearman footrule and Kendall tau distance.
The continuous mirror is a high-multiplicity plurality game. A type \(t\) is a complete sincere ranking \(\pi_t\), together with its dishonesty metric. The society is a rational distribution \(\mu\) over rankings. A reporting plan is a mass transfer \(y_{t,\rho}\), where \(y_{t,\rho}\) is the mass of sincere type \(t\) submitting ranking \(\rho\), and \(\sum_\rho y_{t,\rho}=\mu_t\).
Let \(p_\mu(c)=\sum_{t:\operatorname{top}(\pi_t)=c}\mu_t\) be the sincere first-place mass and let \(M_y\) be the set of candidates with maximum reported first-place mass. As in the paper’s normalization, define \(q_\mu(c)=1+(m-1)p_\mu(c)\). The continuous objective is the worst equilibrium ratio
\(\operatorname{CPoA}_{\mathrm{pl}}(\mu)=\max_{y\in\mathcal E_D(\mu)}\frac{\max_c q_\mu(c)}{|M_y|^{-1}\sum_{c\in M_y}q_\mu(c)}\),
where \(D\) is footrule or Kendall distance and \(\mathcal E_D(\mu)\) is the set of minimally dishonest equilibrium reporting plans.
The associated computational problem, call it \(\textsc{Continuous-Plurality-PoA}\), is: given \(C\), a rational type distribution \(\mu\), a tie-breaking rule, a distance \(D\), and a rational threshold \(R\), decide whether there exists an admissible reporting plan \(y\) with \(\operatorname{CPoA}\ge R\), and output such a plan when one exists. The solution is therefore a mass-reporting plan together with an equilibrium certificate.
The equilibrium semantics must be specified carefully. A naive atomless Nash equilibrium would make every individual non-pivotal, destroying the paper’s phenomenon. I would interpret \(\mu\) and \(y\) through exact replication: choose a common denominator \(N\), create \(qN\mu_t\) voters of every type, and \(qNy_{t,\rho}\) voters using each report. A plan is admissible when every such replication is a minimally dishonest Nash equilibrium under one-voter deviations. Random outcomes are compared by the paper’s rational cutoff dominance: lottery \(L\) is at least as good for type \(t\) as \(L'\) when, for every \(j\), \(L\) gives at least as much probability to one of \(t\)’s top \(j\) candidates. A closer report must produce a strictly worse lottery.
This is not an arbitrary construction. Take two sincere types of mass \(1/2\):
\(t_1: c_m\succ c_1\succ c_2\succ\cdots\succ c_{m-1}\),
\(t_2: c_m\succ c_{m-1}\succ c_{m-2}\succ\cdots\succ c_1\).
Let them report respectively
\(\rho_1=(c_1,c_m,c_2,\ldots,c_{m-1})\)
and
\(\rho_2=(c_{m-1},c_m,c_{m-2},\ldots,c_1)\).
Truthfully, \(c_m\) has first-place mass \(1\), so its normalized score is \(m\). Under the reporting plan, \(c_1\) and \(c_{m-1}\) tie, and each has sincere first-place mass \(0\), hence normalized score \(1\). Reverting to truth makes the other tied candidate win uniquely, which is worse for each type; the same argument works for both distances. Thus the continuous instance has PoA \(m\), exactly the value in Theorem 4.2. Its finite replications are precisely the paper’s two groups of \(k\) voters.
The regime is credible: a large election, referendum, or platform consultation can contain two very large blocs with identical standardized rankings, while the number of voters is enormous and the number of relevant types is two. Mass is more meaningful than named-voter identity in that setting. The paper’s authors should recognise this as their plurality game with counts replaced by proportions, not as a simplified voting rule.
I would expect this mirror to be Class A in the explicit-support regime. Plurality scores depend only on top-choice mass, so the reported-score constraints are linear; deviations can be checked by considering possible top candidates and the minimum footrule or Kendall distance needed to place each candidate first. The global worst case is already identified by the theorem. The richer open questions are instance-wise computation of \(\operatorname{CPoA}_{\mathrm{pl}}(\mu)\), approximation from empirical samples, and optimization over tie-breaking distributions.
A second, independent anchor is Theorem 3.7, also proved in this paper: the normalized PoA for majority judgment with lexicographic tie-breaking is \(\frac{(u-2)m+1}{u-1}\) for every component-wise norm.
Here a type is a cardinal valuation vector \(t\in\{1,\ldots,u\}^m\), and \(\mu_t\) is the fraction of voters with that vector. For a candidate \(c\), the continuous lower median is the quantile
\(z_\mu(c)=\min\{j:\sum_{t:t(c)\le j}\mu_t\ge 1/2\}\).
A reporting plan \(y_{t,\rho}\) transfers mass from sincere valuation vector \(t\) to reported vector \(\rho\). Compute reported medians from the resulting distribution, select the lexicographically first candidate among the maximum-median candidates, and evaluate the winner using the sincere distribution. With normalized scores \(\widehat z_\mu(c)=1+\frac{m-1}{u-1}(z_\mu(c)-1)\), define
\(\operatorname{CPoA}_{\mathrm{MJ},L}(\mu)=\max_{y\in\mathcal E_D(\mu)}\frac{\max_c\widehat z_\mu(c)}{\widehat z_\mu(r_L(y))}\).
The decision problem \(\textsc{Continuous-MJ-Lex-PoA}\) asks, given \(\mu\), \(L\), a component-wise norm, and \(R\), whether an admissible report plan has ratio at least \(R\).
The paper’s witness has a direct mass interpretation. For \(0<\varepsilon<1\), use three types with masses \((1-\varepsilon)/2,(1-\varepsilon)/2,\varepsilon\):
Types \(A\) and \(B\) report truthfully. Type \(D\) reports \(u\) for \(c_1\) and \(1\) for every other candidate. Truthfully, each \(c_i\ne c_1\) has median \(u-1\), while \(c_1\) has median \(1\). After reporting, every candidate has median \(1\), so lexicographic tie-breaking selects \(c_1\). The normalized ratio is exactly \(\frac{(u-2)m+1}{u-1}\). The small type-\(D\) mass is not a vanishing technicality: any positive mass crossing the median threshold changes the result. The paper’s \(k,k,1\) construction is the rational finite realization with \(\varepsilon=1/(2k+1)\).
This is an especially natural continuous object. Majority judgment is already defined by a population quantile, and a large survey or public consultation can plausibly contain two large standardized rating blocs plus a smaller but nonzero constituency with a distinctive evaluation pattern. The type count is three while the population can be arbitrarily large.
I would again expect Class A for explicit finite support. Once candidate medians are guessed, the conditions \(F_c(j)\ge 1/2\) are linear inequalities in the mass variables. The main structure is quantile threshold-crossing, so LP or finite case analysis should compute the worst equilibrium for a given \(\mu\). Further questions include the random-tie analogue corresponding to Theorems 4.3 and 4.5, sensitivity when a type’s mass approaches \(1/2\), and algorithmic optimization of the lexicographic order.
These mirrors cover only two results: Theorem 4.2 and Theorem 3.7. They do not claim that every theorem in the paper has a useful continuous counterpart. They also do not create continuity by randomizing outcomes; the continuous object is the population distribution, while candidate selection remains finite and the random tie-break is merely part of the voting rule.
The weakest point is the replication semantics. If a referee insists on a genuinely atomless game in which a single agent has zero influence, then the strategic effect disappears: truthful reporting becomes minimally dishonest, and the paper’s PoA examples are not recovered. The positive case therefore depends on treating the continuous society as a high-multiplicity relaxation with unit deviations preserved at exact ties and median thresholds. I think that is defensible—and consistent with the programme’s stated bridge—but it must be said openly.
The other weakness is that the paper itself supplies no complexity classification. The proposed continuous problems are genuine computational continuations of its exact PoA results, but their tractability would be a new result, not something established by Bailey and Tovey.
The decisive objection is that this paper has no computational anchor in ChoCo’s stated sense. Its numbered results are price-of-anarchy bounds and equilibrium constructions, not complexity classifications, algorithms, or computational optimization theorems. The proposed \(\textsc{Continuous-Plurality-PoA}\) and \(\textsc{Continuous-MJ-Lex-PoA}\) problems are new problems invented around the paper’s welfare analysis; they are not continuous versions of computational problems posed by the authors.
Even granting that an exact PoA theorem may serve as an anchor, both proposed mirrors have the same fundamental defect: the paper’s manipulation is driven by one-voter pivotality. In a genuinely atomless society, changing one agent’s report leaves the aggregate distribution unchanged:
\[ \mu'=\mu. \]
The winner and lottery therefore do not change. Under the paper’s minimal-dishonesty definition, any nontruthful report has a more sincere report producing the same outcome, so it cannot be minimally dishonest. The strategic equilibria producing the paper’s bad PoA disappear. Enlarging the type space does not fix this; it only gives more types whose individual deviations still have measure zero.
The replication proposal hides this problem rather than solving it. It introduces an extra parameter—the mass of one voter—which is absent from the continuous society. Different replication factors produce different equilibrium notions. Taking one particular finite realization simply returns to the discrete game. Requiring every replication keeps only equilibria robust to changing the indivisible unit; taking the limit removes unilateral influence altogether. A model with a fixed positive deviation mass is likewise not atomless, while a model allowing a whole type to deviate changes unilateral Nash equilibrium into coalition or bloc deviation.
This is fatal for Theorem 3.7. In the paper’s witness, the exceptional type has one voter. With \(k,k,1\) voters, the reported low score of every \(c_i\neq c_1\) is supported by \(k+1\) voters, just enough that the exceptional voter’s more truthful report crosses the lower-median threshold. Replicate the same proportions by \(q\). The low-score count becomes \(q(k+1)\), while the lower-median threshold is \(q(k+\tfrac12)\). After one exceptional voter changes their report, the low-score count is \(q(k+1)-1\), which is still at least the threshold for every \(q\ge2\). The median no longer changes, so the more truthful report gives the same outcome and minimal dishonesty rejects the proposed equilibrium.
Replacing the exceptional voter by a positive-mass bloc does not help. Then the bloc—not an individual voter—must move to change the median. That is a different game. The continuous median itself is perfectly meaningful, but the strategic use of that median in this theorem is not preserved by continuization.
Theorem 4.2 has the strongest positive appearance because its two-block construction is genuinely plausible as a high-multiplicity election. I do not rely on the claim that voting lacks repeated types; it plainly can have large standardized blocs. But the proposed continuous version still fails as a worthwhile ChoCo mirror. In the atomless model, a single member of either bloc cannot change the tie, so the nontruthful reports are eliminated by minimal dishonesty. If one instead declares an infinitesimal mass movement pivotal at an exact tie, one has introduced a special “pivotal continuum” equilibrium concept that the paper does not define. If one retains one-voter deviations, one must retain the hidden population scale. Either repair is an additional modelling choice, not a canonical continuous society.
Moreover, optimizing over all \(\mu\) merely reproduces the paper’s two-block witness with masses \(1/2\) and \(1/2\); it adds no computational content to the theorem. Asking for the worst equilibrium for a fixed \(\mu\) could be an interesting new voting-game problem, but it is not motivated by a computational result in this paper, and its constraints are not the LP structure suggested by the proponent. Median inequalities describe an aggregate report distribution; Nash and minimal-dishonesty conditions require comparing every unilateral deviation and the winner change caused by a hidden \(1/N\) perturbation. Those are discontinuous, replication-dependent conditions, not simply linear quantile constraints.
Thus the two plausible scenarios establish that high multiplicity can describe elections, but not that this paper supplies a useful continuous computational mirror. The negative case is not a proof that no researcher could invent a valuable pivotal-continuum game around Theorem 4.2. It is stronger and more specific: under ChoCo’s population-continuum semantics and computational scope, Theorem 3.7 loses its equilibrium phenomenon, while Theorem 4.2 survives only as a boundary convention or a restatement of a finite two-bloc example. Neither is a genuine computational continuization of the paper.
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.