Multiwinner Elections With Diversity Constraints

The paper supports a genuine continuous mirror, with an instructive boundary: interval diversity constraints become an LP over population masses, while arbitrary independent constraints can preserve the discrete hardness.

My lead anchor is Theorem 15, proved in this paper. It states that \(\mathrm{DCF}\) is \(\mathrm{NP}\)-hard even when the diversity specification consists of interval constraints and the labeling is \(3\)-layered. The reduction is from \(3\)-Dimensional Matching: given disjoint sets \(X,Y,Z\), a family \(T\subseteq X\times Y\times Z\), one candidate is created for each triple \(t=(x,y,z)\), with labels \(x,y,z\); every label must occur exactly once in the committee, and the committee size is \(n=|X|=|Y|=|Z|\). A feasible committee is therefore exactly a perfect \(3\)-dimensional matching.

The continuous mirror is:

\[ \mathrm{3Layered\text{-}Mass\ Feasibility}_{\infty}. \]

An instance contains three finite label sets \(X,Y,Z\), a finite set of candidate types \(\Theta\), a rational population distribution \(\mu\in\mathbb{Q}_{\ge 0}^{\Theta}\) with \(\sum_{\theta}\mu_\theta=1\), and a labeling map assigning each type \(\theta\) one label from each of \(X,Y,Z\). The type description is complete: candidates of the same type have the same labels and any other information relevant to the problem.

Given a target committee mass \(\kappa\) and rational label quotas \(q_\ell\), the task is to find selected masses \(z_\theta\) satisfying

\[ 0\le z_\theta\le \mu_\theta, \]

\[ \sum_{\theta\in\Theta}z_\theta=\kappa, \]

and

\[ \sum_{\theta:\ell\in\lambda(\theta)}z_\theta=q_\ell \qquad\text{for every }\ell\in X\cup Y\cup Z. \]

A solution is the mass vector \(z\), or a declaration that none exists. The exact-cover instance is recovered by setting every label quota to \(1/n\), taking \(\kappa=1\), and interpreting each triple as a candidate type. In a high-multiplicity scenario, there may be thousands of candidates of each triple type: \(N\mu_\theta\) named candidates share the same complete profile.

This is a linear-programming feasibility problem with \(|\Theta|\) variables and \(1+|X|+|Y|+|Z|\) constraints. Hence the expected classification is Class A: the discrete \(\mathrm{NP}\)-hardness dissolves into polynomial-time LP feasibility. With a separable performance score \(w_\theta\), one can instead maximize

\[ \sum_{\theta\in\Theta}w_\theta z_\theta \]

over the same polytope, still in polynomial time.

This is a plausible mirror of the authors’ problem rather than an unrelated fractional allocation problem. Think of a large fellowship, hiring, or conference-selection population. Candidates share complete profiles such as discipline, seniority, region, and institutional category; the committee selects a mass of candidates while enforcing representation quotas. The type-level quantity \(z_\theta\) is fractional because the population is continuous, not because an individual candidate is fractionally admitted: almost every individual still receives the integral decision “selected” or “not selected.”

The second useful anchor is Theorem 4, also proved here. Its full statement is that, for independent diversity constraints, \(1\)-laminar labeling with a separable objective gives polynomial-time algorithms for both \(\mathrm{DCWD}\) and \(\mathrm{DCF}\), with running times \(O(|L|^2k^2+|C|\log |C|)\) and \(O(|L|^2k^2)\), respectively. But with \(2\)-layered labeling, both problems are \(\mathrm{NP}\)-hard, even when each candidate has at most two labels and each label is associated with at most three candidates.

The corresponding continuous problem is:

\[ \mathrm{Independent\text{-}Mass\ DCF}_{\infty}. \]

The input is a two-layered population of candidate types with supplies \(\mu_\theta\), a target selected mass \(\kappa\), and for each label \(\ell\) an explicitly represented set \(B_\ell\) of permitted selected masses. The question is whether there exists \(z\) with

\[ 0\le z_\theta\le\mu_\theta,\qquad \sum_\theta z_\theta=\kappa,\qquad \sum_{\theta:\ell\in\lambda(\theta)}z_\theta\in B_\ell \]

for every label \(\ell\). The optimization version adds the separable objective \(\sum_\theta w_\theta z_\theta\).

Here the natural continuous analogue remains hard if arbitrary independent constraints are retained. In the paper’s X3C construction, normalize the incidence population so that each candidate type has mass \(1/M\). For every set label \(S\), impose

\[ B_S=\{0,3/M\}, \]

and for every element label \(x\), impose

\[ B_x=\{1/M\}. \]

Selecting mass \(3/M\) for \(S\) forces all three of its incidence types to be selected, because each has capacity \(1/M\). Thus a feasible mass solution still chooses whole sets and corresponds exactly to an exact cover. This is Class B: the hardness survives because it is carried by the disconnected diversity policy, not by the number of named candidates.

That boundary is useful rather than damaging. It says that interval quotas are genuinely softened by continuization, while arbitrary “either zero or full quota” requirements deliberately reintroduce integrality. The natural follow-up problems are to locate the boundary between interval, convex, and disconnected quota sets; to study rounding a continuous solution back to a finite committee; and to add submodular objectives or approximation guarantees.

The paper also offers a safer population-level formulation through Theorem 22, proved here using the PTAS of Skowron, Faliszewski, and Slinko. The theorem states that, for every Chamberlin–Courant objective, \(\mathrm{BCWD}\) has a PTAS. Its continuous voter-population mirror keeps the committee integral: the input is a distribution \(\mu\) over complete rankings, the committee must contain exactly \(k'\) candidates from each of two classes \(A\) and \(B\), and the objective is

\[ F_\mu(W)= \sum_{t}\mu_t\left(m-\min_{c\in W}\operatorname{pos}_t(c)\right). \]

This is the most conservative mirror because only the voter population is continuized; candidates and the committee remain discrete. Its regime is a large electorate with \(\tau\) repeated ranking types, and the expected result is a weighted version of the paper’s PTAS, with complexity measured in \(m\), \(\tau\), the mass encoding length, and \(1/\varepsilon\).

The weakest point is the candidate-mass interpretation in the first two mirrors. A hostile reader could say that selecting \(z_\theta\) changes the committee outcome space rather than merely continuizing the population. I think that objection is answerable: \(z_\theta\) is the measure of a selected subset of an atomless candidate population, and every individual still receives an integral selection decision. Nevertheless, the voter-distribution mirror based on Theorem 22 is the safest fallback because it leaves the committee itself integral.

The proposed case therefore covers Theorems 15 and 4 emphatically, with Theorem 22 providing a conservative alternative. It does not claim that every result in the paper has one continuous fate: its label-recognition and arbitrary-submodular cases would require separate analysis. The paper’s strongest contribution for ChoCo is precisely that it supplies both sides of the boundary—an \(\mathrm{NP}\)-hard discrete problem whose interval-quota mirror becomes an LP, and a nearby nonconvex-quota version where hardness remains.