Multiwinner Rules on Paths From k-Borda to Chamberlin-Courant (d4-conf-ijcai-2017-0404)

Given candidates \(C\), committee size \(k\), fixed rational \(p>1\), a rational distribution \(\mu\) over complete rankings \(\pi\) of \(C\), and threshold \(\theta\), decide whether there is a committee \(S\subseteq C\) with \(\lvert S\rvert=k\) and \(F_{\mu,p}(S)=\sum_{\pi}\mu_\pi\left(\sum_{j=1}^{k}b_j(\pi,S)^p\right)^{1/p}\ge\theta\), where \(b_j(\pi,S)\) are the sorted Borda scores of committee members.

Fix a rational \(p>1\). Input consists of a candidate set \(C\) with \(m\ge1\), an integer \(1\le k\le m\), a society \(\mu\), and a binary-rational threshold \(\theta\in\mathbb{Q}\).
A society is given by its support: the list of the \(\tau\) distinct types with positive mass, each with its mass as a binary rational. Types are strict complete rankings of \(C\); masses satisfy \(\sum_{\pi}\mu_{\pi}=1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings.
For a committee \(S\subseteq C\) of size \(k\), let \(b_1(\pi,S)>\cdots>b_k(\pi,S)\) be its members' Borda scores in ranking \(\pi\), using scores from \(m-1\) down to \(0\). Define \(F_{\mu,p}(S)=\sum_{\pi\in\operatorname{supp}(\mu)}\mu_{\pi}\bigl(\sum_{j=1}^{k}b_j(\pi,S)^p\bigr)^{1/p}\).
The decision problem asks whether some such committee satisfies \(F_{\mu,p}(S)\ge\theta\), with exact comparison and equality accepted. Let \(L\) be the total binary input length; state running times in \(m,\tau,k,L\), with \(p\) fixed.

For each fixed rational \(p>1\), is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For finite lists of voters, the corresponding score-threshold problem is \(\mathrm{NP}\)-hard for every fixed rational \(p>1\) ([Faliszewski et al., 2017](https://www.ijcai.org/proceedings/2017/0028.pdf)).
No separate result for exactly this support-distribution formulation was located in the searches performed.

Conclusion

For every fixed rational \(p>1\), the support-distribution decision problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. Hence a running time polynomial in \(m,\tau,k,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

Here, a binary rational means a rational whose numerator and denominator are encoded in binary, as in the question.

Hardness premise

Use the finite-list score-threshold hardness supplied in the task, corresponding to [Faliszewski et al., Theorem 2](https://www.ijcai.org/proceedings/2017/0028.pdf).

For fixed \(p\), a source instance consists of candidates \(C\), committee size \(k\), an explicit nonempty voter list \(V=(\pi_1,\ldots,\pi_n)\), and a binary-rational threshold \(T\). Its question is whether some size-\(k\) committee \(S\) satisfies

\(\displaystyle G_{V,p}(S):=\sum_{i=1}^{n}\left(\sum_{j=1}^{k}b_j(\pi_i,S)^p\right)^{1/p}\ge T.\)

The paper’s formulation using a winning committee is equivalent: the finite, nonempty collection of size-\(k\) committees has a maximum score, and that maximum reaches \(T\) exactly when some committee does.

Reduction and correctness

Keep \(C\) and \(k\) unchanged. For each distinct ranking \(\pi\) occurring in \(V\), let \(n_\pi\) denote its multiplicity. Output precisely these rankings as the society’s support, with

\(\displaystyle \mu_\pi=\frac{n_\pi}{n},\qquad \theta=\frac{T}{n}.\)

Every listed mass is positive. Moreover,

\(\displaystyle \sum_{\pi\in\operatorname{supp}(\mu)}\mu_\pi=\frac{1}{n}\sum_{\pi\in\operatorname{supp}(\mu)}n_\pi=1.\)

Thus the output is a valid instance, with support size \(\tau\le n\).

For every size-\(k\) committee \(S\), grouping voters with identical rankings gives the exact identity

\(\displaystyle F_{\mu,p}(S)=\sum_{\pi\in\operatorname{supp}(\mu)}\frac{n_\pi}{n}\left(\sum_{j=1}^{k}b_j(\pi,S)^p\right)^{1/p}=\frac{G_{V,p}(S)}{n}.\)

Since \(n>0\),

\(\displaystyle F_{\mu,p}(S)\ge\theta\quad\Longleftrightarrow\quad G_{V,p}(S)\ge T.\)

This equivalence holds for every committee, so it also holds after existentially quantifying over committees. Equality is preserved exactly. The transformation is therefore a many-one reduction.

Encoding size, running time, and exact arithmetic

Let \(L_{\mathrm{list}}\) be the source instance’s binary length, and let \(B\) be the threshold’s encoding length. Relabel candidates by integers from \(1\) to \(m\). Each support ranking then uses \(O(m\log(m+1))\) bits.

Each mass \(n_\pi/n\) uses \(O(\log(n+1))\) bits. Writing \(T=a/d\), with \(d>0\), the new threshold is \(a/(dn)\), whose encoding uses \(O(B+\log(n+1))\) bits. Consequently, the target length satisfies

\(\displaystyle L=O\!\left(\tau m\log(m+1)+\tau\log(n+1)+B+\log(n+1)\right).\)

Because the source lists its voters explicitly, \(m,n,k\) are bounded polynomially in \(L_{\mathrm{list}}\). Grouping rankings, counting multiplicities, and constructing the rational numbers can all be performed in polynomial time; a conservative bound is \(O(L_{\mathrm{list}}^3)\) bit operations.

Thus an algorithm taking time \((m+\tau+k+L)^{O(1)}\), for fixed \(p\), would solve the source problem in polynomial time. Its stated \(\mathrm{NP}\)-hardness proves the conclusion.

The reduction never evaluates a radical or compares committee scores. It transfers exact comparisons through an algebraic identity. Accordingly, this proof establishes \(\mathrm{NP}\)-hardness without asserting membership in \(\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The output proves the claimed \(\mathrm{NP}\)-hardness for every fixed rational \(p>1\). The reduction is valid, has polynomial encoding size, and preserves the exact threshold comparison, including equality. No major or minor mathematical issues were found.

1. Hardness premise and applicability

The prover states the source problem precisely: an explicit voter list, the same Borda scores and committee objective, and a rational score threshold.

The cited [Theorem 2](https://www.ijcai.org/proceedings/2017/0028.pdf) states hardness for each rational \(p>1\); the paper’s scoring definitions match the objective used here. The binary-rational score-threshold premise is also expressly supplied by USER_TASK, so the prover may use it without reproving the underlying hardness theorem.

The equivalence between a winning committee reaching the threshold and some committee reaching it is correct. For \(1\le k\le m\), the family of eligible committees is finite and nonempty, and every committee has a well-defined real score. Consequently, a maximum exists.

The nonempty voter-list restriction makes normalization legitimate. It is consistent with the supplied hardness premise; empty elections would have constant zero scores and would not supply the hard instances.

Assessment: Valid application of the supplied hardness result.

2. Validity of the constructed society

For each distinct source ranking, its multiplicity satisfies \(1\le n_\pi\le n\). Therefore \(\mu_\pi=n_\pi/n\) is a positive rational.

Distinct rankings partition the voter list, so their multiplicities sum to \(n\). The displayed normalization calculation correctly establishes total mass one.

The construction retains strict complete rankings, the candidate set, and the valid committee size. Its support consists precisely of the distinct source rankings, hence \(\tau\le n\).

The interpretation of “binary rational” as a numerator and denominator encoded in binary is explicit and matches the task’s evident intended encoding.

Assessment: Every output instance satisfies the target input conditions.

3. Score identity and decision equivalence

Grouping identical rankings is legitimate because their per-committee contributions coincide. The identity \(F_{\mu,p}(S)=G_{V,p}(S)/n\) holds for every eligible committee, without approximation.

Because \(n>0\), dividing both the score and threshold by \(n\) preserves the direction of the inequality. It also preserves equality. Keeping the same candidate set and committee size means that the existential quantifiers range over exactly the same committees.

Zero Borda scores cause no domain difficulty for positive rational \(p\). The argument also remains valid for \(m=1\), \(k=1\), and \(k=m\); hardness does not require these special cases individually to be hard.

Assessment: The transformation preserves yes-instances and no-instances exactly.

4. Encoding size and construction time

The stated encoding bounds are correct:

• A canonically labeled ranking requires \(O(m\log(m+1))\) bits.
• Each multiplicity fraction requires \(O(\log(n+1))\) bits.
• If \(T=a/d\), then \(T/n=a/(dn)\), whose encoding requires \(O(B+\log(n+1))\) bits.

Summing these contributions gives the displayed target-length bound. Reducing fractions, if required by the encoding convention, does not increase their lengths and takes polynomial time.

Because rankings and voters are listed explicitly, \(m\), \(n\), and \(k\) are polynomially bounded by the source input length. Grouping rankings, counting multiplicities, and constructing the fractions require only polynomial-time string and integer operations. The conservative cubic construction bound is sufficient.

Accordingly, a target algorithm polynomial in \(m,\tau,k,L\) would yield a polynomial-time source algorithm.

Assessment: Polynomial-time many-one reduction established.

5. Exact arithmetic and scope

The reduction performs no numerical evaluation of committee scores. Its correctness follows from an exact algebraic identity, so radical comparison introduces no additional computational requirement into the reduction.

The prover correctly claims hardness without claiming membership in \(\mathrm{NP}\). This resolves the requested hardness alternative; an exact-comparison upper bound is unnecessary.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩