| paper | Efficient Algorithms for Electing Successive Committees |
| authors | Pallavi Jain, Andrzej Kaczmarczyk |
| venue | IJCAI 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6
statement extracted from the paper’s text layer
Given candidates \(C\), a finite set \(T\) of complete rankings of \(C\), a rational distribution \(\mu\) over \(T\), integers \(\tau\) and \(k\), and a rational threshold \(\eta\), decide whether there exists an ordered sequence \(W_1,\ldots,W_\tau\) of \(k\)-candidate committees with \(f=1\) such that the committees are pairwise disjoint and \(\sum_{i=1}^{\tau}\sum_{t\in T}\mu_t\max_{c\in W_i}(m-\operatorname{pos}_t(c))\ge\eta\).
The society is a finite type set \(T\) of complete rankings with rational mass vector \(\mu\); the decision variables are the discrete ordered committees \(W_1,\ldots,W_\tau\) obeying the consecutive-frequency constraint, and the objective is \(\sum_i\sum_t\mu_t u_t(W_i)\), where \(u_t(W)=\max_{c\in W}(m-\operatorname{pos}_t(c))\).
The mirror covers the utilitarian ordinal \(\mathrm{CC}\) instances corresponding to Theorems 5 and 6, while leaving the approval variants, \(\mathrm{eCC}\), \(\mathrm{AppCC}\), threshold and weakly separable rules, egalitarian aggregation, and the paper's remaining parameterized results untreated.
The cleanest mirror is to continuize the participants, while leaving candidates, committee membership, and time discrete.
Consider a large online training service with millions of learners, a shortlisted set \(C\) of instructors, and \(H\) daily panels of size \(k\). An instructor may serve on at most \(f\) consecutive days. Learners are grouped by learning-track profiles: every learner of type \(t\) has the same complete ranking \(\succ_t\) of the instructors, and type \(t\) occupies mass \(\mu_t\), with \(\sum_t\mu_t=1\). A realistic regime might have \(N\) in the millions, \(m=20\)–\(50\) instructors, and \(r=|T|\) in the tens or hundreds. This is genuine high multiplicity: agents of the same type are indistinguishable for the problem, and only their population fraction matters.
For a committee \(W\subseteq C\), define the type-\(t\) Chamberlin–Courant utility by \(u_t(W)=\max_{c\in W}(m-\operatorname{pos}_t(c))\), and its population score by \(u_\mu(W)=\sum_{t\in T}\mu_tu_t(W)\). The continuous problem is:
\(\mathrm{CU\text{-}CC\text{-}SCE}_\infty\): given \(C,T,\mu,H,k,f\), and a rational threshold \(\eta\), decide whether there is a sequence \((W_1,\ldots,W_H)\) such that every \(W_i\) has size \(k\), each candidate appears in one contiguous block of at most \(f\) committees, and \(\sum_{i=1}^H u_\mu(W_i)\ge \eta\).
A solution is the ordered committee sequence itself. This is the exact high-multiplicity version of util-CC-SCE: if type \(t\) occurs \(n_t\) times among \(N\) voters, then \(\mu_t=n_t/N\), and the continuous score is the original score divided by \(N\). No committee is fractional, and time is not continuized; only the voting population is.
My lead anchor is Theorem 6. It is a result proved by Jain and Kaczmarczyk in this paper, although the star indicates that the proof is deferred to the full version. The theorem gives an \(O^\star(2.851^{(k-0.5501)\tau})\)-time algorithm for util-\(\beta\)-SCE, for every studied \(\beta\), when \(k\) is constant and \(f=1\). Taking \(\beta=\mathrm{CC}\) gives the short-horizon version of the problem above.
The mirror is especially convincing here. When \(f=1\), all selected committees are pairwise disjoint. Each \(k\)-set \(W\) has a rational weight \(u_\mu(W)\), computable by summing over the \(r\) types. The continuous problem therefore becomes maximum-weight packing of \(H\) disjoint \(k\)-subsets of \(C\). The weighted-set-packing machinery behind Theorem 6 works with arbitrary encoded weights, so I expect an exact algorithm with running time \(O^\star(2.851^{(k-0.5501)H})\operatorname{poly}(m,r,H,L)\), where \(L\) is the mass encoding length.
In the paper’s parameterized regime this is tractable: the population may be enormous, but the computation depends polynomially on the number of distinct types and exponentially only on the short horizon. For the unrestricted problem, however, I expect hardness to transfer rather than disappear. The difficult combinatorics lies in packing candidate committees subject to temporal constraints, not in the number of voters. Thus this is Class A under the short-horizon parameterization and Class B in general, with no reason to expect continuum-specific hardness.
A second, genuinely different anchor is Theorem 5. It is also proved in this paper and gives an \(O^\star(m!(k+1)^m)\)-time FPT algorithm for \(\alpha\)-\(\beta\)-SCE, parameterized by the number \(m\) of candidates, for both utilitarian and egalitarian aggregation and all studied scoring functions.
The corresponding problem is the few-candidate version of \(\mathrm{CU\text{-}CC\text{-}SCE}_\infty\): the input is the same rational type distribution \((T,\mu)\), but \(H\) and \(f\) are unrestricted; the question is whether a valid sequence achieves \(\sum_i u_\mu(W_i)\ge\eta\). I expect Theorem 5’s division-based dynamic program to extend to this utilitarian continuous version. Its structural guesses concern only candidates and their possible consecutive appearances. For each DP state, instead of enumerating an integer score threshold, one can store the best exact rational population score attained by that state. This should give an exact FPT algorithm in \(m\), polynomial in \(r,H\), and \(L\).
This second mirror covers a different realistic regime: a small shortlisted candidate pool but a long planning horizon. It is again Class A in the candidate-parameterized regime and Class B without that parameterization. The paper’s algorithms therefore remain meaningful after continuization, while the high-multiplicity representation removes irrelevant dependence on the total number \(N\) of participants.
The authors should recognize both mirrors as their problem. The candidates, committee size, ordered series, frequency constraint, and Chamberlin–Courant objective are unchanged. The sole transformation is replacing the voter sum by an expectation over voter types. Indeed, this paper is unusually well suited to such a mirror because voters have no individual temporal actions or personalized constraints: they influence the outcome only through their committee scores. That makes \(\mu\) a natural population object rather than an artificial weighting device.
The weakest point is that the continuous formulation may look like ordinary weighted voting rather than a new computational problem. Moreover, continuization does not make the general scheduling problem easy: with \(f=1\), it still contains weighted \(k\)-set packing, so the main hardness can survive intact. I would concede that. The positive claim is narrower: this is nevertheless a legitimate continuous-population problem, with a credible high-multiplicity regime and parameterized algorithms that remain exact for rational mass distributions. It also raises worthwhile questions: whether the known hardness reductions can be realized with \(r\ll N\), whether approximation follows from rounding \(\mu\) to finite electorates, and whether the division or packing methods can be replaced by stronger configuration-LP or column-generation approaches when \(m\) and \(H\) are both moderately large.
The strongest negative case is that both anchors continuize only the coefficients of an already discrete optimization problem. For Theorem 6, if \(\mu_t=a_t/N\), then
\[ \sum_t \mu_t u_t(W)=\frac{1}{N}\sum_t a_tu_t(W), \]
so the proposed problem is exactly the original election with \(a_t\) duplicate voters of type \(t\), represented succinctly. With \(f=1\), the problem is simply weighted \(k\)-set packing. The population contributes no feasibility constraint, no intervention variable, and no continuous object beyond rational weights. Theorem 6’s algorithm therefore survives by ordinary weighted-set-packing arithmetic; it does not reveal a new population-continuous phenomenon.
The same objection applies more strongly to Theorem 5. Its division-based dynamic program is driven entirely by candidate intervals, repetitions, and temporal adjacency. Replacing each committee’s integer score by its rational expectation under \(\mu\) merely changes comparisons in the DP. Exact rational maxima can be stored with polynomial bit complexity, yielding the same FPT result. Any richer “type” containing information beyond the ranking is irrelevant unless the problem itself is changed: the paper never uses that information. Introducing time-varying preferences, individual availability, or cross-period fairness would create a different temporal-election problem rather than a mirror of this one.
Thus neither anchor gives ChoCo a mass-transfer, pricing, convexity, or robustness question. Every rational continuous instance expands to a finite election, and the only benefit is compression of repeated voters. One could reasonably argue that this is routine weighted-election preprocessing rather than a worthwhile continuous-computational mirror.
But this negative case is ultimately weak under the programme’s stated standards. The paper has genuine named computational results; voters are interchangeable whenever they share a ranking; large electorates with repeated ballots are plainly plausible; and the rational distribution is a legitimate high-multiplicity representation whose bit complexity can differ exponentially from the expanded electorate. “Continuization does not change the combinatorics” is expressly not an admissible objection. I therefore cannot honestly defeat either anchor universally: the paper is a credible, if comparatively unexciting, candidate for a continuous-population mirror.
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.