Individual Representation in Approval-Based Committee Voting (aaai22-20418)

Given candidates \(C\), committee size \(k\), and a rational finite-support distribution \(\mu\) over approval types \(A\subseteq C\), define \(\nu_\mu(S)=\sum_{A\supseteq S}\mu_A\) and \(f_\mu(A)=\max\{|S|:S\subseteq A,\ \nu_\mu(S)\ge |S|/k\}\). Decide whether there exists a committee \(W\subseteq C\) with \(|W|\le k\) such that \(|W\cap A|\ge f_\mu(A)\) for every positive-mass type \(A\).

Definitions

An instance consists of a finite candidate set \(C\), \(k\in\{1,\ldots,|C|\}\), and a finite list of approval types \(A\subseteq C\) with positive binary-encoded rational masses \(\mu_A\) summing to \(1\).
For \(S\subseteq C\), let \(\nu_\mu(S)=\sum_{A\supseteq S}\mu_A\), and for each listed type \(A\) let \(f_\mu(A)=\max\{\,|S|:S\subseteq A,\ \nu_\mu(S)\ge |S|/k\,\}\). An IR committee is \(W\subseteq C\) with \(|W|\le k\) and \(|W\cap A|\ge f_\mu(A)\) for every listed type \(A\).

Target

Is deciding whether an IR committee exists for such a rational finite-support distribution solvable in polynomial time, or is it NP-hard?

Nearest known results

For finite approval-voter profiles, deciding whether an IR committee exists is NP-hard.

Complexity of IR-Committee Existence

Claim

Deciding whether an IR committee exists for a rational finite-support distribution is \(\mathrm{NP\text{-}hard}\). Consequently, it is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).

1. Finite profiles as rational distributions

Consider a finite approval-voter profile with voter set \(N\), where \(n=|N|\), candidate set \(C\), target size \(k\), and approval set \(A_i\subseteq C\) for each voter \(i\in N\).

For \(S\subseteq C\), define \(N(S)=\{i\in N:S\subseteq A_i\}\). The standard finite-profile IR demand of voter \(i\) is

\[ f_i=\max\bigl\{|S|:S\subseteq A_i,\ |N(S)|\ge |S|n/k\bigr\}. \]

This is equivalent to the usual definition through cohesive voter groups: a qualifying \(S\) makes \(N(S)\) an \(|S|\)-cohesive group containing \(i\), while any cohesive group containing \(i\) supplies a set \(S\) of commonly approved candidates satisfying the displayed inequality.

For every distinct approval set \(B\) occurring in the profile, let \(n_B=|\{i\in N:A_i=B\}|\), and construct the distribution

\[ \mu_B=\frac{n_B}{n}. \]

These masses are positive and sum to \(1\).

2. Exact preservation of demands

For every \(S\subseteq C\),

\[ u_\mu(S) =\sum_{B\supseteq S}\mu_B =\frac{1}{n}\sum_{B\supseteq S}n_B =\frac{|N(S)|}{n}. \]

Consequently,

\[ u_\mu(S)\ge \frac{|S|}{k} \quad\Longleftrightarrow\quad |N(S)|\ge \frac{|S|n}{k}. \]

Thus, for every voter \(i\) with approval set \(A_i=B\),

\[ f_\mu(B)=f_i. \]

Repeated voters cause no difficulty: all voters with the same approval set have the same demand and are represented by the single type \(B\) with aggregated mass \(n_B/n\).

It follows that a committee \(W\subseteq C\) satisfies

\[ |W\cap B|\ge f_\mu(B) \]

for every listed distributional type \(B\) if and only if it satisfies

\[ |W\cap A_i|\ge f_i \]

for every voter \(i\). The size constraint \(|W|\le k\) is unchanged. Even if the finite-profile formulation requires \(|W|=k\), the distinction is immaterial: any qualifying committee of size below \(k\) can be extended to size \(k\), and adding candidates cannot violate an IR inequality.

3. Polynomial encoding

The transformation is polynomial-time:

• there are at most \(n\) distinct approval types;
• the multiplicities \(n_B\) are computable by grouping equal ballots;
• every mass \(n_B/n\) has binary encoding length \(O(\log n)\);
• \(C\) and \(k\) remain unchanged.

Hence this is a polynomial-time many-one reduction from finite-profile IR existence to rational finite-support IR existence.

The former problem is \(\mathrm{NP\text{-}hard}\) by [Brill, Israel, Micha, and Peters, Theorem 6](https://ojs.aaai.org/index.php/AAAI/article/download/20418/20177). Therefore the distributional problem is also \(\mathrm{NP\text{-}hard}\).

Notice that expanding an arbitrary rational distribution into a voter profile might require exponentially many voters. That inverse transformation is unnecessary: the hardness reduction proceeds from an explicitly listed profile to masses whose common denominator is merely \(n\).

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict

The reduction is mathematically sound and establishes NP-hardness. The only substantive defect is an incorrect theorem number in the citation: IR-committee existence is covered by Theorem 5, whereas Theorem 6 concerns computing whether a particular demand \(f_i\) exceeds a threshold.

Step-by-step audit

• Construction of the distribution.

Aggregating all voters with approval set \(B\) into mass \(\mu_B=n_B/n\) is valid. Every mass is positive, the masses sum to \(1\), and only distinct types are listed.

• Preservation of support values.

The equality
\[ u_\mu(S)=\sum_{B\supseteq S}\frac{n_B}{n}=\frac{|N(S)|}{n} \]
is correct for every \(S\subseteq C\).

• Preservation of feasibility thresholds.

From the preceding equality,
\[ u_\mu(S)\geq \frac{|S|}{k} \]
is equivalent to
\[ |N(S)|\geq \frac{|S|n}{k}. \]
This equivalence is exact, including when \(|S|n/k\) is nonintegral.

• Preservation of individual demands.

For every voter whose approval set is \(B\), the maximizations defining \(f_i\) and \(f_\mu(B)\) range over the same subsets and apply equivalent threshold conditions. Therefore \(f_\mu(B)=f_i\). Duplicate voters indeed have identical demands.

• Preservation of committees.

Requiring \(|W\cap B|\geq f_\mu(B)\) for every distinct type is equivalent to requiring \(|W\cap A_i|\geq f_i\) for every voter. The size condition is preserved.

• Committee-size convention.

The extension argument from \(|W|<k\) to \(|W|=k\) is correct because the instance assumes \(k\leq |C|\), so enough candidates exist, and adding candidates cannot decrease any intersection \(|W\cap A_i|\). The cited paper itself defines IR using size at most \(k\), so this observation is not needed for that source.

• Polynomial encoding.

There are at most \(n\) output types. Grouping explicit ballots is polynomial-time, and both numerator \(n_B\) and denominator \(n\) require \(O(\log n)\) bits. Thus the transformation is a polynomial-time many-one reduction.

• Hardness premise.

The cited paper does establish that deciding whether an approval-based committee election admits an IR committee is NP-hard, but this is [Theorem 5 of the paper](https://ojs.aaai.org/index.php/AAAI/article/download/20418/20177), not Theorem 6. Theorem 6 instead states NP-completeness of deciding whether \(f_i\geq j\). Since the USER_TASK already supplies finite-profile IR-existence hardness as a nearest known result, this citation error does not undermine the reduction’s conclusion.

Actionable feedback

Replace “Brill, Israel, Micha, and Peters, Theorem 6” with “Brill, Israel, Micha, and Peters, Theorem 5.” No new mathematical argument is required.

⟨structured verdict parsed — rendered above⟩