| paper | Online Approval Committee Elections |
| authors | Virginie Do, Matthieu Hervouin, Jérôme Lang, Piotr Skowron |
| 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 4.1
statement extracted from the paper’s text layer
Given \(m\), \(k\), voter types \(T\) with rational masses \(\mu\), a fixed Thiele utility \(f\), and an explicitly represented known rational distribution \(P\) over signatures \(a\in\{0,1\}^{\tau}\), each of \(m\) candidates is revealed sequentially with a signature drawn from \(P\). Find an irrevocable safe policy selecting exactly \(k\) candidates that maximizes \(\mathbb{E}_{P}[\sum_{t\in T}\mu_t f(\sum_{q\in W}a_t^q)]\), with complexity studied especially for fixed \(\tau\).
Known-Prior Online Thiele-\(\infty\): a society is the distribution \(\mu\) over complete voter types; candidates reveal approval signatures; the decision variable is an irrevocable accept/reject policy; and the objective is expected normalized Thiele score \(\mathbb{E}[\sum_t\mu_t f(r_t(W))]\).
The population enters only through terminal score weights, so the mirror may contribute limited population-dependent structure and becomes merely \(m^{O(\tau)}\) when \(\tau\) varies.
fatal: False
The mirror covers the fixed-\(\tau\) high-multiplicity counterpart of Theorem 4.1, including PAV and CCAV, but leaves the unknown-prior approximations, specialized propositions, and proportionality results aside.
The strongest honest case is a single anchor: Theorem 4.1, proved in this paper. It states that for every Thiele rule, including PAV and CCAV, an optimal safe online policy is computable in polynomial time when the number of voters is constant.
The paper has no numbered NP-hardness or parameterized-hardness result. Its statement in Section 5.3 that detecting an \(\ell\)-cohesive group is NP-hard is unnumbered and attributed to Skowron et al. (2017), so I would not use it as this paper’s hardness anchor. The PJR and EJR theorems are primarily axiomatic results, and their continuous versions would fall outside ChoCo’s computational scope.
My proposed problem is Known-Prior Online Thiele-\(\infty\).
There are \(m\) candidates arriving sequentially, a committee size \(k\), and a finite set of voter types \(T=\{1,\ldots,\tau\}\). Type \(t\) has rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). A type is complete: all members have the same approval response to every candidate class and the same role in the objective. When candidate \(c_q\) arrives, the policy observes its approval signature \(a^q\in\{0,1\}^{\tau}\), where \(a^q_t=1\) means that type \(t\) approves it. Candidate signatures are drawn from a known finite rational distribution \(P\), as in the paper’s known-prior setting.
The policy must immediately and irrevocably accept or reject each candidate, and must select exactly \(k\) candidates. For a selected committee \(W\), let
\[ r_t(W)=\sum_{c_q\in W}a^q_t \]
and define the normalized Thiele score by
\[ F_{\mu,f}(W)=\sum_{t=1}^{\tau}\mu_t f(r_t(W)). \]
The problem is to output a safe online policy maximizing
\[ \mathbb{E}_{P}\!\left[F_{\mu,f}(W)\right]. \]
This is recognizably the authors’ problem: candidates still arrive online, approval information is revealed only at arrival, selection is immediate and irrevocable, the committee remains discrete, and the objective is exactly their aggregate Thiele satisfaction. Only the electorate has been replaced by rational masses.
The high-multiplicity correspondence is exact. If \(\mu_t=n_t/N\), replace type \(t\) by \(n_t\) identical voters. Then
\[ F_{\mu,f}(W) = \frac{1}{N} \sum_{i=1}^{N}f\bigl(|A(i)\cap W|\bigr). \]
Thus clearing denominators recovers the finite cloned election, with the same feasible policies, score comparisons, ties, and optimal policy. This is a direct high-multiplicity lift rather than outcome-space fractionalization.
A plausible regime is a large hiring or fellowship programme selecting \(k\) people from a stream of \(m\) applicants. There may be hundreds of thousands of evaluators or represented stakeholders, but only a small number of standardized evaluation roles: for example, accessibility, technical quality, public impact, regional representation, and several domain-specific rubrics. Members of one role apply the same approval rule to every applicant, so \(N\gg\tau\). Historical applications provide the prior \(P\) over approval signatures. This is close to the paper’s own observation that voters may represent evaluation criteria, while giving those criteria genuinely high multiplicity.
The expected direction is Class A in the bounded-type regime. The dynamic-programming state records the number of selected candidates approved by each type:
\[ (\alpha,\beta,r_1,\ldots,r_\tau), \]
together with the current approval signature. Here \(\alpha\) is the number of candidates seen and \(\beta\) the number selected. Since \(0\le r_t\le m\), there are at most \((m+1)^\tau\) score-count vectors. For fixed \(\tau\), the Bellman recurrence is polynomial in \(m\), \(k\), the support size of \(P\), and the rational encoding length. It is precisely the paper’s fixed-\(n\) dynamic programme with voter identities compressed into type masses.
The regime restriction matters. With variable \(\tau\), this straightforward algorithm is \(m^{O(\tau)}\), so it is an XP result rather than an FPT result. A natural follow-up is whether the structure of particular Thiele functions yields an algorithm polynomial in \(\tau\), or whether variable-type instances retain hardness. The known-prior assumption also deserves study: sample-based or partially known priors would generate approximation and learning variants.
The weakest point is that the paper’s theorem itself only proves tractability for a constant number of named voters. The continuous mirror transfers that parameter from the number of individuals to the number of genuine types; it does not establish a polynomial algorithm for arbitrary \(\tau\). Its positive contribution is therefore deliberately modest but solid: this paper supports a faithful, computational population mirror in the natural regime of a very large electorate with few complete approval types. It does not provide the hardness-dissolution result ChoCo ultimately seeks, but it supplies a clean Class A test case in which high multiplicity is meaningful and the online optimization problem survives intact.
The proponent’s mirror is well-defined, but it is not a worthwhile ChoCo mirror. The positive case relies on a computational distinction that disappears once the paper’s own dynamic programme is viewed correctly.
For rational masses \(\mu_t=n_t/N\), clone type \(t\) into \(n_t\) identical voters. For every history and committee \(W\),
\[ \frac{1}{N}f\text{-sc}(W) = \sum_{t=1}^{\tau}\frac{n_t}{N}f(r_t(W)) = \sum_{t=1}^{\tau}\mu_t f(r_t(W)). \]
The transition probabilities, feasible online policies, ties, and optimal policies are therefore identical. This exact correspondence is not itself illegitimate under ChoCo, but here it does all the work: the proposed “continuous” dynamic programme is simply the paper’s fixed-\(n\) programme after deleting duplicate coordinates. In the original state vector \((r_1,\ldots,r_n)\), voters belonging to one complete type remain synchronized on every history. Quotienting those coordinates produces \((r_1,\ldots,r_\tau)\) without introducing a new optimization object.
More importantly, population mass is passive in this problem. It appears only as a coefficient in the terminal Thiele score. It does not enter feasibility, the online transition process, a winner inequality, a capacity constraint, or any operation that moves or changes population mass. For MAV,
\[ F_{\mu,\mathrm{MAV}}(W) = \sum_{c\in W}\sum_t\mu_t a_t^c, \]
so the population is merely a weighted candidate-value function. For CCAV, it is merely the mass of types represented at least once. General Thiele rules retain a vector of approval counts, but still no genuinely population-level structure. The same formulation could be written with arbitrary weights on feature coordinates and without calling those coordinates voters at all.
The proposed hiring example does not fully repair this. If the “voters” are evaluation criteria, they are naturally a small set of dimensions, not a large society. If they are many evaluators, then a complete type requires every evaluator in a type to give the same approval to every possible future candidate. That is a strong perfect-correlation assumption. Under it, the type quotient is exactly the trivial compression above. If instead evaluators merely have the same approval probabilities while making independent judgements—as in the paper’s UI setting—then they are not complete types, and their individual approval histories cannot be replaced by one count \(r_t\) without changing the stochastic problem.
The proposed prior over signatures also shifts the model. A finite explicit distribution \(P\) is acceptable, but when \(\tau\) grows its natural support can contain \(2^\tau\) approval signatures. A compact product or feature-based prior requires additional assumptions about candidate generation and voter responses. With fixed \(\tau\), the claimed polynomial algorithm is just the paper’s fixed-voter result under a renamed parameter; with variable \(\tau\), the stated algorithm is only \(m^{O(\tau)}\), and the prior representation becomes part of the new model. Neither case produces the sort of population-dependent computational landscape that motivates ChoCo.
A richer “better” mirror faces the same dichotomy. If types remain complete and finite, the problem is an exact weighted quotient of the original online process. If types are allowed to split according to newly revealed approval histories, the number of effective types can grow with the candidate stream, potentially up to exponentially many histories. If one adds mass transfers, voter manipulation, or continuous intervention, those may be excellent new ChoCo problems, but they are no longer mirrors of the paper’s online committee-selection result.
This is not an objection that the continuous answer might be easy, nor an objection based on the absence of hardness. Theorem 4.1 is genuinely computational, and a high-multiplicity interpretation is coherent. The objection is narrower: in this particular anchor, continuization contributes only weighted symmetry compression. I would therefore reject it as a worthwhile ChoCo mirror, while admitting that the universal negative is not airtight. If exact high-multiplicity quotients count as sufficient contributions, the proponent has a legitimate Class A test case; it simply does not offer new population-level computational content.
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.