| paper | d4-conf-atal-2013-0282 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), even with \(\tau=2\) and both masses equal to \(\frac12\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.2
statement extracted from the paper’s text layer
Given candidates \(C\), \(k\) as part of the input, a rational distribution \(\mu\) over finitely supported types \(\theta=(R_\theta,\pi_\theta)\), and a candidate \(c\) who is initially the unique \(k\)-approval winner, what is the minimum total cost of transferring mass from each type to output rankings so that some \(a\ne c\) has \(k\)-approval score at least that of \(c\)? Each unit transferred from \(\theta\) to ranking \(R'\) costs \(d_{\pi_\theta}(R_\theta,R')\), the minimum adjacent-swap price for that conversion, and transfers preserve each type's total mass.
A society is a rational distribution \(\mu\) over types containing both a ranking and its complete adjacent-swap price schedule. Decision variables \(x_{\theta,R'}\) allocate each type's mass across output rankings; minimize \(\sum_{\theta,R'}d_{\pi_\theta}(R_\theta,R')x_{\theta,R'}\), subject to mass preservation and a challenger tying or beating \(c\) under \(k\)-approval.
The opponent's strongest remaining point is that the proposed price scaling does not yet prove the two-voter reduction remains hard when mass can split fractionally.
fatal: False
The selected mirror covers Theorem 4.2's priced \(k\)-approval destructive-bribery problem. It leaves the unit-cost scoring algorithm of Theorem 4.1 and the paper's robustness bounds outside this anchor.
My lead is the hardness result, Theorem 4.2. It is proved in this paper, using a result cited from [6]: when \(k\) is part of the input, destructive swap bribery for \(k\)-approval is NP-complete even with only two voters. The input has an election, a designated candidate who is the unique winner, swap prices, and a budget; the question is whether swaps within budget can make that candidate cease to be the unique winner.
Here is its continuous mirror, priced \(k\)-Approval Destructive Bribery\(_\infty\). An instance has candidates \(C\), an input value \(k\), a rational distribution \(\mu\) over supported types \(\theta=(R_\theta,\pi_\theta)\), a designated candidate \(c\) who is initially the unique \(k\)-approval winner, and a budget \(B\). A type includes both its ranking and its complete schedule of adjacent-swap prices. Let \(d_{\pi_\theta}(R_\theta,R')\) be the least cost of transforming \(R_\theta\) into ranking \(R'\) using adjacent swaps. Choose nonnegative transfers \(x_{\theta,R'}\) with \(\sum_{R'}x_{\theta,R'}=\mu_\theta\). They must produce a distribution \(\nu\) in which some \(a\ne c\) has at least \(c\)’s \(k\)-approval score, and their cost \(\sum_{\theta,R'}d_{\pi_\theta}(R_\theta,R')x_{\theta,R'}\) must be at most \(B\). The solution is the transfer plan; equivalently, one can ask for the minimum budget that makes such a plan possible.
A plausible regime is a large electorate made up of cohorts whose members share both a ballot type and a schedule of intervention prices. Then the number of voters can be large while the number of supported types \(\tau\) is small. Those prices are less natural than the paper’s uniform error cost, but cohort-specific intervention tariffs are a recognizable version of the bribery model the authors themselves define.
I expect this mirror to be Class B: hardness transfers, with the hardness driven by the candidate agenda and \(k\), not by population multiplicity. The paper’s two-voter reduction gives a particularly useful starting point: its constructed election has two voter types, which can each have mass \(1/2\). Divisibility does mean the printed reduction’s \(\delta+1\) penalty is not automatically enough: a small fraction of a type could make an expensive change. For the continuous reduction I would set forbidden swap prices to a larger value \(M\), above twice the maximum relevant one-voter path cost. The reduction’s score gap then forces enough mass through the intended low-cost changes that splitting mass cannot turn a no-instance into a yes-instance. That gives a concrete route to a hardness proof with \(\tau=2\), rather than an assumption that fractional mass preserves the discrete reduction.
A second, cleaner anchor is Theorem 4.1, also proved here: unit-cost destructive swap bribery is in P for every polynomial-time-computable family of scoring rules. Its mirror is Unit-Cost Scoring Destructive Bribery\(_\infty\). The input is a scoring vector from such a family, a rational distribution \(\mu\) over supported rankings, and a candidate \(c\) who is initially the unique winner. Transfer mass \(x_{t,R'}\) from each supported ranking \(t\) to output rankings \(R'\), with \(\sum_{R'}x_{t,R'}=\mu_t\) and cost \(\sum_{t,R'}d_{\mathrm{swap}}(t,R')x_{t,R'}\). Minimize that cost subject to some challenger tying or beating \(c\). Types here are just rankings, since every swap has unit cost.
This version is especially close to the paper’s stated robustness question: adjacent swaps represent the same worst-case preference errors, while the society itself is the distribution over ballots. It is also plausible in a large electorate where many voters use a relatively small set of ballot types. I expect Class A. For each challenger, the paper’s single-vote calculation gives the best possible score-margin improvement at each swap cost. Assigning each type’s mass among those cost-and-improvement options yields a rational LP with polynomially many options per supported type. Repeating this for the challengers gives the minimum continuous cost. That makes the expected running time polynomial in \(m,\tau,L\), and the score-vector encoding length.
These anchors also suggest follow-up questions: does priced \(k\)-approval remain hard when \(k\) is fixed, as the paper conjectures for the discrete problem, and which restrictions on type-level price schedules restore tractability? For the unit-cost mirror, one can ask whether the same method extends beyond scoring rules, including to the Condorcet case of Theorem 5.1, or yields useful parameterized bounds in \(\tau\).
The mirror covers Theorems 4.1 and 4.2, not the paper’s entire contribution. I would not use its robustness-bound theorems as anchors here: they give asymptotic bounds, rather than named results asserting a standard complexity classification.
The weakest point is that the hardness anchor needs type-level price schedules, a less immediate high-multiplicity story than identical unit-cost swaps. Also, fractional transfers require adapting—not simply reusing—the paper’s hardness reduction. The unit-cost mirror is the more natural connection to the paper’s error model; the priced mirror earns its place because its hardness appears to survive with only two continuous types.
The strongest objection is to the priced \(k\)-approval mirror. Its type includes a complete swap-price schedule, which makes the cohort story less immediate than cohorts sharing only a ballot: the prices are part of what must repeat. And the paper’s two-voter hardness reduction does not transfer automatically, since divisible mass can split across outcomes. But neither point defeats the better mirror. Cohorts facing the same intervention tariff are plausible, and the reduction can make the target score require moving an entire type’s mass through the intended low-cost changes. This is a real hardness question, though its continuous reduction needs to be proved.
I cannot make a comparable objection to the unit-cost scoring mirror. It uses exactly the paper’s error model, with rankings as types and rational mass in place of voter counts. For a fixed challenger, only the final positions of that challenger and the current winner affect the score gap. For each supported ranking, one can enumerate those position pairs, compute the cheapest swap distance for each, and formulate the mass allocation as a linear program. That looks like a clean, computationally meaningful high-multiplicity question.
The best negative case is therefore about priority: the unit-cost mirror may yield to a short LP argument, and the priced mirror requires more modeling choices. But the programme’s standard explicitly rules out treating an easy or unchanged answer as a reason the question was not worth asking. I don’t see an honest ground that defeats the unit-cost anchor, so I can’t defend the universal claim that no worthwhile continuous mirror exists.
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.