Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Perspectives (d4-conf-aaai-2016-0672)

Given candidates \(C\), committee size \(k\), a rational distribution \(\mu\) over complete ranking types \(t\), and a rational threshold \(\theta\), decide whether there exists \(S\subseteq C\) with \(|S|=k\) such that \(\sum_t\mu_t g_k(|S\cap A_t|)\ge\theta\), under the hypotheses of Theorem 11.

Fix a family of nondecreasing functions \(g_k:\{0,\ldots,k\}\to\mathbb Z_{\ge0}\), independent of the number of candidates, with \(g_k(0)=0\). Their values are computable in time polynomial in \(k\), and \(g_k(k)\) is polynomially bounded in \(k\).
Define \(\operatorname{sing}(g_k)\) as the least \(i\in\{2,\ldots,k\}\) with \(g_k(i)-g_k(i-1)\ne g_k(i-1)-g_k(i-2)\), or \(\infty\) if none exists. For fixed constants \(c>0\) and \(k_0\), every \(k>k_0\) has convex \(g_k\) and \(k-\operatorname{sing}(g_k)\ge k/c\).
An instance has a candidate set \(C\), \(m=|C|\), an integer committee size \(1\le k\le m/2\), and a nonnegative binary rational threshold \(\theta\). Ranking types are unrestricted strict complete orders on \(C\); \(A_t\) is the set of the first \(k\) candidates in type \(t\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Require \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total binary input length; state running times in \(m,\tau,k,L\).
The decision problem asks whether some committee \(S\subseteq C\), \(|S|=k\), satisfies \(\sum_t\mu_t g_k(|S\cap A_t|)\ge\theta\). Equality is accepted; no tie-breaking is used.

For each fixed scoring family satisfying these hypotheses, is this distribution-based decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

For every such scoring family, the corresponding decision problem with an explicitly listed finite electorate and an integer total-score threshold is \(\mathrm{NP}\)-hard ([source](https://doi.org/10.1007/s00355-018-1126-4)).
No separate result for exactly the normalized rational-support formulation was located in the literature search.

Result

For every fixed scoring family satisfying the hypotheses, the distribution-based decision problem is \(\mathrm{NP}\)-hard. In fact, it is \(\mathrm{NP}\)-complete.

The proof transfers the stated finite-electorate hardness result by an exact polynomial-time reduction.

1. Applying the finite-electorate hardness theorem

For an explicitly listed electorate \(V=(v_1,\ldots,v_n)\), let \(A_v\) denote the first \(k\) candidates in voter \(v\)'s ranking. Define the total score of a committee \(S\) by

\(\operatorname{Score}_V(S)=\sum_{v\in V}g_k(|S\cap A_v|).\)

Theorem 11 of [Faliszewski, Skowron, Slinko, and Talmon, *Multiwinner analogues of the plurality rule*](https://doi.org/10.1007/s00355-018-1126-4) establishes \(\mathrm{NP}\)-hardness of deciding whether a size-\(k\) committee has total score at least a given threshold under the hypotheses stated in the question.

Its hypotheses apply here: the counting functions are independent of the number of candidates, their values are polynomial-time computable in \(k\), their maximum values are polynomially bounded, and the required convexity and singularity condition hold for every \(k>k_0\). Nondecreasingness ensures that counting membership among the first \(k\) positions defines a committee scoring function.

We therefore use this finite-electorate problem as the source of our reduction.

We may assume \(n\ge1\) and a nonnegative integer threshold \(T\). An empty electorate has score zero for every committee, and a negative threshold is always met; these cases are decidable directly. When necessary, map them to fixed target instances: use two candidates, \(k=1\), one ranking of mass one, and threshold zero for a yes-instance or threshold \(g_1(1)+1\) for a no-instance.

2. Enforcing the committee-size restriction

Let the source election have candidate set \(C\), with \(m=|C|\) and \(1\le k\le m\). Add

\(d=\max\{0,2k-m\}\)

new candidates. Append them, in a fixed order, below all original candidates in every ranking. Write \(C'\) for the enlarged candidate set and \(m'=|C'|\). Then

\(m'=\max\{m,2k\}\le2m,\qquad k\le m'/2.\)

Because \(m\ge k\), every voter's first \(k\) candidates remain unchanged. Because \(g_k\) is independent of the number of candidates, every committee contained in \(C\) retains its original score.

Conversely, consider any size-\(k\) committee \(S'\subseteq C'\). Suppose it contains \(r\) new candidates. There are

\(|C\setminus S'|=m-(k-r)=m-k+r\ge r\)

original candidates outside \(S'\). Replace the \(r\) new candidates by any \(r\) distinct original candidates outside \(S'\), obtaining a size-\(k\) committee \(S\subseteq C\).

No new candidate belongs to any \(A_v\), and the replacement retains every original member of \(S'\). Consequently,

\(S'\cap A_v\subseteq S\cap A_v\)

for every voter \(v\). Nondecreasingness of \(g_k\) gives

\(g_k(|S'\cap A_v|)\le g_k(|S\cap A_v|).\)

Summing over voters yields \(\operatorname{Score}_V(S')\le\operatorname{Score}_V(S)\). Hence the padded election has a committee meeting \(T\) if and only if the original election does.

Appending at most \(m\) candidates to each explicitly listed ranking increases the encoding length only polynomially.

3. Converting the electorate into normalized rational support

Group the padded voters by their complete rankings. Let the distinct ranking types be \(t_1,\ldots,t_\tau\), with positive integer multiplicities \(n_1,\ldots,n_\tau\). Thus

\(\sum_{i=1}^{\tau}n_i=n,\qquad \tau\le n.\)

Construct the target society by listing precisely these types and assigning

\(\mu_{t_i}=\frac{n_i}{n},\qquad \theta=\frac{T}{n}.\)

All listed masses are positive binary rationals, and

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

For every size-\(k\) committee \(S\subseteq C'\), grouping identical rankings gives the exact identity

\(\sum_{i=1}^{\tau}\mu_{t_i}g_k(|S\cap A_{t_i}|)=\frac{1}{n}\sum_{i=1}^{\tau}n_i g_k(|S\cap A_{t_i}|)=\frac{\operatorname{Score}_V(S)}{n}.\)

Since \(n>0\), it follows that

\(\sum_{i=1}^{\tau}\mu_{t_i}g_k(|S\cap A_{t_i}|)\ge\theta\quad\Longleftrightarrow\quad\operatorname{Score}_V(S)\ge T.\)

In particular, equality is preserved exactly.

Grouping can be performed by sorting the explicitly listed rankings. Each multiplicity and the common denominator \(n\) use \(O(\log(n+1))\) bits. If \(b_T\) is the binary length of \(T\), the target encoding length is

\(O\bigl(\tau m'\log(m'+1)+\tau\log(n+1)+b_T\bigr).\)

This is polynomial in the source input length. Computing the fractions, including reducing them if required by the encoding, also takes polynomial time. Combining this construction with Section 2 proves \(\mathrm{NP}\)-hardness for the exact formulation in the question.

4. Polynomial-time certificate verification

A certificate is a list of the \(k\) selected candidates. We can verify its cardinality and distinctness, and compute every intersection size \(|S\cap A_t|\), in polynomial time.

It remains to justify exact rational comparison. Write the input masses and threshold as

\(\mu_t=p_t/q_t,\qquad \theta=a/b,\)

where all denominators are positive. Put

\(D=b\prod_{t=1}^{\tau}q_t.\)

The sum of the denominator encoding lengths is at most \(L\), so \(D\) has \(O(L)\) bits. The desired comparison is equivalent to the integer comparison

\(\sum_{t=1}^{\tau}p_t g_k(|S\cap A_t|)\frac{D}{q_t}\ge a\frac{D}{b}.\)

All quotients are integers. Since \(0\le g_k(j)\le g_k(k)\) and \(g_k(k)\) is polynomially bounded, the integers occurring in this calculation have \(O(L+\log(k+1))\) bits. The additional bits needed when summing \(\tau\) terms are absorbed by this bound because the support is explicitly listed and \(\log(\tau+1)=O(L)\).

For an explicit running-time bound, let \(p(k)\) bound the time to compute one value of the fixed family. Precompute its \(k+1\) values and use schoolbook integer arithmetic. A sufficient verification bound, including validation of the rankings and normalization, is

\(O\bigl(m+\tau m\log(m+1)+(k+1)p(k)+(\tau+1)(L+\log(k+1))^2\bigr).\)

This is polynomial in \(m,\tau,k,L\), and hence in the explicit input length. Therefore the problem belongs to \(\mathrm{NP}\).

Together with the reduction, this establishes \(\mathrm{NP}\)-completeness. A polynomial-time algorithm would therefore imply \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the assigned question: for every fixed scoring family satisfying the hypotheses, the normalized rational-support decision problem is \(\mathrm{NP}\)-complete. I found no major or minor mathematical issues.

• The cited hardness theorem applies.

Theorem 11 requires counting functions independent of the number of candidates, polynomial-time evaluation in \(k\), polynomially bounded \(g_k(k)\), and eventual convexity together with \(k-\operatorname{sing}(g_k)\ge k/c\). These match the task’s hypotheses. The paper’s definitions of top-\(k\) counting, discrete convexity, and singularity also match those used here. Its standing restriction \(m\ge2k\) is compatible with the target restriction. [Theorem 11 and definitions](https://link.springer.com/article/10.1007/s00355-018-1126-4).

The prover correctly uses this theorem as a finite-electorate hardness result. It does not assume that the theorem already covers normalized rational support.

• The preliminary edge cases are handled correctly.

With an empty electorate, every committee has total score zero. With a negative threshold, every committee meets the threshold because the scoring functions are nonnegative.

The proposed fixed target instances are valid: two candidates and \(k=1\) satisfy the committee-size restriction, and a single ranking with mass one gives a normalized society. Threshold zero produces a yes-instance. Threshold \(g_1(1)+1\) produces a no-instance because every committee’s score is at most \(g_1(1)\). This remains true if \(g_1(1)=0\).

• Candidate padding preserves the decision answer.

The identities
\[ d=\max\{0,2k-m\},\qquad m'=\max\{m,2k\}\le2m \]
are correct under \(k\le m\).

Appending new candidates below all original candidates preserves every top-\(k\) set. Independence of \(g_k\) from the number of candidates therefore preserves the scores of committees containing only original candidates.

The converse is also justified. If a padded committee contains \(r\) new candidates, then exactly \(k-r\) original candidates are selected, leaving
\[ m-k+r\ge r \]
original candidates available for replacement. The replacement retains every selected original candidate and removes only candidates outside every top-\(k\) set. Thus each intersection size weakly increases. Nondecreasingness of \(g_k\) implies that total score weakly increases.

Both directions of the existence equivalence follow. The construction increases each ranking’s length by at most a factor of two, so its encoding cost is polynomial.

• Normalization and grouping are exact.

Grouping by complete rankings produces precisely a support list of distinct ranking types with positive multiplicities. Consequently, \(\tau\le n\), each mass \(n_i/n\) is positive, and the masses sum to one.

The score identity
\[ \sum_{i=1}^{\tau}\frac{n_i}{n}g_k(|S\cap A_{t_i}|) =\frac{\operatorname{Score}_V(S)}{n} \]
follows directly from grouping identical summands. Since \(n>0\), replacing the threshold by \(T/n\) preserves the comparison in both directions, including equality.

This addresses the intended unrestricted ranking domain and the actual support size. It requires no enumeration of all possible rankings.

• The reduction has polynomial encoding size.

Each multiplicity and denominator needs \(O(\log(n+1))\) bits. The stated bound
\[ O\bigl(\tau m'\log(m'+1)+\tau\log(n+1)+b_T\bigr) \]
accounts for the rankings, masses, and threshold. The threshold’s denominator is covered by the logarithmic term because \(\tau\ge1\).

Since the source electorate is explicitly listed, \(n\) and the ranking data are bounded by its input length. Sorting rankings, counting multiplicities, and constructing or reducing the fractions all take polynomial time. The reduction therefore establishes hardness for the exact target encoding.

• Certificate verification uses valid exact arithmetic.

A list of \(k\) distinct candidates is a polynomial-size certificate. Its intersection with each explicitly listed top-\(k\) set is computable in polynomial time.

The common denominator
\[ D=b\prod_{t=1}^{\tau}q_t \]
is positive and divisible by every denominator involved. Multiplying by \(D\) therefore preserves the comparison and yields exactly the displayed integer inequality.

The bit length of \(D\) is \(O(L)\), because logarithms of the factors add. Numerator lengths are also bounded by \(L\). Polynomial boundedness of \(g_k(k)\) contributes only \(O(\log(k+1))\) bits, and summing the explicitly listed terms contributes at most \(O(\log(\tau+1))\) further bits. The stated arithmetic-size bound is sound.

The proposed schoolbook-arithmetic verification bound is a sufficient polynomial bound in \(m,\tau,k,L\), under the usual indexed encoding of candidates. Ranking validation and normalization can be included within it. Thus membership in \(\mathrm{NP}\) is established.

The write-up needs no mathematical repair or additional clarification. The finite-electorate hardness transfer and the certificate verification together support the claimed \(\mathrm{NP}\)-completeness.

⟨structured verdict parsed — rendered above⟩