| paper | Participation Incentives in Approval-Based Committee Elections |
| authors | — |
| venue | AAAI 2024 |
| 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
For a fixed sequential Thiele rule \(R\) other than AV, given candidates \(C\), committee size \(k\), rational approval-type masses \(\mu\), a distinguished type \(t^\star\), and rational \(0 < \beta \le \mu_{t^\star}\), let \(\mu^- = \mu - \beta e_{t^\star}\). Decide whether the set of committees \(F_R(\mu^-)\) selected under all tie-breakings is strictly Kelly-preferred by type \(t^\star\) to \(F_R(\mu)\).
Finite approval types t⊆C, rational mass distribution μ, sequential marginal scores weighted by μ, withdrawal variable β from one type, and committee-set utility |W∩t⋆| compared using Kelly's extension.
The hardness transfer is witnessed by withdrawal mass 1/n, so the paper does not establish complexity for withdrawals bounded away from zero or for minimum macroscopic cohort abstention.
fatal: False
The mirror covers Theorems 3 and 4 and Corollary 3; it leaves the axiomatic participation, impossibility, unrepresented-voter, and laminar-profile results outside the computational scope.
I think this paper supports a positive, but mainly Class-B, continuization case. The strongest anchor is Theorem 3. The mirror should continuousize the electorate only: candidates, committees, approval ballots, sequential rules, and Kelly preferences remain exactly as in the paper.
Let \(C\) be the candidates and \(k\) the committee size. A type is an approval set \(t\subseteq C\), \(t\neq\varnothing\). A society is a rational distribution \(\mu_t\) over a finite support \(T\) of such types. For a sequential Thiele rule with scoring function \(s\), define the weighted marginal score of adding \(c\) to a partial committee \(W\) by
\[ \Delta_\mu(c\mid W) =\sum_{t\in T}\mu_t \bigl(s(|t\cap(W\cup\{c\})|)-s(|t\cap W|)\bigr). \]
The rule chooses candidates attaining the maximum marginal score at each step, with every tie-breaking order retained. Let \(F_R(\mu)\) be the resulting set of winning committees. A type \(t\) evaluates a committee by \(u_t(W)=|W\cap t|\), and sets of committees are compared using exactly the paper’s Kelly extension.
This has a convincing high-multiplicity interpretation. Consider a large recommender system, validator-selection platform, or institutional committee election with millions of participating accounts or users, but only a few dozen or hundred approval policies. A type is a policy such as “approve validators satisfying criteria \(P\)” or “approve films in catalogue categories \(X\).” Mass is the fraction of users following that policy. If \(N\) is in the millions and \(|T|\) is in the tens or hundreds, this is precisely the regime in which a population distribution is more natural than a voter list. Abstention by a cohort is withdrawal of some mass of one approval type.
The paper’s named computational anchors are the following.
My lead is Theorem 3, proved in this paper: “For every sequential Thiele rule except AV, it is NP-hard to decide whether a voter can benefit from abstention.”
The corresponding continuous problem is Beneficial Cohort Abstention\(_\infty(R)\), for a fixed sequential Thiele rule \(R\neq\) AV.
An instance consists of \(C,k\), rational type masses \(\mu\), a distinguished approval type \(t^\star\), and a rational withdrawal amount \(0<\beta\leq\mu_{t^\star}\). Define
\[ \mu^-=\mu-\beta e_{t^\star}. \]
The question is whether
\[ F_R(\mu^-)\succ_{t^\star} F_R(\mu), \]
where \(\succ_{t^\star}\) is the paper’s strict Kelly preference. A YES solution means that withdrawing mass \(\beta\) of the distinguished type makes that type strictly better off, irrespective of the relevant tie-breaking comparison encoded by Kelly’s extension; a NO solution means it does not.
The exact one-voter case is embedded by taking a discrete profile with \(n\) voters, setting \(\mu_t=n_t/n\), and setting \(\beta=1/n\). Removing one voter of type \(t^\star\) gives exactly the weighted society \(\mu^-\). Voters with the same approval ballot are interchangeable, so no identity information used by the paper is lost. Conversely, rational masses can be cleared to integer multiplicities, giving the formal high-multiplicity dictionary.
The expected classification is Class B: hardness transfers. The reduction in Theorem 3 hides an independent-set instance in the candidate and approval structure, not in the inability to aggregate voters. Replacing repeated voters by rational mass preserves the sequential marginal scores and the abstention comparison. The continuous formulation is therefore faithful even though it does not claim a new continuum-specific hardness phenomenon.
The second anchor is Theorem 4, also proved here. It states that abstention-benefit detection is NP-hard for MES after Phase 1, after Phase 2, and for sequential Phragmén.
The corresponding problem is Budgeted Abstention\(_\infty(R,q)\), where \(R\) is MES or sequential Phragmén and \(q\) specifies the checkpoint: Phase 1 or the completed committee.
The instance is a rational mass distribution \(\mu\), candidates \(C\), committee size \(k\), a distinguished type \(t^\star\), and withdrawal mass \(\beta\). For MES, if the current total population mass is \(M\), a type \(t\) has budget density \(b_t\), so its total budget is \(\mu_t b_t\). Initially \(b_t=k/M\), matching the paper’s \(k/n\) budget per voter. A candidate \(c\) is affordable when
\[ \sum_{t:c\in t}\mu_t b_t\geq 1. \]
The chosen candidate minimizes the MES payment threshold \(\rho(c)\) satisfying
\[ \sum_{t:c\in t}\mu_t\min(\rho(c),b_t)=1, \]
after which each approving type’s budget density is reduced by \(\min(\rho(c),b_t)\). Ties are retained exactly as in the paper. Phase 2 is the mass-weighted version of the paper’s sequential-Phragmén completion, retaining the remaining budget densities.
After withdrawing \(\beta\), the new total mass is \(M'=M-\beta\), so the initial budget density becomes \(k/M'\). This renormalization is essential: it reproduces the fact that, in the discrete MES election, the remaining voters receive initial budget \(k/(n-1)\), not \(k/n\).
The decision question is whether the checkpoint outcome after withdrawal is strictly Kelly-preferred by \(t^\star\) to the checkpoint outcome before withdrawal. With \(\mu_t=n_t/n\) and \(\beta=1/n\), the discrete MES and Phragmén executions are reproduced exactly: after abstention, the total budget of type \(t\) is
\[ \frac{n_t'}{n}\cdot\frac{k}{(n-1)/n} =\frac{n_t'k}{n-1}, \]
which is precisely the discrete budget.
This is a stronger mirror than a mere weighted score calculation because it preserves the paper’s budget-sharing mechanism, Phase 1/Phase 2 distinction, and abstention incentive. Its expected classification is again Class B, with hardness transferring from the candidate-selection gadgets. Further questions include whether minimum beneficial withdrawal mass can be computed, whether the breakpoints are rational and piecewise-linear, and whether approximate abstention incentives admit efficient algorithms.
The third anchor is Corollary 3, proved in this paper as a consequence of its reductions. It states that, for every sequential Thiele rule other than AV, Phase 1 or complete MES, and sequential Phragmén, it is NP-complete to decide whether the election outcome changes when a single approval is added or deleted.
The corresponding problem is Approval-Mass Edit\(_\infty(R)\).
An instance contains \(\mu\), \(C\), \(k\), a mass \(\beta>0\), and two types \(t^-\) and \(t^+\) differing by exactly one approval: for some candidate \(c\),
\[ t^+=t^-\cup\{c\} \]
or \(t^-=t^+\cup\{c\}\). Move mass \(\beta\) from \(t^-\) to \(t^+\), obtaining
\[ \mu'=\mu-\beta e_{t^-}+\beta e_{t^+}. \]
The question is whether
\[ F_R(\mu')\neq F_R(\mu), \]
using the appropriate Phase 1 or completed outcome for MES. A single discrete approval edit is the special case \(\beta=1/n\). The paper’s “one approval” gadget therefore becomes a one-unit mass transfer between two approval types.
This also falls in Class B. It preserves the paper’s robustness question exactly while making the electorate a compressed distribution. For the unrestricted rational continuous version I would claim NP-hardness, not automatically NP-completeness: the paper itself notes that membership in NP is unclear for some set-valued sequential-election questions.
I would not use Theorem 1, Theorem 2, Corollary 1, or Propositions 1 and 2 as computational anchors. They are valuable supporting results—weighted masses preserve the same group-participation and laminar-profile statements—but they are axiomatic rather than named complexity or algorithmic results. The mirror’s scope is therefore deliberately limited to Theorem 3, Theorem 4, and Corollary 3.
The weakest point is that the exact hardness transfer uses \(\beta=1/n\), which can look like a disguised atomic voter rather than a genuinely macroscopic continuum. That criticism is fair. The strongest defence is that ChoCo’s notion of continuization explicitly includes high-multiplicity instances and rational mass transfers; it does not require every action to have mass bounded away from zero. Moreover, the same model naturally supports genuinely cohort-level questions, such as the minimum fraction of a policy cohort that must abstain to gain representation, or the smallest mass edit that changes the committee. Those optimization and approximation questions are new continuous problems generated by the mirror, while the paper’s named NP-hard results provide the formal anchors.
So my positive case is not that this paper delivers a new Class-A algorithm. It delivers a particularly clean Class-B mirror: the paper’s computational hardness survives after replacing the voter list by a rational distribution over approval types, and the sequential rules—including their budget-sharing variants—remain the same population-continuized objects.
The strongest negative case is that all three proposed mirrors are atomic relabellings, not genuinely continuous participation problems.
For Theorem 3, in an atomless society a single voter has measure zero. Removing that voter leaves \(\mu\) unchanged, so beneficial abstention disappears. The proponent repairs this by withdrawing \(\beta=1/n\) from a type. But that is exactly a finite election written as normalized frequencies: clearing denominators reconstructs the original voter list. The hardness transfer is valid, yet it contributes no new continuum phenomenon.
The natural repair is to require a macroscopic withdrawal, or to ask for the minimum mass whose abstention benefits the cohort. That is a coherent question, but it is no longer the paper’s unilateral participation problem. It is coordinated coalition abstention, and Theorem 3 says nothing about its complexity. Adding abstention costs, turnout propensities, or type-specific coordination mechanisms makes the model richer, but the computational content then comes from the newly invented intervention model rather than from this paper.
The same defect is sharper for Theorem 4. The proposed MES continuation must renormalize budgets after withdrawal: with total mass \(1\), remaining voters receive initial budget \(k/(1-\beta)\). This faithfully reproduces the discrete \(k/(n-1)\) rule when \(\beta=1/n\), but it also means that one cohort’s abstention globally changes every other voter’s budget. In a genuinely continuous population there is no uniquely compelled choice between this renormalization, fixed total budget, and fixed per-capita budget. Each choice defines a different turnout mechanism. The exact paper theorem supports only the first choice at atomic withdrawal size; macroscopic withdrawal again produces a new model with no anchored result. The same normalization problem appears in the budget/time accounting of sequential Phragmén.
Corollary 3 is weaker still. A single approval addition or deletion has zero mass in the continuum. Moving \(\beta=1/n\) between \(t^{-}\) and \(t^{+}\) merely compresses the discrete instance into two histogram coordinates. A positive-mass transfer represents a platform-wide policy change affecting a cohort, not a single approval edit. The resulting threshold-sensitivity problem might be interesting, but it is not the corollary’s problem, and the corollary supplies no theorem about it.
There is no identity objection here: an approval ballot is a legitimate complete type, and large platforms may well have many users per policy type. That is the proponent’s strongest point, and it prevents an airtight negative verdict. Nor is existing high-multiplicity work a collision. But it does mean the negative case must rest on value: these formulations either make the original individual action vanish, or restore it by encoding a finite voter instance at mass \(1/n\). The proposed cohort-level variants are plausible research questions, but they are not consequences of the paper’s results.
So I cannot honestly defend the universal claim that no worthwhile mirror exists. The paper has real, faithful Class-B continuizations, and under ChoCo’s stated rules that is enough for a green. The defensible negative judgement is narrower: this is a weak Class-B boundary example, not a strong continuization target, unless the programme is willing to develop genuinely macroscopic cohort-abstention questions independently of the paper’s hardness theorems.
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.