| paper | DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections |
| authors | Kunal Relia |
| venue | IJCAI 2022 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), committee size \(k\), positional scoring vector \(s\), finite support \(T\) of complete ranking types, and rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), output a committee \(W\subseteq C\) with \(|W|=k\) maximizing \(\operatorname{CC}_{s,\mu}(W)=\sum_{t\in T}\mu_t\max_{c\in W}s(\operatorname{pos}_t(c))\).
A high-multiplicity Chamberlin–Courant election with complete-ranking types \(T\), rational society masses \(\mu\), integral committee variable \(W\), fixed committee size \(k\), and aggregate representative-utility objective \(\sum_{t\in T}\mu_t\max_{c\in W}s(\operatorname{pos}_t(c))\).
The mirror directly covers Theorems 5 and 6, including representation-constrained separable winner determination and unconstrained Chamberlin–Courant hardness; it leaves the remaining complexity, approximability, heuristic, Monroe, and empirical results unmirrored.
The strongest case is that DiRe has a genuine high-multiplicity mirror, although the expected answer for that mirror is Class B rather than tractability. The paper’s representation constraints are already population-level constraints, and its score is an aggregate over voters. That makes the transition to a distribution over voter types unusually direct.
My lead anchor is Theorem 5, proved by this paper through a reduction from vertex cover. The conference version gives a proof sketch and refers to the extended version for the full proof; it is not merely a cited result. The theorem states that when the paper’s candidate-attribute parameter is \(\mu=0\), there is at least one voter attribute, \(\pi\ge1\), and \(f\) is monotone and separable, \((\mu,\pi,f)\)-DRCWD is NP-hard, even when every representation lower bound is \(1\).
A natural continuous problem mirroring this result is \(\mathrm{Rep\text{-}kBorda\text{-}DRCWD}_\infty\). An instance consists of a finite candidate set \(C\), a committee size \(k\), and a finite set \(T\) of voter types. Each type \(t\in T\) contains a complete ranking \(\succ_t\) of \(C\), together with its voter-population labels. The society is a rational distribution \(\mu=(\mu_t)_{t\in T}\), where \(\sum_t\mu_t=1\). The input also specifies voter populations \(P\), each represented as a subset of types, together with a size-\(k\) committee \(W_P\) for that population, exactly as in the paper’s Definition 5. We impose the paper’s representation requirement
\[ |W\cap W_P|\ge 1 \]
for every population \(P\).
For Borda, define the aggregate candidate score
\[ b_\mu(c)=\sum_{t\in T}\mu_t\bigl(m-\operatorname{pos}_t(c)\bigr). \]
The task is to output a size-\(k\) committee \(W\subseteq C\) maximizing
\[ \sum_{c\in W} b_\mu(c) \]
subject to all representation constraints. The committee remains an integral subset of candidates; only the electorate has been continuized. If the input uses a different monotone separable positional rule, replace the Borda expression by its corresponding expected candidate score.
This is recognizably the paper’s problem. The population committee \(W_P\) is still the local winning committee that the paper requires the global committee to represent; the global objective is still the aggregate separable score; and the representation threshold is still one candidate, independent of population size. The only change is that \(n\) named voters with identical relevant data are represented by one type with mass. A plausible regime is a large recommendation or public-consultation platform with millions of users divided into regions, languages, or demographic populations. Users may fall into a moderate number of recurring complete-ranking profiles, while each population supplies its own local top-\(k\) committee \(W_P\). A population representing \(0.5\%\) of users can still receive one representative, just as the paper’s fairness motivation requires.
I would expect this problem to be Class B. Given a discrete election, put mass \(\mu_t=n_t/n\) on each distinct ranking-and-population type. Multiplying all aggregate scores by \(n\) gives exactly the discrete objective, while the representation constraints are unchanged. If one wants a visibly high-multiplicity realization, replicate every voter type \(R\) times; the distribution and the support \(T\) remain unchanged while the number of agents becomes arbitrarily large. The hardness therefore survives because the combinatorics live in the candidate set and the incidence pattern of the population committees \(W_P\), not in the number of named voters. This is precisely the programme’s Class B phenomenon.
The main follow-up question is whether Theorem 5 remains hard under the more endogenous requirement that \(W_P\) must itself be computed from the conditional distribution of population \(P\), rather than supplied as part of the input. That would be a stricter and arguably more elegant continuous model. Other natural questions concern parameterization by \(k\), the number of populations, the number of types per population, or the treewidth of the candidate–population incidence graph.
A second, cleaner anchor is Theorem 6, also presented as a result of this paper and proved using the Chamberlin–Courant rule. It states that DRCWD is NP-hard for monotone submodular scoring functions even when there are no candidate attributes and no voter attributes, \(\mu=\pi=0\). By Observation 1, this contains unconstrained committee winner determination as a special case.
The corresponding problem is \(\mathrm{CC}_s\text{-Winner}_\infty\). An instance consists of \(C\), \(k\), a finite support \(T\) of complete ranking types, rational masses \(\mu_t\), and the positional scoring vector \(s\) used by the Chamberlin–Courant rule. For a committee \(W\), its continuous score is
\[ \operatorname{CC}_{s,\mu}(W) = \sum_{t\in T}\mu_t \max_{c\in W}s\bigl(\operatorname{pos}_t(c)\bigr). \]
The task is to output a size-\(k\) committee maximizing this quantity. This is the exact high-multiplicity version of the paper’s unconstrained CC winner-determination problem: every voter’s contribution is replaced by the mass of the type producing that contribution, but the candidates, rankings, committee size, and winner-selection objective are unchanged.
The natural regime is again substantial. For example, a platform may select \(k\) items from a fixed catalogue for a very large user base, where users are clustered into a moderate number of recurring preference profiles. The CC objective says that each user type is represented by its most preferred selected item. This is precisely a population interpretation of the paper’s representative-committee objective, not a fractional or probabilistic outcome model.
Here too the expected classification is Class B. A discrete CC election embeds by setting \(\mu_t\) equal to the fraction of voters of type \(t\). The continuous score is then the discrete score divided by \(n\), so the maximizing committees are identical. Replicating every type produces arbitrarily large populations without changing the instance at the level of types. There is no honest reason to expect the continuum to dissolve this hardness: the reduction’s structure is in the candidate and ranking incidence pattern, not in the multiplicity of agents.
This second mirror generates questions about whether CC becomes tractable for bounded \(k\), bounded numbers of ranking types, or restricted ranking domains, and about approximation algorithms whose guarantees depend on \(\tau=|T|\) rather than on the underlying population size.
The scope of this case is deliberately limited. It covers Theorem 5’s representation-constrained separable slice and Theorem 6’s unconstrained submodular slice. It does not claim to continuize every diversity-constraint result, the size-optimization in Theorems 7–9, the Monroe rule, or the heuristic algorithm.
The weakest point is that the first mirror can be criticized as “normalizing the voter counts” while leaving the hardest part—the binary committee and the supplied \(W_P\) sets—untouched. That criticism is fair. This is not a strong claim that continuization makes DiRe tractable. The positive claim is narrower: DiRe has a faithful continuous-population formulation, its high-multiplicity regime is socially plausible, and its main hardness results survive as meaningful Class B boundaries. The paper’s use of voter populations is therefore supporting evidence for the mirror, not a novelty collision with it.
The strongest negative case is asymmetric: Theorem 5 is a weak anchor, but Theorem 6 defeats the universal negative claim.
Theorem 5’s representation constraints do not genuinely use population mass. Once each \(W_P\) is supplied, the population \(P\) matters only as a label for the constraint
\[ |W\cap W_P|\ge 1. \]
The same instance can therefore be written as a weighted separable committee problem subject to an arbitrary family of candidate-subset constraints. The hard object is the candidate–constraint incidence system, not the distribution over voters. A zero-mass or arbitrarily small population would impose exactly the same obligation as a large one. That makes the proposed mirror formally valid but conceptually thin: the “population” is bookkeeping around an exogenous set system.
A stronger formulation would derive \(W_P\) from the conditional distribution of types in \(P\), rather than supplying it. That is a sensible new research problem, but it is no longer the problem proved hard in Theorem 5. The theorem allows the \(W_P\) sets to encode essentially arbitrary combinatorial structure; requiring them to be local winners may destroy that encoding. Conversely, making representation quotas depend on \(\mu(P)\) would give mass a substantive role, but would change the paper’s deliberately size-independent representation principle. Thus Theorem 5 does not by itself establish a worthwhile continuous mirror of the paper’s representation result.
Theorem 6 is different. Its Chamberlin–Courant slice has an exact and natural high-multiplicity formulation. With ranking types \(t\) and masses \(\mu_t\),
\[ \operatorname{CC}_{s,\mu}(W) = \sum_{t\in T}\mu_t \max_{c\in W}s(\operatorname{pos}_t(c)). \]
This is precisely the discrete CC objective divided by the number of voters when \(\mu_t\) is the fraction of voters of type \(t\). It preserves the paper’s candidates, rankings, integral committee, committee size, and representation objective. No individual identity, arrival time, or private datum is lost. A recommendation platform with millions of users clustered into recurring preference profiles is an entirely credible high-multiplicity regime.
Replicating every type arbitrarily many times gives societies with very large populations while leaving the type distribution unchanged. The fact that the reduction’s support may grow with the number of candidates does not invalidate the mirror: high multiplicity is an instance regime, not a promise that the number of types is constant. Restricting \(\tau\) would be a further parameterized question, not a prerequisite for legitimacy.
Nor can this be dismissed as “only normalization” or as an inert Class B restatement. The programme explicitly treats faithful hardness transfer as a valuable outcome: it identifies where continuization does not remove the combinatorial difficulty. The continuous problem also exposes the correct complexity parameters \(m\), \(\tau\), and encoding length, and supports questions about bounded type support, restricted ranking domains, approximation, and parameterized algorithms.
Accordingly, I can make a credible negative case against Theorem 5 as the main anchor, but I cannot honestly defeat the Theorem 6 mirror. It is a clean, socially plausible, computationally defined population continuization with no identity or degeneracy objection. The universal claim that DiRe has no worthwhile continuous mirror therefore fails.
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.