| paper | d4-conf-ecai-2023-0146 |
| 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: Computing \(\operatorname{OPT}\) is possible in time polynomial in \(m,\tau,L\); the budget problem is in \(\mathrm{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
Given candidates \(C\), target \(p\), and a finite support of types \(t=(B_t,\rho_t)\) with rational masses \(\mu_t>0\) summing to \(1\), where \(B_t\in\binom{C}{3}\) is the type’s bottom-three set and \(\rho_t\) its bribery price, minimize \(\sum_t \rho_t\sum_{S\in\binom{C}{3},\,S\ne B_t} y_{t,S}\) over \(y_{t,S}\ge 0\), subject to \(\sum_{S\in\binom{C}{3}}y_{t,S}=\mu_t\) for every \(t\) and \(\sum_{t,S:\,p\in S}y_{t,S}\le\sum_{t,S:\,c\in S}y_{t,S}\) for every \(c\in C\).
A society is a rational distribution over types \(t=(B_t,\rho_t)\); \(y_{t,S}\) is the mass of type \(t\) assigned bottom-three set \(S\). Moving mass to a different set costs \(\rho_t\) per unit, and the objective is to make \(p\) a nonunique 3-Veto winner at minimum total cost. This is a linear program with \(\tau\binom{m}{3}\) variables.
The mirror covers Theorem 5, the NP-completeness of priced 3-Veto bribery. It leaves Theorems 3 and 4, the matching results, and the other control and bribery results untreated.
My lead is Theorem 5, proved in this paper. It states that 3-Veto-\(\$\)Bribery is NP-complete: given candidates, voters with nonnegative integer prices, a preferred candidate \(p\), and a budget \(k\), can the votes of a set of voters costing at most \(k\) be changed so that \(p\) is a winner? The paper proves hardness by reduction from Restricted Exact Cover by 3-Sets, where each element appears in exactly three sets; the NP-completeness of that source problem is cited.
A natural high-multiplicity setting is a very large election under 3-Veto, with millions of voters but relatively few combinations of relevant preferences and campaign prices. For this problem, a type can be \(t=(B_t,\rho_t)\), where \(B_t\) is the voter’s set of bottom-three candidates and \(\rho_t\) is their price to persuade. The rest of the ranking does not affect veto scores or bribery cost. A type’s mass \(\mu_t\) is its fraction of the electorate. This preserves the paper’s central operation—paying to change votes to make a preferred candidate win—while letting a campaign change a fraction of a type. Such types could arise when many voters share a preference pattern and belong to the same campaign-cost tier.
Here is the continuous problem I would hand to a prover. The input is a candidate set \(C\), a finite support of types \(t=(B_t,\rho_t)\) with rational masses \(\mu_t>0\) summing to \(1\), a preferred candidate \(p\), and a normalized budget \(\beta\). A solution assigns each type’s mass to post-bribery bottom-three sets: choose \(y_{t,S}\ge 0\) for every type \(t\) and every \(S\in\binom{C}{3}\), with \(\sum_S y_{t,S}=\mu_t\). The resulting veto mass for candidate \(c\) is
\[
v_y(c)=\sum_t\sum_{S:c\in S} y_{t,S}.
\]
The question is whether such an assignment exists with
\[
v_y(p)\le v_y(c)\quad\text{for every }c\in C
\]
and
\[
\sum_t \rho_t\sum_{S\ne B_t}y_{t,S}\le\beta.
\]
Equivalently, minimize that cost subject to the mass and winner constraints. The budget is normalized per capita: an original budget \(k\) for \(n\) voters becomes \(\beta=k/n\). Every destination triple is achievable by a strict ranking, and the cost charges the source type’s price for each unit of mass moved.
I expect this mirror to be Class A. It has \(\tau\binom{m}{3}\) variables and a polynomial number of rational linear constraints, so standard LP methods solve it in time polynomial in \(m\), support size \(\tau\), and input bit length. The paper’s exact-cover reduction relies on choosing whole voters for set gadgets; this model permits fractional mass transfers, so that integrality pressure can disappear. The question remains recognizably the authors’ priced 3-Veto bribery problem: the rule, prices, permissible vote changes, target, and winner condition are all retained. Only the population representation changes.
This case covers Theorem 5; it does not claim to mirror the paper’s control results or its 2-Veto algorithm. It also raises a useful bridge question: for a finite election with repeated types, how closely can an optimal mass transfer be rounded to whole voters, and what additive loss does that rounding incur? The weakest point is that the exact-cover hardness construction need not have a small type support, and real campaign prices may be highly individualized. So this is a convincing mirror for the regime with many voters per preference-price type, but it does not by itself settle how closely that tractable regime tracks the paper’s worst-case discrete instances.
I do not see an honest way to defeat the Theorem 5 mirror. The anchor is a named computational result, and a large electorate with repeated bottom-three patterns and campaign price tiers is a plausible high-multiplicity regime. Grouping voters by bottom-three set and price preserves everything this bribery problem uses: their veto contribution and the cost of changing their vote. Full rankings can be compressed away without changing the problem.
The proposed mass-transfer LP is also a strong version of the mirror. Each mass unit can be assigned to any destination bottom-three set, its source price is charged when that set changes, and the winner constraints are linear. Even allowing destination-dependent prices would leave a linear objective. The exact-cover reduction’s reliance on choosing whole voters does not undermine this model; fractional mass is precisely what makes it a continuization.
The best skeptical point is that this mirror may be too immediate to yield much beyond an LP anyone can write down once the model is specified. But that is a claim about the result’s research payoff, not a fundamental failure of the mirror, and the programme counts tractable continuizations as meaningful outcomes. I cannot make the requested universal negative case here: this anchor survives.
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.