| paper | The Complexity Landscape of Outcome Determination in Judgment Aggregation |
| authors | Ulrich Endriss, Ronald de Haan, J. Lang, M. Slavkovik |
| venue | JAIR 2020 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.14
statement extracted from the paper’s text layer
Input a finite literal agenda \(\Phi\), a rational constraint \(\Gamma\) with \(\Gamma_{\mathrm{in}}=\Gamma_{\mathrm{out}}=\Gamma\), and a finite-support rational distribution \(\mu\) over complete \(\Gamma\)-consistent judgment types. Decide, for \(\varphi^\star\in\Phi\), whether some \(K\in\arg\min_{K'}\sum_t\mu_tG(K',t)\)\) contains \(\varphi^\star\)\.
Types are complete \(\Gamma\)-consistent judgment sets, \(\mu_t\) is population mass, \(K\) is a complete collective judgment, and the objective is expected geodesic distance \(\sum_t\mu_tG(K,t)\), followed by a credulous formula-membership query.
The mirror covers the AvgGeo and Kemeny outcome-determination hardness results, together with their stated completeness context; it leaves the other aggregation rules and framework-specific results untreated.
The strongest positive case is a direct Class B mirror: the paper’s judgment-aggregation problems become aggregation over a rational distribution of judgment types. The hardness does not dissolve, because the reductions place their combinatorics in the agenda and integrity constraints rather than in the number of agents.
My lead is AvgGeo\(_\infty\)-Outcome, mirroring the paper’s AvgGeo rule.
Let \(\mathcal J_{\mathrm{in}}\) be the set of complete judgment sets consistent with \(\Gamma_{\mathrm{in}}\), and let \(\mathcal J_{\mathrm{out}}\) be the corresponding set for \(\Gamma_{\mathrm{out}}\). A type is one complete individual judgment set \(t\in\mathcal J_{\mathrm{in}}\). A society is a finite-support rational distribution \(\mu\) over these types, where \(\mu_t\) is the fraction of agents of type \(t\). The geodesic distance \(G\) is exactly the paper’s distance on the graph of complete \(\Gamma_{\mathrm{out}}\)-consistent judgment sets.
The continuous problem is:
\[ \operatorname{AvgGeo}_\infty(\mu) = \arg\min_{K\in\mathcal J_{\mathrm{out}}} \sum_{t\in\operatorname{supp}(\mu)}\mu_t\,G(K,t). \]
Given \(\Phi,\Gamma_{\mathrm{in}},\Gamma_{\mathrm{out}},\mu\), and \(\varphi^\star\in\Phi\), ask whether there exists \(K\in\operatorname{AvgGeo}_\infty(\mu)\) with \(\varphi^\star\in K\). A yes-certificate is such a minimizing collective judgment set \(K\).
This is a genuine population mirror. The outcomes remain discrete complete judgments; only the society is continuous. There is no lottery over outcomes, continuous proposition values, time variable, or noise model.
The population regime is a large consultation or diagnostic population facing a fixed logical agenda. Millions of participants may fall into a small number of information or training profiles, and everyone in one profile submits the same complete consistent judgment set. Thus \(N\gg |\operatorname{supp}(\mu)|\), with mass representing population share. This is precisely the high-multiplicity regime: a type is a complete description of everything the rule uses.
The anchor is Theorem 4.14, proved in this paper. It states that outcome determination for AvgGeo is \(\Theta_3^p\)-hard, already for framework variant (1)—literal agendas with \(\Gamma_{\mathrm{in}}=\Gamma_{\mathrm{out}}\)—and the restricted credulous query asking whether some outcome contains a specified formula. The reduction is from the paper’s \(\mathrm{QSat}_2\)-Min-Model\(^{\prime}\) problem: among existential assignments satisfying the quantified formula on all normal universal assignments, determine whether a minimum-weight assignment sets \(x^\star\) to true. The construction uses a three-judgment profile and makes AvgGeo outcomes correspond to those minimum-weight assignments. The companion Theorem 4.11 gives membership in \(\Theta_3^p\), so the paper establishes completeness.
Hardness transfers exactly. Given a finite profile \((t_1,\ldots,t_n)\), set \(\mu_t=\#\{i:t_i=t\}/n\). Then, for every candidate collective judgment \(K\),
\[ \sum_t\mu_tG(K,t) = \frac{1}{n}\sum_{i=1}^{n}G(K,t_i). \]
Therefore the minimizing outcomes and the credulous query are unchanged. In particular, the three-type profile used in Theorem 4.14 becomes a society with masses \(1/3,1/3,1/3\), and arbitrarily many cloned agents can realize exactly the same society. The expected classification is therefore Class B: hardness survives because it lives in the agenda and constraints.
A second, independently credible anchor is Theorem 4.6, also proved here. It states that outcome determination for the Kemeny rule is \(\Theta_2^p\)-hard, again for framework variant (1) and the restricted credulous query. Its reduction is from \(\mathrm{Max\text{-}Model}\), using the same construction as the Slater hardness proof; in that construction every issue receives the same amount of support, so Kemeny and Slater coincide. Together with Theorem 4.5, which proves \(\Theta_2^p\)-membership, this gives completeness.
The corresponding continuous problem is Kemeny\(_\infty\)-Outcome:
\[ \operatorname{Kem}_\infty(\mu) = \arg\min_{K\in\mathcal J_{\mathrm{out}}} \sum_{t\in\operatorname{supp}(\mu)}\mu_t\,H(K,t), \]
where \(H\) is the paper’s Hamming distance between complete judgment sets. Given a rational society and \(\varphi^\star\), ask whether some minimizing \(K\) contains \(\varphi^\star\). Again, finite profiles embed exactly through empirical masses, since the continuous objective is the finite Kemeny objective divided by \(n\). This is another Class B mirror, with expected \(\Theta_2^p\)-hardness.
These mirrors are plausible because they are literal population versions of the authors’ definitions: their rules already minimize sums of distances over individual judgment sets. Replacing the empirical sum by an expectation over type mass is exactly what one would write for a high-multiplicity society. Existing finite profiles are not a novelty collision, since the paper never makes the population itself a distributional input.
The weakest point is also clear: mass is a coefficient here, not an optimization variable. These mirrors do not produce a new LP, pricing problem, or continuum-specific tractability gain; for rational empirical masses, they are weighted high-multiplicity restatements. Their value is instead diagnostic: they show that continuization can be mathematically faithful while preserving very high complexity. The main follow-up questions are whether binary-encoded rational weights change the precise upper complexity, which agenda parameters yield fixed-parameter tractability, and whether more active mirrors—such as continuous mass deletion for Young or Dodgson aggregation—retain hardness or admit genuine fractional relaxations.
The strongest negative case is that both proposed anchors are mathematically valid but contributionally empty: they do not create a new population-continuous computational object.
For either rule, let \(\mu_t=a_t/D\) be rational. Replacing each type \(t\) by \(a_t\) cloned agents gives, for every collective judgment \(K\),
\[ \sum_t \mu_t G(K,t) = \frac{1}{D}\sum_{i=1}^{D}G(K,J_i) \]
and likewise
\[ \sum_t \mu_t H(K,t) = \frac{1}{D}\sum_{i=1}^{D}H(K,J_i). \]
Thus the minimizing outcomes are exactly the paper’s outcomes. This is not a discrete-to-continuous theorem to be discovered; it follows immediately from the definitions. The paper already permits arbitrary profiles, already treats repeated judgment sets anonymously, and already bases the rules on additive sums. The proposed “continuum” is merely the empirical frequency vector of the existing profile, with a common normalization.
This is especially damaging for the AvgGeo anchor. Theorem 4.14’s hardness construction uses only three individual judgments. Its proposed society is simply the fixed distribution \((1/3,1/3,1/3)\), regardless of the size of the agenda or the quantified formula. Cloning those three types produces an arbitrarily large population, but nothing in the computation depends on population multiplicity. The continuous population is decorative: the theorem is already hard before any population-continuous phenomenon appears.
The Kemeny anchor is weaker still. Its objective depends only on per-issue marginals. If
\[ p_\varphi=\sum_{t:\,\varphi\in t}\mu_t, \]
then choosing \(\varphi\) contributes cost \(1-p_\varphi\), while choosing \(\neg\varphi\) contributes cost \(p_\varphi\). Hence
\[ \sum_t\mu_t H(K,t) \]
is completely determined by the marginal support of each agenda issue; correlations between judgment types disappear. The alleged society is therefore reduced to weighted constraint optimisation over the agenda, not an analysis of a population distribution.
A stronger proposal could make mass an intervention variable: for example, ask for the minimum \(L_1\)-change to \(\mu\) that makes a target judgment Kemeny- or AvgGeo-optimal. That could be a worthwhile new control or robustness problem. But it is not a mirror of Theorems 4.6 or 4.14. It adds a new intervention model, a cost metric, and feasibility assumptions that the paper does not supply. Using Hamming or geodesic distance as conversion costs would be a further modelling choice, not a consequence of the paper’s results.
I would not claim that these mirrors are ill-posed, nor that their hardness is somehow disqualifying. The paper does contain genuine computational anchors, and large populations sharing judgment types are plausible. The honest negative conclusion is narrower: the direct AvgGeo\(_\infty\) and Kemeny\(_\infty\) formulations are exact high-multiplicity encodings of the paper’s existing anonymous profiles, with no new population-sensitive operation or structural phenomenon. If ChoCo counts such faithful Class B reformulations as worthwhile in their own right, the proponent’s case survives—particularly for AvgGeo. The universal negative case is therefore weak, and should not be presented as decisive.
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.