| paper | Algorithmics of Egalitarian versus Equitable Sequences of Committees |
| authors | Eva Michelle Deltl, Till Fluschnik, Robert Bredereck |
| venue | IJCAI 2023 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given \(C\), \(\tau\), \(k\), \(y\), a finite support \(T\subseteq(C\cup\{\varnothing\})^\tau\), rational masses \(\mu_\sigma\ge0\) summing to \(1\), and rational \(X\), decide whether there are integral committees \(D_1,\ldots,D_\tau\subseteq C\) with \(|D_t|\le k\), \(\sum_{\sigma\in T}\mu_\sigma\mathbf{1}[\sigma_t\in D_t]\ge X\) for every \(t\), and \(\sum_{t=1}^{\tau}\mathbf{1}[\sigma_t\in D_t]\ge y\) for every \(\sigma\in T\) with \(\mu_\sigma>0\).
Types are complete nomination trajectories \(\sigma\in(C\cup\{\varnothing\})^\tau\), and \(\mu_\sigma\) is population mass. The decision variables are the shared integral committees \(D_t\); the objective is feasibility subject to level mass threshold \(X\) and per-positive-mass-type score threshold \(y\).
The mirror covers Theorem 3, Theorem 7, and the QCSE component of Proposition 3. It leaves the kernelization bounds, most level and parameter dichotomies, Proposition 2, and the generalized OWA variants without separate continuous analyses.
The strongest positive case is a typed high-multiplicity version of the paper’s own model. It preserves integral committees and the temporal nomination structure; only the population becomes continuous.
Let \(C\) be the candidate set and let a voter type be a complete nomination trajectory \(\sigma=(\sigma_1,\ldots,\sigma_\tau)\in(C\cup\{\varnothing\})^\tau\). A society is a rational distribution \(\mu\) over a finite support \(T\) of such trajectories. The mass \(\mu_\sigma\) is the fraction of voters of type \(\sigma\). A solution is still an integral committee sequence \(D_1,\ldots,D_\tau\), with \(D_t\subseteq C\) and \(|D_t|\le k\). Its level-\(t\) satisfaction is
\[ S_t(D,\mu)=\sum_{\sigma\in T}\mu_\sigma\mathbf 1[\sigma_t\in D_t], \]
and the score of type \(\sigma\) is
\[ r_\sigma(D)=\sum_{t=1}^{\tau}\mathbf 1[\sigma_t\in D_t]. \]
The continuous decision problem asks whether \(S_t(D,\mu)\ge X\) for every level and \(r_\sigma(D)\ge y\) for every positive-mass type \(\sigma\); the equitable version replaces the last inequality by \(r_\sigma(D)=y\). The objective is feasibility at the supplied population-fraction threshold \(X\), exactly as the paper’s objective is feasibility at the count threshold \(x\).
This is an exact high-multiplicity dictionary. Given \(N\) finite voters, set \(\mu_\sigma=N_\sigma/N\) and \(X=x/N\). Conversely, any rational \(\mu\) can be expanded into a finite population of clones. Crucially, mass does not choose different committees independently: all members of a type face the same public committee sequence. Thus the egalitarian or equitable condition remains a genuine per-agent condition, not a fractional relaxation.
The regime is natural for the paper’s own applications: a large festival, multi-day event, curriculum, or public programme chooses at most \(k\) activities per day from a common menu. A large population may consist of recurring cohorts with identical full nomination trajectories. The relevant comparison is \(N\gg |T|\), not merely “many voters”; the complete trajectory, including all levels, is the type.
My lead anchor is Theorem 3, proved in this paper. It states that both GCSE and QCSE are solvable in \(2^{k\cdot\tau^2}\operatorname{poly}(n+m+\tau)\) time, hence are fixed-parameter tractable for \(k+\tau\).
The corresponding problem is:
Small-Sequence GCSE\(_\infty\). The input is \((C,T,\mu,k,\tau,X,y)\), with rational masses \(\mu_\sigma\), and the question is whether there is a sequence \(D_1,\ldots,D_\tau\) with \(|D_t|\le k\), \(S_t(D,\mu)\ge X\) for every \(t\), and \(r_\sigma(D)\ge y\) for every \(\sigma\in T\).
I expect this to be Class A. The proof of Theorem 3 branches on the fingerprint of an unsatisfied agent, namely which levels satisfy that agent. In the typed model, one branches on an unsatisfied type instead. There are at most \(2^\tau\) fingerprints, and at most \(k\tau\) candidate selections in the whole sequence. The per-level threshold updates become rational mass additions rather than integer count additions. Hence the same argument should give a running time of the form
\[ 2^{k\cdot\tau^2}\operatorname{poly}(|T|+m+\tau+L), \]
where \(L\) is the encoding length of the rational data. This is a meaningful population-continuous result: the population may be arbitrarily large and the number of types need not be a parameter.
The second anchor is Theorem 7, also proved here. It states that each of GCSE and QCSE is solvable in \(O((y+1)^n2^n n\tau)\) time. Its typed analogue is a genuinely different question:
Small-Support QCSE\(_\infty\). Given a rational type distribution \(\mu\) over \(T\), integers \(k,\tau,y\), and a rational level threshold \(X\), decide whether there is a committee sequence \(D_1,\ldots,D_\tau\) satisfying \(S_t(D,\mu)\ge X\) for every \(t\) and \(r_\sigma(D)=y\) for every positive-mass type \(\sigma\).
This should be fixed-parameter tractable in \(|T|+y\), even when the number of physical voters is enormous. The dynamic-programming state records the current satisfaction count of each type, so there are at most \((y+1)^{|T|}\) states. At each level, only the satisfaction fingerprint over \(T\) matters. Candidates never nominated by a positive-mass type can be discarded, leaving at most \(|T|\) relevant candidates per level and at most \(2^{|T|}\) fingerprints to test. The expected running time is therefore
\[ O\!\left((y+1)^{|T|}2^{|T|}|T|\tau\operatorname{poly}(L)\right). \]
This anchor is particularly good for continuization because the algorithm exploits precisely what high multiplicity supplies: many named voters collapse to a small number of complete behavioural types. The equitable condition remains exact at the type level.
The boundary anchor is Proposition 3, proved in this paper using reductions from 3-SAT and EXACTLY-1-IN-3-SAT. It states that for at least three levels and \(x=0\), GCSE and QCSE with \(k\ge m\) are NP-hard, with the stated ETH lower bound.
The matching continuous problem is:
Three-Level QCSE\(_\infty\). The input is a rational distribution over complete three-level nomination trajectories, with \(X=0\), \(k\ge m\), and \(y=1\). Decide whether there are committees \(D_1,D_2,D_3\) such that every positive-mass type is satisfied in exactly one of the three levels.
This is Class B: hardness transfers. Take the construction in Proposition 3 for EXACTLY-1-IN-3-SAT, assign positive rational mass to every constructed voter type, and impose exactly the same typewise condition. The proof’s gadget forces one of the two candidates associated with each variable to be selected consistently across all three levels; a clause type is satisfied exactly once precisely when its clause has exactly one true literal. Arbitrarily many physical clones can be attached to every constructed type without changing the instance’s solution set. Thus the continuous formulation is recognizable as the paper’s problem, while the hardness is driven by the variable/clause and level structure rather than by population multiplicity.
I would not claim that these arguments cover the paper’s kernelization results, Proposition 2’s two-level polynomial case, or the general OWA variants without separate proofs. The mirror covers Theorem 3, Theorem 7, and the QCSE component of Proposition 3.
The weakest point is that population mass is most visible in the level constraints; the per-type fairness constraint itself is discrete, and in the \(X=0\) hardness anchor mass is mathematically dormant. The action is also an integral common committee sequence rather than a fractional committee. So this is not yet a continuous optimization model in the strongest LP sense. But that is a limitation of scope, not a failure of the mirror: it is a faithful continuous population model, it has exact finite/high-multiplicity correspondence, it yields new type-sensitive algorithmic questions, and it preserves a genuine hardness boundary rather than smoothing the paper into an easier but different problem.
The strongest case against is that the proposed mirror has a continuity trilemma. If it preserves the paper’s semantics, committees remain integral and every positive-mass type must receive the same per-agent guarantee. Then, for fixed support, the type scores
\[ r_\sigma(D)=\sum_{t=1}^{\tau}\mathbf 1[\sigma_t\in D_t] \]
are completely independent of \(\mu\); only the per-level threshold uses population mass. A type of arbitrarily small positive mass remains fully binding, and disappears entirely at mass zero. Thus the fairness objective has no continuous limit. Replacing typewise fairness by a mass-based guarantee would make \(\mu\) genuinely central, but would no longer mirror GCSE or QCSE. Fractionalizing committees would restore convexity, but that continuizes the outcome space, which is outside ChoCo’s scope.
Theorem 3 therefore gives the best negative attack. Its fingerprint branching proof extends almost mechanically from integer agent counts to rational type masses: subtract rational masses instead of integer counts. This is a legitimate compressed high-multiplicity encoding, but its algorithm never uses population divisibility or continuous optimization. It branches on at most \(k\tau\) candidate choices and performs arithmetic on weights. The same statement could be made for a finite instance with binary-encoded multiplicities, without introducing a continuous society. The result is consequently about bounded trajectory diversity, not about a population continuum.
Theorem 7 has the same weakness more visibly. The proposed dynamic programme is parameterized by \(|T|\), not by anything intrinsically continuous. It is simply the paper’s finite-state DP after replacing named agents by duplicate-profile classes. The masses affect only whether a committee fingerprint reaches the level threshold; the state and the equitable condition depend solely on the support types. A more genuinely mass-sensitive formulation would have to allow fractional satisfaction or require only a specified fraction of each behavioural class to be treated fairly, both of which change the paper’s problem.
Proposition 3 is the weakest anchor for the proponent’s stated purpose. Its reduction sets \(x=0\), so every level-satisfaction constraint is vacuous. In the proposed QCSE\(_\infty\), the masses can be changed arbitrarily, provided the constructed types retain positive mass, without changing the feasible committee sequences. The reduction therefore proves hardness of a finite temporal exact-one selection problem copied into type notation; it does not expose a population-mass phenomenon. A positive-threshold version would be a new weighted problem requiring a new reduction.
That is the strongest negative case, but it does not honestly establish the universal conclusion requested. Under ChoCo’s own rules, high-multiplicity work is admissible evidence, and Class B hardness is explicitly a worthwhile outcome even when population mass is not the source of hardness. Theorem 3 and Theorem 7 plausibly yield genuine compressed high-multiplicity variants, while Proposition 3 is a recognizable hardness transfer. I therefore cannot defeat every anchor without relying on the forbidden claim that “continuization does not help.” The honest assessment is that the negative case is substantial only if ChoCo requires population mass to affect the fairness constraints themselves; under the stated programme, the proponent’s mirror likely survives.
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.