| paper | Bribery Can Get Harder in Structured Multiwinner Approval Election |
| authors | — |
| venue | AAMAS 2023 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) for the budget-decision version; hence minimum-cost computation is \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), preferred candidate \(p\), rational budget \(B\), an ordered population partitioned into \(\tau\) contiguous cohorts of rational masses \(\mu_t\), common approval ballots inducing candidate intervals \(J_c\), and common per-candidate deletion prices \(g_c\), choose final intervals \(J'_c\subseteq J_c\), with \(J'_p=J_p\), minimizing \(\sum_{c\ne p}\int_{J_c\setminus J'_c} g_c\,d\mu\), such that \(p\) belongs to at least one size-\(k\) approval-winning committee; decide whether the optimum is at most \(B\).
An ordered high-multiplicity VI approval election with voter types \(t\), masses \(\mu_t\), identical approval ballots, and identical deletion-price vectors. Decision variables are endpoint-deleted masses for each candidate, the objective is total priced deleted mass, and feasibility requires every candidate’s approval region to remain an interval and \(p\) to be a nonunique AV co-winner.
With finitely many piecewise-constant cohorts, the mirror adds little computational structure beyond the paper’s endpoint trimming calculation, so its programme-level priority may be modest.
fatal: False
The mirror covers Theorem 3’s constructive priced VI deletion result. It leaves the paper’s CI results, approval addition, swap bribery, destructive variants, and other hardness or polynomial-time theorems untreated.
The strongest positive case is narrow but quite solid: the paper supports a high-multiplicity, continuous mirror of its VI deletion result, Theorem 3.
The anchor is:
Theorem 3. \( \mathrm{AV}\text{-}\$\mathrm{DelApprovals}\text{-}\mathrm{VI}\text{-}\mathrm{Bribery}\in\mathrm{P} \).
This theorem is proved in the paper, not merely cited. It is the best anchor because its tractability comes directly from the voter-interval structure, and that structure survives population continuization without fractionalizing the committee or the candidates.
Call the continuous problem \( \mathrm{AV}\text{-}\$\mathrm{DelApprovals}\text{-}\mathrm{VI}\text{-}\mathrm{Bribery}_\infty \). An instance contains a discrete candidate set \(C\), committee size \(k\), preferred candidate \(p\), and an ordered voter population divided into \( \tau \) contiguous cohorts \(I_1\prec\cdots\prec I_\tau\). Cohort \(I_t\) has rational mass \(\mu_t\), with \( \sum_t\mu_t=1 \). Its members have the same complete type: the same approval ballot, the same per-candidate deletion prices, and the same position block in the voter order.
For every candidate \(c\), the initial approval region is an interval \(J_c\) of the ordered population. Thus \(c\)'s initial approval score is
\[ \sigma(c)=\mu(J_c). \]
A feasible continuous bribery chooses, for every candidate \(c\), a subinterval \(J'_c\subseteq J_c\). The mass in \(J_c\setminus J'_c\) is deleted from \(c\)'s approval ballot. This is exactly the VI-preserving form of deletion: deleting approvals from the interior would create a gap, whereas deleting a prefix and/or suffix leaves an interval. If \(g_c(u)\) is the per-unit deletion cost at population position \(u\), the objective is
\[ \min \sum_{c\neq p}\int_{J_c\setminus J'_c} g_c(u)\,d\mu(u). \]
There is no reason to delete approvals for \(p\), so \(J'_p=J_p\) may be imposed without loss of generality. The question is whether there are final intervals \(J'_c\) of total cost at most a rational budget \(B\) such that
\[ \left|\{c\in C\setminus\{p\}:\mu(J'_c)>\mu(J'_p)\}\right|\leq k-1. \]
Equivalently, \(p\) must belong to at least one winning \(k\)-committee under the paper's nonunique-winner convention. A solution consists of the new interval endpoints, or equivalently the deleted mass from the left and right endpoint of every candidate's approval interval, together with its cost certificate.
This is a natural high-multiplicity regime. Imagine a large population of residents or customers ordered along a one-dimensional service corridor, with a fixed set of projects or facilities as candidates. Each project is supported by a contiguous geographic or demographic band. Many residents in each zone share the same approval profile and the same estimated cost of losing support. The population may contain millions of residents but only a few hundred or thousand distinct cohorts, so \(N\gg\tau\). This is not the claim that every voter in an arbitrary election is interchangeable. The type includes the information relevant to the VI constraint, including its position block and price vector.
The connection to the finite problem is exact for rational instances. If \(\mu_t=n_t/N\), replace cohort \(t\) by \(n_t\) consecutive cloned voters. A continuous deletion of rational mass becomes deletion of the corresponding number of clones from the appropriate endpoint. Conversely, any finite VI deletion instance with repeated cohorts maps to such a mass instance after normalizing scores and costs by \(N\). Thus this is a high-multiplicity relaxation, not merely a new geographic interpretation.
The continuous problem should be Class A. Let
\[ H=\{c\neq p:\sigma(c)>\sigma(p)\}. \]
At least \(r=\max(0,|H|-k+1)\) candidates in \(H\) must have their scores reduced to at most \(\sigma(p)\). For each \(c\in H\), define
\[ q_c=\sigma(c)-\sigma(p). \]
To reduce \(c\)'s score by \(q_c\) while preserving the VI property, one deletes \(x\) mass from the left endpoint and \(q_c-x\) from the right endpoint. If \(L_c(x)\) and \(R_c(x)\) are the costs of deleting those endpoint masses, the cheapest reduction cost is
\[ d_c=\min_{0\leq x\leq q_c} \bigl(L_c(x)+R_c(q_c-x)\bigr). \]
Because the costs and masses are piecewise constant over the \(\tau\) cohorts, each \(L_c\) and \(R_c\) is a piecewise-linear function with polynomially many breakpoints. The \(d_c\) values can therefore be computed by scanning the cohorts, and the final decision is to choose the \(r\) candidates with smallest \(d_c\). This is the same endpoint-independence exploited in the proof of Theorem 3, but implemented over mass rather than an explicitly listed voter population. The expected running time is polynomial in \(m\), \(\tau\), and the encoding length.
The mirror is author-recognizable: it keeps approval voting, the constructive bribery objective, arbitrary operation prices, the given voter order, the requirement that the VI property survive, and the exact co-winner semantics. Only the multiplicity of identical ordered voter cohorts has been made explicit. It also preserves the source of tractability: in a VI election, each candidate's approvals form an interval, so deletions can be optimized independently at the two endpoints.
I would deliberately stop at this one anchor. Theorem 4, Theorem 7, and Theorem 8 are tempting additional anchors, but their reductions rely on discrete all-or-nothing choices encoded by \(0/1/+ \infty\) prices or by Independent Set and RX3C gadgets. Once a cohort's mass may split between alternatives, those reductions may acquire fractional solutions. That makes their continuous complexity interesting, but not yet a secure positive mirror. Theorem 3 gives the cleaner case.
The weakest point is that VI structure contains an order, and that order must remain part of the type description. If prices or approval profiles vary from voter to voter, then \(\tau\) may grow to \(N\), and the high-multiplicity benefit disappears. Likewise, an atomless model permits partial deletion from a repeated cohort; an author could object that this is an extension rather than the literal finite operation model. The rational-clone correspondence answers the latter objection, but not the former. The mirror is therefore strongest for repeated geographic, demographic, or temporal cohorts with common price vectors—not for arbitrary named voters.
It generates several worthwhile follow-up questions: whether the same Class A result survives succinctly represented cost functions; whether continuous VI swap-bribery remains tractable; and whether the NP-hard CI and VI swap constructions retain hardness after mass splitting or instead become linear-programming problems. Those questions locate precisely where continuization may stop helping, while Theorem 3 already supplies one clean tractable mirror.
The strongest negative case is that Theorem 3 does not really expose a new continuous-computation problem. Its proof already reduces the instance to independent endpoint trimming. For each superior candidate \(c\), one computes the cheapest way to remove \(q_c=\mathrm{score}(c)-\mathrm{score}(p)\) approvals from the two ends of its voter interval, then selects the \(k-1\) cheapest candidates to demote. The proposed continuum merely replaces finite sums by integrals:
\[ d_c=\min_{0\le x\le q_c}\bigl(L_c(x)+R_c(q_c-x)\bigr). \]
With piecewise-constant cohort data, this is the same endpoint calculation and the same final sorting step. There is no exponential type space, separation problem, or coupling between candidates for continuization to expose. If the programme’s scarce resource is substantial new computational structure, this is a weak candidate.
The paper’s own motivating VI examples also provide only weak multiplicity. Days and excavation sites are indexed by distinct times or locations, and the prices may depend on the particular day or booking. Making many agents share an identical position, approval ballot, and price vector can therefore look manufactured. A richer spatial model with continuously varying prices is no longer a finite-type society unless those functions are given a separate representation; with arbitrary functions, the computational problem becomes representation-dependent rather than a clean high-multiplicity mirror.
Those objections do not survive the programme’s modelling standard, however. A plausible alternative scenario is a large population divided into geographic zones, where residents in each zone have the same approval interval over projects and the same estimated deletion prices. The zone, ballot, and price vector together form a complete type, and \(N\gg\tau\) is entirely credible. Rational masses clone exactly to repeated ordered voters, while partial deletion is the natural mass version of deleting a prefix or suffix of a cohort. The objective does not depend on individual identity, and the co-winner condition remains meaningful.
Thus the negative case cannot honestly defeat this anchor. At most, it can argue that the mirror is technically routine and lower priority than a continuization whose algorithm depends on column generation or whose complexity changes. But “routine” and “continuous does not help” are not grounds for rejecting a well-posed high-multiplicity question. Theorem 3 therefore survives as a worthwhile, if modest, Class A 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.