| paper | Elections with Few Voters: Candidate Control Can Be Easy |
| authors | Jiehua Chen, Piotr Faliszewski, R. Niedermeier, Nimrod Talmon |
| venue | AAAI 2015 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given candidates \(C\), complete ranking types \(T\) with rational masses \(\mu_t\ge 0\) satisfying \(\sum_t\mu_t=1\), a preferred candidate \(p\), an integer budget \(k\), and a bundle map \(\beta:C\to 2^C\) with \(c\in\beta(c)\), does there exist \(S\subseteq C\) with \(|S|\le k\) and \(p\notin\beta(S)\) such that \(p\) is a Borda co-winner after deleting \(\beta(S)=\bigcup_{s\in S}\beta(s)\)?
A high-multiplicity Borda candidate-control model in which types carry masses \(\mu\), candidate deletions or bundle-leader choices remain integral, and the objective is to make \(p\) maximize \(\mathrm{sc}_{\mu,S}(c)=\sum_{t\in T}\mu_t\lvert\{d\in C\setminus\beta(S):c\succ_t d\}\rvert\).
The mirror covers Theorem 5.1, Theorem 5.2, and the Borda instance of Corollary 6.2; it leaves the paper's other voting rules, control variants, parameterized algorithms, and open \(2\)-Veto-Comb-DCAC case untreated.
My lead case is a genuine high-multiplicity mirror of the paper’s standard Borda candidate-deletion problem.
Take a large population of evaluator agents—say, automated hiring or procurement agents—who rank the same slate of candidates. There may be millions of agents but only a small number \(\tau\) of complete ranking types: agents of one type have identical rankings and are indistinguishable for the problem. The input is a rational distribution \(\mu\) over those types. A central agenda setter may delete candidates, add candidates, or activate candidate bundles. Population mass is continuous; candidates and control actions remain integral.
For deletion, define \(\textsc{Borda-CCDC}_{\infty}\) as follows. An instance consists of candidates \(C\), ranking types \(T\), rational masses \(\mu_t\) summing to \(1\), a preferred candidate \(p\in C\), and a budget \(k\). The question is whether there exists \(D\subseteq C\setminus\{p\}\), \(|D|\le k\), such that \(p\) is a Borda co-winner after deleting \(D\). If \(C_D=C\setminus D\), the continuous Borda score is \(\mathrm{sc}_{\mu,D}(c)=\sum_{t\in T}\mu_t\,|\{d\in C_D\setminus\{c\}:c\succ_t d\}|\). Equivalently, the optimization version minimizes \(|D|\).
This is my lead mirror because it preserves the authors’ underlying problem exactly: only the voter population changes from named unit voters to a distribution of repeated voter types.
The anchor is Theorem 5.1, proved in this paper: “Borda-CCDC is \(\mathsf{NP}\)-hard, even for elections with only ten voters.” In full, the underlying problem is constructive control by deleting candidates under Borda: given a Borda election, a preferred candidate \(p\), and a deletion budget \(k\), decide whether at most \(k\) candidates can be deleted so that \(p\) becomes a winner. The paper proves this by reducing from Cubic Vertex Cover. Its ten voters encode a cubic graph through a decomposition of the edges into four matchings; deleting a vertex candidate lowers the Borda scores of its incident edge candidates by one extra point, so a successful control action corresponds exactly to a vertex cover.
The continuous transfer is exact. Take the ten-voter election produced by the paper and make its ten votes ten types, each with mass \(1/10\). For every deletion set \(D\), every candidate’s continuous Borda score is exactly its discrete score divided by \(10\). Thus \(p\) wins after \(D\) in the discrete election if and only if \(p\) wins after \(D\) in \(\textsc{Borda-CCDC}_{\infty}\). Alternatively, create \(N/10\) agents of each type for any large \(N\) divisible by \(10\). Therefore the continuous problem is \(\mathsf{NP}\)-hard even when \(\tau\le 10\), hence \(\mathsf{paraNP}\)-hard when parameterized by the number of ranking types.
I expect this problem to be Class B: hardness transfers because the reduction’s combinatorics live in the candidate graph, not in the number of named voters. The useful follow-up is not whether hardness disappears—it does not—but whether there is a sharp boundary as \(\tau\) grows, whether approximation by winner margin is possible, and which restrictions on the candidate-action graph yield an LP or fixed-parameter algorithm.
A second, independent mirror is \(\textsc{Maximin-CCAC}_{\infty}\). Its instance consists of registered candidates \(C\), unregistered candidates \(A\), a rational distribution over complete rankings of \(C\cup A\), a preferred candidate \(p\in C\), and a budget \(k\). We ask whether some \(B\subseteq A\), \(|B|\le k\), makes \(p\) a Maximin co-winner in \(C\cup B\). For \(c,d\), let \(N_\mu(c,d)=\sum_t\mu_t\mathbf 1[c\succ_t d]\), and let \(p\)’s score be \(\min_{d\ne p}N_\mu(p,d)\).
The anchor is Theorem 5.2, also proved here: “Maximin-CCAC is \(\mathsf{NP}\)-hard, even for elections with only ten voters.” In full, the paper shows that, given a preferred candidate, a set of registered and unregistered candidates, and an addition budget, deciding whether enough candidates can be added to make the preferred candidate a Maximin winner is \(\mathsf{NP}\)-hard, already with ten voters. The reduction is again from Cubic Vertex Cover. Registered edge candidates initially beat \(p\) in their critical pairwise contests; adding a vertex candidate changes precisely the contests involving its incident edges, so the added vertices must cover every edge.
Again assign mass \(1/10\) to each of the ten constructed voter types. The paper’s Maximin scores \(4\) and \(5\) become \(2/5\) and \(1/2\), and all pairwise comparisons are preserved. Adding a vertex lowers the relevant edge candidate’s score from \(1/2\) to \(2/5\), exactly as in the discrete proof. Hence \(\textsc{Maximin-CCAC}_{\infty}\) is also \(\mathsf{NP}\)-hard with \(\tau\le10\). This is another Class B mirror, now for candidate addition and a Condorcet-style rule rather than a scoring rule.
The bundled variant gives an even stronger one-type boundary. Define \(\textsc{Borda-Comb-CCDC}_{\infty}\) by adding a bundle map \(\beta:C\to 2^C\), with \(c\in\beta(c)\). A solution selects at most \(k\) bundle leaders \(S\subseteq C\); the deleted candidates are \(\beta(S)=\bigcup_{c\in S}\beta(c)\), and the goal is to make \(p\) a Borda co-winner.
The relevant named result is Corollary 6.2, proved in this paper from Theorem 6.1: for each \(\mathcal R\in\{\)Plurality, Borda, Copeland\({}^{\alpha}\), Maximin\(\}\), \(\mathcal R\)-Comb-CCDC is \(\mathsf{NP}\)-hard even with a single voter. For the Borda case, the continuous mirror has one type with mass \(1\). Given a Set Cover instance, there is an element candidate \(x_i\) for every ground element and a set candidate \(s_j\) for every set, with \(\beta(s_j)=\{s_j\}\cup\{x_i:x_i\in S_j\}\) and singleton bundles for the other candidates. With one ranking type, \(p\) wins exactly when every element candidate has been deleted, which can be achieved with at most \(k\) selected bundles exactly when the original Set Cover instance has a cover of size \(k\).
This is Class B in its purest form: the mirror is hard even at \(\tau=1\). The hardness is not caused by population multiplicity at all; it is caused by the combinatorics of bundled candidate control. That makes it a useful boundary result rather than a failure of continuization.
The paper’s scope covered here is deliberately limited: standard Borda deletion, standard Maximin addition, and bundled Borda deletion. I would not claim that every \(\mathsf{FPT}\) or \(\mathsf{XP}\) result in the paper automatically becomes a theorem parameterized by \(\tau\); weighted masses require separate proofs. Nor would I claim that these mirrors make the problems easier. Their value is that they show exactly where continuization stops helping: the continuous population is natural, but candidate-side combinatorics survive unchanged.
The weakest point is that the hardness transfer is, mathematically, a normalization argument. An opponent can fairly say that ten voter types with masses \(1/10\) look like the paper’s ten-voter input written in percentages. I concede that. But that is precisely what makes the case honest and useful: the paper is not already a continuous-population study, while its hard instances inhabit the high-multiplicity regime without modification. The mirror asks the authors’ own candidate-control questions for large populations of interchangeable agents, and the answer is a meaningful Class B result: discrete hardness does not dissolve merely because the society is represented by mass.
The strongest negative case is ultimately weak, because all three anchors survive the programme’s actual gate.
For Theorem 5.1, the proposed \(\textsc{Borda-CCDC}_{\infty}\) is a genuine high-multiplicity version. Borda scores are linear in the population measure, so assigning mass \(1/10\) to the paper’s ten rankings gives, for every deletion set \(D\),
\[ \mathrm{sc}_{\mu,D}(c)=\frac{1}{10}\mathrm{sc}_{D}(c). \]
Replicating each type arbitrarily many times produces a large electorate with the same outcome. The objection that this is “just a normalization” is not available: the programme explicitly treats rational finite elections as high-multiplicity instances, and an unchanged answer is still a valid Class B result. The reduction’s graph-dependent rankings may be artificial, but that is a standard feature of worst-case complexity and does not prevent a plausible interpretation as repeated automated evaluator policies.
Theorem 5.2 is even harder to dismiss. Maximin depends only on aggregate pairwise masses,
\[ N_\mu(c,d)=\sum_t \mu_t\mathbf 1[c\succ_t d], \]
so the ten-voter reduction transfers exactly to ten voter types. The added candidates remain integral, while the society is continuous, which is precisely the permitted co-modification. One might demand a more structured utility-based model of evaluator types, but that would be an additional restriction, not an obstruction to this mirror. A question about whether the hardness persists under such restrictions would itself be worthwhile.
Corollary 6.2 provides the strongest negative talking point: with one voter type of mass \(1\), the population distribution has no nontrivial geometry, and all the hardness comes from the bundle map encoding Set Cover. Thus this anchor does not illuminate population continuization. But it is still a legitimate high-multiplicity society: millions of interchangeable agents can share one complete ranking. The construction can even be made non-degenerate by using several ranking types that all place the element candidates above \(p\) and \(p\) above the set candidates, while varying the order within those blocks. The answer remains controlled by the bundles, but that is a boundary result, not a modelling failure.
The residual negative case is therefore only about emphasis. These mirrors do not expose the LP-and-pricing phenomena that motivate the ChoCo programme; they are candidate-control problems whose voter population enters merely through weighted score coefficients. The paper’s motivating few-voter settings—small committees, holiday groups, and meta-search engines—also do not naturally suggest millions of interchangeable voters. But the programme expressly permits a different, convincing high-multiplicity scenario, and it treats surviving discrete hardness as valuable rather than as a defect.
I cannot honestly defeat the proponent’s case. The first two anchors are valid Class B mirrors, and the third is a valid one-type boundary result. The negative case should be recorded as a caution that these are straightforward hardness-transfer mirrors, not as evidence that no worthwhile continuous mirror exists.
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.