Simulating Multiwinner Voting Rules in Judgment Aggregation (aamas22-00033)

Given an agenda \(\Phi\), integrity constraint \(\Gamma\), rational distribution \(\mu\) over complete judgment types \(\theta\), and partial judgment \(d\), decide whether some feasible judgment \(J\models\Gamma\) agreeing with \(d\) maximizes the PAV-JA population score \(\sum_{\theta}\mu_{\theta}\bigl(f_{\mathbf u}(|J^+\cap\theta^+|)-f_{\mathbf v}(|J^+\setminus\theta^+|)\bigr)\).

Let Φ be a finite agenda with \(m=|Φ|\). A complete judgment type \(θ\) is a map \(Φ\to\{0,1\}\), and \(θ^+=\{φ\inΦ:θ(φ)=1\}\); a rational distribution \(μ\) is given by its finite support and binary-encoded masses summing to \(1\). For \(J^+=\{φ\inΦ:J(φ)=1\}\), set \(f_{\mathbf u}(r)=r\), \(f_{\mathbf v}(0)=0\), and \(f_{\mathbf v}(r)=\sum_{q=m-r+1}^{m}1/q\) for \(r\geq1\). Thus \(S_\mu(J)=\sum_{θ}\mu_{θ}\bigl(f_{\mathbf u}(|J^+\capθ^+|)-f_{\mathbf v}(|J^+\setminusθ^+|)\bigr)\). A partial judgment \(d\) is respected when \(J(φ)=d(φ)\) on its domain.

Target. Is the problem of deciding whether some \(J\models\Gamma\) respecting \(d\) maximizes \(S_\mu(J)\) solvable in polynomial time, or is it NP-hard?

For explicitly listed finite judgment profiles, the corresponding Outcome(PAV-JA) problem is NP-hard. The discrete hardness result does not address rational distributions over judgment types.

Complexity of Distributional PAV-JA

Decision problem

Let \(\mathcal R=\{J:J\models\Gamma\}\), and let \(\mathcal R_d\subseteq\mathcal R\) consist of the judgments respecting \(d\). The outcome question is whether

\(\operatorname*{arg\,max}_{J\in\mathcal R}S_\mu(J)\cap\mathcal R_d\neq\varnothing\).

Theorem

The distributional Outcome(PAV-JA) problem is \(\mathrm{NP}\)-hard.

Proof

We give a polynomial-time reduction from the stipulated \(\mathrm{NP}\)-hard Outcome(PAV-JA) problem for explicitly listed finite profiles.

Let an instance of that problem contain the nonempty profile

\(P=(\theta_1,\ldots,\theta_n)\),

together with \(\Phi,\Gamma\), and \(d\). For a judgment \(J\) and type \(\theta\), define

\(g(J,\theta)=f_{\mathbf u}(|J^+\cap\theta^+|)-f_{\mathbf v}(|J^+\setminus\theta^+|)\).

Thus the finite-profile score is

\(S_P(J)=\sum_{i=1}^n g(J,\theta_i)\).

Let \(T\) be the set of distinct types occurring in \(P\). For every \(\theta\in T\), let

\(c_\theta=|\{i\in\{1,\ldots,n\}:\theta_i=\theta\}|\),

and construct the rational distribution

\(\mu_\theta=c_\theta/n\).

These masses are positive and satisfy

\(\sum_{\theta\in T}\mu_\theta=\sum_{\theta\in T}c_\theta/n=n/n=1\).

For every judgment \(J\),

\(S_\mu(J)=\sum_{\theta\in T}(c_\theta/n)g(J,\theta)=(1/n)\sum_{i=1}^n g(J,\theta_i)=(1/n)S_P(J)\).

Because \(n>0\), multiplication by \(1/n\) preserves all strict comparisons and all ties. Hence, for every \(J,K\in\mathcal R\),

\(S_\mu(J)\geq S_\mu(K)\) if and only if \(S_P(J)\geq S_P(K)\).

Consequently,

\(\operatorname*{arg\,max}_{J\in\mathcal R}S_\mu(J)=\operatorname*{arg\,max}_{J\in\mathcal R}S_P(J)\).

The agenda, integrity constraint, and partial judgment are unchanged. Therefore, a finite-profile maximizer respecting \(d\) exists if and only if a distributional maximizer respecting \(d\) exists.

It remains to verify that the transformation is polynomial. There are at most \(n\) distinct types. Each mass \(c_\theta/n\), reduced or unreduced, has binary encoding length \(O(\log n)\). The multiplicities can be computed by sorting or hashing the explicitly represented \(m\)-bit types. Thus the entire distribution is constructible in time polynomial in the finite-profile input size.

This is a polynomial-time many-one reduction from the stipulated \(\mathrm{NP}\)-hard discrete problem, proving the claim.

Encoding observation

Expanding an arbitrary binary-encoded rational distribution into a finite profile can require exponentially many voters. That reverse transformation is unnecessary here: the hardness reduction goes from an explicitly listed profile to its empirical distribution, whose denominators are at most the explicitly given profile size \(n\).

Thus rational distributions do not yield a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verification report

Summary

The reduction is correct and fully resolves the target by establishing NP-hardness. It converts an explicitly listed profile into its empirical rational distribution and proves that every feasible judgment’s score is scaled by the same positive factor. Hence the set of maximizers, including those respecting the partial judgment \(d\), is unchanged.

Step-by-step audit

• Source problem. The proof starts from the stipulated NP-hard Outcome(PAV-JA) problem for explicitly listed finite profiles. This is exactly the hardness premise supplied in the task.

• Construction of the distribution. For each distinct type \(\theta\), the mass

\[ \mu_\theta=\frac{c_\theta}{n} \]
is positive, rational, and binary-encodable. Since the multiplicities sum to \(n\), the masses sum exactly to \(1\).

• Score correspondence. Grouping identical types gives

\[ S_\mu(J)=\frac{1}{n}S_P(J) \]
for every judgment \(J\). This calculation is exact and correctly accounts for multiplicities.

• Preservation of maximizers. Because \(n>0\), scaling all scores by \(1/n\) preserves strict comparisons, equalities, and therefore the complete argmax set over judgments satisfying \(\Gamma\).

• Preservation of the decision question. The agenda, integrity constraint, and partial judgment are unchanged. Since the argmax sets coincide, one contains a judgment respecting \(d\) exactly when the other does.

• Polynomial encoding size. There are at most \(n\) support types. Each numerator and denominator has \(O(\log n)\) bits, while each type is already explicitly represented using \(m\) bits. Computing multiplicities and writing the distribution therefore takes polynomial time and produces polynomial-size output.

• Reverse expansion. The observation that arbitrary rational distributions may require exponentially large explicit profiles is accurate and irrelevant to this reduction, whose direction is from profiles to distributions.

• Scope of the conclusion. Establishing NP-hardness answers the target. Membership in NP or NP-completeness was neither claimed nor required.

No unjustified mathematical step, missing hypothesis, or relevant edge case remains. The assumption \(n>0\) is explicitly stated and is needed only to define the empirical distribution and positive scaling.

⟨structured verdict parsed — rendered above⟩