| paper | Semi-random Impossibilities of Condorcet Criterion |
| authors | — |
| venue | AAAI 2023 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1 and Theorems 2–4 are named probability bounds about axiom satisfaction, not computational results, so bit (a) fails categorically. The proposed minimum-mass abstention problem is a coherent high-multiplicity research question, but it replaces the paper’s sampling probability with a new deterministic extensive-coalition optimization. Therefore the paper is red despite the plausible related mirror.
fails bit a — no named computational result to mirror
The proposed problem loses the paper’s finite-population fluctuation scale because B/n tends to zero, and replacing semi-random probability by positive-mass optimization changes the question.
fatal: True
The proposed mirror covers only participation via deterministic mass abstention; it does not cover the paper’s semi-random probability bounds or the HM, MM, and SP results.
The strongest honest case is conditional: this paper has a plausible population mirror, but it fails the programme’s strict anchor requirement.
None of the paper’s named results is a computational-complexity result. Theorem 1 (CC+Participation), Theorem 2 (CC+half-way monotonicity), Theorem 3 (CC+Maskin monotonicity), Theorem 4 (CC+strategy-proofness), and Corollary 1 all prove probability bounds of the form \(1-\Omega(B/\sqrt n)\). They do not assert membership in P, NP-hardness, parameterized hardness, or an algorithmic result. Claims 1–5 are proof-counting claims, not computational results. Thus there is no eligible anchor under the stated ChoCo screening rule.
If the anchor rule is relaxed to include a computationally posed robustness problem, the best lead is Theorem 1, proved in this paper.
Take \(m\ge4\) alternatives and \(T=L(A)\), the \(\tau=m!\) complete rankings. A society is a mass vector \(\mu\in\Delta(T)\), where \(\mu_t\) is the fraction of voters with ranking \(t\). Fix an anonymous Condorcet rule \(r\), such as Copeland, maximin, ranked pairs, or Schulze—the rules the paper itself names as commonly studied and asymptotically optimal.
For a mass vector \(z\) of abstaining voters, define
\[ 0\le z_t\le \mu_t,\qquad b(z)=\sum_t z_t<1, \]
and the post-abstention society
\[ (\mu\ominus z)_t=\frac{\mu_t-z_t}{1-b(z)}. \]
Let \(w=r(\mu)\) and \(w_z=r(\mu\ominus z)\). The vector \(z\) is a beneficial mass-abstention attack if every type that contributes positive mass strictly prefers the new winner:
\[ z_t>0 \implies w_z\succ_t w. \]
Define the minimum abstaining mass
\[ \rho_{\mathrm{PAR}}(r,\mu) = \inf\{b(z):z\text{ is a beneficial mass-abstention attack}\}. \]
The continuous problem is:
Given \(A\), a rational society \(\mu\), a rational threshold \(\beta\), and a fixed rule \(r\), compute \(\rho_{\mathrm{PAR}}(r,\mu)\), or decide whether \(r\) satisfies Condorcet criterion at \(\mu\) and whether \(\rho_{\mathrm{PAR}}(r,\mu)\le\beta\). If so, output an attacking mass vector \(z\).
This is the direct mass analogue of the paper’s \(B\)-voter group version of participation. A discrete profile with \(n_t\) voters maps to \(\mu_t=n_t/n\), and a coalition of \(B\) voters maps to mass \(\beta=B/n\). The objective is no longer to identify named voters; it is to find the smallest fraction of a repeated preference type whose abstention changes the outcome beneficially.
The regime is quite natural: a national or platform election with millions of voters, a small candidate set, and at most \(m!\) ballot types. For four candidates there are only \(24\) complete rankings, while the electorate may have millions of members. The paper itself makes this mirror especially plausible because it explicitly introduces the anonymized histogram \(\operatorname{Hist}(P)\), and its proof works with profiles near scaled histogram vectors. The continuous society is simply the normalized histogram.
I would expect this deterministic problem to be Class A for fixed \(m\) and explicitly represented types, at least for standard pairwise-based Condorcet rules. Pairwise margins after abstention are affine in \(z\) up to the common positive normalization \(1-b(z)\). Once a candidate and the relevant winner relations are fixed, the attack constraints become linear; one can enumerate finitely many winner cases and solve LPs. With variable \(m\), hardness may arise from the candidate-comparison structure, making it more plausibly Class B than continuum-specific Class C.
The paper’s probabilistic theorem suggests a second question, but not a transferred theorem. Put a probability law \(\mathcal Q\) over society vectors \(\mu\), induced by a population mixture of Mallows, Plackett–Luce, or other preference segments, and ask for
\[ \Pr_{\mu\sim\mathcal Q} \left[ \text{r satisfies CC and } \rho_{\mathrm{PAR}}(r,\mu)>\beta \right]. \]
One could then optimize this probability over Condorcet rules. Theorem 1 motivates this question, but does not establish its continuous analogue.
The weakest point is substantial: the paper’s \(\Omega(B/\sqrt n)\) phenomenon is driven by finite-population fluctuations. Under the paper’s regime \(B\le\sqrt n\), the corresponding mass \(B/n\) tends to zero. In an exact atomless society, unilateral abstention has zero effect, and the theorem’s violation probability may collapse rather than survive. Preserving the \(1/\sqrt n\) scaling would require a stochastic law over society vectors with finite-size fluctuations, which risks becoming merely a noise model over discrete profiles—the programme explicitly excludes that as its central object.
So the positive case is that Theorem 1 naturally generates a faithful and potentially tractable continuous mass-robustness problem, in a genuinely high-multiplicity electoral regime. But it is a new computational question inspired by the paper, not a continuous reformulation of one of the paper’s named computational results. Under the strict ChoCo rubric, that missing anchor is decisive.
The paper fails the programme’s strict gate before the modelling question begins. Theorem 1, Theorems 2–4, and Corollary 1 are probability bounds for axiom satisfaction. Claims 1–5 are counting steps in their proofs. None is a theorem about an algorithm, complexity class, hardness, approximation, or parameterized computation. Thus there is no named computational result to mirror.
The proposed \(\rho_{\mathrm{PAR}}\) is the strongest rescue, but it is a new problem rather than a continuization of Theorem 1. The theorem studies
\[ \inf_{\vec\pi}\Pr_{P\sim\vec\pi}[X(r,P,B)=1], \]
where a finite labelled population is sampled independently from adversarially chosen individual distributions. The proposed problem instead takes one deterministic histogram \(\mu\) and optimizes the mass of a beneficial abstaining coalition. It replaces probability by optimization, the product distribution by its aggregate histogram, and the coalition size \(B\) by a macroscopic mass threshold.
That last change is not cosmetic. In the theorem’s regime \(B\le\sqrt n\), the corresponding mass is \(B/n\), which tends to zero. In the continuum, removing or changing such a coalition leaves \(\mu\) unchanged. The same collapse affects all four axioms: finite-group abstention, reversal, rank improvement, and misreporting become invisible to the normalized society. One can repair this by allowing a coalition of fixed positive mass \(\beta\), but that is a different extensive-coalition robustness problem. It may be interesting, but it is not the paper’s semi-random impossibility result.
The natural high-multiplicity setting does not rescue the missing anchor. A national election with finitely many ranking types is certainly a sensible continuous society, and the histogram argument makes that clear. There is no valid objection based on identity or on the existence of repeated types. But that only establishes that \(\rho_{\mathrm{PAR}}\) is well-defined. It does not turn an axiomatic probability theorem into a computational result from the paper.
The probabilistic extension over society vectors is weaker still. A law \(\mathcal Q\) over \(\mu\) could be studied, but the paper does not determine such a law. Its independent per-voter distributions contain finite-\(n\) variance and covariance information that the aggregate continuous vector discards. Different vectors \(\vec\pi\) can have the same mean society and radically different fluctuation behaviour. To recover the paper’s \(1/\sqrt n\) phenomenon, one must reintroduce empirical sampling, a \(\sqrt n\)-scaled fluctuation field, or an atomic finite-population component. Those are respectively a noise model, a stochastic tangent-limit model, or a hybrid discrete population—not the deterministic population continuization at the centre of ChoCo.
Adding richer type spaces does not fix this. A finite family of Mallows or Plackett–Luce segments gives a legitimate high-multiplicity model, but still loses the individual sampling fluctuations. Making each voter’s distribution or random seed part of the type preserves the theorem only by making types effectively individualised, defeating the intended multiplicity regime. Retaining explicit atoms of mass \(1/n\) simply puts the discrete population back into the model.
The negative case should not overclaim: if the anchor rule were relaxed from “named computational result” to “any natural computational question inspired by an axiom,” the deterministic mass-abstention problem would be a credible ChoCo candidate. The proponent is right that it is semantically coherent. But under the stated programme, it is an unanchored new problem, while the paper’s defining semi-random phenomenon disappears in the continuous limit. The paper should therefore be rejected as a source for a worthwhile continuous computational mirror, even though a related mass-coalition project could independently be worthwhile.
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.