Achieving fully proportional representation: Approximability results (d4-journals-ai-2015-0009)

Given candidates \(A\), committee limit \(K\), a normal increasing positional scoring function \(\alpha^m\), complete ranking types \(\mathcal{T}\), and rational masses \(\mu_\pi\ge 0\) with \(\sum_{\pi\in\mathcal{T}}\mu_\pi=1\), choose \(S\subseteq A\) with \(|S|\le K\) and \(x_{\pi,a}\ge 0\) satisfying \(\sum_{a\in S}x_{\pi,a}=\mu_\pi\), minimizing \(D_\mu(S,x)=\sum_{\pi\in\mathcal{T}}\sum_{a\in S}x_{\pi,a}\alpha^m(\operatorname{pos}_\pi(a))\); determine whether a polynomial-time \(r\)-approximation exists for each fixed \(r>1\).

Given an explicitly listed finite set \(A\) of \(m\) candidates, \(K\), and ranking types \(\mathcal T\), each type \(\pi\) is a strict ranking of \(A\), with \(\operatorname{pos}_{\pi}(a)\) its position. A normal IPSF is a polynomial-time computable family \(\alpha=(\alpha^m)_{m\ge1}\) with \(\alpha^m(1)=0\), strictly increasing entries, and \(\alpha^{m+1}(i)=\alpha^m(i)\) for \(i\in[m]\).

The input gives rational masses \(\mu_\pi\ge0\) with \(\sum_{\pi\in\mathcal T}\mu_\pi=1\). Choose \(S\subseteq A\), \(|S|\le K\), and \(x_{\pi,a}\ge0\) with \(\sum_{a\in S}x_{\pi,a}=\mu_\pi\), minimizing \(D_\mu(S,x)=\sum_{\pi\in\mathcal T}\sum_{a\in S}x_{\pi,a}\alpha^m(\operatorname{pos}_\pi(a))\).

Target. For every fixed \(r>1\), does this problem admit a polynomial-time \(r\)-approximation algorithm, or is such approximation NP-hard?

For the discrete Chamberlin--Courant counterpart, where each voter is assigned integrally to one of at most \(K\) selected candidates, no polynomial-time \(r\)-approximation exists for any fixed \(r>1\) unless \(\mathrm{P}=\mathrm{NP}\). No result for the mass-distribution formulation is asserted here.

Conclusion

For every fixed \(r>1\), a polynomial-time \(r\)-approximation for the mass-distribution problem would yield a polynomial-time \(r\)-approximation for the discrete Chamberlin–Courant problem. Thus, by the discrete inapproximability result given in the question, no such algorithm exists unless \(\mathrm{P}=\mathrm{NP}\).

The reduction preserves the scoring family \(\alpha\). Splitting a type’s mass does not improve its achievable dissatisfaction.

1. Optimal assignment for a fixed committee

Fix a nonempty committee \(S\subseteq A\), and define
\[ c_\pi(S)=\min_{a\in S}\alpha^m(\operatorname{pos}_\pi(a)). \]
For every feasible mass assignment \(x\), nonnegativity and the mass constraint give
\[ \sum_{a\in S}x_{\pi,a}\alpha^m(\operatorname{pos}_\pi(a)) \;\ge\; c_\pi(S)\sum_{a\in S}x_{\pi,a} = \mu_\pi c_\pi(S). \]
Summing over types yields
\[ D_\mu(S,x)\ge \sum_{\pi\in\mathcal T}\mu_\pi c_\pi(S). \]

This bound is attained: choose a candidate \(b_\pi\in S\) attaining the minimum and assign all mass \(\mu_\pi\) to \(b_\pi\). Consequently, the minimum dissatisfaction for committee \(S\) is exactly
\[ F_\mu(S)=\sum_{\pi\in\mathcal T}\mu_\pi c_\pi(S). \]

Because \(\alpha^m\) is strictly increasing, \(b_\pi\) is simply the highest-ranked member of \(S\) in ranking \(\pi\), and it can be found by scanning that ranking.

2. Polynomial-time reduction from the discrete problem

Consider a discrete Chamberlin–Courant instance with explicitly listed voters \(1,\ldots,n\), where \(n\ge1\), candidate set \(A\), committee bound \(K\ge1\), and voter rankings \(\pi_1,\ldots,\pi_n\). Use the same scoring family \(\alpha\).

Let \(\mathcal T\) be the set of distinct rankings occurring in this instance. For each \(\pi\in\mathcal T\), let
\[ n_\pi=\bigl|\{i:\pi_i=\pi\}\bigr|, \qquad \mu_\pi=\frac{n_\pi}{n}. \]
These are nonnegative rational masses summing to one. Keep \(A\) and \(K\) unchanged.

This construction is polynomial-time: identical explicitly listed rankings can be grouped in polynomial time, and each numerator and denominator requires at most \(O(\log(n+1))\) bits.

For any nonempty committee \(S\), the optimal discrete assignment sends each voter to their highest-ranked candidate in \(S\). Its total dissatisfaction is therefore
\[ F_{\mathrm{disc}}(S) = \sum_{i=1}^{n}\min_{a\in S} \alpha^m(\operatorname{pos}_{\pi_i}(a)) = \sum_{\pi\in\mathcal T}n_\pi c_\pi(S) = nF_\mu(S). \]
Taking minima over the same committees proves
\[ \operatorname{OPT}_{\mathrm{disc}} = n\operatorname{OPT}_\mu. \]

3. Preservation of the approximation guarantee

Suppose a polynomial-time \(r\)-approximation algorithm for the mass problem returns a feasible solution \((S,x)\). Its guarantee is
\[ D_\mu(S,x)\le r\operatorname{OPT}_\mu. \]

Construct a discrete solution using committee \(S\), assigning each original voter to their highest-ranked member of \(S\). This requires polynomial time. By the fixed-committee calculation,
\[ F_{\mathrm{disc}}(S) = nF_\mu(S) \le nD_\mu(S,x) \le rn\operatorname{OPT}_\mu = r\operatorname{OPT}_{\mathrm{disc}}. \]
Thus the resulting algorithm is an \(r\)-approximation for the discrete problem.

The argument also covers instances with zero optimum: all costs are nonnegative, so the approximation guarantee forces the returned cost to be zero. No division by the optimum is used.

4. Application of the given hardness premise

The question supplies the discrete inapproximability theorem for every fixed \(r>1\). The reduction above preserves the candidate set, committee bound, strict rankings, and scoring family, and converts every approximate mass solution into an equally good approximate discrete solution.

Therefore the supplied theorem applies directly. The mass-distribution formulation is NP-hard to approximate within any fixed factor \(r>1\), in the stated sense that a polynomial-time algorithm with that guarantee would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verdict: The proof is correct and resolves the target using the discrete inapproximability premise supplied in the question. No major or minor issues were found.

• Optimal assignment for a fixed committee. For nonempty \(S\), the minimum defining \(c_\pi(S)\) exists because \(S\) is finite. Every selected candidate’s cost is at least \(c_\pi(S)\); multiplying by nonnegative \(x_{\pi,a}\) and summing proves the stated inequality. Assigning all of \(\mu_\pi\) to a minimizing candidate is feasible and attains equality. This also covers types with \(\mu_\pi=0\). Strictly increasing scores justify identifying the minimizing candidate as the highest-ranked member of \(S\).

• Reduction and encoding size. Grouping explicitly listed voters by identical rankings is polynomial-time. The counts satisfy \(1\le n_\pi\le n\), so the rational masses \(n_\pi/n\) have the asserted bit lengths and sum to one. There are at most \(n\) distinct types, and the candidate set, rankings, committee bound, and scoring family are preserved. The construction has polynomial output size. It needs no conversion of arbitrary rational masses into an explicit voter population.

• Equality of optimum values. In the discrete formulation, there are no assignment capacities or other constraints coupling voters. Thus, for each fixed committee, assigning each voter to their least-cost selected candidate is optimal. Grouping these costs by ranking gives exactly \(F_{\mathrm{disc}}(S)=nF_\mu(S)\). Since both instances permit the same committees and \(n>0\), minimizing gives the claimed equality of optimum values.

• Approximation preservation. A feasible returned mass solution necessarily has a nonempty committee: total mass is one, whereas an empty committee cannot receive positive mass. The discrete assignment constructed from that committee is therefore defined and computable in polynomial time. Every equality and inequality in

\(F_{\mathrm{disc}}(S)=nF_\mu(S)\le nD_\mu(S,x)\le rn\operatorname{OPT}_\mu=r\operatorname{OPT}_{\mathrm{disc}}\)
is justified. The conversion does not require the returned mass assignment to be optimal for its committee.

• Boundary cases. Nonnegative costs follow from the initial score being zero and subsequent scores being strictly larger. Consequently, the discussion of zero optimum is correct. Restricting the reduction to \(n\ge1\) and \(K\ge1\) excludes empty-population and infeasible source instances without affecting the stated hardness argument. In the mass formulation, \(K=0\) is infeasible because total mass is one; such instances do not undermine hardness on the feasible subclass. Bounds exceeding the number of candidates cause no discrepancy between the two formulations.

• Use of the supplied hardness premise. The proof invokes precisely the discrete inapproximability statement provided in the task, with the same fixed approximation factor and scoring family. The polynomial reduction and solution conversion establish its required implication. The final paragraph explicitly uses “NP-hard to approximate” in the task’s conditional sense: a polynomial-time approximation algorithm with the stated guarantee would imply \(\mathrm{P}=\mathrm{NP}\).

Feedback to the prover: No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩