Answer: \(\mathrm{NP}\)-hard
Proposition 9 — class: hardness
Assuming P , NP, there is no algorithm that, given an ABSAF S = (F, N, ¯A) and given prf (F), returns an outcome for S that is optimal with respect to the Utilitarian, Egalitarian, or Harmonic rule in polynomial time with respect to m = |prf (F)|. We have now introduced several voting rules. Next, we will compare them axiomatically and in numerical simulations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an explicitly represented argumentation framework \(F=(\mathrm{Arg},\mathrm{Att})\), its preferred-extension catalogue \(E=\mathrm{prf}(F)\), a rational distribution \(\mu\) over nonempty approval types \(A\subseteq\mathrm{Arg}\), and \(k\), find \(\Omega\subseteq E\) with \(|\Omega|\le k\) maximizing \(U_\mu(\Omega)=\sum_A\mu_A\max_{\pi\in\Omega}|\pi\cap A|/|A|\); alternatively, decide whether an outcome core-represents every positive-mass type perfectly.
Let \(F=(\mathrm{Arg},\mathrm{Att})\) be an argumentation framework and let \(E=\operatorname{prf}(F)\) be its explicitly enumerated catalogue of preferred extensions. An explicitly represented rational distribution \(\mu\) has finite support on nonempty approval types \(A\subseteq\mathrm{Arg}\), with \(\sum_A\mu_A=1\).
For \(\Omega\subseteq E\), define \(U_\mu(\Omega)=\sum_A\mu_A\max_{\pi\in\Omega}|\pi\cap A|/|A|\). Given \(1\le k\le|E|\), choose \(\Omega\subseteq E\) with \( |\Omega|\le k\) maximizing \(U_\mu(\Omega)\).
Is computing a \(U_\mu\)-maximizing outcome \(\Omega\) polynomial-time solvable, or is it NP-hard?
For finite lists of voters, computing a Utilitarian-optimal outcome is intractable even when the preferred-extension catalogue is supplied explicitly: unless \(P=NP\), no algorithm runs in time polynomial in \(m=|E|\).
Computing a \(U_\mu\)-maximizing outcome is \(\mathrm{NP}\)-hard, even when the catalogue \(E=\operatorname{prf}(F)\) is supplied explicitly and every probability has a common denominator. Consequently, it is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
Moreover, the natural threshold decision version is \(\mathrm{NP}\)-complete.
We use the supplied result that computing a Utilitarian-optimal outcome is \(\mathrm{NP}\)-hard for a finite list of voters, even when \(E\) is explicitly enumerated.
Consider such an instance with nonempty approval sets \(A_1,\ldots,A_n\), argumentation framework \(F\), explicitly enumerated catalogue \(E=\operatorname{prf}(F)\), and bound \(k\). Its normalized Utilitarian objective is
\[ \operatorname{Util}_V(\Omega) = \frac{1}{n}\sum_{i=1}^n \max_{\pi\in\Omega}\frac{|\pi\cap A_i|}{|A_i|}. \]
Normalization by \(1/n\) does not affect the maximizing outcomes.
For every distinct approval type \(A\) occurring among \(A_1,\ldots,A_n\), let
\[ c_A=\bigl|\{i:A_i=A\}\bigr| \]
and define
\[ \mu_A=\frac{c_A}{n}. \]
All other approval types receive mass zero.
This is a valid explicitly represented rational distribution because every occurring \(A\) is nonempty and
\[ \sum_A\mu_A = \frac{1}{n}\sum_A c_A = 1. \]
The construction leaves \(F\), \(E\), and \(k\) unchanged.
There are at most \(n\) distinct approval types. The multiplicities \(c_A\) can be computed by grouping identical approval sets.
Each weight \(c_A/n\) has binary encoding length \(O(\log n)\). Hence the distribution can be constructed in time and space polynomial in the finite-voter input size. In particular, the reduction does not expand voters by clearing denominators.
For every feasible nonempty \(\Omega\subseteq E\),
\[ \begin{aligned} U_\mu(\Omega) &= \sum_A\frac{c_A}{n} \max_{\pi\in\Omega}\frac{|\pi\cap A|}{|A|} \\ &= \frac{1}{n}\sum_A \sum_{\{i:A_i=A\}} \max_{\pi\in\Omega}\frac{|\pi\cap A_i|}{|A_i|} \\ &= \frac{1}{n}\sum_{i=1}^n \max_{\pi\in\Omega}\frac{|\pi\cap A_i|}{|A_i|} \\ &= \operatorname{Util}_V(\Omega). \end{aligned} \]
Thus the reduction preserves the objective value of every feasible outcome, and therefore
\[ \operatorname*{arg\,max}_{\substack{\Omega\subseteq E\\1\leq|\Omega|\leq k}} U_\mu(\Omega) = \operatorname*{arg\,max}_{\substack{\Omega\subseteq E\\1\leq|\Omega|\leq k}} \operatorname{Util}_V(\Omega). \]
An algorithm computing a \(U_\mu\)-maximizer would therefore compute a Utilitarian-optimal outcome for the finite-voter instance. By the supplied hardness result, this proves \(\mathrm{NP}\)-hardness.
The reduction uses only empirical distributions whose weights are of the form \(c_A/n\). Hence arbitrary binary-encoded rational weights are not needed for the hardness.
Consider the decision problem asking, for a rational threshold \(q\), whether some \(\Omega\subseteq E\) with \(1\leq|\Omega|\leq k\) satisfies \(U_\mu(\Omega)\geq q\).
This problem belongs to \(\mathrm{NP}\). A certificate consists of at most \(k\) indices into the explicit catalogue \(E\). For every support type \(A\), one computes each intersection size \(|\pi\cap A|\), takes the maximum, and then sums the resulting rational quantities exactly.
If the support has \(t\) types and \(\mu_A=p_A/q_A\), every summand has denominator dividing \(q_A|A|\). During exact rational addition, numerator and denominator bit lengths remain polynomial because their lengths are bounded by the sum of the input denominator lengths. Thus comparison with \(q\) is polynomial-time computable.
The objective-preserving reduction above also preserves threshold questions. Therefore this decision version is \(\mathrm{NP}\)-complete.
Explicit enumeration of the preferred-extension catalogue does not make the optimization polynomial-time solvable. The finite-voter instances embed directly as rational distributions by aggregating identical approval types, so computing a maximizing outcome remains \(\mathrm{NP}\)-hard unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The reduction from finite voter lists to rational distributions is objective-preserving and, conditional on the corresponding finite-voter optimization problem being NP-hard, correctly establishes NP-hardness of computing a \(U_\mu\)-maximizing outcome.
However, two complexity claims are stronger than the supplied premise supports:
Thus the main reduction is genuine progress and likely captures the intended argument, but the theorem as stated is not fully established from the given premises.
For each distinct approval type \(A\), the prover defines its multiplicity \(c_A\) and sets \(\mu_A=c_A/n\).
This is correct:
The construction is polynomial in the ordinary explicit encoding of the voter list. Grouping identical explicitly represented sets can be done in polynomial time.
The statement that each weight \(c_A/n\) has encoding length \(O(\log n)\) is correct when numerator and denominator are stored in binary. Even if fractions are not reduced, the representation remains polynomial.
The prover should technically account for the storage of the approval types themselves, but these are copied from the input rather than expanded. This omission is routine and does not threaten the reduction.
The displayed calculation proving
\[ U_\mu(\Omega)=\frac{1}{n}\sum_{i=1}^n\max_{\pi\in\Omega}\frac{|\pi\cap A_i|}{|A_i|} \]
is correct for every nonempty feasible \(\Omega\). Aggregating identical voters into a probability mass preserves each outcome’s value exactly, not merely its ordering.
Consequently, the sets of maximizers coincide, provided that the finite-voter objective appearing in the cited hardness result is exactly this normalized satisfaction objective.
The original definition says \(|\Omega|\leq k\), while the prover uses \(1\leq|\Omega|\leq k\). Since \(\max_{\pi\in\varnothing}\) is undefined, the original problem implicitly needs either nonempty outcomes or a convention for \(U_\mu(\varnothing)\).
Because \(k\geq1\) and \(E\neq\varnothing\), restricting to nonempty outcomes is natural, but the prover should explicitly identify this as the interpretation of the original definition.
The reduction shows that an algorithm returning a \(U_\mu\)-maximizer would return a maximizer for the corresponding finite-voter instance.
The gap is in the cited premise. The supplied nearest result says that, unless \(P=NP\), there is no algorithm polynomial in \(m=|E|\). It does not explicitly state that the finite-voter optimization problem is NP-hard under a specified reduction notion. Conditional nonexistence of a polynomial-time algorithm is not, by itself, logically equivalent to NP-hardness.
Furthermore, “polynomial in \(m\)” is not automatically the same as polynomial in the total input length, because the explicit encodings of extensions, arguments, voters, and \(k\) also contribute to the input length.
The minimum needed clarification is a precise finite-voter hardness theorem stating that computing a maximizer for this exact objective is NP-hard under an appropriate polynomial-time reduction, including its input encoding and complexity measure. With that premise, the main NP-hardness reduction is valid.
The membership argument is essentially correct:
The verifier should also check that the selected indices are distinct if \(\Omega\) is represented as a set, although duplicates can simply be discarded. This is a minor omitted verification detail.
The assertion that the objective-preserving reduction “also preserves threshold questions” is true as a statement about corresponding instances and thresholds. It does not establish NP-hardness unless the threshold version of the finite-voter problem is already known to be NP-hard.
Hardness of computing an optimal solution does not automatically imply NP-hardness of the natural threshold decision problem without an additional reduction or an applicable theorem relating the two problems. No such theorem is stated, and its hypotheses are not checked.
Therefore, the claimed NP-completeness of the threshold problem is unproved.
The minimum clarifications needed are:
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.