| paper | Selecting Interlacing Committees |
| authors | — |
| venue | AAMAS 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 4.4
Given candidates \(C\), committee size \(k\), a supplied candidate order, and rational masses \(\mu_t\) on approval types \(I_t\subseteq C\), each an interval, choose \(W\subseteq C\) with \(|W|=k\) maximizing \(Pairs_\infty(\mu,W)=\sum_{t,u}\mu_t\mu_u\mathbf{1}[I_t\cap I_u\cap W\neq\varnothing]\); equivalently, decide whether this value is at least a rational threshold \(q\).
Weighted candidate-interval approval committee selection with indivisible committee \(W\), voter types \(t\), rational masses \(\mu_t\), and objective equal to the weighted measure of type pairs jointly hit by \(W\).
The paper proves the finite unweighted VCI algorithm, whereas the polynomial extension to rational masses and its bit-complexity bound are argued by the analysts rather than established in the paper.
fatal: False
The mirror covers the NP-complete Cons and Pairs threshold problems as mass-weighted variants and Proposition 4.4 as a weighted polynomial-time interval problem; it leaves the weighted Cons dynamic program and approximation trade-offs unproved.
My lead mirror is a continuous version of the paper’s Cons objective, anchored in Theorem 4.2. That theorem is proved by the authors, via an X3C reduction; the proceedings version refers omitted proof details to the full version. It states that deciding whether there is a size-\(k\) committee with \(Cons(W,\mathcal E)\ge q\) is NP-complete, even when \(q=\binom n2\), so the goal is to connect every voter.
Call the continuous problem \(Cons_\infty\)-Committee.
An instance consists of candidates \(C=\{c_1,\ldots,c_m\}\), a committee size \(k\), a finite set of approval types \(\mathcal T\subseteq 2^C\), rational masses \(\mu_t\ge0\) with \(\sum_{t\in\mathcal T}\mu_t=1\), and a rational threshold \(q\in[0,1]\). Type \(t\) is the complete approval set of a positive-mass cohort. Given \(W\subseteq C\), \(|W|=k\), construct a graph on the represented types \(t\) with an edge between \(t\) and \(u\) whenever \(t\cap u\cap W\neq\varnothing\). Let \(\mathcal K_W\) be its connected components and \(\mu(K)=\sum_{t\in K}\mu_t\). Define
\[ Cons_\infty(\mu,W)=\sum_{K\in\mathcal K_W}\mu(K)^2. \]
The question is whether some size-\(k\) committee satisfies \(Cons_\infty(\mu,W)\ge q\), with the optimization version asking for a maximizing committee. The value is the limiting fraction of unordered voter pairs connected by the selected committee: if type \(t\) is replicated \(n_t\) times and \(\mu_t=n_t/N\), then normalized finite \(Cons\) converges to this expression as the multiplicities grow. A type that approves no selected candidate contributes no connected pairs, as it should.
The regime is a large national consultation or parliamentary election with millions of voters but relatively few approval cohorts: for example, citizens with the same issue profile approve the same contiguous block of candidates on a left–right spectrum. The population might have \(N\) in the millions and \(\tau=|\mathcal T|\) in the hundreds or thousands. The paper itself explicitly notes that each voter in its examples could represent a quarter of a large electorate. This is therefore not an invented mean-field story: it is the paper’s voter hypergraph after quotienting repeated, computationally indistinguishable vertices into mass types.
Theorem 4.2 transfers especially cleanly for its all-connected special case. Set \(q=1\). Then \(Cons_\infty(\mu,W)=1\) exactly when every positive-mass type is represented and the type graph is connected. Given a finite election, merge voters with identical approval sets and assign every resulting type positive mass. The original voters are all connected under \(W\) if and only if the quotient type graph is connected. Thus the paper’s NP-hardness yields NP-hardness for the continuous all-connected problem. I would classify this mirror as Class B: hardness transfers because the combinatorics lives in selecting candidates, not in the number of voter copies. The continuous formulation remains meaningful in high-multiplicity instances even though its general hardness does not depend on multiplicity.
A second anchor is Theorem 4.1, also proved in this paper from X3C. It concerns threshold maximization of \(Pairs\), with committees of size at most \(k\). The corresponding problem is \(Pairs_\infty\)-Threshold:
\[ Pairs_\infty(\mu,W) = \sum_{t,u\in\mathcal T} \mu_t\mu_u\, \mathbf 1[t\cap u\cap W\neq\varnothing]. \]
This is the limiting fraction of voter pairs sharing at least one selected candidate. The instance asks whether some \(W\subseteq C\), \(|W|\le k\), has \(Pairs_\infty(\mu,W)\ge q\). The action remains an ordinary indivisible committee; only the electorate is continuous.
This is recognizably the paper’s objective rather than a tractable substitute. Each candidate covers the pair-types whose two approval sets both contain it, and the objective is the weighted union of those pair sets. I expect the unrestricted problem to be Class B, essentially a weighted maximum-coverage problem. The paper’s Theorem 4.1 is strong evidence, although its proof does not by itself establish a gap-preserving reduction for the atomless normalization; that would be a worthwhile technical lemma. The continuous version also immediately gives a greedy \(1-1/e\)-approximation because \(Pairs_\infty\) is a monotone submodular function of \(W\).
The paper’s positive structured result gives a third, more algorithmic mirror. Proposition 4.4, proved in the paper using the existing polynomial-time algorithms for Chamberlin–Courant on the candidate-interval domain, states that a committee maximizing \(Pairs\) can be computed in polynomial time for VCI elections. Define \(CI\text{-}Pairs_\infty\) by additionally giving an order \(c_1,\ldots,c_m\) in which every approval type is an interval \(I_t\). Each pair of types then induces the interval \(I_t\cap I_u\), with weight \(\mu_t\mu_u\). The problem is to select \(k\) candidate positions maximizing the total weight of pair-intervals hit by at least one selected position.
I expect this version to be Class A. The associated pair instance has at most \(\tau^2\) weighted voter types, and the interval dynamic program extends from unit counts to rational weights using only additions and comparisons of numbers of encoding length polynomial in \(L\). Thus the expected running time is polynomial in \(m,\tau,L\), independent of the actual electorate size \(N\). This is exactly the kind of payoff the programme seeks: the finite paper’s VCI structure becomes a weighted interval-coverage problem over population types.
I would not claim that every result in the paper has already been mirrored. In particular, I would leave Theorem 4.5, the polynomial-time Cons algorithm on VCI profiles, as a follow-up rather than an anchor. Its finite dynamic program uses the number of voters in a connected component as a state. Replacing that integer by an arbitrary rational mass may require a new representation of attainable component masses; it is not automatically polynomial in \(\tau\) and \(L\). Likewise, the approximation trade-offs in Propositions 5.1–5.11 would require careful continuous definitions of AV, CC, and especially EJR. None of that is needed for the present case.
The weakest point is that population continuization does not make committee selection itself divisible. In the general problem, \(W\) is still a discrete \(k\)-subset, so the continuous model may preserve NP-hardness rather than unlock an LP. Moreover, the strongest hardness transfer uses the support graph and therefore does not rely on large multiplicities. But that is a limitation of the expected complexity outcome, not a failure of the mirror: the population is genuinely a distribution over approval types, the objective is the fraction of society’s connected pairs, and the VCI restriction produces a new weighted polynomial-time problem. The additional questions are whether general \(Cons_\infty\) admits useful approximation guarantees, whether the VCI Cons dynamic program has a polynomial weighted analogue, and how finite-election optima round to and from the continuous values.
The strongest negative case is that these mirrors do not produce the programme’s characteristic continuous-optimization phenomenon. The committee remains an indivisible \(k\)-subset, and continuization merely replaces voter counts by weights. For Theorem 4.2, this criticism is especially sharp: at \(q=1\), \(Cons_\infty(\mu,W)=1\) depends only on whether the positive-mass type graph is connected. The actual values of the masses disappear. The reduction therefore establishes ordinary committee-connectivity hardness, not continuum-specific difficulty or an LP-shaped problem. Its hardness also does not require a genuinely compressed regime: one can replicate every voter arbitrarily many times, but the number of types may still grow with the reduction.
That objection does not defeat the mirror under the programme’s rules. Theorem 4.2 transfers exactly after quotienting identical approval sets. If a type has positive mass, its clones are mutually connected whenever that type is represented; hence the quotient graph is connected exactly when the original voter graph is connected. The fact that the resulting problem is Class B rather than Class A is explicitly an allowed outcome. A stronger mass-sensitive version with \(q<1\) is also natural: it asks for the maximum population mass lying in connected components, not merely all-or-nothing connectivity. That is an extension, but one the paper’s authors would clearly recognize.
Theorem 4.1 is harder to dismiss. The proposed \(Pairs_\infty\) objective is precisely the rational-clone limit of the finite objective. For rational masses, denominator clearing recovers a finite election with identical winning committees and normalized objective values. The problem becomes weighted maximum coverage over pairs of approval types, with weights \(\mu_t\mu_u\). This is familiar algorithmically, but familiarity is not a modelling failure: it is a legitimate high-multiplicity computational problem, and it immediately supports exact, approximation, and parameterized questions. The proponent may overstate the theorem’s direct implication for arbitrary weighted instances—the reduction only gives the special rank-one weights induced by \(\mu_t\mu_u\)—but the clone correspondence itself is sound.
Proposition 4.4 is the strongest surviving anchor. In the candidate-interval domain, every approval type is an interval \(I_t\), and every pair of types produces the interval \(I_t\cap I_u\) with weight \(\mu_t\mu_u\). Thus \(Pairs_\infty\) is weighted interval coverage by \(k\) candidate positions. The finite dynamic program extends using rational addition and comparison; there are at most \(\tau^2\) pair types, and the arithmetic bit length remains polynomial. This gives a genuine Class A algorithm whose running time depends on \(m\), \(\tau\), and the mass encoding length rather than on the electorate size.
The remaining criticism is therefore one of novelty and depth, not validity: the paper is unusually amenable to high-multiplicity compression, but its continuous mirrors may mostly expose weighted versions of already familiar coverage and connectivity problems. That is not enough to reject it. No identity, history, atomless-incentive, or indivisibility obstruction applies; the objectives depend only on approval types, and the paper itself supplies a natural large-electorate interpretation.
So the honest negative case is weak. Theorem 4.2 supplies a direct Class B mirror, Theorem 4.1 supplies a mass-sensitive weighted mirror, and Proposition 4.4 supplies a clean Class A mirror. The only real reservations are that the hardness transfer is population-insensitive and that the weighted extensions need formal proofs. Neither supports the universal claim that no worthwhile continuous mirror exists.
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.