SAT-based Judgment Aggregation

The clean positive case is the Kemeny part of the paper. It is not a route to making Kemeny easy; it is a very natural continuous, high-multiplicity version whose hardness should survive for the right reason.

The anchor is Proposition 3.1, proved in this paper. For \(R=\) Kemeny (among other listed rules), it says that \(J\in R(P)\) iff an optimal solution of the constructed MaxSAT instance \(F_R(P)\) restricts to \(J\). The paper’s statement that Kemeny outcome determination is \(\Theta^p_2\)-complete is not given a theorem number here: it is explicitly presented as known and cited to Endriss et al. [32]. That is still useful context, but Proposition 3.1 is the numbered, in-paper result I would mirror.

Call the continuous problem Kemeny Judgment Aggregation\(_\infty\) Outcome Determination.

An instance consists of:

• an agenda \(X=\{x_1,\ldots,x_m\}\), input and output constraints \(\Gamma_{\rm in},\Gamma_{\rm out}\), and a required set \(L\) of agenda literals;
• a finite set of input judgment types \(T\subseteq J(\mathcal A,\Gamma_{\rm in})\);
• rational masses \(\mu_t\geq 0\), with \(\sum_{t\in T}\mu_t=1\).

Here a type is a complete, \(\Gamma_{\rm in}\)-consistent judgment set: every person of mass \(\mu_t\) endorses exactly the same positions on every issue relevant to the aggregation. For every feasible collective judgment set \(J\in J(\mathcal A,\Gamma_{\rm out})\), define its societal disagreement cost by

\[ D_\mu(J)=\sum_{t\in T}\mu_t H(J,t). \]

Equivalently, it maximizes total mass-weighted agreement,
\[ \sum_{\ell\in J}\sum_{t:\ell\in t}\mu_t. \]

The question is whether there is a \(J\) satisfying \(\Gamma_{\rm out}\) and \(L\subseteq J\) with minimum \(D_\mu(J)\) among all output-feasible collective judgments. A solution is such a judgment set \(J\); the optimization version returns one or all minimizers.

This is not merely “use weights.” It changes the represented society from a list of named people to a distribution over complete judgment types, and the objective from a total number of disagreements to the fraction of the society with which the collective judgment disagrees. The paper’s own Kemeny encoding already points directly at this formulation: its soft-clause weights are derived from support counts \(N(P,\ell)\). Replacing \(N(P,\ell)/n\) by mass support \(\sum_{t:\ell\in t}\mu_t\) preserves the authors’ objective exactly.

A plausible regime is a large recurring-membership or public-consultation setting: for example, a national professional association aggregates positions on a fixed policy agenda, and members select one of a relatively small number of internally coherent policy platforms. There may be millions of members but only dozens, hundreds, or a few thousand observed complete judgment types. The types are not “people with identical names”; they are the complete policy packages relevant to this decision. In such a setting, “42% support this coherent platform” is the natural input, while enumerating every member is artificial. The same applies to repeated large-scale citizen panels whose answers are clustered into recurring consistent judgment patterns.

The correct expected classification is Class B: hardness transfers. Given an ordinary discrete profile \(P\), group equal judgment sets and put \(\mu_t=\#_P(t)/|P|\). Multiplying \(D_\mu\) by \(|P|\) yields precisely the discrete Kemeny objective, with precisely the same set of minimizers. Thus the cited \(\Theta^p_2\)-hardness is not an artefact of having many voters: its combinatorics live in the logically constrained collective judgment and the agenda. This is exactly the informative boundary the continuization programme seeks.

That does not make the mirror uninteresting. In a high-multiplicity input, it can be exponentially shorter than an explicit voter list, and it puts the problem in the weighted MaxSAT/optimization language used by Proposition 3.1. It also creates sensible follow-up questions: which structural restrictions on \(\Gamma_{\rm out}\) yield polynomial algorithms in the number of supported types; whether bounded treewidth or compiled constraints permit efficient weighted outcome determination; and which approximation or preprocessing guarantees transfer back to a large finite electorate.

I would deliberately not anchor the case on Young or Dodgson as well. Their natural mass-removal and mass-editing analogues are promising, but strict-majority boundaries in a continuum require an explicit closure or \(\varepsilon\)-optimal convention. Kemeny has none of that technical ambiguity and is the paper’s strongest mirrorable result.

The weakest point is also plain: for rational masses induced by a discrete profile, Kemeny Judgment Aggregation\(_\infty\) has exactly the same winners as the normalized discrete problem. Someone demanding that a continuous mirror must dissolve hardness will find this disappointing. But that is the wrong standard for ChoCo: a faithful continuum can—and here should—be inherently hard. The continuous society is still the right object in the large-population regime, and the exact embedding gives unusually strong evidence that the authors would recognise it as their problem rather than a tractable surrogate.