| paper | d4-conf-atal-2017-0344 |
| 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 under both conventions, in \(\operatorname{poly}(L)+t\,\operatorname{poly}(m+\tau+L)\) time. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), an ordered finite grade set \(G\), a target \(p\in C\), a rational distribution \(\mu\) over supported complete grade vectors \(r\in G^C\), a budget \(\beta\in[0,1]\), and a unique-winner or co-winner convention, is there a nonnegative mass transfer \(x_{r,s}\) from supported input types \(r\) to output vectors \(s\in G^C\), with \(\sum_s x_{r,s}\le\mu_r\) for every \(r\) and \(\sum_{r\ne s}x_{r,s}\le\beta\), such that \(p\) wins? Define candidate \(c\)'s majority grade as the least \(g\in G\) for which \(\sum_{r:r(c)\preceq g}\mu'_r\ge\tfrac12\), where \(\mu'\) is the resulting distribution.
Types are complete grade vectors \(r\in G^C\), with rational masses \(\mu_r\). Choose how much mass \(z_r\) remains unchanged and how much recast mass to assign each candidate-grade pair, represented by marginals \(y_{c,g}\); require total recast mass at most \(\beta\) and the majority-grade winner conditions, with the optimization version minimizing recast mass.
The X3C reduction uses essentially distinct ballots, so its hard instances may have support close to the population size; the proposed short-slate, repeated-rating regime makes the mirror plausible but does not show that it captures that hard regime.
fatal: False
The mirror covers Theorem 8's constructive whole-vote bribery result only; it makes no claim about the paper's control, destructive-bribery, or grade-bribery results.
The strongest positive case is constructive bribery, anchored by Theorem 8. The paper proves there that constructive bribery for majority judgment is NP-hard even with only two grades. The theorem is proved in this paper by reduction from Exact 3-Set Cover: it builds an election where a set of at most \(\kappa\) voters can be bribed to make the target candidate win exactly when the X3C instance has an exact cover. The paper states that its results hold in both the unique-winner and co-winner models. This is a good anchor because the paper’s decision problem—how many voters must an external agent persuade or pay to recast their votes?—has a direct population-mass analogue.
The regime I would use is a large rating platform or evaluation exercise: millions of users grade the same shortlist of products, films, or proposals using a common scale. A voter type is the user’s complete grade vector across that shortlist. With a fixed shortlist and finite grade scale, many users can share one of finitely many vectors, so the population can be much larger than the number \(\tau\) of observed types. A campaign that persuades a fraction of users to submit new ratings is a plausible mass intervention.
Call the mirror Continuous Majority-Judgment Constructive Bribery. An instance consists of candidates \(C\), a linearly ordered finite grade set \(G\), a target \(p\in C\), a rational distribution \(\mu\) over the supported types \(r\in G^C\), a rational budget \(\beta\in[0,1]\), and a winner convention (unique winner or co-winner). The masses satisfy \(\sum_r\mu_r=1\). A solution is a nonnegative rational transfer plan \(x_{r,s}\), where \(r\) is an original supported type and \(s\in G^C\) is any new grade vector, such that
\[
\sum_s x_{r,s}\le \mu_r
\quad\text{for every }r,
\qquad
\sum_{r,s:\,r\ne s}x_{r,s}\le\beta.
\]
It produces the society
\[
\mu'_u=\mu_u-\sum_s x_{u,s}+\sum_r x_{r,u}.
\]
The question is whether such a plan exists that makes \(p\) a winner. Define a candidate’s majority grade as the least \(g\in G\) for which \(\sum_{r:r(c)\preceq g}\mu'_r\ge \tfrac12\). The optimization version minimizes the transferred mass. This is the paper’s whole-vote bribery operation with its budget measured as a fraction of the population; the discrete profile maps to masses \(\mu_r=n_r/n\), and a budget of \(k\) voters maps to \(\beta=k/n\).
I expect this mirror to be tractable (Class A). For each possible majority grade \(g\) of \(p\), the winner conditions are linear inequalities on cumulative grade masses. A compact LP can keep variables for the mass \(z_r\) left unchanged at each input type and variables \(y_{c,h}\) for the grade-\(h\) mass assigned to each candidate among the bribed population. The bribed mass is \(1-\sum_r z_r\), bounded by \(\beta\). Since a bribed voter may submit any grade vector, any chosen per-candidate grade marginals for that mass can be realized jointly. Thus the LP need not enumerate all \(t^m\) possible output types. Enumerating \(g\) gives polynomially many LPs in \(m,\tau,t\), and the input bit length. Strict inequalities for the unique-winner case can be handled by maximizing a common slack and checking whether it is positive.
The mirror covers Theorem 8’s constructive, whole-vote bribery result only. It does not claim to cover the paper’s control problems, its destructive-bribery algorithm, or grade bribery, where the unit being changed and the cost are different. The weakest point is the same feature that makes the expected LP possible: the continuous model allows a type’s mass to be split, while Theorem 8’s reduction depends on choosing indivisible voters. If the authors regard voter-by-voter atomicity as essential to the question, they may see this as an LP relaxation rather than their problem. I think the mass budget remains a faithful high-multiplicity version of their bribery question, but the continuous tractability would be a new result to establish, not a consequence of Theorem 8. Further work would need to pin down the finite-to-continuous dictionary at exact median ties and measure how well the continuous optimum approximates finite-\(n\) bribery.
The strongest case against Theorem 8’s mirror is that “many people rate things” does not by itself give high multiplicity. A type must be a voter’s complete grade vector across all candidates, so with \(m\) candidates and \(t\) grades there are \(t^m\) possible types. As the shortlist grows, users may have mostly distinct vectors and \(\tau\) may be close to the population size. The theorem’s X3C construction illustrates the issue: its set-encoding ballots are essentially distinct types, so grouping identical voters does little to compress those hard instances.
That objection weakens for a fixed, short slate with a common grade scale and a uniform campaign that can ask any voter to recast their whole ballot. There, the type space is finite and can be small relative to the population; the budget can naturally be measured as a fraction of voters. The proposed mirror also preserves the paper’s operation: bribed mass can be reassigned to arbitrary grade vectors, just as a bribed voter can recast an arbitrary vote. I see no fundamental loss of information in its marginal-based formulation that would rule this version out.
So I cannot honestly defeat this anchor across all scenarios. The case against is that the proponent’s large-platform example may have too many complete ballot types to make the continuum a useful population model. But a short, repeated-rating setting remains plausible, and the fact that fractional mass removes the discrete reduction’s combinatorics is not a valid objection under the programme’s criteria. The negative case is weak; Theorem 8’s constructive-bribery problem survives as a worthwhile continuous mirror.
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.