| paper | d4-conf-aaai-2016-0455 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
Given a fixed three-candidate axis \(L\), a rational distribution \(\mu\) over voter types \(t=(w,b)\), where \(w\) is the voting weight and \(b\) is a legal top-truncated single-peaked ballot, a preferred candidate \(p\), and a budget \(\beta\), can at most \(\beta\) mass be bribed so that \(p\) is the unique winner under eliminate(veto), using the paper’s round-up and vote-deletion conventions?
Normalize the population mass so \(\sum_t \mu_t=1\). For each type \((w,b)\), transfer mass \(x_{(w,b),(w,b')}\geq 0\) to legal ballots \(b'\) at the same weight \(w\), with total transferred mass at most \(\beta\); ask whether the resulting society makes \(p\) the unique eliminate(veto) winner. Equivalently, minimize total transferred mass.
Covers Theorem 14’s three-candidate eliminate(veto) bribery hardness and also admits the analogous Theorem 16 Baldwin mirror; leaves the paper’s manipulation results, complete-ballot results, and other bribery results outside this mirror.
My lead is Top-Truncated Single-Peaked Veto Bribery\(_\infty\). The anchor is Theorem 14, proved in this paper: in single-peaked electorates, in the unique-winner model, and with three candidates, weighted bribery for eliminate(veto) is in P with complete votes but NP-complete with top-truncated votes.
Here is the continuous version. Fix the candidate axis \(L\), with three candidates, and let a voter type be \(t=(w,b)\): voting weight \(w\), and a top-truncated ballot \(b\) that is single-peaked with respect to \(L\). The input is a rational distribution \(\mu\) over these types, with support size \(\tau\), a preferred candidate \(p\), and a budget \(\beta\), the fraction of the electorate that may be bribed. A solution is a transfer \(x_{t,t'}\geq 0\) of mass from each type to a type with the same voting weight and a different legal ballot, such that \(\sum_{t\ne t'}x_{t,t'}\leq\beta\) and \(p\) is the unique winner under eliminate(veto). Bribery costs one unit per person of mass; voting weight affects the scores, not the cost. Use the paper’s round-up scoring and vote-deletion conventions for top-truncated ballots, and the same tie handling as the underlying rule. Equivalently, the optimization version minimizes the mass transferred.
A plausible regime is a large association or union election with candidates on a common policy axis, where many members share the same expressed top choices and voting-weight class. Top truncation represents uncertainty or indifference about lower-ranked candidates. The population can be millions while \(\tau\), the number of ballot-and-weight types, is modest. This keeps the paper’s election rule, preference restriction, weighted scores, and bribery action; the population and the amount bribed are what become divisible.
I expect this three-candidate mirror to be tractable. There are only constantly many legal ballots and elimination orders at three candidates. For each possible order, the scores at every stage are linear in the transfer variables, as is the mass budget. Checking the resulting finite family of rational linear feasibility problems should take time polynomial in \(\tau\) and the input bit length \(L\). The discrete reduction’s indivisible choices may be exactly what disappears when cohorts can be split. For variable \(m\), the question is whether single-peaked structure makes the elimination-order and ballot-selection problems manageable, or whether hardness remains.
A second, distinct anchor is Theorem 16, also proved here: in single-peaked electorates, weighted bribery with top-truncated votes is NP-complete for three-candidate Baldwin’s rule. The paper’s default non-unique-winner convention applies. The mirror, Top-Truncated Single-Peaked Baldwin Bribery\(_\infty\), uses the same types, distribution, and transfer budget; success means that \(p\) is a winner under Baldwin’s rule, with the paper’s round-up and vote-deletion conventions. For three candidates, I again expect tractability by considering the constant number of elimination orders and solving the corresponding linear feasibility cases. Its variable-candidate version raises the same further question about whether the required optimization over ballot changes and elimination paths admits an efficient method.
Both mirrors cover the paper’s top-truncated weighted-bribery hardness results, not its other results. They do not make the ballot space, candidate axis, or voting rule continuous; only voter mass and bribed mass are continuous. The authors could reasonably recognize these as high-multiplicity versions of their bribery problems: agents remain identical in every feature the model uses, including their voting weight.
The weakest point is the match between the paper’s hardness instances and the intended high-multiplicity regime. The reductions use individually weighted voters to encode subset choices, so their type support can grow with the instance. That is not strong evidence that the hard instances themselves have many agents but few types. Nor is a large election with many identical non-unit voting weights as ordinary as a one-person-one-vote election. Still, the continuous questions remain faithful versions of the paper’s bribery tasks; the reductions’ reliance on indivisibility is a reason to investigate whether the hardness dissolves, not a reason to reject the mirror.
I cannot make an honest case that defeats either anchor. Theorem 14 is a named complexity result for weighted bribery with top-truncated ballots, single-peaked preferences, and three candidates. Theorem 16 gives a distinct result for Baldwin’s rule. Both ask computational questions of the kind ChoCo targets.
The strongest objection is that the paper’s reductions encode Partition using voters with varying weights. A type must include its weight as well as its ballot, so those instances may have support growing with the reduction size. They do not establish that the hard cases have many voters but few types. That weakens the bridge from the paper’s hardness results to a high-multiplicity regime; it does not make the continuous question ill-posed.
A stronger mirror would use a large association with candidates on a shared policy axis, where many members fall into a few voting-weight classes and share the same top-truncated ballot. A society is then a distribution over weight–ballot types, and bribing a fraction of a type changes both its mass and its contribution to the election. The model retains the paper’s relevant features, including weighted scores and per-voter bribery costs. Such a regime is plausible enough that I cannot rule it out on modeling grounds.
The same case applies to Baldwin bribery. Its non-unique-winner convention and elimination rule need to be carried through faithfully, but neither creates a fundamental obstacle to representing voter mass. The two anchors therefore survive the strongest objection available: the paper does not show that its particular hard instances lie in a low-support regime. I would report that limitation, but I would not recommend rejecting either 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.