The Complexity Landscape of Outcome Determination in Judgment Aggregation (d4-journals-jair-2020-0032)

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

Let \(\Phi=\{x_i,\neg x_i:1\le i\le m\}\), with \(m\ge1\), and let \(\Gamma\) be an explicitly encoded propositional rationality constraint over these variables, used for both individual and collective judgments.
Let \(\mathcal J\) consist of the subsets of \(\Phi\) containing exactly one literal from each complementary pair and consistent with \(\Gamma\).
The geodesic graph has vertex set \(\mathcal J\); distinct vertices \(U,V\) are adjacent exactly when no \(W\in\mathcal J\setminus\{U,V\}\) satisfies \(W\subseteq U\cup V\). Let \(G(U,V)\) be their shortest-path distance.
A society is given by its support: a list of \(\tau\ge1\) distinct types \(t\in\mathcal J\), each with positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Define \(\operatorname{AvgGeo}(\mu)=\arg\min_{K\in\mathcal J}\sum_t\mu_tG(K,t)\), retaining all tied minimizers. Given \(\varphi^\star\in\Phi\), decide whether some \(K\in\operatorname{AvgGeo}(\mu)\) contains \(\varphi^\star\).

Is this rational-mass credulous AvgGeo outcome-determination problem solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For explicit finite profiles, credulous AvgGeo outcome determination is \(\Theta_3^p\)-complete; hardness holds for literal agendas, identical input and output constraints over agenda variables, and a query asking whether some outcome contains one designated literal.

Result

The problem is \(\mathrm{NP}\)-hard. In fact, the finite-profile theorem supplied in the question implies \(\Theta_3^p\)-hardness. Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

Here, rational masses are encoded by binary numerators and denominators.

Reduction from explicit finite profiles

Use the stated \(\Theta_3^p\)-complete finite-profile problem as the source problem. Its hardness holds with precisely the required restrictions: a literal agenda, identical individual and collective constraints over the agenda variables, and a designated-literal credulous query.

Let a source instance have profile \(P=(J_1,\ldots,J_n)\), where \(n\ge1\) and every \(J_j\in\mathcal J\). Keep the agenda, constraint \(\Gamma\), and query literal \(\varphi^\star\) unchanged.

Let \(t_1,\ldots,t_\tau\) be the distinct judgments appearing in \(P\). Define their multiplicities and masses by

\(c_i=\lvert\{j:J_j=t_i\}\rvert,\qquad \mu_{t_i}=c_i/n.\)

Output the support list \((t_i,\mu_{t_i})_{i=1}^{\tau}\). This is a valid target society: its types are distinct and feasible, every mass is positive, and

\(\sum_{i=1}^{\tau}\mu_{t_i}=\frac{1}{n}\sum_{i=1}^{\tau}c_i=1.\)

Exact preservation of outcomes

The feasible set \(\mathcal J\) is unchanged. Because adjacency depends only on this feasible set, the geodesic graph and every distance \(G(K,t)\) are also unchanged.

For every feasible collective judgment \(K\), grouping identical profile entries gives

\(\sum_{i=1}^{\tau}\mu_{t_i}G(K,t_i)=\frac{1}{n}\sum_{i=1}^{\tau}c_iG(K,t_i)=\frac{1}{n}\sum_{j=1}^{n}G(K,J_j).\)

Thus the target objective is exactly the source sum-of-distances objective multiplied by the positive constant \(1/n\). If the source objective is already averaged, the objectives are identical. In either convention, every comparison and every tie is preserved. Hence

\(\operatorname{AvgGeo}(\mu)=\operatorname{AvgGeo}(P).\)

Since the query literal is unchanged, some target minimizer contains \(\varphi^\star\) if and only if some source minimizer contains it. This proves preservation of both yes-instances and no-instances.

Polynomial encoding size

Let \(N\) be the source input length. Because the profile is explicit, \(n\) is bounded by \(N\). Also, \(\tau\le n\).

The distinct types and their multiplicities can be computed by sorting or comparing the explicitly listed judgments, in polynomial time. Both \(c_i\) and \(n\) have \(O(\log(n+1))\) bits. Therefore each mass \(c_i/n\) has polynomial encoding length. If reduced fractions are required, greatest-common-divisor computation supplies them in polynomial time.

The output length satisfies

\(L=O\bigl(\lvert\Gamma\rvert+m+\tau(m+\log(n+1))\bigr),\)

so the entire transformation is a polynomial-time many-one reduction.

Complexity conclusion

By the supplied finite-profile hardness theorem and the reduction above, rational-mass credulous AvgGeo outcome determination is \(\Theta_3^p\)-hard, and therefore \(\mathrm{NP}\)-hard.

This settles the requested hardness alternative. The reduction proves a lower bound; it does not establish a matching completeness classification for arbitrary binary-encoded rational masses.

⟨structured verdict parsed — rendered above⟩

The argument is correct and resolves the requested hardness alternative. No major or minor issues were found.

• Use of the supplied theorem. The source problem is exactly the explicit finite-profile problem whose hardness is given in the task. The stated restrictions match the target: literal agendas, identical individual and collective constraints, and a designated-literal credulous query. The prover uses the supplied theorem as a premise and does not need to reprove it.

• Validity of the constructed society. Each listed type occurs in the source profile, so it belongs to \(\mathcal J\). Removing duplicates makes the types distinct. Every multiplicity satisfies \(c_i\ge1\), and \(n\ge1\), so each mass \(c_i/n\) is positive. The multiplicities partition the profile entries, giving \(\sum_i c_i=n\) and therefore \(\sum_i\mu_{t_i}=1\). These masses meet the stated rational encoding requirement.

• Preservation of the graph. The agenda and constraint are unchanged, so the feasible set \(\mathcal J\) is unchanged. The adjacency definition depends only on this set and the judgments themselves. Consequently, the graph and all distances used in the objectives remain unchanged.

• Preservation of every minimizer. For every \(K\in\mathcal J\), grouping repeated judgments yields

\[ \sum_i\mu_{t_i}G(K,t_i)=\frac1n\sum_{j=1}^{n}G(K,J_j). \]
The factor \(1/n\) is positive and independent of \(K\). Thus all objective comparisons, including ties, are preserved. The complete minimizer sets coincide, which is essential because the query is credulous.

• Preservation of the decision answer. The query literal is unchanged. Equality of the minimizer sets therefore preserves both yes-instances and no-instances.

• Polynomial-time construction and encoding. An explicit profile has \(n\le N\), and its support has \(\tau\le n\). Comparing or sorting its explicitly encoded judgments takes polynomial time. Each numerator and denominator has \(O(\log(n+1))\) bits; optional fraction reduction also takes polynomial time. The displayed output-size bound uses the natural bit-vector encoding of complete judgments. More generally, copying distinct judgments from the explicit input still gives a polynomial-size output, so the reduction's complexity conclusion is sound.

• Hardness conclusion and scope. The polynomial-time many-one reduction transfers the supplied \(\Theta_3^p\)-hardness to the rational-mass problem, implying \(\mathrm{NP}\)-hardness. Since all output parameters are polynomially bounded in the source input length, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\). The prover correctly confines its conclusion to a lower bound and makes no unsupported completeness claim.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩