| paper | Relaxed Notions of Condorcet-Consistency and Efficiency for Strategyproof Social Decision Schemes |
| authors | — |
| venue | AAMAS 2022 |
| filed under | voting · probabilistic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper contains no named result asserting algorithmic tractability, computational hardness, approximation, or parameterized complexity, so bit (a) fails. The proposed \( \mathsf{Max\text{-}Condorcet\text{-}SDS}_\infty \) is a new infinite-dimensional mechanism-design problem whose query society is not an algorithmic instance of any theorem in the paper. Outcome randomization and population distributions do not supply the required computational mirror.
fails bit a — no named computational result to mirror
Theorems 4–6 and Lemmas 1–5 concern axiomatic properties and impossibility bounds; no named computational result is covered.
The strongest honest positive case is a salvage, not a qualifying ChoCo case: this paper contains no named computational result. Theorem 1 and Theorem 2 are Gibbard characterizations cited from elsewhere; Theorem 3 is Barberà’s characterization, also cited. Theorems 4–6 and Lemmas 1–5 are proved here or in the extended version, but they are axiomatic characterizations and impossibility bounds, not statements that a problem is in \( \mathrm{P} \), NP-hard, FPT, or otherwise computationally classified. The paper’s “continuous strengthening” varies \( \epsilon \), \( \beta \), and \( \gamma \); it does not continuize the population. Its lotteries are outcome-space randomization, which is also out of scope.
If a non-computational anchor were nevertheless admitted, Theorem 4 is the strongest one. It states, as proved in this paper, that the randomized Copeland rule is the only anonymous, neutral, strategyproof SDS guaranteeing a Condorcet winner probability \(2/m\), and that no strategyproof SDS guarantees more than \(2/m\).
A faithful population mirror would use alternatives \(A\), complete ranking types \(T=\mathcal R(A)\), and a rational society distribution \( \mu\in\Delta(T) \). For \(x\ne y\), define
\[ p_{xy}(\mu)=\sum_{t:x\succ_t y}\mu_t. \]
Thus \(x\) is a Condorcet winner exactly when \(p_{xy}(\mu)>1/2\) for every \(y\ne x\). A continuous SDS is a map \(F:\Delta(T)\to\Delta(A)\), with \(F(\mu,x)\) the probability assigned to \(x\).
The natural high-multiplicity regime is a large electorate with \(N\gg\tau=|T|\): millions of voters share one of a small number of complete preference templates. The vector \( \mu \) is then exactly the normalized count vector of a finite election, \( \mu_t=n_t/N \). Anonymity and neutrality remain meaningful, while the pairwise counts in the paper become population masses.
The resulting problem could be called \( \mathsf{Max\text{-}Condorcet\text{-}SDS}_\infty \). Given \(m\), \(T\), a query society \( \mu \), a rational threshold \( \alpha \), and a finite representation bound \(B\), decide whether there exists a finitely represented SDS \(F\) that is anonymous, neutral, strategyproof, and satisfies
\[ F(\nu,x)\ge \alpha \]
for every society \( \nu\) and every Condorcet winner \(x\) of \( \nu \). If so, output the rule and its lottery \(F(\mu)\); the optimization version maximizes \( \alpha \).
A natural finite representation is the continuous limit of Barberà’s point-voting/supporting-size form:
\[ F(\mu,x)=\theta P_a(\mu,x)+(1-\theta)S_b(\mu,x), \]
where
\[ P_a(\mu,x)=\sum_{t\in T}\mu_t a_{\operatorname{rank}_t(x)} \]
for a nonincreasing scoring vector \(a\), and
\[ S_b(\mu,x)=\sum_{y\ne x} b(p_{xy}(\mu)) \]
for a nondecreasing step function \(b\) with at most \(B\) rational breakpoints and
\[ b(q)+b(1-q)=\frac{2}{m(m-1)}. \]
The randomized Copeland rule is obtained from the step function that is \(0\) below \(1/2\), \(1/(m(m-1))\) at \(1/2\), and \(2/(m(m-1))\) above \(1/2\).
The action is therefore the choice of the SDS \(F\); the decision variable at a given society is the lottery \(F(\mu)\); and the objective is the worst-case Condorcet-winner probability \( \alpha(F) \). The expected answer is that \( \alpha^\star=2/m \), with randomized Copeland uniquely attaining it under anonymity and neutrality. In the restricted finite-dimensional representation, I would expect a tractable or even closed-form optimization problem, with linear or separation-oracle subproblems over the population simplex. That would be a new Class A result, not something established by this paper.
The main modelling weakness is strategyproofness. For a nonatomic population, a single voter has zero mass, so literal unilateral strategyproofness becomes vacuous. A nontrivial mirror must instead require that no positive mass of one type can jointly misreport:
\[ F(\nu)\succeq_t^{SD} F(\nu-\lambda e_t+\lambda e_{t'}) \]
for every \(t,t'\), society \( \nu \), and \(0\le\lambda\le\nu_t\). This is a sensible mass-action analogue, and randomized Copeland plausibly satisfies it, but it is stronger than the paper’s unilateral notion and is not implied by Theorem 4. Proving equivalence with an appropriate high-multiplicity limit is itself a new question.
I would cover only Theorem 4. Theorems 5 and 6 suggest further continuous design problems involving the \( (\beta,\gamma) \) and \( (\alpha,\beta) \) tradeoffs, but adding them would not repair the missing computational anchor.
So the best positive claim is that Theorem 4 inspires a natural, mathematically exact population-distribution extension with a plausible tractable design problem. Under the programme’s stated eligibility rule, however, the paper cannot support a genuine positive ChoCo verdict because it contains no named computational result to mirror.
The negative case is unusually strong because the paper offers no ChoCo anchor at all. Theorem 4 is an axiomatic characterization: it classifies which social decision schemes can satisfy strategyproofness, anonymity, neutrality, and a Condorcet guarantee. It does not assert that any computational problem is in \( \mathrm{P} \), NP-hard, approximable, or parameterized. Theorems 5 and 6 have exactly the same defect. The paper has no input-action-output problem whose high-multiplicity version can be taken.
The proposed \( \mu \)-model is mathematically legitimate, but it does not repair this. For anonymous profiles, \( \mu_t=n_t/n \) is simply a normalized count vector. It is a sensible high-multiplicity representation, and I would not object to it on the ground that it loses voter identity. The problem is that Theorem 4 never asks anyone to act on that population. It quantifies over all profiles while characterizing a rule. The population distribution is a domain point, not an instance on which an algorithm performs bribery, control, campaigning, or robustness optimization.
The proposed \( \mathsf{Max\text{-}Condorcet\text{-}SDS}_\infty \) therefore changes the object. Its decision variable is an entire function \(F:\Delta(T)\to\Delta(A)\), subject to global axioms over every society. The query society \( \mu \) is irrelevant to feasibility and to the optimal value \( \alpha \); it is merely evaluated after the rule has been designed. If one fixes \(F\), computing \(F(\mu)\) is just evaluation. If one searches over all \(F\), one has a new infinite-dimensional mechanism-design problem, not a continuization of a computational result in this paper.
The proposed bounded-breakpoint representation does not solve that problem faithfully. In the finite theorem, the supporting-size rule is specified by an arbitrary vector \( (b_0,\ldots,b_n) \). Passing to a continuum naturally produces an arbitrary monotone function \(b:[0,1]\to\mathbb{R}\), not a function with a fixed number \(B\) of breakpoints. Imposing \(B\) is an additional syntactic restriction chosen by the analyst. It may yield a pleasant finite optimization problem, but that problem is newly designed and need not contain the full continuous analogue of the theorem.
Strategyproofness creates a second, more fundamental break. A unilateral finite-voter deviation changes \( \mu \) by \( \frac1n(e_{t'}-e_t) \), which vanishes for an individual in a nonatomic limit. For continuous \(F\), unilateral strategyproofness consequently becomes vacuous or reduces to a limiting regularity condition. The proposed positive-mass constraint,
\[ F(\nu)\succeq_t^{SD} F\bigl(\nu-\lambda e_t+\lambda e_{t'}\bigr), \]
is instead a coalition or mass-action strategyproofness axiom. That may be interesting, but it is not the paper’s notion and is not supplied by Gibbard’s or Barberà’s characterizations. Choosing positive-mass deviations is a new modelling decision; choosing price-taking agents makes incentives vacuous; retaining finite atomic voters gives a high-multiplicity finite model rather than the proposed continuum. None yields a canonical mirror of Theorem 4.
The same applies to Theorems 5 and 6: their \( \alpha,\beta,\gamma \) tradeoffs concern universal axioms of a rule, not computational tasks over a society. Replacing finite profiles by distributions may produce worthwhile continuous randomized-social-choice theory, but it does not make those theorems computational results.
Thus the strongest charitable verdict is that the paper motivates a new axiomatic continuum mechanism-design project. Under ChoCo’s stated scope, however, no choice of ranking type space or population scenario supplies a computational mirror of this paper. The proponent’s own conclusion is therefore correct: this is not a worthwhile continuous-computational 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.