The Complexity of Learning Approval-Based Multiwinner Voting Rules (aaai22-20422)

Given \(m,k\), a rational distribution \(\mu\) over nonempty approval types \(\sigma\subseteq\Sigma\), and a \(k\)-committee \(A\), decide whether there exists a non-trivial monotone ABCS scoring function \(f\) such that \(A\in\arg\max_{|C|=k}\sum_{\sigma}\mu_{\sigma}f(|C\cap\sigma|,|\sigma|)\).

Let \(\Sigma\) contain \(m\) candidates, let \(1<k<m\), and let \(A\subseteq\Sigma\) have size \(k\).
A society is given by its support: the list of the \(\tau\) nonempty proper approval types \(\sigma\subsetneq\Sigma\) with positive mass, each mass \(\mu_\sigma\) a binary rational, with \(\sum_\sigma\mu_\sigma=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Define \(X_{m,k}=\{(x,y)\in\mathbb Z^2:1\le y\le m-1,\ \max\{0,y-m+k\}\le x\le\min\{k,y\}\}\).
An ABCS scoring function \(f:X_{m,k}\to\mathbb R_{\ge0}\) is nondecreasing in \(x\) for each fixed \(y\), and normalized by \(f(\max\{0,y-m+k\},y)=0\). It is non-trivial when \(f\not\equiv0\).
For each committee \(C\), define \(S_f(C)=\sum_\sigma\mu_\sigma f(|C\cap\sigma|,|\sigma|)\); all committees attaining the maximum are winners, with ties allowed.

Is deciding whether there exists such a non-trivial \(f\) with \(A\in\arg\max_{C\subseteq\Sigma,\,|C|=k}S_f(C)\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? Express running times in \(m,\tau,L,k\).

For finite voter profiles, this existence problem is \(\mathrm{coW}[1]\)-hard parameterized by \(k\), via a polynomial-time reduction from the complement of Independent Set. [Source](https://arxiv.org/pdf/2110.00254).
No result specifically settling the rational-support distribution formulation was located.

Classification

The problem is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. It is consequently \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, and it admits a polynomial-time algorithm if and only if \(\mathrm P=\mathrm{NP}\).

The reduction convention matters: many-one \(\mathrm{NP}\)-hardness of this problem is equivalent to \(\mathrm{NP}=\mathrm{coNP}\). Thus the proposed “\(\mathrm P\) or \(\mathrm{NP}\)-hard” dichotomy needs this qualification.

Here is a complete proof of the classification, using the published finite-profile reduction.

1. An exact linear-program formulation

For each ballot size \(y\), define
\[ \ell_y=\max\{0,y-m+k\}, \qquad u_y=\min\{k,y\}. \]
Introduce the increments
\[ \delta_{y,t}=f(t,y)-f(t-1,y) \qquad (\ell_y<t\le u_y). \]

Monotonicity and baseline normalization are equivalent to
\[ \delta_{y,t}\ge0, \qquad f(x,y)=\sum_{t=\ell_y+1}^{x}\delta_{y,t}. \]
Indeed, the displayed sum reconstructs every normalized scoring function, and every nonnegative increment vector reconstructs an admissible scoring function.

The number of increments is
\[ d=\sum_{y=1}^{m-1}(u_y-\ell_y)=k(m-k). \]
To verify the equality, the increment indices correspond bijectively to pairs
\[ (t,z)\in\{1,\ldots,k\}\times\{0,\ldots,m-k-1\} \]
by setting \(z=y-t\). The inequalities defining a valid increment are exactly \(1\le t\le k\) and \(0\le y-t\le m-k-1\).

Nontriviality is equivalent to at least one positive increment. Since multiplying all increments by a positive constant preserves every score comparison, we may impose
\[ \sum_{y,t}\delta_{y,t}=1. \]
Write \(\Delta\) for this simplex of nonnegative increment vectors.

For each committee \(C\), define a vector \(g_C\in\mathbb Q^d\) by
\[ g_C(y,t)= \sum_{\sigma:\,|\sigma|=y} \mu_\sigma \left( \mathbf 1_{\{|C\cap\sigma|\ge t\}} - \mathbf 1_{\{|A\cap\sigma|\ge t\}} \right). \]
Substituting the reconstruction formula and interchanging finite sums gives
\[ S_f(C)-S_f(A)=g_C\cdot\delta. \]

Therefore the instance is YES if and only if the following rational linear system is feasible:
\[ \delta\in\Delta, \qquad g_C\cdot\delta\le0 \quad\text{for every }C\subseteq\Sigma,\ |C|=k. \]
The weak inequalities preserve exactly the stipulated treatment of ties.

The coefficients have polynomial bit length. In particular, a common denominator can be obtained by multiplying the denominators of the input masses; its bit length is at most their total encoding length. Since \(|g_C(y,t)|\le1\), each coefficient has \(O(L)\) bits.

2. Membership in \(\mathrm{coNP}\)

We use finite Helly’s theorem: if a finite family of convex subsets of an affine space of dimension \(r\) has empty intersection, some subfamily of at most \(r+1\) sets already has empty intersection. See [Bertsekas, *Convex Optimization Theory*, Exercise 1.42](https://web.mit.edu/dimitrib/www/Convex_Theory_Entire_Book.pdf).

For every committee \(C\), let
\[ K_C=\{\delta\in\Delta:g_C\cdot\delta\le0\}. \]
These sets are convex and lie in the affine space
\[ H=\left\{\delta:\sum_{y,t}\delta_{y,t}=1\right\}, \]
whose dimension is \(d-1\). There are finitely many committees.

If the instance is NO, then \(\bigcap_C K_C=\varnothing\). Helly’s theorem therefore supplies at most \(d\) committees \(C_1,\ldots,C_r\) such that
\[ \delta\in\Delta, \qquad g_{C_i}\cdot\delta\le0 \quad(1\le i\le r) \]
is infeasible.

These committees form a certificate for a NO answer. A verifier checks that they are valid committees, computes their coefficient vectors, and decides infeasibility of this explicitly given rational LP. Rational LP feasibility is decidable in polynomial time. The certificate uses
\[ O\!\left(k^2(m-k)\log m\right) \]
bits, and verification takes \(\operatorname{poly}(m,\tau,L,k)\) time.

There is also no difficulty if the candidate universe is encoded succinctly. If some ballot size \(y\in\{1,\ldots,m-1\}\) is absent from the support, choose one positive increment in that row and set all other increments to zero. Such an increment exists because \(\ell_y<u_y\). Every supported ballot then contributes zero to every committee, giving a YES answer. Consequently, every NO instance satisfies
\[ m-1\le\tau. \]
Since the support is explicitly listed, the certificate and verification bounds are polynomial in \(L\) even under that encoding convention.

Thus the problem belongs to \(\mathrm{coNP}\).

3. Hardness transfers to rational support

The relevant published result is stronger than merely an abstract parameterized-hardness statement: Section 5 explicitly gives a polynomial-time reduction from the complement of Independent Set to finite-profile TargetABCS. Its scoring functions have the same baseline normalization, and winning permits ties. These conventions appear in Section 2, including footnote 2; the reduction is Theorem 14. [Caragiannis and Fehrs, *The Complexity of Learning Approval-Based Multiwinner Voting Rules*](https://arxiv.org/pdf/2110.00254).

We now prove the representation transfer.

Take any explicitly listed finite profile \(P\) containing \(N\) voters. For every distinct approval type \(\sigma\), let \(n_\sigma\) be its multiplicity and set
\[ \mu_\sigma=\frac{n_\sigma}{N}. \]
Keep \(\Sigma\), \(k\), and \(A\) unchanged. The resulting support has positive binary-encoded rational masses summing to one. For every admissible \(f\) and every committee \(C\),
\[ S_f(C) = \sum_\sigma\frac{n_\sigma}{N} f(|C\cap\sigma|,|\sigma|) = \frac1N\sum_{i=1}^{N} f(|C\cap\sigma_i|,|\sigma_i|). \]
Hence all committee-score comparisons, including ties, are preserved. The scoring-function domain, normalization, and nontriviality are unchanged as well.

This transformation is polynomial-time. With ballots represented by \(m\)-bit incidence vectors, sorting and grouping takes \(O(Nm\log N)\) time. Each mass requires \(O(\log N)\) bits, and the resulting support encoding has length
\[ O\!\left(m\log m+\tau(m+\log N)\right). \]

Composing this transformation with the published polynomial-time reduction proves \(\mathrm{coNP}\)-hardness, because the complement of Independent Set is \(\mathrm{coNP}\)-complete. Together with Section 2, this proves \(\mathrm{coNP}\)-completeness.

The transformation also preserves \(k\), so the cited \(\mathrm{coW}[1]\)-hardness transfers.

4. Deterministic running time

Let
\[ B=\binom{m}{k}. \]
The LP has \(d=k(m-k)\) variables, \(B\) committee inequalities, nonnegativity constraints, and one normalization equality. Constructing it explicitly and applying polynomial-time rational LP feasibility gives
\[ \operatorname{poly}(B,m,\tau,L,k) = m^{O(\min\{k,m-k\})}\operatorname{poly}(\tau,L). \]

A sharper dependence on \(B\) follows from the ellipsoid method. The standard rational-polyhedron feasibility theorem uses polynomially many separation-oracle calls in the dimension and the maximum encoding length of a defining inequality, including for lower-dimensional feasible sets. See [MIT’s notes on linear-programming algorithms](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).

Here these parameters are polynomial in \(m,k,L\). An exact separation oracle checks the simplex constraints and then enumerates all \(B\) committees, returning a violated score inequality if one exists. Each committee check takes \(\operatorname{poly}(m,\tau,L,k)\) time at the rational query points produced by the algorithm. Thus the overall bound is
\[ \boxed{\binom{m}{k}\operatorname{poly}(m,\tau,L,k)}. \]
In particular, the problem is polynomial-time solvable for every fixed \(k\), and also for every fixed \(m-k\).

5. Interpreting the requested alternatives

Let \(E\) denote the existence problem.

Because \(E\) is \(\mathrm{coNP}\)-complete,
\[ E\in\mathrm P \quad\Longleftrightarrow\quad \mathrm P=\mathrm{NP}. \]
For the forward implication, completeness gives \(\mathrm{coNP}\subseteq\mathrm P\); taking complements gives \(\mathrm{NP}\subseteq\mathrm P\). The reverse implication follows from \(E\in\mathrm{coNP}\).

Likewise,
\[ E\text{ is many-one }\mathrm{NP}\text{-hard} \quad\Longleftrightarrow\quad \mathrm{NP}=\mathrm{coNP}. \]
Indeed, many-one hardness combined with \(E\in\mathrm{coNP}\) gives \(\mathrm{NP}\subseteq\mathrm{coNP}\), hence equality by complementation. Conversely, that equality turns \(\mathrm{coNP}\)-hardness into \(\mathrm{NP}\)-hardness.

Under polynomial-time Turing reductions, \(\mathrm{NP}\)-hardness follows unconditionally: reduce the complement of Independent Set to \(E\), query \(E\), and negate its answer to decide Independent Set.

⟨structured verdict parsed — rendered above⟩

The claimed classification is proved: the rational-support existence problem is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. The distinction between many-one and Turing \(\mathrm{NP}\)-hardness is correct. I found no mathematical issue requiring repair.

• Increment formulation and normalization.

The increment indices are valid precisely when \(\ell_y<t\le u_y\). Baseline normalization and monotonicity give nonnegative increments, and the telescoping reconstruction recovers every admissible scoring function. Conversely, the reconstruction from nonnegative increments satisfies all the required conditions, including nonnegativity of \(f\).

Nontriviality is equivalent to a positive increment because every row starts at zero. The increment set is finite, so its sum is positive exactly when the function is nontrivial. Rescaling this sum to one preserves all committee comparisons. Thus the simplex normalization neither loses nor introduces feasible scoring functions.

• Number of variables.

The stated bijection is correct. An increment index satisfies \(1\le t\le k\) and \(0\le y-t\le m-k-1\). Conversely, each pair in the displayed rectangle determines \(y=t+z\) in the permitted ballot-size range and a valid increment.

Consequently, \(d=k(m-k)\). Under \(1<k<m\), this dimension is positive, and the simplex has affine dimension \(d-1\). There is no degenerate zero-variable case.

• Committee inequalities.

In the reconstruction formula, an increment contributes to a committee’s score exactly when its intersection size reaches the increment threshold. The definition of \(g_C\) therefore gives the claimed score difference, with the correct sign.

Requiring \(g_C\cdot\delta\le0\) for every committee is exactly the condition that no committee beats \(A\). Equality remains permitted, so ties are handled correctly. The inequality corresponding to \(C=A\) is redundant but harmless.

This establishes both directions of the LP equivalence. The use of real scoring functions causes no difficulty: rational LP feasibility decides whether a real solution exists.

• Coefficient encoding.

Multiplying the input denominators gives a common denominator whose bit length is bounded by the total denominator encoding length. Each coordinate is a signed sum of input masses. Because the masses are positive and sum to one, its absolute value is at most one.

Hence the claimed \(O(L)\) coefficient bit bound is valid. Computing these coefficients requires only polynomial-time rational arithmetic and intersection calculations on the explicitly listed support.

• Helly certificate and membership in \(\mathrm{coNP}\).

The version of finite Helly’s theorem stated in the output is correct. Its hypotheses hold: the family is finite, each \(K_C\) is convex, and all sets lie in the affine space \(H\) of dimension \(d-1\).

Importantly, each \(K_C\) already includes the simplex constraints. Therefore an empty intersection of at most \(d\) such sets is exactly infeasibility of the smaller LP displayed in the output; no additional simplex sets need to be counted.

Listing at most \(d\) committees uses \(O(dk\log m)=O(k^2(m-k)\log m)\) bits. A verifier can check their cardinalities and candidate indices, construct the smaller rational LP, and decide its infeasibility in polynomial time. A feasible original system cannot produce an accepted certificate of this form. Thus both certificate completeness and soundness hold.

• Succinct candidate-universe observation.

Every permitted ballot-size row has at least one increment. The claim remains true at the extreme sizes \(y=1\) and \(y=m-1\), and when \(k=m-1\).

If a ballot size is absent, the proposed scoring function is nontrivial on the full prescribed domain while giving every supported ballot score zero. All committees then tie. This is a valid YES instance under the task’s definition of nontriviality.

Accordingly, every NO instance must have every ballot size represented, implying \(m-1\le\tau\). Since the support list is explicit, this makes the certificate bound polynomial in \(L\) even if \(m\) itself is encoded succinctly. The argument does not confuse support size with the number of possible approval types.

• Published hardness result.

The cited source supports the exact facts needed for the transfer. Section 5 explicitly identifies a polynomial-time reduction from the complement of Independent Set, and the proof of Theorem 14 states the required YES/NO equivalence with committee size preserved. Section 2 and footnote 2 give the matching scoring domain, normalization, nontriviality convention, and treatment of ties. Thus the output relies on more than the bare parameterized-hardness label. [Caragiannis and Fehrs, Sections 2 and 5](https://arxiv.org/pdf/2110.00254)

The source reduction applies within the finite-profile setting required by the transfer. Its construction uses nonempty proper ballots and polynomially many explicitly representable votes. No incompatible profile convention obstructs the composition.

• Transfer to rational support.

Grouping equal ballots and assigning mass \(n_\sigma/N\) produces positive rational masses summing to one. The displayed score identity is exact for every admissible \(f\) and every committee. It preserves all comparisons, including ties, and leaves the scoring-function domain and nontriviality requirement unchanged.

The transformation assumes an explicitly listed nonempty profile, as stated. Under incidence-vector representation, its sorting and grouping bound is polynomial, and each rational mass has \(O(\log N)\) encoding length. The resulting support-length bound is valid.

Therefore composition with the cited polynomial-time reduction establishes \(\mathrm{coNP}\)-hardness. Together with the verified membership argument, this establishes \(\mathrm{coNP}\)-completeness. Preservation of \(k\) also supports the claimed transfer of parameterized hardness.

• Deterministic running times.

The explicit LP has the stated numbers of variables and committee inequalities. Constructing and solving it takes \(\operatorname{poly}(\binom{m}{k},m,\tau,L,k)\) time.

The conversion to \(m^{O(\min\{k,m-k\})}\operatorname{poly}(\tau,L)\) is valid: the binomial coefficient is bounded by \(m^{\min\{k,m-k\}}\), and the remaining polynomial factors in \(m,k\) can be absorbed into this bound.

The sharper ellipsoid bound also stands. The cited notes discuss separation with implicitly represented constraints, polynomial encoding bounds, and the treatment of lower-dimensional feasible sets. Here the polyhedron is bounded by the simplex, every defining inequality has polynomial encoding length, and enumeration supplies an exact separating inequality whenever a query violates the system. The output explicitly invokes the rational feasibility theorem that handles lower-dimensional sets, rather than assuming positive volume. [MIT linear-programming notes, Sections 5 and 5.1](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html)

Consequently, \(\binom{m}{k}\operatorname{poly}(m,\tau,L,k)\) is justified. Polynomial-time solvability for fixed \(k\) or fixed \(m-k\) follows.

• Interpretation of the requested alternatives.

All three complexity implications are correct:

• Membership in \(\mathrm P\) is equivalent to \(\mathrm P=\mathrm{NP}\), using completeness and closure of \(\mathrm P\) under complementation.
• Many-one \(\mathrm{NP}\)-hardness is equivalent to \(\mathrm{NP}=\mathrm{coNP}\), using closure of \(\mathrm{coNP}\) under polynomial-time many-one preimages.
• Polynomial-time Turing \(\mathrm{NP}\)-hardness follows by reducing the complement of Independent Set and negating the oracle answer.

This qualification resolves the task without asserting unconditional many-one \(\mathrm{NP}\)-hardness.

No blocking issue or additional mathematical clarification is needed. The proof establishes the claimed classification and running-time bounds.

⟨structured verdict parsed — rendered above⟩