| paper | d4-conf-ecai-2014-0030 |
| 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}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a candidate set \(C\), a finite set \(T\) of ranking types, registered masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), available unregistered masses \(\nu_t\ge 0\), a target \(p\in C\), and a rational budget \(\kappa\ge 0\), decide whether there are additions \(x_t\in[0,\nu_t]\) with \(\sum_{t\in T}x_t\le\kappa\) such that \(p\) wins under \(1\text{-Approval THEN }1\text{-Approval}\). In the first round, the finalists are the candidates maximizing \(\sum_{t:\,t\text{ ranks }c\text{ first}}(\mu_t+x_t)\). In the runoff among those finalists, each mass unit supports its highest-ranked finalist; \(p\) must receive at least as much runoff mass as every other finalist. What is the complexity in \(m=|C|\), \(\tau=|T|\), and the input bit length?
Types are complete rankings of \(C\), with registered mass \(\mu_t\) and available unregistered mass \(\nu_t\) for each type. The decision variable \(x_t\) is the added mass of type \(t\); the objective in the optimization version is to minimize \(\sum_t x_t\), subject to the capacity bounds and the two-stage winner condition. Normalizing the resulting masses by their total does not change either round’s winners.
The mirror covers Theorem 2’s CCAV result for \(1\text{-Approval THEN }1\text{-Approval}\). It does not cover that theorem’s CCDV result or the paper’s other control results.
The strongest mirror I see is continuous constructive control by adding votes for \(1\text{-Approval THEN }1\text{-Approval}\).
My anchor is Theorem 2, proved in this paper. It says that both CCAV and CCDV for \(1\text{-Approval THEN }1\text{-Approval}\) are NP-hard, even though the corresponding adding-votes and deleting-votes problems for one-stage \(1\)-Approval are polynomial-time solvable. The proof gives a reduction from Vertex Cover on 3-regular graphs for CCAV and from Independent Set on 3-regular graphs for CCDV. I use the CCAV result as the lead; this mirror does not cover Theorem 2’s CCDV result.
Here is the continuous problem I would hand to a prover. Let \(C\) be the candidate set, and let each type \(t\) be a complete ranking of \(C\). The input gives registered mass \(\mu_t\) and available unregistered mass \(\nu_t\) for each supported type, with \(\sum_t\mu_t=1\), along with a target \(p\) and a rational budget \(\kappa\). The masses are binary rationals. Choose added mass \(x_t\) with \(0\le x_t\le\nu_t\) and \(\sum_t x_t\le\kappa\); the resulting society has mass \(q_t=\mu_t+x_t\).
For any candidate \(c\), let \(A_q(c)\) be the mass ranking \(c\) first. The first-round finalists are \(S=\arg\max_{c\in C}A_q(c)\). For each \(c\in S\), let \(B_q(c;S)\) be the mass whose highest-ranked candidate within \(S\) is \(c\). The question is whether some choice of \(x\) makes \(p\in S\) and \(B_q(p;S)\ge B_q(c;S)\) for every \(c\in S\). A solution is the vector \(x\); the optimization version minimizes \(\sum_t x_t\).
The regime is a large electorate with many voters sharing complete rankings, and a pool of eligible voters grouped by those same rankings. For instance, a campaign might be able to mobilize a fraction of each ballot cohort. The electorate size \(N\) can greatly exceed the number \(\tau\) of supported ranking types. Registration status determines whether mass belongs to \(\mu\) or \(\nu\); within a cohort, voters have the same preference and unit control cost. This keeps the paper’s action and runoff semantics while making selected mass, rather than individual voters, the decision variable. The authors should recognize it as their adding-votes problem in a high-multiplicity regime.
My cautious expectation is that the full variable-\(m\) mirror could be Class C, though that is a conjecture, not a consequence of Theorem 2. For a fixed finalist set \(S\), the mass constraints and runoff conditions are linear in \(x\); one can check that case by LP. The unresolved search over possible finalist sets is the apparent source of remaining combinatorial difficulty. A useful boundary question is whether this can be handled in time polynomial in \(m,\tau,L\), or whether the finalist-set choice keeps the problem hard.
The soft spot is substantial: the paper’s displayed CCAV reduction does not itself establish hardness after continuization. In that construction, each graph-vertex candidate has three registered first-place votes and can receive one available vote, while the existing finalists have score four. If the available ballots rank \(p\) second, adding a small mass \(k/n\) to each of the \(n\) vertex types leaves every vertex candidate below the first-round threshold, while that added mass transfers to \(p\) in the runoff. For \(0<k<n\), this can make \(p\) win within budget regardless of whether the graph has a size-\(k\) vertex cover. So the mirror is not justified by simply reusing the reduction. Its value is the precise computational question it exposes: does fractional population control make the problem tractable, or does the discrete choice of finalists retain enough structure for a new hardness result?
Theorem 2 gives a real computational result to mirror, so “there is no named problem” is unavailable. Its CCAV result is a plausible target: many voters can share a ranking, and a campaign can have a pool of eligible voters in each cohort. The proponent’s version captures that by assigning masses to registered and unregistered ranking types and allowing the campaign to mobilize some available mass.
The strongest objection is that this changes what “adding votes” operationally means. In the paper, a campaign selects at most \(k\) individual voters from a fixed pool. In the continuous version, it can select any fraction of a type’s available mass. If the campaign’s reach depends on location, cost, or personal eligibility, those attributes must also be part of the type. That can make the support large and the fractional action less representative of the real intervention.
But this is not a decisive objection under the programme’s definition. A large electorate can plausibly contain many voters with the same ranking and action-relevant attributes, and a campaign can target a fraction of such a cohort. Adding the availability and cost data to the types is a recognizable high-multiplicity version of CCAV. Normalizing the enlarged population after adding mass is a straightforward bookkeeping fix.
The paper’s reduction does not establish that its hardness survives this version: fractional additions can change the first-round finalists without selecting a discrete vertex cover. That weakens any claim that the mirror is already known to be hard. It does not make the question unworthy; whether this relaxation is tractable is exactly the computational question a continuous mirror would pose.
So I cannot honestly defeat this anchor. The negative case rests on a mismatch between individual mobilization and fractional control, but the mismatch has a credible large-cohort scenario and a natural formal repair. This is a weak case against a worthwhile 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.