Complexity of Judgment Aggregation (d4-journals-jair-2012-0013)

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)\)?

An agenda \(\Phi\) is a finite nonempty set of propositional formulas, closed under syntactic complementation and containing no doubly negated formulas; tautologies and contradictions are allowed. Let \(\mathcal J(\Phi)\) be its complete, logically consistent judgment sets. Write \(\Phi^+\) for the formulas in \(\Phi\) without an outer negation, and let \(H(J,J')=\sum_{\varphi\in\Phi^+}|\mathbf 1_{\varphi\in J}-\mathbf 1_{\varphi\in J'}|\).
Given explicitly listed types \(T\subseteq\mathcal J(\Phi)\), binary-encoded rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\), and \(L\subseteq\Phi\), ask whether some \(K\in\mathcal J(\Phi)\) containing \(L\) minimizes \(D_\mu(K)=\sum_{t\in T}\mu_tH(K,t)\) over all \(\mathcal J(\Phi)\).

Is this rational-mass winner determination problem in \(P\), or is it \(NP\)-hard?

For a finite list of agents with equal weight, the corresponding winner determination problem is \(\Theta_2^p\)-complete. No separate complexity result for the exact rational-mass formulation was verified.

Proven result

The rational-mass winner determination problem is NP-hard, even with exactly two types, both of mass \(1/2\), and an agenda containing only three complementary pairs.

We prove this by a polynomial-time many-one reduction from \(3\)-SAT. The proof does not require the stated complexity result for equal-weight agents.

Construction

Let \(F\) be a \(3\)-CNF formula. Choose fresh propositional variables \(p,q\) not occurring in \(F\), and define \(g=p\lor(q\land F)\).

Construct the agenda
\[ \Phi=\{p,\neg p,q,\neg q,g,\neg g\}. \]
Here and below, the displayed expression is equivalently \( \Phi=\{p,\neg p,q,\neg q,g,\neg g\} \).

This agenda is finite, nonempty, and closed under syntactic complementation. Its three formulas without outer negation are \(p,q,g\), and none of its formulas is doubly negated.

Take the two types \(t_+=\{p,q,g\}\) and \(t_-=\{\neg p,\neg q,\neg g\}\), with masses \(\mu_{t_+}=\mu_{t_-}=1/2\). Both are complete and logically consistent:

• Setting \(p=q=\mathrm{true}\) satisfies every formula in \(t_+\), regardless of the values of the variables in \(F\).
• Setting \(p=q=\mathrm{false}\) makes \(g\) false and thus satisfies every formula in \(t_-\), again regardless of \(F\).

Finally, set \(L=\{\neg p,q,g\}\).

The construction has size linear in the size of \(F\), and the rational masses have constant-size binary encodings.

Every consistent judgment set minimizes the objective

Let \(K\in\mathcal J(\Phi)\). For each \(\varphi\in\Phi^+=\{p,q,g\}\), write \(b_\varphi=\mathbf 1_{\varphi\in K}\). The two types take opposite positions on every such formula. Consequently, that formula contributes

\( \frac12|b_\varphi-1|+\frac12|b_\varphi-0|=\frac12 \)

to \(D_\mu(K)\), because \(b_\varphi\in\{0,1\}\).

Summing over the three formulas gives \(D_\mu(K)=3/2\). Thus every member of \(\mathcal J(\Phi)\) is a global minimizer.

Correctness of the reduction

Suppose first that \(F\) is satisfiable. Extend a satisfying valuation by setting \(p=\mathrm{false}\) and \(q=\mathrm{true}\). Then \(g=p\lor(q\land F)\) is true. The judgment set induced by this valuation is complete, logically consistent, and contains \(L\). By the preceding calculation, it minimizes \(D_\mu\).

Conversely, suppose some minimizing \(K\in\mathcal J(\Phi)\) contains \(L\). Logical consistency supplies a valuation satisfying every formula in \(K\), hence satisfying \(\neg p,q,g\). Under \(p=\mathrm{false}\) and \(q=\mathrm{true}\), the formula \(g=p\lor(q\land F)\) has exactly the truth value of \(F\). Therefore that valuation satisfies \(F\).

We have proved that \(F\) is satisfiable if and only if the constructed winner determination instance has answer yes. This establishes NP-hardness. In particular, a polynomial-time algorithm for the rational-mass problem would imply \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the task: the rational-mass winner determination problem is NP-hard, even under the stated restrictions. No mathematical gaps or false steps were found.

• Reduction source and construction. The proof uses the standard NP-hard decision problem \(3\)-SAT. For any input formula \(F\), fresh variables \(p,q\) can be chosen, and \(g=p\lor(q\land F)\) can be constructed in polynomial time. Here \(g\) denotes the displayed formula, not an additional independent variable.

• Agenda validity. The formulas \(p,q,g\) are syntactically distinct, have no outer negation, and yield exactly three complementary pairs. Their complements introduce no double outer negation. Thus the constructed agenda satisfies the task’s requirements. The syntactic nature of the agenda matters: even if \(F\) is unsatisfiable and \(g\) is logically equivalent to \(p\), they remain distinct agenda formulas.

• Type validity. Each listed type chooses exactly one formula from each complementary pair, so both are complete. Setting \(p=q=\mathrm{true}\) satisfies \(t_+\), and setting \(p=q=\mathrm{false}\) satisfies \(t_-\), independently of \(F\). Thus both types are logically consistent for every source instance. They are distinct, and their nonnegative rational masses sum to \(1\).

• Objective calculation. For every coordinate, the two types have indicator values \(1\) and \(0\). For either possible value \(b_\varphi\in\{0,1\}\), the displayed weighted contribution is exactly \(1/2\). Summing over the three coordinates gives \(D_\mu(K)=3/2\) for every feasible \(K\). The feasible family is nonempty because it contains the listed types. Consequently, every feasible judgment set is indeed a global minimizer.

• Forward implication. A satisfying valuation for \(F\), extended with \(p=\mathrm{false}\) and \(q=\mathrm{true}\), satisfies all formulas in \(L\). Its induced agenda judgment set is complete and consistent. The constant-objective calculation establishes its optimality.

• Reverse implication. A logically consistent judgment set containing \(L\) has a satisfying valuation. That valuation makes \(p\) false, \(q\) true, and \(g\) true, which forces \(F\) true by the definition of \(g\). This implication is valid independently of optimality.

• Encoding and conclusion. Expanding the abbreviation \(g\) wherever needed introduces only constantly many copies of \(F\). The entire explicitly represented instance therefore has size linear in the source formula, and the masses have constant encoding size. The proved equivalence supplies a polynomial-time many-one reduction and establishes NP-hardness. The proof correctly makes exclusion of a polynomial-time algorithm conditional on \(\mathrm P\ne\mathrm{NP}\).

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩