| paper | Bribery Can Get Harder in Structured Multiwinner Approval Election |
| authors | — |
| venue | AAMAS 2023 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given a candidate/day axis \(C\), committee size \(k\), target \(p\), a finite set of interval-booking types \(T\), masses \(\mu_t\), initial intervals \(I_t\subseteq C\), and per-addition costs \(q_t(c)\), allocate each \(\mu_t\) among interval extensions \(J\supseteq I_t\) so as to minimize total cost subject to \(p\) belonging to a top-\(k\) approval committee in the resulting mass society.
A continuous AV society consists of masses of complete booking types \(t=(I_t,q_t)\); variables \(x_{t,J}\) transfer mass from each initial interval \(I_t\) to an extended interval \(J\supseteq I_t\), and the objective minimizes the aggregate per-unit addition cost while making \(p\) a top-\(k\) day.
The mirror directly covers the constructive CI priced-additions setting of Theorem 2; the related swap-to-\(p\) formulation covers Theorem 5, while the deletion, arbitrary-swap, VI, and destructive results remain separate.
The strongest mirror is the CI hotel/booking interpretation, anchored on Theorem 2: “AV-$AddApprovals-CI-Bribery ∈ P.” This is a result proved in this paper (with the proof printed in the supplied text). It is already about a fixed candidate axis, interval ballots, individually priced changes, and a target joining a top-\(k\) set—the ingredients survive continuization unusually cleanly.
Call the continuous problem CI-$AddApprovals-\(p\)-Bribery\(_\infty\). An instance has a candidate/day axis \(C\), committee size \(k\), target day \(p\), and a finite set of booking types \(T\). A type \(t\) consists of an initial nonempty interval \(I_t\subseteq C\) and a complete per-addition price vector \(q_t(c)\in\mathbb Q_{\geq0}\cup\{\infty\}\). Its mass \(\mu_t\) is the fraction of bookings of that type. A decision is nonnegative mass \(x_{t,J}\), for every interval \(J\supseteq I_t\), where \(\sum_Jx_{t,J}=\mu_t\). It means that this mass of type-\(t\) bookings is extended from \(I_t\) to \(J\). Its cost is
\[ \sum_{t,J}x_{t,J}\sum_{c\in J\setminus I_t}q_t(c). \]
The resulting approval score of a day is the total mass of bookings whose chosen interval contains it. The question is to find minimum cost, or decide whether cost at most \(B\) suffices, such that at most \(k-1\) days have score strictly above \(p\)’s score. Equivalently, \(p\) belongs to some winning AV committee. This is not a softened substitute for the paper’s problem: it retains the same CI requirement after modification, the same priced additions, and the same nonunique-winner interpretation.
The regime is a resort, travel platform, or large accommodation chain forecasting staffing needs across a month or season. There may be hundreds of thousands of bookings but only modestly many relevant types: arrival/departure window, room/product class, cancellation or extension terms, and perhaps a small number of customer-policy categories. The full price vector belongs in the type, so this does not assume away heterogeneous prices; it groups precisely those bookings for which the system uses the same change-likelihood schedule. With \(m=31\) or \(365\) days, \(\tau\) can be thousands while the booking population is orders of magnitude larger. Mass is then exactly the useful forecast quantity: “what fraction of bookings must plausibly extend so that 23 June enters the \(k\) busiest days?”
I would expect this to be a Class A problem. Theorem 2 is strong evidence that the interval geometry, rather than voter-by-voter identity, is doing the useful work. The continuous problem is a configuration LP over interval extensions, coupled to an ordered top-\(k\) condition. The printed discrete dynamic program cannot simply be quoted as a continuous proof—its states count voters—so the real technical task is to give a piecewise-linear or flow/extended-LP replacement. But that is exactly a credible ChoCo question: does the theorem’s interval-side dynamic program admit a polynomial-size continuous optimization formulation? If so, the output is a genuine fractional robustness measure, not merely an additive approximation to a discrete answer.
A worthwhile second anchor is Theorem 5, “AV-$SwapApprovals to \(p\)-CI-Bribery \(\in P\),” again a result of this paper, rather than a cited result. Its proof is not printed in the supplied conference text, but the theorem is explicitly one of the paper’s results.
Its mirror, CI-$Swap-to-\(p\)-Bribery\(_\infty\), uses the same society \((T,\mu)\). For each type \(t\), let \(I_t\) be its interval ballot and let its finite action menu contain doing nothing plus every permissible one-approval move \(r\mapsto p\), with \(r\in I_t\), for which \((I_t\setminus\{r\})\cup\{p\}\) remains an interval. The type records the corresponding price \(q_t(r,p)\). Variables allocate each type’s mass among these actions; final scores, the top-\(k\) requirement, and total per-unit-mass cost are defined as above. The question is whether \(p\) can enter a winning committee within budget, or what its minimum such cost is.
Here the hotel story is even more literal: a booking of fixed length shifts one endpoint so as to include a prospective peak day. The action preserves both the booking length and contiguity. Standardized booking classes again make repeated types natural. I would also expect Class A: Theorem 5 says the discrete structured action space is already sufficiently constrained for polynomial optimization, and fractional type mass should make its shortest-path/DP structure more, not less, amenable to a flow or LP formulation. A useful follow-up is whether the two mirrors admit a common interval-configuration formulation, and where allowing arbitrary CI-preserving swaps makes its pricing problem hard.
I would deliberately not anchor the positive case on the paper’s NP-completeness theorems, such as Theorem 4 or Theorem 7. Their reductions rely on one-off solution/edge voters whose choices encode Exact Cover or Independent Set. In the continuous relaxation, splitting those voters’ mass risks turning the reduction into its fractional LP relaxation; that is not evidence that hardness transfers. This restraint matters: the paper does not establish that every one of its complexity reversals has a meaningful or hard continuous counterpart.
The weak point is therefore real. These mirrors are compelling for large, standardized booking systems, but not for a small hotel with idiosyncratic reservations, where \(\tau\) is essentially the number of bookings. And Theorem 2’s discrete polynomial algorithm is not yet a proof of a polynomial continuous algorithm. Still, the high-multiplicity regime is strong, explicitly close to the paper’s own application, and the stated continuous questions preserve rather than dilute its core issue: the least aggregate, interval-respecting change needed to make a day enter the top-\(k\).
I cannot make a credible universal negative case here. The proponent’s Theorem 2 anchor survives the relevant objections.
A large booking platform genuinely can have many bookings of the same complete operational type: the same initial stay interval and the same contractual/change-likelihood price schedule. Treating the mass of that type as divisible is then a natural high-multiplicity relaxation, not an identity-erasing distortion. The target question—minimum aggregate, interval-respecting change needed for a day to enter the top-\(k\) demand days—is computational and preserves the paper’s actual object: priced approval additions with CI maintained after intervention. Individual booking identities do not enter AV scores or the stated action costs once the complete price vector is included in the type.
The strongest attempted objection is practical rather than fundamental. In a small hotel, or where every reservation has a bespoke contract, \(\tau\) is essentially the number of bookings and the continuum has little modelling value. But that is only one instance regime. It does not defeat the platform/chain regime with standardized contracts, which is precisely the distinction the programme requires us to make.
Theorem 5 survives for much the same reason. A fixed-length booking shifted by one endpoint to include a prospective peak day is an especially clean CI-preserving swap-to-\(p\). Again, customer identity is irrelevant after types include all action prices, and a large cohort of interchangeable bookings is plausible. One might object that real changes include cancellations, length changes, and nonlocal rescheduling; that merely means this narrow action menu is not a universal demand model. It does not make the model or its high-multiplicity version incoherent.
Nor can one use the fact that the discrete DP counts voters, or that a continuous formulation might turn out not to be polynomial. That is the proposed computational question, not a reason it is unworthy. Indeed, the finite interval-extension/action menu gives a particularly direct configuration-LP candidate.
So the negative verdict is weak: I would not green-light a claim that this paper has *no* worthwhile continuous mirror. Theorem 2 alone provides one; Theorem 5 is a reinforcing, though narrower, second 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.