The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality (d4-conf-ijcai-2017-0309)

Given a finite candidate set \(C\), committee size \(k\), and a rational distribution \(\mu\) over complete ranking types \(\mathcal{T}\subseteq\mathcal{R}(C)\), decide whether there exists \(S\subseteq C\) with \(|S|=k\) such that, for every \(c\notin S\), \(\sum_{t:\,c\succ_t s\ \forall s\in S}\mu_t\leq \frac{1}{k+1}\).

Let \(C\) be a candidate set with \(m\geq 1\), and let \(k\) be an input integer satisfying \(1\leq k\leq m\). Each type \(t\) is a strict complete ranking \(\succ_t\) of \(C\).
A society is given by its support: the list \(\mathcal T\) of the \(\tau\) types with positive mass, each with its mass \(\mu_t\) as a binary rational, with \(\sum_{t\in\mathcal T}\mu_t=1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings; let \(L\) be the total input bit length. State running times in \(m,\tau,L,k\).
A committee \(S\subseteq C\) with \(|S|=k\) is locally stable if, for every \(c\in C\setminus S\), \(\sum_{t\in\mathcal T:\,c\succ_t s\ \forall s\in S}\mu_t\leq 1/(k+1)\). Equality is permitted.

Is deciding whether such a locally stable committee exists solvable in polynomial time, or is it NP-hard?

For explicitly listed voters with strict complete rankings, existence of a size-\(k\) locally stable committee with Droop quota \(\lfloor n/(k+1)\rfloor+1\) is NP-complete; checking a specified committee is polynomial-time ([Aziz et al.](https://arxiv.org/pdf/1701.08023v1)). No separate complexity result for the rational-distribution formulation was verified.

Conclusion

The decision problem is NP-complete when \(k\) is part of the input. The explicitly listed voter result transfers by grouping identical rankings and normalizing their multiplicities. Crucially, allowing equality at \(1/(k+1)\) matches the Droop quota exactly.

1. Polynomial-time verification

Number the candidates from \(1\) to \(m\). A certificate is a list of \(k\) distinct candidates forming a committee \(S\).

For each type \(t\), let \(r_t(c)\) be the position of candidate \(c\) in its ranking, with smaller positions preferred. Compute \(h_t=\min_{s\in S}r_t(s)\). Then, for any \(c\notin S\),

\(c\succ_t s\text{ for every }s\in S\quad\Longleftrightarrow\quad r_t(c)<h_t.\)

Thus, after constructing the rank tables, determining all blocking types takes \(O(\tau(m+k))\) rank operations.

Exact arithmetic remains polynomial in the input length. Write each mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers encoded in binary. Define

\(D=\prod_{t\in\mathcal T}b_t,\qquad w_t=a_t(D/b_t).\)

These are integers, and normalization gives \(\sum_t w_t=D\). Since the total bit length of the denominators is at most \(L\), the integer \(D\) has \(O(L)\) bits. Each \(w_t\), and every sum of a subset of these weights, also has \(O(L)\) bits.

For each outside candidate \(c\), compute

\(W_c=\sum_{t:\,r_t(c)<h_t}w_t.\)

The required condition is exactly

\(\dfrac{W_c}{D}\leq\dfrac1{k+1}\quad\Longleftrightarrow\quad(k+1)W_c\leq D.\)

All comparisons are therefore exact integer comparisons. Using schoolbook integer arithmetic, a conservative verification bound is \(O((\tau(m+k)+m)L^2)\) bit operations, including checking the certificate. Hence the problem belongs to \(\mathrm{NP}\).

2. Polynomial reduction from explicitly listed voters

The known source problem is the following: given \(n\) explicitly listed voters with strict complete rankings and a target size \(k\), decide whether there is a committee with no outside candidate preferred to every committee member by at least \(\lfloor n/(k+1)\rfloor+1\) voters. This problem is NP-complete by [Aziz et al., Theorem 4; the Droop convention is fixed in Section 3.2](https://arxiv.org/pdf/1701.08023v1).

Consider a source instance with \(n\geq1\). Keep its candidate set and committee size. Group the voters by identical ranking. For each distinct ranking \(t\), let \(n_t\) denote its multiplicity, and output the mass

\(\mu_t=\dfrac{n_t}{n}.\)

This produces valid support data: every mass is positive, and \(\sum_t\mu_t=1\). The rankings remain strict and complete.

The construction has polynomial size and running time in the source input length. Indeed, \(\tau\leq n\); each output ranking has \(O(m\log(m+1))\) bits; and each numerator and denominator has \(O(\log(n+1))\) bits. Consequently, the output length is

\(O(\tau m\log(m+1)+\tau\log(n+1)+\log(m+1)).\)

Grouping rankings and counting their multiplicities can be performed by sorting the explicitly listed ballots.

3. Exact preservation of stability

Fix any committee \(S\) of size \(k\) and any candidate \(c\notin S\). Let \(B_c(S)\) be the number of source voters who prefer \(c\) to every member of \(S\).

By construction, the blocking mass in the output instance is exactly

\(\sum_{t:\,c\succ_t s\ \forall s\in S}\mu_t=\dfrac{B_c(S)}n.\)

Because \(B_c(S)\) is an integer,

\(\dfrac{B_c(S)}n\leq\dfrac1{k+1} \quad\Longleftrightarrow\quad B_c(S)\leq\left\lfloor\dfrac n{k+1}\right\rfloor \quad\Longleftrightarrow\quad B_c(S)<\left\lfloor\dfrac n{k+1}\right\rfloor+1.\)

The last inequality says precisely that candidate \(c\) does not violate Droop local stability in the source election. Applying this equivalence to every outside candidate shows that the same committees are stable in both instances.

The transformation is therefore a polynomial-time many-one reduction preserving both yes and no instances. The rational-support problem is NP-hard; together with Section 1, it is NP-complete.

4. Scope and running time

For \(k=m\), the answer is always yes because there are no outside candidates. More generally, enumeration gives a deterministic decision algorithm taking

\(O\!\left(\binom mk\,(\tau(m+k)+m)L^2\right)\)

bit operations. This is polynomial for every fixed \(k\), but NP-completeness rules out a polynomial-time algorithm for unrestricted input \(k\) unless \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the task correctly: the rational-support decision problem is NP-complete when \(k\) is part of the input. The reduction preserves precisely the equality-permitted stability condition. No major or minor issues were found.

1. Polynomial-time verification

The proposed certificate is valid: a list of \(k\) distinct candidates specifies a committee of the required size. Its length is polynomial in the input length, and membership in \(C\), distinctness, and cardinality can all be checked within the stated bound.

For each type, the quantity \(h_t=\min_{s\in S}r_t(s)\) is well-defined because \(k\geq1\). Since each ranking is strict and complete, the equivalence
\(c\succ_t s\text{ for every }s\in S\Longleftrightarrow r_t(c)<h_t\)
is correct: \(h_t\) is the position of the most-preferred committee member.

Computing these minima requires \(O(\tau k)\) rank operations. Testing all candidates against the minima requires \(O(\tau m)\) more. Thus the stated \(O(\tau(m+k))\) operation count is valid, including rank-table construction.

The exact-arithmetic argument is also correct:

• \(D=\prod_t b_t\) is positive, and each \(b_t\) divides \(D\).
• Each \(w_t=a_t(D/b_t)\) is a positive integer satisfying \(w_t/D=\mu_t\).
• Normalization implies \(\sum_t w_t=D\).
• The bit length of \(D\) is bounded by the sum of the denominator bit lengths, hence is \(O(L)\).
• Positivity and normalization imply that each weight and every subset sum is at most \(D\), so these integers also have \(O(L)\) bits.

The comparison \((k+1)W_c\leq D\) is exactly equivalent to the required mass bound. The factor \(k+1\) contributes only \(O(\log(k+1))\) additional bits, which are covered by \(O(L)\).

Schoolbook multiplication and division therefore support the conservative bound \(O((\tau(m+k)+m)L^2)\) bit operations. This establishes membership in \(\mathrm{NP}\).

2. Applicability of the cited hardness theorem

The cited source matches the required source problem. Its elections use explicitly listed voters with linear preference orders, its Section 3.2 fixes the Droop quota, and Theorem 4 states NP-completeness of existence for a specified committee size. The theorem’s hardness construction uses positive numbers of voters and admissible positive committee sizes. Thus the prover’s restriction to \(n\geq1\) does not lose the needed hardness. [Aziz et al., Sections 2 and 3.2 and Theorem 4](https://arxiv.org/pdf/1701.08023v1).

The prover states the relevant source problem precisely enough to verify that its blocking condition is the one needed for the reduction.

3. Validity and size of the reduction

Grouping identical rankings and assigning \(\mu_t=n_t/n\) produces valid target data:

• Every retained type has positive mass.
• The masses sum to one.
• All rankings remain strict and complete.
• The candidate set and committee size are preserved.

The bound \(\tau\leq n\) is correct. Each multiplicity and denominator uses \(O(\log(n+1))\) bits, and each ranking uses \(O(m\log(m+1))\) bits under the candidate numbering used in the write-up. The stated output-length bound is therefore valid.

Sorting and counting the explicitly listed ballots is polynomial in the source input length. No expansion of binary-encoded multiplicities is required.

4. Exact preservation of stability

For every committee \(S\) of size \(k\) and every outside candidate \(c\), grouping voters preserves their total contribution, so the target blocking mass is exactly \(B_c(S)/n\).

The displayed equivalences are correct because \(n>0\), \(k+1>0\), and \(B_c(S)\) is an integer:
\(B_c(S)/n\leq1/(k+1)\Longleftrightarrow B_c(S)\leq\lfloor n/(k+1)\rfloor\Longleftrightarrow B_c(S)<\lfloor n/(k+1)\rfloor+1\).

This handles the boundary case correctly. When \(n/(k+1)\) is integral, equality is allowed in the target and remains below the source’s blocking quota.

Because this equivalence holds for every outside candidate and every size-\(k\) committee, the same committees are stable in both instances. The reduction consequently preserves both yes and no instances, establishing NP-hardness.

5. Scope, enumeration, and edge cases

For \(k=m\), stability is vacuous and the answer is yes, as stated. This also covers \(m=1\).

Enumeration examines all \(\binom{m}{k}\) committees. Multiplying by the verification bound gives the stated deterministic running time. For each fixed \(k\), this is polynomial in the input parameters. The conclusion concerning unrestricted input \(k\), conditional on \(\mathrm P\ne\mathrm{NP}\), follows correctly from NP-completeness.

No additional lemma, clarification, or repair is needed.

⟨structured verdict parsed — rendered above⟩