| paper | d4-conf-ecai-2012-0180 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\): every valid input is a YES-instance. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 22
statement extracted from the paper’s text layer
Given rational sincere-type masses \(\mu\) and an initial rational state \(x\) of reported ballots, consider plurality with randomized tie-breaking and all locally uniform subsequential limits of interpolated RBR runs on exact finite replications, where each update transfers mass \(1/N\) and time is scaled as \(u=k/N\). Does every such fluid trajectory become stationary by time \(u=m-1\)?
Represent each sincere ranking \(t\) by mass \(\mu_t\), and let \(x_{t,\pi}\) record how much of that mass currently reports ballot \(\pi\), with \(\sum_\pi x_{t,\pi}=\mu_t\). Define trajectories as limits of finite replicated societies that retain the paper’s unilateral RBR moves and randomized tie-breaking; the theorem predicts a stationary fluid state by \(u=m-1\), without asserting that the endpoint is a Nash equilibrium of a conventional atomless game.
The fluid path is induced by finite replicated runs: an atomless voter cannot change the outcome, and producing a path may require \(N\)-scale microscopic updates even when the rational masses have short encodings.
fatal: False
The mirror covers the plurality convergence guarantee in Theorem 22 and, separately, the antiplurality guarantee in Theorem 14. It does not cover the cycling examples or convergence behavior under other scoring rules.
The strongest positive case is a population-size-normalized limit of the paper’s one-voter-at-a-time dynamics. I would anchor it on two convergence theorems; the paper has no named hardness result, so these are algorithmic anchors rather than hardness anchors.
The lead anchor, Theorem 22, is proved in this paper: for plurality with randomized tie-breaking, Restricted Best Reply Dynamics (RBRD) converges to a Nash equilibrium from any state in at most \(m+(m-1)n\) steps. The paper’s stochastic-dominance definition of improvement applies to randomized outcomes.
Theorem 14, also proved here, gives the corresponding antiplurality result: with randomized tie-breaking, RBRD converges to a Nash equilibrium from any state in at most \(mn\) steps.
Here is the mirror I would put to a prover. Let \(T\) be the set of sincere rankings, and let \(\mu_t\) be the fraction of society with ranking \(t\). A current state is \(x_{t,\pi}\): the mass of sincere type \(t\) currently reporting ballot \(\pi\), with \(\sum_\pi x_{t,\pi}=\mu_t\). Supply \(\mu\) and \(x\) as rational masses, along with the rule and tie-breaking convention. The action remains a single voter changing their reported ranking according to the paper’s RBR rule; there are no coordinated group moves.
For each population size \(N\) that represents those rational masses exactly, replicate the population to \(N\) voters. One update moves mass \(1/N\) from one report to another. Interpolate the states after \(k\) updates at normalized time \(u=k/N\). Call a locally uniform subsequential limit of these interpolated paths a *fluid RBR trajectory*.
The two named questions are:
The finite theorems give affirmative answers: the antiplurality bound \(mn\), divided by \(N\), yields fluid horizon \(m\); the plurality bound \(m+(m-1)n\), divided by \(N\), yields horizon \(m-1\) as \(N\) grows. Each fluid trajectory’s terminal state is a limit of finite-population Nash equilibrium states. I would not claim that its endpoint is necessarily a Nash equilibrium of a conventional atomless game.
The regime is a large poll or election with many voters but relatively few distinct sincere rankings: \(N\) grows while the support size \(\tau\) stays moderate. A type is a complete sincere ranking; the current ballot is part of the evolving state, not a new preference type. This preserves the paper’s strategic setting in each finite population, including unilateral moves and stochastic-dominance improvement. It also makes the continuous question specific: does the convergence result have a population-size-independent meaning when each voter’s share tends to zero?
I expect Class A for these two mirrors. The paper’s bounds already imply finite normalized horizons, independent of the particular mass values and their bit lengths. Further questions include whether the limiting terminal state is independent of the update path, how to characterize the reachable terminal states, and which other scoring rules have stationary fluid limits.
The soft spot is substantial: in an exact atomless society, one voter has zero mass and cannot change the outcome. The mirror therefore inherits the one-voter incentive test from finite replicated societies and studies its limit; it is not a standalone nonatomic best-reply game. A strict atomless interpretation could make the authors reject it. What supports the case is that the limit keeps their one-at-a-time moves intact at every finite stage and asks a concrete, population-scale question about their convergence theorems. This mirrors only Theorems 14 and 22; it makes no claim about the paper’s unnumbered cycling examples or its dynamics under other scoring rules.
I would not claim that the paper lacks named algorithmic results: Theorems 14 and 22 give convergence bounds of \(mn\) and \(m+(m-1)n\) moves. The difficulty is that both bounds count individual pivotal moves. In a society with report masses \(x_{t,\pi}\), one atomless voter changing their report leaves \(x\), the scores, and the winner lottery unchanged. Under the paper’s costly-voting and strict stochastic-dominance conditions, that is not an improvement. Every state is therefore stationary in the literal atomless game, so neither theorem’s convergence phenomenon survives there.
The strongest version of the proponent’s mirror is the replicated fluid limit: take \(N\) voters, let each move transfer mass \(1/N\), and scale time by \(N\). The bounds then give horizons \(m\) for antiplurality and \(m-1\) for plurality. That is a coherent limit of finite runs, but its legal moves and their incentives come from the finite replicas. The resulting horizon counts \(N\) microscopic updates per unit of fluid time. It gives no algorithm for computing a trajectory or its endpoint from support-encoded rational masses in time polynomial in \(m,\tau,L\). In that encoding, \(N\) can be exponential in \(L\). The proposed question is thus a fluid-limit convergence claim, rather than a computational problem over a continuous society of the kind the programme targets.
This objection applies to Theorem 14 and Theorem 22 alike. Replacing individual moves with positive-mass moves would restore changes to the aggregate outcome, but a block moving together is a coalition, contrary to the paper’s no-coalition premise. A more ambitious question—computing the reachable terminal mass profiles—might be worthwhile. The paper’s order-dependence example makes it natural to ask, but the atomless model supplies no strict best replies to generate those paths; a nontrivial revision rule would need to be added. That would be a new dynamics to study, not a continuous mirror of either convergence theorem.
This is a limited negative case. If ChoCo counts limits of finite-agent dynamics as computational mirrors in their own right, the two anchors may survive: the fluid question is coherent, and the bound rescaling is exact. My case against them rests on the gap between that limit statement and an intrinsic, computationally meaningful best-reply process on a continuous society.
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.