| paper | Multiwinner Voting with Fairness Constraints |
| authors | L. Celis, Lingxiao Huang, Nisheeth K. Vishnoi |
| venue | IJCAI 2018 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: There exists an absolute constant \(c>0\) for which attaining a \(c\log\Delta/\Delta\)-approximation is NP-hard, even with uniform positive rational masses and an explicit feasible committee. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), candidate groups \(P_1,\ldots,P_p\), upper bounds \(u_i\), and a rational distribution \(\mu\) over complete ranking types, promised that some committee \(S\) with \(|S|=k\) satisfies \(|S\cap P_i|\le u_i\), compute or approximate a feasible committee maximizing \(\operatorname{score}_\mu(S)=\sum_t\mu_t\mathbf{1}[\operatorname{top}(t)\in S]\), with complexity measured in the type representation and mass encoding.
The society is a distribution \(\mu\) over complete voter-ranking types; the decision variable is an integral committee \(S\subseteq C\) of size \(k\); the objective is the \(\mu\)-weighted SNTV representation score; and feasibility is imposed by discrete overlapping candidate-group quotas.
The mirror directly covers Theorems 9 and 14 by replacing the explicit voter list with type masses \(\mu_t\). It leaves the feasibility results in Theorems 6–8, the other approximation results, and the empirical section outside the proposed mirror.
I think this paper admits a credible continuous mirror, with Theorem 9 as the strongest anchor.
The natural mirror keeps candidates, committees, and candidate-side fairness constraints discrete, and continuizes only the voter population. Let \(C\) be the \(m\) candidates, \(k\) the committee size, and \(P_1,\ldots,P_p\subseteq C\) the possibly overlapping candidate groups. A voter type \(t\) is a complete preference list \(\succ_t\); the society is a rational distribution \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) with \(\sum_t\mu_t=1\). Thus \(\mu_t\) is the fraction of users having preference type \(t\).
This is plausible for news recommendation or product selection: millions of users may fall into a much smaller number of recurring preference profiles, while the selected \(k\) items must respect quotas across political, commercial, or demographic categories. Candidate memberships remain ordinary finite attributes; they are not being continuized.
For SNTV, define
\[ \operatorname{score}_{\mu}(S) = \sum_{t\in T}\mu_t \mathbf{1}\!\left[\operatorname{top}(\succ_t)\in S\right]. \]
The committee remains integral: \(S\subseteq C\), \(|S|=k\), and
\[ \ell_i\le |S\cap P_i|\le u_i \]
for every group. The objective is to maximize \(\operatorname{score}_{\mu}(S)\), the fraction of the population represented by its favourite selected candidate.
This is an exact high-multiplicity version of the paper’s model. If \(\mu_t=n_t/n\), expanding type \(t\) into \(n_t\) identical voters gives exactly the paper’s SNTV score divided by \(n\). Conversely, any finite profile can be compressed into its distinct types. Replicating every type arbitrarily many times produces a genuinely large population without changing the continuous instance.
My lead anchor is Theorem 9, an authors’ result in this paper; its formal proof is deferred to the full version, and it uses the external hardness of maximum \(\Delta\)-hypergraph matching from Hazan, Safra, and Schwartz. The theorem states:
A feasible constrained multiwinner voting problem with \(\ell_i=0\) for every group is NP-hard to approximate within a factor of \(\Omega(\log\Delta/\Delta)\), even when the scoring function is SNTV.
The reduction is from maximum \(\Delta\)-hypergraph matching and works even for feasible instances.
The corresponding continuous problem is therefore:
Continuous-Population Fair SNTV. Given \(C,k,P_1,\ldots,P_p,u_1,\ldots,u_p\), a rational distribution \(\mu\) over preference types, and the promise that some size-\(k\) committee satisfies \(|S\cap P_i|\le u_i\) for every \(i\), find a feasible committee maximizing \(\operatorname{score}_\mu(S)\). Determine whether a polynomial-time algorithm can guarantee a factor better than \(\Omega(\log\Delta/\Delta)\).
I expect the hardness to transfer, placing this mirror in Class B. The reduction’s combinatorics live in the candidate/group-incidence structure, not in the number of named voters. Replacing repeated voters by mass changes neither feasible committees nor approximation ratios. Indeed, every finite hard instance can be replicated to make the population arbitrarily larger than its number of types. This is precisely the kind of case where continuization should preserve hardness rather than dissolve it.
A useful secondary anchor is Theorem 14, also an authors’ result in this paper, with the complete proof supplied in the full version. It states:
Given a feasible constrained monotone-submodular multiwinner instance with \(\Delta=1\), there is a randomized polynomial-time \((1-1/e)\)-approximation algorithm.
Here \(\Delta=1\) means that the candidate groups are pairwise disjoint. The theorem applies to the paper’s monotone submodular score functions, including the relevant Chamberlin–Courant variants.
Its continuous counterpart is:
Continuous-Population Disjoint-Group MS Committee Selection. Given \(C,k\), pairwise disjoint candidate groups \(P_i\), integer bounds \(\ell_i,u_i\), and a rational type distribution \(\mu\), maximize
\[ F_\mu(S)=\sum_{t\in T}\mu_t f_t(S) \]
over feasible size-\(k\) committees, where each \(f_t\) is the per-voter monotone submodular score induced by type \(t\), such as the \(\alpha\)-CC or \(\beta\)-CC contribution. A solution is an integral committee \(S\), not a fractional committee or lottery.
The paper’s Theorem 14 gives a randomized polynomial-time \((1-1/e)\)-approximation, with expected score at least \((1-1/e)\operatorname{OPT}\). In the type-compressed representation, the relevant complexity is polynomial in \(m\), \(\tau\), and the encoding length of the masses, rather than in the expanded population size. I would classify this mirror as Class A, although the tractability is inherited rather than caused solely by continuization.
This case deliberately covers only Theorems 9 and 14. I would not use Theorems 6–8 as primary anchors: their feasibility problems ignore voter scores almost entirely, so the population distribution would be inert. I also would not treat the multilinear extension in Definition 10 as the mirror itself. That is an outcome-space relaxation used inside the paper’s algorithm; the proposed mirror leaves the committee integral and changes only the population representation.
The weakest point is that, for Theorem 9, continuization does not make the problem easier or create a new LP phenomenon. It is essentially a mathematically exact weighted-profile compression. The opposing analyst can fairly say that the hardness result is driven by candidate-side constraints. My answer is that this is still a legitimate continuous-population question under the programme: the point is not that every mirror becomes tractable, but to determine whether hardness survives high multiplicity. Here the answer is plausibly yes, and Theorem 9 gives a clean, named hardness boundary.
The resulting follow-up questions are whether \(\tau\), \(\Delta\), or \(k\) yield useful parameterized algorithms; whether population-dependent proportionality bounds \(u_i(\mu)\) change the classification; and whether overlapping groups with \(\Delta\ge2\) produce any genuinely continuum-specific hardness beyond the transferred hypergraph-matching obstruction.
The strongest negative case is that both anchors leave the population as a passive coefficient vector rather than making it the computational object.
For Theorem 9, this is especially stark. Under SNTV, define
\[ w_c=\sum_{t:\operatorname{top}(t)=c}\mu_t . \]
Then
\[ \operatorname{score}_{\mu}(S)=\sum_{c\in S}w_c. \]
All rankings with the same top candidate are indistinguishable for this problem, so the entire society collapses to at most \(m\) candidate weights. The hard part is selecting candidates subject to the overlapping constraints \( |S\cap P_i|\le u_i \); the population contributes only objective coefficients. Giving voters richer ranking types cannot help, because SNTV ignores the extra information. Making candidate selection fractional would change the outcome problem, not continuize the population.
Thus the proposed mirror is more accurately a weighted hypergraph-packing problem with a voting interpretation. Its instances can be padded with arbitrarily many duplicate voters, but that padding does not create a new population-level object. This is the best argument against calling Theorem 9 a worthwhile continuous-computational mirror.
It is not, however, a decisive objection under the programme’s rules. High multiplicity is expressly about replacing repeated individuals by rational masses, and the programme’s own example—“\(23\%\) of voters favour \(c\)”—has exactly the form \(w_c\). Theorem 9 therefore gives a legitimate Class B question: does the candidate-side constrained selection problem remain hard when voter multiplicity is represented compactly? The fact that the answer may be “yes” is not a defect. Nor can one object that the hardness lies in the candidates; the programme explicitly permits that.
Theorem 14 is a weaker anchor for a negative case. For any explicit per-type score contribution \(f_t\), the continuous objective is
\[ F_\mu(S)=\sum_t \mu_t f_t(S). \]
If each \(f_t\) is monotone submodular, then \(F_\mu\) is also monotone submodular. The continuous-greedy and dependent-rounding proof therefore applies unchanged. The paper’s theorem already treats the aggregate score as an arbitrary monotone-submodular oracle, so population continuization does not introduce a new optimization mechanism; it only supplies a compressed way to evaluate that oracle.
A population-dependent proportionality constraint does not rescue the anchor very much. Bounds such as
\[ \ell_i(\mu)=\lfloor kq_i(\mu)\rfloor,\qquad u_i(\mu)=\lceil kq_i(\mu)\rceil \]
remain integer committee constraints and change only at discrete thresholds. Allowing fractional committee membership or lotteries would create an outcome-space relaxation, which is outside the requested scope. Consequently, the natural continuous version of Theorem 14 is mainly a high-multiplicity implementation question: can the weighted score be represented and queried in time polynomial in the number of types and the bit-length of the masses? That is potentially useful, but the paper itself does not motivate it as a population-computational phenomenon.
Still, this only downgrades Theorem 14; it does not defeat it. Rational masses may have exponentially large denominators, so the paper’s polynomial-time bound in the expanded voter count does not automatically yield a polynomial-time algorithm in compressed input length. Establishing that bound is a legitimate high-multiplicity result.
Accordingly, an unconditional negative verdict is not defensible. The best negative case is that Theorem 14 is largely a repackaging of weighted submodular maximization and that Theorem 9 produces no genuinely continuum-specific structure. But Theorem 9 remains a valid continuous-population mirror under the programme’s stated definition, and it alone defeats the claim that no worthwhile mirror exists in any scenario.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.