| paper | d4-conf-aaai-2008-0253 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Exactly solvable in \(\operatorname{poly}(m,\tau,L)\) time; the fixed polynomial \(q(z)=z\) suffices. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given \(m\) candidates, a rational distribution \(\mu\) over supported types \(t=(v_t,g_t)\), where \(v_t\) is a complete ranking and \(g_t\) is its bribery price, a target \(p\), and a per-capita budget \(b\), choose transfers \(x_{t,r}\geq 0\) from source type \(t\) to ranking \(r\), subject to \(\sum_r x_{t,r}\leq\mu_t\) and \(\sum_{t,r}g_t x_{t,r}\leq b\). What is the maximum increase in \(p\)'s per-capita Borda performance, \(\mathrm{perf}_{\mu'}(p)-\mathrm{perf}_{\mu}(p)\), over the resulting societies \(\mu'\)?
Each type is a ranking paired with its price; transfers preserve the source type's price when charging the budget. For each source type, scaled doubly stochastic assignment variables describe how bribed mass is distributed across candidate positions and hence across rankings. The budget and Borda performance constraints are linear, giving an exact LP with \(O(\tau m^2)\) assignment variables.
The mirror covers the Borda bribery results in Theorems 8 and 9. It leaves the weighted-manipulation approximation and inapproximability results, including Theorems 2 and 4–7, aside.
My strongest mirror is Borda Continuous Price-Bribery Performance, based on Theorem 9. It is proved in this paper: for every polynomial \(q\), unless \(P=NP\), there is no polynomial-time algorithm for Borda-\(\$\)-bribery-max that always returns a legal strategy \(s\) with \(q(\beta(E,s))\geq \mathrm{OPT}(I)\). Here the input gives each vote a price, a preferred candidate \(p\), and a budget; a strategy changes votes whose total price is within budget and maximizes \(\beta(E,s)=\mathrm{perf}_{s(E)}(p)-\mathrm{perf}_E(p)\), where \(\mathrm{perf}_E(p)=\mathrm{score}_E(p)-\max_{c\ne p}\mathrm{score}_E(c)\).
In the mirror, a type is a complete ranking together with its per-voter price. The instance gives a rational mass \(\mu_t\) for each of the \(\tau\) supported types, a target \(p\), and a per-capita budget \(b\). Choose nonnegative transfers \(x_{t,r}\), where \(x_{t,r}\) is mass taken from source type \(t\) and given ranking \(r\). Require \(\sum_r x_{t,r}\leq\mu_t\) and \(\sum_{t,r}g_t x_{t,r}\leq b\), where \(g_t\) is the price in type \(t\). The question is to maximize the increase in \(p\)’s per-capita Borda performance; a solution is the transfers and their resulting society. This is the lead because it mirrors the paper’s priced optimization problem, including its objective and budget, while making the population itself continuous.
This fits a large election or consultation in which many people have one of a relatively small number of rankings and standardized price categories: the population size \(n\) is much larger than \(\tau\), with \(\tau\leq m!R\) if there are \(R\) price categories. In a discrete instance with \(n\) voters, masses are \(n_t/n\) and the per-capita budget is \(k/n\). Prices belong in the type definition because they determine how much an agent costs to bribe. Fractional mass transfers are the natural high-multiplicity version of changing up to a budgeted number of ballots.
I expect this mirror to be tractable. Let \(x_t=\sum_r x_{t,r}\). For each source type \(t\), describe the bribed mass’s output ballots by \(y_{t,c,j}\): the amount of that mass placing candidate \(c\) in Borda position \(j\). Require every candidate and every position to receive exactly \(x_t\) mass. This is a scaled doubly stochastic assignment matrix, so it decomposes into a mixture of complete rankings. It gives a compact LP with \(O(\tau m^2)\) variables; price budgets and the final per-capita score margins are linear. An optimal solution can be converted back to a mass transfer among rankings. Thus the continuous question appears exactly solvable by LP.
Theorem 8 gives a second, simpler anchor for the same case. It is also proved here: Borda-bribery is NP-complete. Its input is an election, a distinguished candidate \(p\), and an integer \(k\); it asks whether changing at most \(k\) votes can make \(p\) a winner. My corresponding Borda Continuous Winner-Bribery question takes a distribution over ranking types, a target \(p\), and a mass budget \(b\). Can transfers from those types, totaling at most \(b\), produce a society in which \(p\) is a Borda winner? A transfer certificate is a solution. This is the feasibility version of the LP above, with unit cost per unit mass, and I likewise expect it to be tractable. It is a direct mirror of the paper’s underlying bribery question: the decision variable is how much of each preference type to change and into which rankings.
These mirrors cover the paper’s Borda bribery results in Theorems 8 and 9; they do not claim to continuize the weighted-manipulation results or the paper as a whole. The central follow-up is how the LP’s optimum compares with the discrete optimum when mass is restricted to multiples of \(1/n\): can one bound the rounding loss in terms of \(m,\tau\), and \(n\)? A further question is which richer price or action models preserve the compact assignment structure.
The weakest point is that fractional transfers can destroy the indivisibility that carries the Theorem 8 reduction’s exact-cover structure. The continuous LP is therefore a high-multiplicity relaxation, not an algorithm for every finite electorate. That is still a plausible mirror: the paper formulates bribery directly as changing ballots under a budget, and a society with millions of voters sharing a moderate number of complete preference-and-price types is a credible regime for asking how much of that computational hardness survives. One caveat on Theorem 9: its stated polynomial-\(q\) inapproximability uses total score units, whereas the continuous model naturally uses per-capita scores. I am mirroring its optimization problem and expect the continuous problem to be tractable; I do not claim the exact scale-sensitive approximation statement transfers unchanged.
The best negative case is narrow. Theorem 9’s guarantee is stated using total score improvement, while a continuous society naturally uses per-capita improvement. Dividing by the electorate size changes the scale inside \(q(\beta)\), so the paper’s precise inapproximability statement does not carry over unchanged. The price-type model also has practical force only in regimes with a moderate number of distinct ranking and price combinations.
Those limits do not defeat the stronger version of the mirror. For each source type \(t\), let \(x_t\) be the mass bribed and \(y_{t,c,j}\) the mass assigned to ballots placing candidate \(c\) in position \(j\). Require each candidate and each position to receive \(x_t\) mass. These scaled assignment constraints describe mixtures of complete rankings, by the Birkhoff–von Neumann theorem. The budget is \(\sum_t g_t x_t\leq b\). Final Borda scores are linear in the \(y\) variables, and maximizing \(p\)’s performance is an LP: introduce \(z\leq \mathrm{sc}(p)-\mathrm{sc}(c)\) for every rival and maximize \(z\). The original performance is constant, so this also maximizes its increase. The LP has \(O(\tau m^2)\) variables. A large election with many voters but relatively few ranking and price types is a sensible setting for this question.
Theorem 8 gives a second mirror that avoids the price-model concern. With unit cost per voter, impose \(\sum_t x_t\leq b\) and require \(p\)’s final Borda score to be at least every rival’s. This is also an LP over the same assignment variables. The exact-cover reduction depends on indivisible voter choices; the continuous version asks what happens when those choices become divisible. That is precisely the kind of change the programme is meant to study.
The paper has named computational results, the objective depends on aggregate scores rather than voter identities, and the per-capita quantities remain meaningful in the limit. I see no continuous treatment here that already answers either question. So the honest negative case is weak: the two bribery anchors survive their strongest natural formulations. The real caveat is that these mirrors describe a high-multiplicity regime; they do not promise useful compression when almost every voter has a unique type.
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.