| paper | d4-conf-aaai-2006-0054 |
| 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 in \(m,\tau,L\); the problem belongs to \(\mathrm{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given candidates \(C\), a target \(p\in C\), rational \(\beta\in[0,1]\), and approval types \(A_i\subseteq C\) with positive rational masses \(\mu_i\) summing to \(1\), is there a mass transfer of total cost at most \(\beta\) that makes \(p\) a winner? Each unit of mass may be bribed at unit cost and assigned any approval ballot.
Represent the society by its supported approval types \(A_i\) and masses \(\mu_i\). Let \(x_i\) be the mass bribed from type \(A_i\), and send it to ballot \(\{p\}\), which never worsens \(p\)'s margin. With \(S_c=\sum_{i:c\in A_i}\mu_i\), minimize \(\sum_i x_i\) subject to \(0\le x_i\le\mu_i\) and, for each \(c\ne p\), \(S_p+\sum_{i:p\notin A_i}x_i\ge S_c-\sum_{i:c\in A_i}x_i\); ask whether the minimum is at most \(\beta\).
The mirror covers the approval-bribery hardness claim in Theorem 7. It does not mirror that theorem’s polynomial-time manipulation claims, approval-bribery′ in Theorem 8, or the paper’s other bribery results.
My lead is Continuous Approval Bribery, mirroring Theorem 7. The paper proves that approval-bribery is NP-complete: given approval ballots, a target candidate, and a limit of \(k\) voters to bribe, decide whether changing up to \(k\) voters’ ballots can make the target a winner. The theorem also states that approval-manipulation and approval-weighted-manipulation are both in P. The paper proves the hardness result by reduction from Exact-Cover-by-3Sets; the two manipulation algorithms are straightforward.
The continuous problem keeps the same approval rule and the same action of overwriting a bribed voter’s entire ballot. Its instance is a candidate set \(C\), target \(p\in C\), rational budget \(\beta\in[0,1]\), and a list of the \(\tau\) approval types \(A_i\subseteq C\) present in the society, each with rational mass \(\mu_i>0\), where \(\sum_i\mu_i=1\). A type is a complete approval ballot; its mass is the fraction of society casting that ballot. Each unit of mass costs one unit to bribe, matching the paper’s unpriced, unweighted bribery model. Continuous Approval Bribery asks whether mass at most \(\beta\) can be bribed and reassigned approval ballots so that \(p\) is a winner. A solution is the mass transferred from each type and its destination ballot.
It suffices to send every bribed voter to the ballot \(\{p\}\): this never lowers \(p\)’s score and never raises another candidate’s. Let \(x_i\) be the bribed mass from type \(A_i\), and let \(S_c=\sum_{i:c\in A_i}\mu_i\) be candidate \(c\)’s original score. The question is whether there are \(x_i\) satisfying \(0\le x_i\le\mu_i\), \(\sum_i x_i\le\beta\), and, for every \(c\ne p\),
\[
S_p+\sum_{i:p\notin A_i}x_i
\;\ge\;
S_c-\sum_{i:c\in A_i}x_i.
\]
Thus the mirror is a polynomial-size linear program, with \(\tau\) variables and \(m\) winner constraints. I expect it to be in Class A, tractable, in time polynomial in \(m,\tau\), and the input bit length. This is a result to investigate for the mirror, not a theorem claimed by the paper.
A plausible regime is a large membership organization or online community voting on candidates or proposals by approving any subset. Many members may share the same ballot, so the population size \(N\) can be much larger than the number of distinct ballots \(\tau\). A campaign might persuade a fraction of a ballot cohort to replace its ballot. This is a high-multiplicity scenario: agents of a type are identical in every respect relevant to this anchor, and the population is the continuous object. Winners and ballots remain discrete. The authors should recognize this as their bribery problem because the vote tally and the full-ballot change are preserved; the limit of whole voters is replaced by a limit on population mass.
The continuous answer also makes the paper’s exact-cover hardness informative: selecting whole voters creates an integrality requirement that the mass-transfer LP does not have. A useful next question is how closely this mirror approximates finite elections. If a finite profile has \(n_i\) voters of each type, then \(\mu_i=n_i/n\); rounding each \(x_i\) upward to a whole voter preserves the winner inequalities and adds fewer than \(\tau\) bribes. That gives an additive \(\tau/n\) bound on the bribed fraction, and motivates sharper questions about integrality gaps and exact correspondence. One can also ask how the LP changes when the problem adds type-dependent prices or voting weights; those features are not part of this anchor.
The weakest point is that persuading an arbitrary fraction of a cohort to overwrite its ballot must make sense in the chosen setting. If influence happens only voter by voter, this is a relaxation rather than a literal operational model. The large-cohort scenario makes mass the natural quantity, but it does not establish that every real campaign can act at that granularity. That qualification limits the regime, while leaving the continuous question faithful to the paper’s approval-bribery action and winner condition.
I can’t honestly defeat this anchor. Theorem 7 is a named computational result about approval bribery, and its mass version is well posed: approval ballots are complete types, bribery is an allowed transfer between types, and the winner condition remains meaningful for fractional masses. A large organization with recurring ballot patterns gives a plausible high multiplicity regime. Neither voter identity nor a vanishing cost undermines the model.
The strongest objection is that persuading an arbitrary fraction of a ballot cohort may not be an available real-world action. But that is a limitation of a particular campaign scenario, not of the mirror: ChoCo treats a continuous society as the high multiplicity version of the problem, and the paper’s bribery model imposes no further constraints on which voters can be persuaded. The membership-organization scenario is credible enough to answer that concern.
The exact-cover hardness disappearing into a polynomial-size LP also cannot count against the mirror; that difference is precisely the kind of result the programme seeks. The proponent’s rounding observation reinforces the connection to finite elections. The negative case here is weak: this anchor survives the stated criteria.
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.