| paper | Voting by Axioms (Extended Abstract) |
| authors | Marie Christin Schmidtlein, Ulle Endriss |
| venue | IJCAI 2024 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), ranking-type set \(T\), rational distribution \(\mu\in\Delta(T)\), and finite propositional encoding \(\varphi_A\) of a nontrivial axiom set over variables \(p_{\nu,c}\), decide whether every anonymous population-domain voting rule \(F_\infty:\Delta(T)\to 2^C\setminus\{\varnothing\}\) satisfying \(\varphi_A\) returns the same nonempty outcome \(O\) on \(\mu\); output \(O\) if forced and otherwise report that no outcome is forced.
Anonymous, replication-invariant voting rules over \(\Delta(T)\), with complete rankings as types, population mass \(\mu\) as the society, \(\varphi_A\) as the normative input, and universal forcing of an exact outcome \(O\) as the computational task.
Theorem 1 does not automatically descend to anonymous homogeneous rules on Δ(T), and a finite propositional encoding over named distributions may leave the continuous population structure computationally inert.
fatal: False
The mirror covers the forcing-complexity result in Theorem 1; it leaves Theorems 2 and 3 aside because they are semantic and axiomatic rather than computational complexity results.
The strongest honest case is a narrow one: the paper has one clear computational anchor, and it yields a genuine continuous-population mirror, but probably a Class B mirror rather than a tractability result.
My lead anchor is Theorem 1, proved by Schmidtlein and Endriss in the full paper rather than cited from elsewhere:
“The problem of deciding whether a given non-trivial axiom set \(A\) forces an outcome for a given profile \(R\) is coNP-complete in the combined size of \(A\).”
Consider a large public consultation or referendum over a fixed small set \(C\) of policy alternatives. Each participant reports a complete ranking of \(C\). A type is therefore a ranking \(t\in T\), with \(T\) containing at most \(m!\) types. The society is a distribution \(\mu\in\Delta(T)\), where \(\mu_t\) is the fraction of participants with ranking \(t\). For four alternatives, there are at most \(24\) ranking types, even if the electorate contains millions of people.
The normative input is a finite axiom set \(A\), representing the institution’s accepted principles for collective decision making. A population-domain voting rule is a function \(F_\infty:\Delta(T)\to 2^C\setminus\{\varnothing\}\). Its output remains an ordinary nonempty set of winning alternatives; only the society is continuous. There is no fractional or probabilistic outcome.
To retain the paper’s encoding, use variables \(p_{\nu,c}\), where \(\nu\) is a named rational distribution over \(T\) and \(p_{\nu,c}\) means \(c\in F_\infty(\nu)\). An axiom set is given by a finite propositional encoding \(\varphi_A\) over such variables, with nontriviality meaning that at least one well-formed population-domain voting rule satisfies it.
The continuous problem is:
\(\mathrm{Continuous\text{-}Force}_\infty\): given \(C\), \(T\), a rational population distribution \(\mu\), and a nontrivial encoded axiom set \(A\), decide whether there exists a nonempty \(O\subseteq C\) such that every population-domain voting rule satisfying \(A\) returns exactly \(O\) on \(\mu\). If so, output \(O\); otherwise report that \(A\) does not force an outcome on \(\mu\).
This is directly the paper’s question with \(R\) replaced by a distribution over voter types. The decision variable is the forced outcome \(O\), and the objective is exact normative determination: does the axiom set uniquely justify a decision for this society?
The high-multiplicity regime is plausible in settings such as constitutional referenda, large-scale participatory budgeting, or public consultations on a small menu of policies. The individuals need not be identical in every real-world respect; they need only be indistinguishable for the formal problem. If institutional role or eligibility matters, it can be included in the type. The important regime is millions of participants and a fixed, small number of complete preference types.
The bridge is exact for anonymous profiles. A discrete profile \(R\) with \(n_t\) voters of type \(t\) maps to \(\mu_t=n_t/n\). Conversely, every rational \(\mu\) has a common denominator and therefore corresponds to a discrete high-multiplicity profile. The continuous input compresses repeated ballots into their type masses. This is precisely the population continuization, not continuity of outcomes or a noise model.
I would expect this problem to be Class B, probably coNP-complete under the same finite encoding, although the exact transfer should be proved rather than asserted. The hardness in Theorem 1 appears to live in the Boolean space of admissible voting rules and axiom encodings, not in the number of individually named voters. Replacing a discrete profile by its rational type-frequency vector should therefore preserve the reduction. The theorem’s cited comparison with the \(\Sigma_2^p\)-hard justification problem is not an additional anchor; only Theorem 1 is being mirrored here.
The main technical obligation is anonymity. If the original theorem exploits named agents or non-anonymous rules, the mirror must either restrict attention to the anonymous specialization or add only finitely many role attributes to the voter type. It should not add unique identities, since that would destroy the high-multiplicity regime.
The authors should recognize this as their problem rather than a simplified scoring-rule substitute. The mirror keeps their central objects intact: complete rankings, arbitrary axiom sets, the quantification over all admissible voting rules, exact nonempty outcome sets, and the possibility that no outcome is forced. The only changed object is the population representation. The paper’s explicit mention of ANONYMITY also makes aggregation by type a natural formal quotient.
I would stop at this anchor. Theorem 2 and Theorem 3 are genuine results of the paper, proved in the full version, but they are semantic results about intraprofile axioms and induced voting rules rather than computational complexity results. Treating their extension from finite profiles to \(\Delta(T)\) as a separate selling point would drift toward the axiomatic continuization that the programme excludes.
The weak point is substantial: the paper motivates voting by axioms primarily for fairly small, high-stakes groups, whereas the proposed regime is a large electorate. Also, Theorem 1’s hardness is driven by the axiom representation, so this mirror does not demonstrate that population multiplicity itself creates a new tractability phenomenon. The continuous society may function mainly as a compressed representation of an anonymous discrete profile. I think that still qualifies as a valid Class B mirror, but it is not yet a flagship example of continuization unlocking LP or convex-optimization machinery.
The natural follow-up questions are whether coNP-completeness survives when \(A\) is restricted to standard axioms such as PARETO, CONDORCET, and ANONYMITY; how ranked forcing behaves computationally for a corpus \(\langle\mathcal A,\succ\rangle\); whether exact forcing is stable under small \(\ell_1\)-perturbations of \(\mu\); and whether adding natural regularity conditions on population-domain voting rules changes the complexity.
The negative case turns entirely on Theorem 1, and the proposed mirror does not yet establish a genuine continuization of that theorem.
Theorem 1 is not really a complexity result about populations. Its input is an explicitly encoded propositional theory over variables \(p_{R,x}\), where \(R\) is a named profile. The \(\mathrm{coNP}\) quantifier comes from asking whether there exists a voting rule, viewed as a Boolean assignment, that satisfies the formula while producing another outcome at \(R\). The number of voters, their multiplicities, and their type frequencies play no essential role. The hardness can already occur at one fixed profile and one fixed population distribution.
There is also no faithful quotient from the paper’s model to \(\Delta(T)\) for the theorem as stated. The map
\[ R\longmapsto \mu_R \]
is sufficient only if every admissible rule treats profiles with the same type frequencies identically. The paper does not impose that. Its rules may distinguish named agents, electorate size, or two profiles having the same normalized frequencies but different multiplicities. Anonymity alone is insufficient: one also needs replication invariance or homogeneity. Imposing those conditions changes the quantified class of voting rules and therefore changes the forcing problem. The rational-profile correspondence establishes a correspondence between inputs, not between the models quantified over in Theorem 1.
The proposed repair—restricting to anonymous population-domain rules \(F_\infty:\Delta(T)\to 2^C\setminus\{\varnothing\}\)—is a legitimate new model, but it no longer inherits Theorem 1 automatically. The reduction would have to survive the quotient that identifies all profiles with the same distribution. The paper gives no such result. Adding identity or electorate-size attributes to the type space would preserve more of the original semantics only by making the type space grow with the instance, which defeats the intended fixed finite high-multiplicity regime.
A more serious problem concerns the axiom encoding. If \(\varphi_A\) is a finite propositional formula over variables \(p_{\nu,c}\), it can mention only finitely many distributions \(\nu\). Then \(\mathrm{Continuous\text{-}Force}_\infty\) is merely propositional entailment with \(\mu\) used as the name of one variable. The geometry of \(\Delta(T)\), rational masses, and high multiplicity disappear entirely. The same \(\mathrm{coNP}\)-hard instance can be run with \(\mu\) fixed in advance.
If instead \(A\) is intended to mean a genuine axiom such as PARETO, CONDORCET, or REINFORCEMENT over every distribution in \(\Delta(T)\), the finite propositional encoding no longer works. There are infinitely many rational distributions, and reinforcement relates continuously many mixtures such as
\[ F_\infty(\lambda\mu+(1-\lambda)\nu) \]
to \(F_\infty(\mu)\) and \(F_\infty(\nu)\). One then needs a new compact language for quantified constraints over the simplex, together with a new complexity measure and new model-existence arguments. That could be worthwhile research, but it is not the continuous version of the paper’s Theorem 1; it is a new computational theory of anonymous population-domain axioms.
Thus the proponent’s “exact bridge” is weaker than claimed. Every rational \(\mu\) corresponds to a repeated discrete profile, but the original forcing problem does not descend to that quotient without additional assumptions. With a finite local encoding, the mirror is a syntax-level tautology problem whose population is decorative. With a genuinely semantic continuum of distributions, the paper supplies neither the representation nor the complexity result.
The large-referendum scenario is plausible, so there is no honest identity or multiplicity impossibility here. If one is willing to develop the missing anonymous, homogeneous axiom language, a valid new project may exist. But that concession also identifies the limit of the negative case: I cannot defensibly claim that no worthwhile mirror could ever be designed. I would reject the proposed mirror as an established anchor, however. Theorem 1 by itself does not show that this paper contributes a meaningful continuous-population problem; it shows only that arbitrary encoded constraints on rule outputs are computationally hard.
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.