| paper | A taxonomy of non-dictatorial unidimensional domains |
| authors | S. Chatterji, Huaxia Zeng |
| venue | GEB 2023 |
| filed under | voting · structured |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Corollary 1 is an axiomatic existence and non-existence classification, not a computational result under ChoCo’s gate. The proposed \(F\) adds positive-mass deviations and cross-population consistency, which the paper neither defines nor classifies; its projection rule can ignore mass magnitudes. Thus a plausible continuous extension exists, but no named computational result supplies the required anchor.
fails bit a — no named computational result to mirror
The candidate addresses Corollary 1’s rule-existence classification over distributions; it leaves the Auxiliary Proposition, Theorem 1, Fact 1, Proposition 1, and Corollary 2 without computational analogues.
The strongest honest conclusion is qualified: this paper has no named computational-complexity result. No numbered theorem, lemma, corollary, or proposition establishes NP-hardness, membership in \(P\), FPT, W[1]-hardness, or an algorithmic complexity bound. Thus, under ChoCo’s strict anchor rule, the paper supplies no qualifying computational anchor and cannot by itself support an A/B/C complexity classification.
There is nevertheless a credible continuous-population mirror of its main classification result.
The best substantive anchor is Corollary 1, proved in this paper (Appendix C). It states that for a non-dictatorial, unidimensional domain \(D\): an anonymous, tops-only, strategy-proof rule exists if and only if \(D\) is semi-single-peaked, equivalently if and only if \(D\) admits a strategy-proof projection rule. Conversely, no anonymous, tops-only, strategy-proof rule exists if and only if \(D\) is a semi-hybrid domain satisfying the unique seconds property; moreover, every tops-only, strategy-proof rule behaves like a dictatorship on a weak superset of the free zone.
My lead mirror would be:
Continuous Anonymous Rule Design. The alternatives are a finite set \(A\), arranged on the line or tree used by the paper. The voter types are complete preference orders \(D\subseteq\mathcal P(A)\). A society is a distribution \(\mu\in\Delta(D)\), where \(\mu_P\) is the fraction of society with ranking \(P\). The planner must construct a rule \(F:\Delta(D)\to A\) satisfying:
\[ F(\mu)\succeq_P F\bigl(\mu-\varepsilon e_P+\varepsilon e_{P'}\bigr). \]
A solution is a finite description of such an \(F\), together with the outcome \(F(\mu)\); a negative solution is a certificate that the supplied domain is semi-hybrid with the relevant free zone and hence admits no such rule.
This is a genuine high-multiplicity regime. Consider a large population of residents choosing the location of a public facility along a railway. Residents from the same neighbourhood and transportation environment have the same complete ranking over stations. There may be millions of residents but only a moderate number \(\tau=|D|\) of distinct ranking types, with \(\mu_P=n_P/n\). This is exactly the sort of repeated-type society for which a distribution over preferences is more natural than a list of named voters.
The paper’s projection rule has an immediate continuous form. If \(H^{\Gamma(\mu)}\) is the minimal subtree containing all alternatives that are peaks of positive mass, define
\[ F_{\bar x}(\mu)=\operatorname{Proj}\bigl(\bar x,H^{\Gamma(\mu)}\bigr). \]
Thus the mirror is not merely “apply an arbitrary voting rule to fractions”; it turns the paper’s own rule into a rule over the population simplex.
I would expect the semi-single-peaked branch to be the constructive, tractable side: the threshold and underlying tree give a compact description, and evaluating the projection outcome is straightforward from the peak masses. The semi-hybrid branch should remain impossible. Indeed, if such an \(F\) existed, then for every empirical distribution \(\mu=\frac1n\sum_i e_{P_i}\), the induced finite rule \(f(P_1,\ldots,P_n)=F(\mu)\) would be anonymous, tops-only, and strategy-proof. Corollary 1 would therefore rule it out on semi-hybrid domains. This gives a clean upward/downward bridge, although it transfers an impossibility result rather than computational hardness.
The weakest point is important: mass-strategy-proofness is not the paper’s original unilateral strategy-proofness. In a nonatomic society, one individual has zero mass, so literal unilateral deviations are vacuous. The mass-transfer formulation is the natural repair, but it is a co-modification and may be stronger than the authors’ question. A second weakness is that the paper studies axiomatic classification, not computational complexity; the proposed mirror is therefore a promising continuous rule-design problem, not a valid ChoCo computational anchor without new work.
The case against is strongest at ChoCo’s gate: this paper has no qualifying computational anchor. Its numbered results are all axiomatic existence, classification, or incentive-compatibility statements. Nothing asserts a complexity bound, an algorithm, a reduction, or even a finite computational decision problem. That is decisive for the programme as defined.
Corollary 1 does not repair this. The proposed \(F:\Delta(D)\to A\) is a new population-level mechanism-design problem, not the continuous form of the theorem. If strategy-proofness retains its original unilateral meaning, it becomes vacuous: one agent has measure zero, so changing that agent’s report leaves \(\mu\) unchanged. The displayed condition reduces to \(F(\mu)\succeq_P F(\mu)\).
The proposed mass-transfer condition is a sensible repair, but it is materially stronger. Moving \(\varepsilon\) mass from \(P\) to \(P'\) is a coalition deviation by a positive block of voters, whereas the paper excludes profitable deviations by one named voter. Corollary 1 therefore does not establish the existence or classification of such \(F\). An \(F\) would induce a consistent family of anonymous finite rules
\[
f_n(P_1,\ldots,P_n)
=
F\!\left(\frac{1}{n}\sum_i e_{P_i}\right),
\]
but the paper’s finite rules need not be consistent across \(n\), and nothing there supplies an extension to irrational distributions. The continuous model adds a new cross-population and group-strategy-proofness requirement.
The particular projection mirror is also computationally hollow. Its outcome depends on
\[
\operatorname{supp}(\mu)
=
\{P:\mu_P>0\},
\]
not on the magnitudes of the masses: \(F_{\bar x}(\mu)\) sees only the minimal subtree spanned by the peaks appearing with positive mass. A society with \(99\%\) of one type and \(1\%\) of another is indistinguishable from one with the proportions reversed, provided the support is unchanged. Thus the proposed mirror turns the population into a support set, not a genuinely quantitative continuous society.
One can improve it by considering mass-dependent generalized-median or phantom-voter rules. But that abandons the paper’s named result: Corollary 1 does not classify such measure-valued rules, nor does it provide a computational representation or algorithm for them. The remaining computational task—recognizing whether an explicitly given finite domain is semi-single-peaked or semi-hybrid—is a property of the preference-domain encoding, independent of \(\mu\). With tops-onlyness, the population itself compresses to peak masses over the finite alternative set.
The railway-resident story makes high multiplicity plausible, and I would not object that the voters lack repeated types. The failure is more fundamental: the paper studies axiomatic domain structure, while the continuum contributes no nontrivial computational object. A continuous extension could become an interesting new theory of population-level group-strategy-proof mechanisms, but that would be a new problem requiring new axioms and new results—not a worthwhile ChoCo mirror of this paper.
The negative case is therefore strong under the programme’s computational-anchor rule, though not literally airtight against every conceivable axiomatic extension.
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.