| paper | d4-conf-atal-2015-0204 |
| 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 dyadic masses; also \(\mathrm{W}[2]\)-hard parameterized by \(B\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given two candidates \(p,d\), a budget \(B\), and \(\tau\) types with positive rational masses \(\mu_t\) summing to \(1\), each type has a ranking and a response \(a_{jt}\in\{0,1\}\) to each of \(\zeta\) campaigns. Is there a set \(S\) of at most \(B\) campaigns such that, after their effects add and \(p\)'s position is capped at the top, at least half the society ranks \(p\) first? Equivalently, does \(\sum_{t:\,p\text{ initially ranks first or }\sum_{j\in S}a_{jt}\ge1}\mu_t\ge\frac12\) hold for some such \(S\)?
Represent each complete preference-and-response type \(t\) by mass \(\mu_t\). Choose binary campaign variables \(x_j\in\{0,1\}\), minimize \(\sum_{j=1}^{\zeta}x_j\), and require \(\sum_{t:\,p\text{ initially ranks first or }\sum_j a_{jt}x_j\ge1}\mu_t\ge\frac12\).
The mirror covers Theorem 4's positive-only, two-candidate, unit-effect setting; the signed cohort variant also mirrors Theorem 6. It leaves the paper's other action restrictions, parameterized results, and approximation algorithms outside this mirror.
My lead is a high-multiplicity version of Combinatorial Shift Bribery, anchored in Theorem 4. The theorem is proved by the paper’s authors; the paper notes that some proof details are deferred to the full version. It says that both Plurality-CSB and Borda-CSB are NP-hard and W[2]-hard parameterized by budget \(B\), even with only two candidates and even when every action’s effect on every voter is either \(0\) or \(+1\).
The mirror is Continuous Cohort Shift Bribery\(_+\). An instance lists two candidates \(p,d\), a budget \(B\), and \(\tau\) voter types with positive rational masses \(\mu_t\) summing to \(1\). A type includes a complete ranking and its response to each of the \(\zeta\) available campaigns. Campaign \(j\) has a unit effect \(a_{jt}\in\{0,1\}\) on type \(t\). Choose a subset \(S\) of at most \(B\) campaigns. Each unit of type \(t\) experiences net shift \(\sum_{j\in S}a_{jt}\), moving \(p\) forward that many positions, capped at the top of the ranking. The question is whether some such \(S\) makes \(p\) a nonunique Plurality winner; equivalently, the optimization version asks for the smallest successful campaign set. With two candidates, Borda has the same winner condition.
The scenario is a large electorate with stable preference and campaign-response cohorts: for example, many voters whose initial ranking and response to each campaign are alike. The unit of mass is a fraction of the electorate; a national campaign might have millions of voters but only dozens or hundreds of such types. The model keeps the paper’s central choice intact: select a shared campaign package, whose effects accumulate across the population, to make the preferred candidate win.
I expect this mirror to be Class B: hardness transfers. Given a discrete election, make each voter a type of mass \(1/n\) and copy that voter’s ranking and campaign effects. Every campaign subset then produces exactly the same winner as in the discrete instance, so the NP-hardness and W[2]-hardness carry over. This also shows why the hardness is plausible here: the difficult choice is the subset of campaigns, not allocating indivisible voters. A natural next question is whether the problem becomes tractable when parameterized by \(\tau\), or when both \(\tau\) and \(B\) are small; Theorem 4’s hardness in \(B\) alone does not settle that.
A second anchor is Theorem 6, also a result proved by the authors, with some proof details deferred. It says that, unless \(P=NP\), neither Plurality-CSB nor Borda-CSB has a polynomial-time exact algorithm or approximation algorithm, even with two candidates and only \((+1,-1)\)-shift actions. Each such action affects at most two voters, one positively and one negatively.
The corresponding mirror, Continuous Cohort Shift Bribery\(_{\pm}\), uses the same input and winner condition, but restricts each campaign to a \(+1\) effect on one type and a \(-1\) effect on another, with zero effect on all other types. Selecting campaigns still means selecting a subset; the effects add before \(p\)’s position is capped at the top or bottom. This is a model of campaigns that persuade one cohort while alienating another. The same one-voter-per-type embedding carries the stated hardness and approximation barrier, so I also expect Class B. It raises the related question of whether backlash changes tractability in low-\(\tau\) societies, even where positive-only campaigns might be manageable.
The positive-only lead is stronger for me: it shows that the hard campaign-selection problem does not depend on negative reactions. The signed result adds a plausible feature of campaign management and a stronger approximation warning.
The weakest point is that the embedding proves hardness when the number of types can grow with the election. It does not show hardness for a fixed or small \(\tau\), or that the paper’s hard instances already have a small number of complete response types. Replicating each type can make the population arbitrarily large without changing the instance, but it does not reduce type diversity. So the mirror is a credible high-multiplicity problem, while its complexity in the especially appealing \(N\gg\tau\) regime remains a question. This case covers the two-candidate, unit-cost, unit-shift results; it does not claim a mirror of the paper’s full range of rules, action restrictions, and parameterized results.
The strongest objection is about whether the hard instances have a meaningful high-multiplicity regime. In Theorem 4, campaigns can affect arbitrary subsets of voters. A voter’s complete type must therefore include their ranking and their response to every available campaign. Those response signatures can distinguish every voter: in the set-cover view, voters are elements and campaigns are sets. Theorem 6 is even more individualized, with actions aimed at pairs of voters. The proposed one-voter-per-type embedding preserves the instances, but it gives no reason to expect few types relative to the population. Cloning each voter makes the electorate arbitrarily large while leaving the number of types unchanged; it does not make the original hard instances low-support.
A stronger mirror would posit stable voter cohorts with shared responses to a standardized campaign menu, and represent each cohort by a rational mass and its full response signature. That avoids losing information and makes Theorem 4’s positive campaigns and Theorem 6’s signed effects well-defined at cohort level. But it also exposes the limit of the objection: these are recognizable high-multiplicity versions of the paper’s problem. The two-voter actions become cohort-wide effects, and arbitrary campaigns may require many response types, so the paper does not establish that its particular hardness results arise in a persuasive low-support scenario. Still, a society with repeated preference-and-response cohorts is plausible, and studying its weighted campaign-selection problem is within scope. The continuous question is neither already answered continuously nor invalidated by the fact that its answer might be dull.
So the negative case is weak. It casts doubt on whether the paper’s hard instances model large societies with few stable response types, especially for pair-specific backlash. It cannot honestly defeat the best cohort mirror or support the universal claim that no worthwhile mirror exists. Theorem 4 remains a credible anchor; Theorem 6 is less natural, but its limitations do not undo the positive-only case.
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.