| paper | d4-conf-atal-2014-0006 |
| 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}\)-complete for both the unique-winner and nonunique-winner models, for every fixed rational \(0\leq\alpha<1\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
For fixed \(0\leq\alpha<1\), given candidates \(C\), target \(p\), a valid supplied single-peaked partition \(P\) of width at most \(2\), and binary-rational registered and eligible masses \(\rho_r,\sigma_r\) for supported rankings \(r\), with total mass \(1\), is there a choice of \(x_r\in[0,\sigma_r]\) with \(\sum_r x_r\leq\beta\) such that \(p\) wins after adding the selected mass? For the resulting mass \(w_r=\rho_r+x_r\), pairwise support is \(M(a,b)=\sum_{r:a\succ_r b}w_r\), and \(\mathrm{Copeland}_\alpha(a)=|\{b:M(a,b)>M(b,a)\}|+\alpha|\{b:M(a,b)=M(b,a)\}|\); the input specifies unique-winner or nonunique-winner.
Agents are complete ranking-and-status types carrying rational mass; registered mass is fixed, eligible mass can be added fractionally through variables \(x_r\), and the total added mass is bounded by \(\beta\). The induced pairwise mass comparisons determine the \(\mathrm{Copeland}_\alpha\) scores and whether the target wins.
The primary mirror covers the constructive adding-vote branch of Theorem 3 for fixed \(0\leq\alpha<1\); the analogous width-\(3\) Maximin question from Theorem 8 also survives. These questions leave the deleting-vote branches and the paper’s other results unaddressed.
The cleanest mirror is the paper’s constructive control by adding votes. Take a large electorate or membership poll with a much smaller number of distinct preference types: millions of people may be represented by the shares holding each complete ranking, with separate shares for registered voters and eligible voters who could still be mobilized. A type is a complete ranking together with that eligibility status. People of one type are interchangeable for this problem, as they are in the paper’s vote-count model. The control action is to add some mass from each eligible type; the objective is to make the designated candidate win using at most a given share of the population.
My lead anchor is Theorem 3, proved in this paper. It states that, for every fixed \(0\leq\alpha<1\), constructive control by adding or deleting votes for \(\mathrm{Copeland}_\alpha\) is NP-complete on elections of single-peaked width \(2\), in both the unique-winner and nonunique-winner models. The paper proves the result by reductions from Exact 3 Set Cover, giving the adding-votes proof in detail and covering the other variants as well.
Here is the corresponding continuous question, Width-2 Fractional Constructive Adding for \(\mathrm{Copeland}_\alpha\). An instance gives candidates \(C\), a target \(p\), a supplied single-peaked partition \(P=(C_1,\ldots,C_\omega)\) with \(|C_i|\leq 2\), and registered and eligible-unregistered mass for each supported complete ranking. Every supported ranking must be compatible with \(P\): its contracted order over the intervals is single-peaked on that axis. The masses are binary rationals, and the total registered plus eligible mass is normalized to \(1\). The instance also gives a rational budget \(\beta\) and a choice of unique-winner or nonunique-winner model.
A solution is a vector \(x_t\), one entry for each eligible ranking type \(t\), with \(0\leq x_t\leq\sigma_t\) and \(\sum_t x_t\leq\beta\), such that \(p\) wins after the active mass of each ranking becomes \(\rho_t+x_t\). Pairwise support is measured by mass: \(p\) beats \(q\) when more active mass ranks \(p\) above \(q\), and ties when those masses are equal; \(\mathrm{Copeland}_\alpha\) scores then use the paper’s beat-plus-\(\alpha\)-times-tie rule. The question is whether such an \(x\) exists. This uses the paper’s vote-addition operation and winner condition, with the amount controlled measured as a share rather than a count. The relevant input-size parameters are \(m\), support size \(\tau\), and the binary encoding length \(L\) of the masses and budget.
A second worthwhile anchor is Theorem 8, also proved here. It states that constructive control by adding or deleting votes for Maximin is NP-complete on elections of single-peaked width \(3\), for both winner models. Its hardness proof is again from Exact 3 Set Cover, with the other variants obtained from the adding-votes construction. The matching mirror is Width-3 Fractional Constructive Adding for Maximin: use the same input and action format with \(|C_i|\leq3\), and accept exactly when \(p\) has maximum Maximin score after adding the chosen mass. For active ranking masses \(w_t\), the pairwise support is \(q(a,b)=\sum_{t:a\succ_t b}w_t\), and Maximin score is \(\min_{b\ne a}q(a,b)\). The decision objective is to make \(p\) a unique winner or a co-winner within budget \(\beta\).
Both mirrors are plausible objects for these authors: they retain the candidates, complete voter rankings, control action, width restriction, voting correspondence, and winner question. They replace the number of selected ballots with the fraction of an eligible population selected. That is a meaningful change in granularity, but it does not simplify the question to a different outcome rule or to a question about axioms. I would expect an electoral campaign or large organization to understand “mobilize at most \(\beta\) of the eligible electorate” as a natural version of “add at most \(t\) votes.” The relevant regime has \(N\gg\tau\): many people, with each ranking-and-status type shared by many of them. The type support may still grow with \(m\); the point is that population size need not be the number of distinct agents the computation must track.
My initial expectation for both mirrors is Class A, though only as a research bet. The paper’s reductions choose whole ballots, one per set in an Exact 3 Set Cover instance. In the continuous versions, a type can be selected fractionally. That turns the obvious set-choice condition into a fractional feasibility question, which may admit LP or related continuous-optimization methods. The two questions should be investigated separately: Copeland’s score depends on the pattern of pairwise wins and ties, while Maximin compares minima of pairwise supports, so a tractable formulation for one would not automatically settle the other. Further questions include whether either problem is polynomial in \(m,\tau,L\) at its stated fixed width, and how far its answer can differ from the discrete problem when actions are restricted to increments of \(1/N\).
The weak point is the same for both anchors: the paper proves hardness for indivisible ballot selection. The reductions do not establish hardness when each ranking type can be split into arbitrary rational mass. Fractional exact cover can have solutions even when exact integral cover does not, so those proofs cannot simply be carried over. Conversely, that gap is exactly why these are useful mirrors: they ask whether the population-continuous version makes the paper’s control problems tractable, without pretending that the paper already answered the question. I would mirror the adding-votes results only here; the deleting-votes branches have natural mass versions, but they are outside the scope of these two questions.
The strongest case against these anchors is that they turn “adding votes” into mobilizing fractional shares of a latent electorate. That action can be a useful relaxation, but it is not the paper’s intervention: its chairman selects actual ballots from a specified finite pool. A campaign cannot generally choose \(0.37\) of the people with a given ranking, and the ranking distribution of people who can be mobilized may be unknown or change in response to the campaign. The width restriction adds another modeling burden: the preference types in both the registered and eligible populations must fit one common bounded-width partition.
That objection does not survive the best version of either mirror. A large organization or electorate can have many interchangeable members, divided into registered and eligible groups by complete preference type. Mobilization of a share of those groups is a sensible high-multiplicity control question. The action need not be exact at individual scale to be informative: it can model a proportional target or approximate a large finite electorate. The common width condition is a meaningful restriction on the instance regime, not a population-limit failure.
Theorem 3 is therefore a real anchor. Its exact-cover reduction selects indivisible ballots, so it does not establish hardness for fractional control. But that gap is a reason the continuous question could be worthwhile: does fractional mobilization remove the combinatorial obstruction, or do Copeland’s pairwise outcomes retain enough structure to keep the problem hard? The fact that the combinatorics encode candidate relationships does not make the question inert; the answer could establish a boundary for when continuization helps.
Theorem 8 has the same weakness as a negative anchor. Fractional Maximin control is also a coherent problem over ranking masses. Its score is defined directly from pairwise support, and asking whether a target can reach the maximum score within a mass budget is well-posed. The discrete exact-cover proof says nothing decisive about that fractional feasibility question. Nor is Maximin’s dependence on the minimum pairwise support a reason to avoid asking it; it gives the mirror a distinct computational shape from Copeland’s.
A narrower concern is that these particular adding-votes mirrors may be less compelling than deleting-votes versions, where suppressing or losing a share of voters has an especially direct population interpretation. But that does not defeat either anchor, and the paper itself studies both operations. The honest negative case is weak: I can question the implementation story and the priority of these specific formulations, but I cannot show that they fail the programme’s high-multiplicity test or lack a meaningful computational question.
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.