| paper | A Graph-Based Algorithm for the Automated Justification of Collective Decisions |
| authors | — |
| venue | AAMAS 2022 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), ranking types \(T=L(C)\), a rational society \(\mu^\star\in\Delta(T)\), target outcome \(X^\star\subseteq C\), a finite corpus \(\mathcal A\) of scale-free lifted axiom schemas, and a certificate bound \(k\), compute whether there exists an inclusion-minimal explanation \(A_E\) with \(|A_E|\le k\) and normative basis \(A_N\) such that every anonymous rule \(F_\infty:\Delta(T)\to2^C\setminus\{\varnothing\}\) satisfying \(A_E\) yields \(F_\infty(\mu^\star)=X^\star\), \(A_E\) consists of instances from \(A_N\), and \(A_N\) is jointly satisfiable.
A high-multiplicity axiomatic-justification model with ranking types \(t\in T\), society mass \(\mu_t\), discrete winner sets, Boolean axiom constraints over rational mass profiles, and an inclusion-minimal explanation objective.
The all-real version lacks an effective finite representation, while the rational version may look like a normalized finite-profile formulation rather than a genuinely new computational model.
fatal: False
The mirror covers Theorem 1 and can extend to Propositions 2 and 3; it leaves the external \(\Sigma_2^p\)-hardness claim, empirical runtime results, and implementation heuristics largely untouched.
There is a defensible continuous mirror, although it is important to state exactly what the paper does and does not prove. The paper has no numbered NP-hardness, polynomial-time, or parameterized-complexity theorem. Its relevant numbered results are correctness results. The strongest anchor is therefore Theorem 1 (Correctness), proved in this paper: *Algorithm Justify is correct whenever its subroutine Solve is correct*. The \(\Sigma_2^p\)-hardness statement in Section 2.3 is cited from Boixel and de Haan [10], is not numbered here, and should not be presented as this paper’s theorem.
The natural mirror keeps alternatives and outcomes discrete while making the electorate continuous. Fix \(C\), let \(T=L(C)\) be the set of complete rankings, and let \(\tau=|T|=m!\). A society is a mass profile \(\mu\in\Delta(T)\), where \(\mu_t\) is the fraction of voters of ranking type \(t\). A continuous voting rule is a map
\[ F_\infty:\Delta(T)\longrightarrow 2^C\setminus\{\varnothing\}. \]
The action is not to choose fractional alternatives: it is to choose a normative basis and a finite explanatory certificate forcing the target outcome. The objective is exactly the paper’s objective: find \(\langle A_N,A_E\rangle\), with \(A_E\) inclusion-minimal, such that accepting the axioms in \(A_N\) forces \(F_\infty(\mu^\star)=X^\star\).
The six axioms in Section 2.1 have credible mass versions. Faithfulness applies to a society concentrated on one ranking. Pareto says that an alternative cannot win when every positive-mass type ranks another alternative above it. Neutrality acts by pushing \(\mu\) forward under a permutation of candidates. Cancellation applies when all pairwise majority margins are zero. Positive Responsiveness applies when positive mass is moved to rankings raising a current winner. Reinforcement becomes the scale-free condition that, whenever \(F_\infty(\mu)\cap F_\infty(\nu)\neq\varnothing\),
\[ F_\infty(\lambda\mu+(1-\lambda)\nu) = F_\infty(\mu)\cap F_\infty(\nu) \]
for \(0<\lambda<1\). Thus the mirror preserves the paper’s normative content; only integer profile addition is replaced by convex mixing of population masses.
I would name the resulting problem Continuous Axiomatic Justification.
An instance consists of \(m\), a rational mass profile \(\mu^\star\), a nonempty target set \(X^\star\subseteq C\), and a finite corpus \(\mathcal A\) of lifted axiom schemas. An axiom instance is a finite rational tuple of mass profiles together with the corresponding constraint on the Boolean variables \(p_{\mu,x}\), meaning \(x\in F_\infty(\mu)\). A solution is a pair \(\langle A_N,A_E\rangle\) satisfying:
A bounded version may additionally ask whether such a certificate exists with \(|A_E|\le k\). This is not a fractional-outcome problem: \(F_\infty(\mu)\) is still a discrete winner set.
The continuous instance graph has mass profiles as nodes and axiom instances as hyperedges. Starting from \(\mu^\star\), a graph-search algorithm generates instances at increasing distance and invokes a MUS-style solver on the generated constraints. For a finite rational encoding bound, this is literally the paper’s finite graph algorithm. For the unrestricted rational version, the instance set is countable and can be dovetailed by encoding length; every finite certificate is eventually generated. The direct mirror of Theorem 1 is then:
Continuous Justify Correctness. If the continuous solving subroutine is sound and complete, the graph-search procedure returns only valid continuous justifications, and eventually returns one whenever a continuous justification exists.
This is a genuine computational mirror of the paper’s main theorem. It is not merely “voting with probabilities”: it preserves the unknown voting rule, the axiom corpus, the MUS-style explanation, the relevance and nontriviality conditions, and the graph structure over profiles.
The most plausible regime is a national or platform-wide consultation over a small menu of policies. Suppose millions of citizens rank four standardized alternatives. There are at most \(24\) preference types, and the relevant information is exactly each citizen’s complete ranking; identities do not matter because the paper explicitly assumes anonymous elections. A profile such as \(n_t\) citizens of type \(t\) becomes \(\mu_t=n_t/n\). Conversely, every rational \(\mu\) can be expanded into a finite electorate by clearing denominators. This is precisely the high-multiplicity bridge, not an objection about losing individualized prices or identities: the paper’s model contains no such individual attributes.
I would expect the bounded rational-certificate version to be Class B: hardness transfers, rather than Class A. The population multiplicity is not where the difficult combinatorics primarily live. The hard part is selecting a minimally sufficient set of axiom constraints and reasoning over possible voting rules, which survives after duplicate voters are compressed into mass. Denominator clearing gives a direct finite-electorate interpretation of every rational mass profile. The full real-domain version may additionally become Class C if universal quantification over all \(\mu\in\Delta(T)\) requires genuinely new real-algebraic reasoning, but that is a further question, not something claimed by the paper.
Propositions 2 and 3 strengthen the mirror but need not be separate anchors. Proposition 2, proved here, says that omitting implied instances preserves correctness; its mass version says redundant constraints between distributions may likewise be removed. Proposition 3, also proved here, says that derived-axiom heuristics followed by expansion back to the original axioms preserve correctness for nontrivial corpora. These are natural continuization questions about compressed explanations and axiom compilation.
The weakest point is that the paper fixes a finite electorate bound and permits voting rules whose behaviour may depend on total population size, whereas the mirror identifies profiles with normalized mass distributions. A referee could therefore say that scale invariance is an added assumption. The response is that this is the intended high-multiplicity regime, but it must be stated and studied explicitly; one should also prove when rational continuous certificates suffice for the all-real model. The paper does not establish polynomial running time for this mirror, nor does it establish a Class A result. What it does provide is a well-motivated, nontrivial continuous population problem whose central correctness theorem survives and whose likely hardness boundary is itself informative.
The proponent’s strongest anchor, Theorem 1, does not provide the continuous computational result claimed for it. Its proof is entirely domain-agnostic: it assumes a sound and complete Solve, a graph whose edges are finite axiom instances, and the fact that a finite inconsistent constraint set has an inconsistent connected component. Nothing depends on voters, multiplicities, or even voting. Replacing integer profiles by distributions therefore leaves the theorem unchanged in substance.
The proposed mirror splits into three cases, none of which supplies the claimed payoff. If one fixes a finite rational encoding bound, the mass-profile space is finite. Clearing denominators turns every mass profile into an ordinary anonymous profile with a suitably chosen number of voters, so the algorithm is merely the original finite-profile algorithm under a change of coordinates. If one allows all rational distributions, the graph is countable and can be dovetailed, but “eventually finds a certificate” is only a semidecision statement, not a complexity result. If one means the genuine space \( \Delta(T) \) of real distributions, countable dovetailing is no longer complete: the algorithm does not enumerate irrational profiles, and the paper proves no rational-certificate or finite-description theorem that would justify restricting attention to them. The proposed mirror silently changes the real problem into a rational one.
There is also no continuous object doing computational work here. The unknown voting rule is an arbitrary map \(F_\infty:\Delta(T)\to 2^C\setminus\{\varnothing\}\), and the algorithm reasons about Boolean constraints \(p_{\mu,c}\) indexed by profiles. The population distribution is merely an index for constraints; there is no mass-transfer variable, aggregate objective, convex feasible region, or finite-dimensional parametrisation of \(F_\infty\). To make the real-domain problem effective, one would need to impose additional regularity or symbolic structure on the rule and on the axiom schemas. That would be a new theory of continuous rule representations, not a continuization of this algorithm.
Proposition 2 does not rescue the case. Preservation under deletion of implied instances is a purely logical fact about constraint sets. On a finite rational profile space it carries over verbatim and adds no continuous content. On the full distribution simplex, determining whether one parametrised or real-valued instance is implied by others is precisely part of the missing representation and decision theory.
The same problem is sharper for Proposition 3. In the paper’s finite universe, a derived axiom can be expanded into the finitely many original instances that imply it. Over \( \Delta(T) \), a derived instance may be justified only by an infinite family of constraints. Then the proposed postprocessing need not produce a finite explanation at all. If one restricts derived axioms to those having an explicitly finite derivation, Proposition 3 survives, but only as another generic syntactic lemma independent of continuization.
The paper’s anonymity does defeat the obvious multiplicity objection. A national consultation with a small menu of policies is a perfectly sensible high-multiplicity interpretation, and normalising its ballot counts to \( \mu_t \) is legitimate. But that establishes only that the mass-profile formulation is admissible; it does not establish that this paper contributes a worthwhile continuous computational problem. Its central computation is already about anonymous histograms and axiom-instance logic, not about a population whose continuity enables new optimisation machinery.
The honest negative case is therefore not an airtight universal impossibility claim. A new paper could define scale-free axioms, choose a finite symbolic language for regions of \( \Delta(T) \), and prove a rational or semialgebraic finite-certificate theorem. That might be worthwhile, but it would be substantial new foundational work. The present paper supplies no such result. Its alleged continuous mirror is either a high-multiplicity restatement of the finite problem or an under-specified real-domain constraint problem, so I would not count this paper as a convincing ChoCo 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.