| paper | d4-conf-sagt-2013-0011 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 9
statement extracted from the paper’s text layer
Given a finite candidate set \(X\), strict candidate preference rankings with each candidate ranked first in their own ranking, a fixed tie-breaking priority, and a rational distribution \(\mu\) over supported complete voter rankings with no tied pairwise masses, find a nonempty running slate \(Y\subseteq X\) that is a pure Nash equilibrium. For each slate, restrict rankings to \(Y\), elect the Copeland winner under strict pairwise majority and the fixed priority, and treat the empty slate as a no-election outcome ranked below every candidate. A slate is an equilibrium if no running candidate benefits by withdrawing and no nonrunning candidate benefits by joining.
Types are complete rankings of \(X\), each carrying rational mass \(\mu_t\); the decision variable is the running slate \(Y\), represented by one entry decision per candidate. There is no optimization objective: find a slate satisfying the unilateral-deviation constraints. Pairwise support is computed as \(p_\mu(x,y)=\sum_{t:\,x\succ_t y}\mu_t\), and Copeland scores determine the winner of each slate.
The continuous algorithm applies the paper’s existing tournament construction after aggregating type masses, so it adds little new complexity content; this limits the mirror’s novelty, not its plausibility.
fatal: False
The mirror covers Proposition 9’s Copeland pure-Nash equilibrium guarantee. It leaves the other voting-rule results, the strong-equilibrium result, and the paper’s broader open complexity questions aside.
The strongest mirror here is Copeland candidacy with a continuous electorate. The scenario is a large election with a finite slate of potential candidates and millions of voters concentrated in a much smaller set of complete ballot rankings. A type is one such ranking; its mass \(\mu_t\) is the fraction of voters with that ranking. Candidates remain individual strategic players, as in the paper. Each has a strict preference over possible winners and ranks themself first.
My anchor is Proposition 9, proved in this paper: under Copeland, with any number of candidates and an odd number of voters, every candidacy game has a pure Nash equilibrium. The paper’s proof also gives a way to construct one. This is an equilibrium-existence result, not a stated P/NP classification; the paper leaves the computational complexity of deciding equilibrium existence for future work.
Here is the continuous problem I would hand to a prover: Continuous Copeland Candidacy — find a pure Nash equilibrium. An instance consists of a finite candidate set \(X\), candidate preference rankings as above, a fixed tie-breaking priority, and a rational distribution \(\mu\) over the supported voter rankings, with support size \(\tau\). Assume no pair of candidates ties in the electorate’s pairwise comparison, matching the paper’s odd-electorate condition. For candidates \(x,y\), define
\[
p_\mu(x,y)=\sum_{t:\,x\succ_t y}\mu_t.
\]
For any nonempty running slate \(Y\), restrict each voter ranking to \(Y\), select the Copeland winner by pairwise majority, and use the fixed priority to break Copeland-score ties. Complete the empty-slate case with a no-election outcome ranked below every candidate.
A solution is a nonempty slate \(Y\) such that no running candidate can improve by withdrawing and no nonrunning candidate can improve by joining. The expected direction is tractable. In the proof of Proposition 9, select the priority-preferred Copeland winner \(c\) of the full slate and return
\[
D(c)=\{c\}\cup\{y\in X:p_\mu(c,y)>1/2\}.
\]
The proposition’s argument shows this slate is a Nash equilibrium. Computing all pairwise masses and forming \(D(c)\) takes time polynomial in \(m,\tau,L\), where \(L\) is the input bit length. This computes an equilibrium from the type-mass representation without expanding the electorate into individual voters.
The mirror is plausible because the paper’s outcome rule already depends on aggregate pairwise support, and its candidate actions and incentives are unchanged. It covers Proposition 9’s Copeland pure-Nash result only; it does not claim a mirror for the paper’s other voting rules or its strong-equilibrium result. Natural follow-up questions are whether the construction extends to tied pairwise masses under the Copeland-zero convention mentioned in the paper, and what the search and decision complexities are for rules where equilibrium existence is not guaranteed.
The soft spot is that this is a clean population mirror, but not a case where continuization dissolves discrete hardness: Proposition 9 already guarantees an equilibrium for the finite electorate. Also, the no-pairwise-ties assumption excludes some natural continuous distributions. So this is a credible, constructive Class A-style mirror of one named result, not evidence that the paper’s broader complexity questions have been answered.
The sharpest objection is that Proposition 9 is an equilibrium-existence theorem, not a complexity result. The paper gives no named classification of an algorithmic problem there; it explicitly leaves the computational complexity of deciding whether an equilibrium exists for future work. The proposed “find a pure Nash equilibrium” task is a search problem attached to that theorem, and the paper’s proof already supplies the construction. That makes it a poor anchor for a programme aimed at charting new computational questions.
But the mirror itself is well formed. A large electorate with repeated complete rankings is a plausible high-multiplicity regime, and keeping candidates as individual strategic players is appropriate. The paper’s proof depends on the voters’ majority tournament, so rational type masses can supply exactly the needed input. The restriction to strict pairwise margins is legitimate; even the tie caveat has a natural repair using the paper’s Copeland-zero variant.
The strongest version of the mirror therefore survives the main modelling objections. Given \(\mu\), compute the pairwise support, find the full-slate Copeland winner \(c\), and return \(D(c)=\{c\}\cup\{y:p_\mu(c,y)>1/2\}\). This takes time polynomial in \(m,\tau,L\). It is a genuine continuous-population formulation, but its algorithm is the paper’s existing tournament argument with a mass-aggregation step. The continuous input does not expose a new computational obstacle in this result.
A more substantial mirror would ask for the complexity of deciding or finding equilibria under rules where existence is not guaranteed. That is close to the paper’s stated future work, but it is not the anchor the proponent chose, and the paper does not establish a named complexity result for it. Still, the continuous voter-mass model for that question is plausible. I can make a case that the Copeland anchor is low priority and poorly matched to ChoCo’s complexity aim; I cannot honestly defeat it as a worthwhile continuous mirror, or defend the universal claim that no scenario works.
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.