| paper | Multiwinner Voting with Possibly Unavailable Candidates |
| authors | — |
| venue | AAAI 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 2
statement extracted from the paper’s text layer
Given candidates C, committee size k, a fixed non-AV Thiele rule w, a rational distribution μ over approval-set types, and candidate c, decide whether for every availability set X⊆C there is a winning committee W⊆X of size min(k,|X|) containing c whenever c∈X.
A finite population of approval types with rational masses μ; candidates and availability scenarios remain discrete; Thiele committee scores are mass-weighted, and the decision concerns safe binding invitations.
The cited hardness may require the number of approval types to grow with the candidate set, so it does not establish the complexity of a genuinely fixed-support compressed regime.
fatal: False
The mirror directly covers Theorems 2 and 4 and supports mass-based versions of Theorem 1 and Proposition 3; it leaves the PJR/EJR results and other structural results outside the proposed anchors.
The strongest honest case is that this paper has an unusually clean population mirror. Its voter side is already anonymous: for Thiele rules, voters matter only through their approval sets and their aggregate contribution to committee scores. The continuous analogue therefore replaces voter counts by masses while leaving candidates, availability, binding invitations, and committee selection completely discrete.
Let \(C\) be the candidate set and let \(T\) consist of approval-set types. A type \(t\) has approval set \(A_t\subseteq C\), and the society is a rational distribution \(\mu\in\mathbb Q_{\ge 0}^{T}\) with \(\sum_t\mu_t=1\). For a fixed Thiele weight vector \(w\), define
\[ \operatorname{sc}^{w}_{\mu}(W) =\sum_{t\in T}\mu_t \sum_{j=1}^{|A_t\cap W|}w_j. \]
For each available-candidate set \(X\subseteq C\), the winning committees are the size-\(\min(k,|X|)\) subsets of \(X\) maximizing this score. A set \(B\subseteq C\) is safe if, for every \(X\subseteq C\), some winning committee \(W\) satisfies \(B\cap X\subseteq W\). Thus \(B\) can be queried in parallel as a binding invitation: every member of \(B\) who is available can safely be forced into a committee completion.
This is not merely an analogy. Given the paper’s discrete profile with \(n_t\) voters of type \(t\), set \(\mu_t=n_t/n\). For every \(X\) and every committee \(W\),
\[ \operatorname{sc}^{w}_{\mu}(W) =\frac{1}{n}\operatorname{sc}^{w}(W). \]
Consequently, the winning committees and all safe sets are identical. Conversely, rational masses can be expanded into a finite profile by clearing denominators. The continuous problem is therefore the exact high-multiplicity version of the paper’s problem, not a softened problem with fractional committees or probabilistic availability.
A plausible regime is a large university system, professional association, or public recruitment programme selecting from a finite slate of candidates. There may be tens of thousands or millions of stakeholders, but only a few dozen recurring approval types: members of the same department, professional constituency, student cohort, union, or institutional role approve the same candidates. Candidates may still accept or decline invitations individually, so availability remains the paper’s binary uncertainty. The population has \(n\gg\tau\), while \(m\) and \(\tau\) are moderate. This is precisely the regime in which approval counts are better understood as percentages than as named voters.
My lead anchor is Theorem 2, proved in this paper:
“For any sequential and non-sequential Thiele rule except AV, even in the first step of the query policy, it is coNP-hard to decide whether a given candidate is safe.”
The corresponding continuous problem is:
Continuous Safe Candidate for Thiele Rules. Given \(C\), \(k\), a fixed non-AV Thiele rule \(w\), a rational type distribution \(\mu\), and a candidate \(c\), decide whether, for every \(X\subseteq C\), there exists a \(w\)-winning committee \(W\subseteq X\) of size \(\min(k,|X|)\) such that \(c\in W\) whenever \(c\in X\).
A yes-instance means that \(c\) may be queried first as a binding invitation. A no-instance means that some availability scenario \(X\) makes every optimal committee exclude \(c\), despite \(c\) being available.
I expect this problem to remain coNP-hard, in Class B of the ChoCo trichotomy. The transfer is exact: take the discrete hard instance from Theorem 2 and replace its voter multiplicities by normalized masses. Every score comparison, tie, winning committee, and safety statement is preserved. The hardness is therefore not dissolved by removing voter individuation. Its combinatorics live in the candidate set and in the universal quantification over possible availability sets, not in the numerical fact that one voter rather than another was counted.
The mirror is especially faithful because it preserves the paper’s central difficulty. It does not introduce utility functions, availability probabilities, fractional candidates, or non-binding queries. The only change is that an approval cohort is represented by its fraction of the electorate. The authors should recognize this as their own safe-candidate problem in the high-multiplicity regime.
A second, independently meaningful anchor is Theorem 4, also proved in this paper:
“Given a \(w\)-Thiele rule with \(w_1=\cdots=w_q=1\) and \(w_{q+1}<1\), it is coNP-hard to decide whether \(q+1\) safe candidates exist if no candidates have been queried yet.”
Its continuous counterpart is:
Continuous Parallel Safe Query for Thiele Rules. Given \(C\), \(k\), a rational type distribution \(\mu\), and a Thiele vector satisfying \(w_1=\cdots=w_q=1>w_{q+1}\), decide whether there exists a set \(B\subseteq C\) with \(|B|=q+1\) such that, for every \(X\subseteq C\), some winning committee under \(\mu\) contains \(B\cap X\).
If the answer is yes, the solution is the set \(B\), which can be queried in one parallel round. For PAV, \(q=1\), so this asks whether two candidates can safely be invited simultaneously. This is not just the single-candidate problem repeated: individual safety does not imply joint safety, and the paper’s parallel-query question is exactly about that interaction.
Again, the expected classification is Class B and the discrete coNP-hardness transfers verbatim under \(\mu_t=n_t/n\). The continuous problem retains the paper’s operational meaning: parallel invitations are safe only if every possible pattern of acceptances and refusals still admits an optimal committee containing all available queried candidates.
The paper’s positive structural results also support the mirror. Theorem 1 and Proposition 3 show that sequential rules such as sequential PAV and MES admit safe query policies. Their constructions survive unchanged with masses: a candidate’s marginal contribution is computed as a weighted sum over approval types rather than by iterating over individual voters. Thus the continuous model contains both sides of the paper’s landscape: tractable construction of safe queries for sequential rules, and coNP-hard certification or maximization questions for nontrivial Thiele rules and parallel queries.
I would not claim that this mirror covers every result in the paper. In particular, the PJR and EJR results in Theorems 5 and 6 would require a separate measure-theoretic treatment of cohesive voter groups and should not be smuggled into this case by simply replacing \(n\) with \(1\). The two safe-query anchors above are sufficient.
The weakest point is that the mirror is conservative. For these anchors, continuization does not make the problem easier; it gives an exact high-multiplicity restatement whose hardness transfers. A sceptic may say that this is only normalization, not a new continuous algorithmic phenomenon. That criticism is fair. The present case does not establish that safety becomes tractable when \(\tau\) is fixed or small, nor that a continuous relaxation yields a new approximation scheme. Those are genuine follow-up questions:
That limitation does not invalidate the mirror. The programme explicitly includes Class B problems where hardness survives population continuization. Here the population regime is natural, the type aggregation is exact, and the paper’s computational questions—safe binding invitations and safe parallel queries—remain intact.
The strongest case against is that this paper is already written in an anonymous, aggregate language. For every Thiele rule, voters enter only through sums of approval-dependent weights; their names, identities, and individual histories are irrelevant. Replacing \(n_t\) by \(\mu_t=n_t/n\) therefore does not create a new population model. It merely changes the units of an already weighted approval profile.
That objection applies equally to both proposed anchors. For Theorem 2, clearing denominators in \(\mu\) reconstructs the original profile, and every score comparison, tie, winning committee, and safety statement is preserved exactly. Theorem 4 is no different: joint safety is genuinely distinct from individual safety, but its truth value is likewise unchanged by normalization. The continuous formulations are thus faithful, but they add no new semantic object beyond the paper’s existing approval-count vector.
A stronger proposed mirror would seek a genuinely large-population regime with fixed or small \(\tau\). That is where continuization might compress the electorate. But then each candidate is characterized by its approval pattern across the \(\tau\) types, yielding at most \(2^\tau\) candidate classes. The transferred coNP-hardness results do not establish difficulty in this genuinely compressed regime; their hard instances may require the number of approval types to grow with the candidate set. Conversely, adding availability probabilities, fractional committees, or individual acceptance behaviour would create new problems, not continuous mirrors of this paper.
Still, this is not enough to defeat the anchors under the programme’s rules. The voter cohorts have a perfectly plausible high-multiplicity interpretation, the objective does not depend on voter identity, and the continuous society does not degenerate. Most importantly, the programme explicitly counts exact Class B transfers as worthwhile and forbids rejecting a mirror merely because hardness survives or because the formulation is conservative.
So the honest negative case is weak. It can question novelty and the likelihood of a Class A payoff, but it cannot defeat either Theorem 2 or Theorem 4. On the stated standard, this paper should be green.
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.