Declarative Approaches to Outcome Determination in Judgment Aggregation

The strongest case is a high-multiplicity mirror of the paper’s Kemeny outcome-determination problem. I would make this the lead case.

The relevant anchor is Proposition 2.1. It is cited from Endriss et al. (2020), rather than proved in this paper. In full, it states that outcome determination is \(\Theta^P_2\)-complete for Kemeny, Slater, MaxHamming, Young, Dodgson, and reversal scoring; \(\Delta^P_2\)-complete for LexiMax; and \(\Sigma^P_2\)-complete for Condorcet and ranked agenda. I use its Kemeny entry.

The natural regime is a large consultation, electorate, or distributed expert population deciding a fixed finite agenda of logically related propositions. A type is a complete \(\Gamma_{\mathrm{in}}\)-consistent judgment set \(t\): two people have the same type when they submit exactly the same judgments over the agenda. Millions of respondents may be represented by only a few hundred or thousand recurring stakeholder, party, organizational, or policy-position types. The mass \(\mu_t\) is the fraction of the population of type \(t\), not a probability about an individual draw.

This is not outcome-space continuity. Every unit of mass still holds a complete integral judgment set, and the collective judgment remains a complete \(\Gamma_{\mathrm{out}}\)-consistent judgment set. Only the population becomes continuous.

I would state the mirror as follows.

Continuous Kemeny Outcome Determination. An instance consists of an agenda \(\Phi\), input and output constraints \(\Gamma_{\mathrm{in}}\) and \(\Gamma_{\mathrm{out}}\), a finite support of voter types \(T=\{t_1,\ldots,t_\tau\}\subseteq\mathcal J(\Phi,\Gamma_{\mathrm{in}})\), rational masses \(\mu_i\ge 0\) with \(\sum_i\mu_i=1\), and a set of required literals \(L\subseteq\Phi\).

For every output judgment \(J\in\mathcal J(\Phi,\Gamma_{\mathrm{out}})\), define its population-average Hamming distance by

\[ D_\mu(J)=\sum_{i=1}^{\tau}\mu_i H(J,t_i). \]

The task is to decide whether there exists a Kemeny-optimal output

\[ J^\star\in\operatorname*{arg\,min}_{J\in\mathcal J(\Phi,\Gamma_{\mathrm{out}})}D_\mu(J) \]

such that \(L\subseteq J^\star\), and, if so, return such a \(J^\star\).

Because the judgments are complete, this is equivalently the problem of maximizing

\[ \sum_{\ell\in J}p_\mu(\ell), \qquad p_\mu(\ell)=\sum_{i:\ell\in t_i}\mu_i. \]

That is exactly the paper’s Kemeny objective after replacing the finite support counts \(N(P,\ell)\) by normalized population masses.

The paper’s authors should recognize this as their problem rather than as a weakened surrogate. Definition 2.5 defines Kemeny by minimizing total Hamming distance from the individual judgment sets, while the paper’s MaxSAT and integer-programming formulations use only aggregate support counts. Given a finite profile \(P\) with \(n\) agents, set

\[ \mu_t=\frac{N(P,t)}{n}. \]

Then

\[ D_\mu(J)=\frac{1}{n}\sum_{J_i\in P}H(J,J_i), \]

so the set of Kemeny-optimal collective judgments, and hence the outcome-determination answer, is unchanged. This is precisely the high-multiplicity relaxation: the individual list disappears, but its type histogram remains.

I expect this mirror to be Class B: hardness transfers rather than dissolves. The discrete Kemeny problem embeds directly by the normalization above, so the continuous problem is at least \(\Theta^P_2\)-hard under the natural explicit rational encoding. Continuization compresses repeated population types, but it does not remove the combinatorics of selecting a \(\Gamma_{\mathrm{out}}\)-consistent collective judgment. In the preference-aggregation special case, that remaining difficulty is the familiar difficulty of selecting an optimal ranking over the alternatives. The population has become continuous; the agenda and collective judgment have not.

That negative computational prediction is still a useful continuous-computational result. It would separate hardness caused by population multiplicity from hardness caused by the agenda or output space. It also leaves meaningful questions: how does complexity depend jointly on the number of types \(\tau\), the number of issues, and the encoding length of \(\mu\)? Which constraint languages \(\Gamma_{\mathrm{out}}\) admit column-generation, approximation, or parameterized algorithms? Can the compressed distribution support fast sensitivity analysis when a small amount of mass moves between types?

The case is narrower than a mirror of the whole paper. It covers the underlying Kemeny outcome-determination problem, not the SAT encoding, solver engineering, or benchmark methodology. Proposition 4.2 supports the reading: the paper proves that its Kemeny and Slater MaxSAT optima correspond exactly to the intended collective judgments, but the continuous question should concern the underlying weighted Kemeny problem, not “continuous MaxSAT.”

My weakest point is that this mirror may provide compression without tractability. In fact, the expected outcome is that Kemeny’s hardness survives. An opposing analyst can therefore say that the proposal merely rewrites a finite weighted profile as a distribution. My answer is that this is exactly the programme’s high-multiplicity notion of continuization, and Class B is an intended outcome: a continuous population can be a legitimate mirror even when the mirror proves that continuity does not help.