| paper | Complexity of Judgment Aggregation |
| authors | U. Endriss, Umberto Grandi, Daniele Porello |
| venue | JAIR 2012 |
| filed under | frontier · ja |
| 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 9
statement extracted from the paper’s text layer
Given an agenda \(\Phi\), explicitly represented complete consistent judgment types \(T\subseteq\mathcal J(\Phi)\), rational masses \(\mu_t\ge 0\) summing to \(1\), and \(L\subseteq\Phi\), does some \(K\in\mathcal J(\Phi)\) with \(L\subseteq K\) minimize \(D_\mu(K)=\sum_{t\in T}\mu_t H(K,t)\)?
A society is a rational distribution \(\mu\) over complete consistent judgment types. The decision variable is a discrete collective judgment set \(K\), and the objective is the mass-weighted Hamming disagreement \(D_\mu(K)\); agenda safety replaces the finite-profile universal quantifier by universal quantification over such \(\mu\).
Because Hamming distance is additive, \(D_μ\) depends only on formula marginals, so the mirror discards correlations among judgment types and resembles weighted logical optimization more than population-level optimization.
fatal: False
The mirror covers distance-based winner-determination hardness and majority-rule agenda-safety complexity; it leaves manipulation, quota and premise-based procedures, other distance rules, and most axiomatic characterizations untouched.
The strongest mirror is a high-multiplicity judgment-aggregation model in which the continuous object is the population profile, while judgments and collective outcomes remain discrete.
The natural type for this paper is a complete, consistent judgment set \(t\in\mathcal J(\Phi)\). A society is a distribution \(\mu\) over such types: \(\mu_t\) is the fraction of agents submitting judgment set \(t\). This is a plausible regime for large deployments of replicated software agents, standardized expert cohorts, or large panels whose members fall into a relatively small number of epistemic profiles. The relevant comparison is \(N\gg\tau\), where \(N\) is the number of agents and \(\tau\) the number of distinct judgment types. The paper’s own multiagent-systems motivation makes this scenario recognizable to its authors.
The continuous model is not changing the outcome space: a collective outcome is still a judgment set. It is only replacing the explicit profile \(J_1,\ldots,J_n\) by masses. If \(\mu_t=n_t/n\), then for every candidate collective judgment set \(K\),
\[ \sum_t\mu_t H(K,t)=\frac{1}{n}\sum_{i=1}^n H(K,J_i). \]
Thus the continuous objective is exactly the discrete one up to a constant factor. Rational continuous societies and finite profiles translate in both directions.
My lead anchor is Theorem 9. The paper proves here:
Theorem 9. \(\operatorname{WinDet}^{\star}(\mathrm{DBP})\) is \(\Theta_2^p\)-complete.
The underlying problem is: given an agenda \(\Phi\), a profile of complete and consistent judgment sets, and \(L\subseteq\Phi\), determine whether some judgment set \(J^\star\) minimizing
\[ \sum_i H(J^\star,J_i) \]
contains every formula in \(L\). The theorem is proved in this paper: Lemmas 6 and 7 establish membership, while Lemma 8 gives hardness through a reduction from the cited \(\Theta_2^p\)-hard Kemeny Winner problem.
The continuous problem I would hand to a prover is:
Continuous DBP Winner Determination. An instance consists of an agenda \(\Phi\), a finite explicitly represented set of judgment types \(T\subseteq\mathcal J(\Phi)\), rational masses \(\mu_t\ge 0\) summing to \(1\), and \(L\subseteq\Phi\). Define
\[ D_\mu(K)=\sum_{t\in T}\mu_t H(K,t). \]
Question: does there exist \(K\in\mathcal J(\Phi)\) such that \(L\subseteq K\) and
\[ D_\mu(K)=\min_{K'\in\mathcal J(\Phi)}D_\mu(K')? \]
A solution is either a yes/no answer or, constructively, an optimal collective judgment set \(K\) containing \(L\).
I expect this to be Class B: hardness transfers. Every discrete instance embeds by setting \(\mu_t=n_t/n\), and duplicating every member of a cohort any number of times leaves the continuous instance unchanged. In the natural rational encoding, I would expect the same \(\Theta_2^p\) boundary, although the precise upper-bound statement should specify how rational masses are encoded. The important point is that the hard combinatorics live in the agenda and logical consistency, not in the number of separately named voters. The continuous problem therefore exposes a legitimate high-multiplicity version without pretending that population continuity dissolves all hardness.
This mirror generates useful follow-up questions: is the problem fixed-parameter tractable in the number \(\tau\) of supported judgment types or in the number of propositional variables? Do sparse distributions admit approximation schemes? Which restricted agenda languages make the pricing/minimization problem tractable?
A second, independent anchor is Theorem 26(i), proved in this paper. The theorem states that deciding agenda safety is \(\Pi_2^p\)-complete for
\[ F_\Phi[\mathrm{WR},\mathrm{A},\mathrm{S},\mathrm{MI}], \]
the class consisting only of the majority rule. In full, the finite problem asks whether a given agenda \(\Phi\) guarantees a logically consistent collective judgment set for every profile of individually complete and consistent judgments. The paper obtains the result from its own safety characterization and the \(\Pi_2^p\)-hardness results for the median properties.
The continuous analogue is:
Continuous Majority Agenda Safety. Given an agenda \(\Phi\), let \(T=\mathcal J(\Phi)\). For every distribution \(\mu\) over \(T\), define the strict-majority collective set
\[ M_\mu=\left\{\varphi\in\Phi: \sum_{t:\varphi\in t}\mu_t>\frac12\right\}. \]
Question: is \(M_\mu\) logically consistent for every population distribution \(\mu\)?
Strict-majority ties produce neither member of a complementary pair; this is the natural continuous extension, and safety concerns consistency rather than completeness. The expected result is again Class B, in fact the same \(\Pi_2^p\)-completeness. Every odd finite profile gives a rational \(\mu\) with exactly the same majority outcome. Conversely, if a real-valued \(\mu\) produces an inconsistent majority set, all relevant strict-majority inequalities have positive margin and can be preserved by a rational approximation with an odd common denominator. Hence continuous safety is equivalent to the paper’s finite safety problem. The paper’s Theorem 11 gives the structural explanation: safety holds exactly when the agenda satisfies the median property.
This second mirror asks further questions about approximate safety, safety with a positive majority margin, and continuous versions of the systematic, neutral, and independent classes in Theorem 26(ii)–(iv).
I would not use Theorem 10 on manipulation as a primary anchor. A literal individual has vanishing mass in a continuum, so the nondegenerate analogue is manipulation by a positive-mass homogeneous bloc, which is a meaningful problem but not exactly the paper’s one-agent problem. That limitation is also the weakest point of the programme here: Theorem 9’s hard instances may contain many distinct judgment types, and Theorem 26 can look close to a restatement because safety already quantifies over all finite profiles. Nevertheless, both mirrors are genuine population continuizations, have exact finite-to-mass dictionaries, and are questions the paper’s authors should recognize as their own problems.
The strongest negative case is that both anchors are population encodings rather than genuinely population-dependent problems.
For Theorem 9, let
\[
\rho_\varphi=\sum_{t:\varphi\in t}\mu_t.
\]
Because Hamming distance is additive over formulas,
\[
D_\mu(K)=\sum_{\varphi\in\Phi^+}
\begin{cases}
1-\rho_\varphi,&\varphi\in K,\\
\rho_\varphi,&\varphi\notin K.
\end{cases}
\]
Thus the full distribution over judgment types is irrelevant: only the marginal support of each formula matters. Two societies with radically different correlations between judgments are computationally indistinguishable. The proposed “continuum” therefore introduces no mass transfer, fractional decision, or population-level optimisation; it replaces integer support counts by rational coefficients in an already discrete weighted logical optimisation problem. Since every rational instance is exactly a finite profile after denominator scaling, this is best understood as a compressed encoding of the paper’s existing anonymous input, not as a new continuous-social-choice object.
That objection is not decisive under ChoCo’s rules, however. High-multiplicity compression is expressly allowed, and the resulting weighted DBP problem is still a legitimate computational question. The authors would recognise it as their problem, and the Kemeny reduction supplies a real hardness anchor. One can also strengthen it by studying positive-mass bloc manipulation or robustness under mass perturbations. I therefore cannot honestly defeat Theorem 9 outright.
Theorem 26 is weaker as a population anchor. Agenda safety does not take a society as input at all; it asks whether every admissible profile produces a consistent outcome. Replacing finite profiles by distributions merely changes the domain of a universal quantifier. Every finite profile yields its empirical distribution, while any inconsistent majority outcome under a real distribution can be preserved by a rational approximation because only finitely many strict-majority inequalities matter. The \(\Pi_2^p\) computation remains a property of the agenda and propositional logic, not of a continuous society. Asking safety for a specified \(\mu\) would introduce a genuine population input, but it would no longer mirror the paper’s safety problem; asking for the minimum mass perturbation that creates inconsistency would be a new robustness problem rather than Theorem 26.
So the negative case is ultimately not strong enough. The safety anchor largely collapses into a profile-domain reformulation, but Theorem 9 survives the objection: a high-multiplicity, rational-mass DBP is well-defined, recognisably the authors’ problem, and computationally nontrivial. Under the programme’s stated standards, I would not defend the universal claim that this paper has no worthwhile continuous mirror.
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.