| paper | d4-conf-atal-2014-0092 |
| 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 \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6.3
statement extracted from the paper’s text layer
Given candidates \(C\), target \(p\), registered mass \(\mu_t\) and eligible unregistered mass \(\nu_t\) on supported ranking types \(t\), and an addition budget \(\kappa\), decide whether there are masses \(x_t\) with \(0\le x_t\le\nu_t\) and \(\sum_t x_t\le\kappa\) such that \(\sum_t(\mu_t+x_t)(s_r(t,p)-s_r(t,c))\ge0\) for every \(c\ne p\) and \(r\in\{2\text{-Approval},1\text{-Veto}\}\). Take \(\mu\), \(\nu\), and \(\kappa\) as binary rational masses on the same registered-population scale.
Ranking types \(t\) carry registered mass \(\mu_t\) and eligible mass \(\nu_t\); choose mobilized mass \(x_t\), minimize \(\sum_t x_t\), subject to \(0\le x_t\le\nu_t\) and the requirement that \(p\) co-win under both rules at mass profile \(\mu+x\). Compare the optimum with \(\kappa\).
The mirror covers Theorem 6.3 for \(\{2\text{-Approval},1\text{-Veto}\}\text{-CCAV}\) only; it makes no claim about the paper’s other bribery, manipulation, or control results.
I would lead with Theorem 6.3, proved in this paper. It says that constructive control by adding voters under the uncertain family \(\{2\text{-Approval},1\text{-Veto}\}\) is NP-complete: given registered voters, an unregistered voter pool, a preferred candidate \(p\), and a limit \(k\), decide whether adding at most \(k\) unregistered voters can make \(p\) a co-winner under both rules. The paper proves this by reduction from 3-Dimensional Matching. This is a strong anchor because the uncertainty and the shared action are part of the problem itself.
A continuous counterpart is Fractional \(\{2\text{-Approval},1\text{-Veto}\}\)-CCAV. An instance has candidates \(C\), target \(p\), a registered mass distribution \(\mu\) over rankings, an available unregistered mass \(\nu\) over rankings, and a budget \(\kappa\). Both pools are described by their supported rankings and binary rational masses; normalize \(\mu\) to sum to \(1\), and measure \(\nu\) and \(\kappa\) relative to that registered-population scale. A type is a complete ranking, with registration or eligibility status represented by which pool contains its mass.
The decision question is whether there is a vector of added masses \(x_t\) satisfying \(0\le x_t\le\nu_t\) and \(\sum_t x_t\le\kappa\), such that \(p\) is a co-winner under both rules in the resulting society. Equivalently, minimize \(\sum_t x_t\) subject to those winner conditions, and ask whether the optimum is at most \(\kappa\). Writing \(s_{2A}(t,c)=1\) when \(c\) is ranked in the top two of \(t\), and \(s_{1V}(t,c)=1\) when \(c\) is not ranked last, the shared-action requirement is captured by the same \(x\) in both sets of inequalities:
\[
\sum_t(\mu_t+x_t)\bigl(s_r(t,p)-s_r(t,c)\bigr)\ge 0
\quad\text{for every }c\ne p,\quad r\in\{2A,1V\}.
\]
Normalizing \(\mu+x\) to sum to \(1\) does not change its winners. A solution is a feasible rational mass vector \(x\).
This is a sensible high-multiplicity regime for a large online or institutional election: many registered and eligible voters share a relatively small set of complete rankings, and a campaign can mobilize a fraction of an unregistered group. The actor still has the paper’s goal, faces the same uncertainty about which rule will be used, and must use one addition action that succeeds under both. For a finite election scaled by \(N\), the corresponding masses are \(\mu_t=n_t/N\), \(\nu_t=w_t/N\), and \(\kappa=k/N\); the continuous version allows \(x_t\) to vary continuously instead of requiring multiples of \(1/N\).
I expect this mirror to be tractable. The winner conditions are linear, so the problem is a rational linear program with \(O(\tau)\) variables and \(O(m)\) winner inequalities for each of the two rules. It is solvable in time polynomial in \(m,\tau\), and the input bit length. In the programme’s terms, this is a Class A mirror: fractional population action turns the decision into an LP.
The main weakness is that Theorem 6.3’s reduction encodes 3-dimensional matches in the available ballots and relies on choosing an indivisible subset. It does not show that hardness persists when many voters share each type; indeed, the mirror relaxes precisely that indivisibility. That is also why the result is interesting as a continuization question: it preserves the paper’s underlying CCAV task while asking whether its hardness survives when mobilization is measured in mass. A natural next question is whether the LP solution admits useful rounding guarantees for finite elections, perhaps with an additive error governed by the number of supported types.
This case covers Theorem 6.3 alone; I would not use it to claim a mirror for the paper’s other bribery, manipulation, or control results.
The strongest negative case against Theorem 6.3 is about how much research value this particular mirror adds. For any fixed finite family of scoring rules, fractional CCAV can be written as an LP: choose added mass \(x_t\) for each available ranking type, bound it by that type’s available mass, and impose the score inequalities for every rule and opponent of \(p\). That makes this a clean Class A example, but it needs no pricing algorithm or new structural insight. The paper’s 3-Dimensional Matching reduction relies on choosing an indivisible subset of ballots; the continuous version relaxes exactly that feature.
That criticism does not defeat the mirror. In a large online or institutional election, many registered voters and eligible but unregistered voters can share a relatively small set of rankings. Let \(\mu_t\) be registered mass, \(\nu_t\) eligible mass, and \(x_t\) the mobilized mass, with \(0\le x_t\le\nu_t\) and \(\sum_t x_t\le\kappa\). Requiring \(p\) to co-win under both rules gives linear inequalities in \(\mu_t+x_t\). Eligibility can be part of a voter’s type, and rescaling after adding mass does not change the winners. This preserves the paper’s central feature: one action must succeed regardless of which rule is used.
The usual objections do not hold here. The action does not depend on individual identities; the relevant inputs are rankings and eligibility. Mass remains meaningful as the population and mobilization limit scale. There is no degeneracy in the stated model, and the paper’s discrete hardness is not a reason to reject a well-posed continuous question. Nor does the supplied prior art identify a continuous computational treatment of this CCAV problem.
So I cannot honestly defeat this anchor. Its likely weakness is that the resulting LP may be a modest contribution, not that the mirror is incoherent or unworthy of study. Under the stated standard, Theorem 6.3 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.