| paper | d4-conf-atal-2017-0225 |
| 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 registered candidates \(R\), addable candidates \(D\), a nonempty set \(J\subseteq R\), a budget \(b\), and a list of \(\tau\) complete rankings \(t\) over \(R\cup D\) with positive rational masses \(\mu_t\) summing to \(1\), is there an \(A\subseteq D\), \(|A|\le b\), such that no candidate in \(J\) is a Maximin winner after restricting every ranking to \(R\cup A\)? Here \(M_\mu(a,c)=\sum_{t:a\succ_t c}\mu_t\), and the score of \(a\) is \(\min_{c\ne a}M_\mu(a,c)\); under random-candidates tie-breaking, the condition is that the resulting winner set is disjoint from \(J\).
The population consists of ranking types \(t\) with masses \(\mu_t\); pairwise support is \(M_\mu(a,c)\). The decision variable is the discrete candidate set \(A\subseteq D\), constrained by \(|A|\le b\). The objective is feasibility: make every candidate in \(J\) lose under Maximin with random-candidates tie-breaking.
The mirror covers RCAC for Maximin from Theorem 2 and its parameterized counterpart from Theorem 5. It leaves the paper’s vote-control results, other voting correspondences, RCDC results, and tie-breaking-specific constructions unmirrored.
My strongest mirror is a high-multiplicity version of resolute control by adding candidates under Maximin. It keeps the paper’s control action intact and makes the electorate itself a distribution over voter types.
Take an election with registered candidates \(R\), an eligible set \(D\) of candidates who may be added, a nonempty distinguished set \(J\subseteq R\), and an addition budget \(b\). The society is a list of \(\tau\) complete rankings \(t\) over \(R\cup D\), each with a positive rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\mu_t\) is the fraction of voters of that ranking type; the masses are encoded in binary, with total bit length \(L\). For any candidates \(a,b\), let
\[
M_\mu(a,b)=\sum_{t:\,a\succ_t b}\mu_t.
\]
If \(A\subseteq D\) is added, rankings are restricted to \(R\cup A\), and each candidate’s Maximin score is
\[
s_{\mu,A}(a)=\min_{c\in(R\cup A)\setminus\{a\}}M_\mu(a,c).
\]
Call the decision problem Continuous Resolute Candidate Addition for Maximin (CRCA-Maximin): does there exist \(A\subseteq D\), \(|A|\le b\), such that no candidate in \(J\) is a Maximin winner? Use the paper’s random-candidates tie-breaking rule \(\mu_{RC}\). Since every tied Maximin winner then has positive probability, a solution is exactly a set \(A\) for which
\[
\arg\max_{a\in R\cup A}s_{\mu,A}(a)\ \cap J=\varnothing.
\]
The solution is the added-candidate set \(A\).
The regime is a large electorate whose members share a relatively small number \(\tau\) of complete ballot types: for example, many voters rank a known slate of registered and eligible candidates according to recurring party or issue-based rankings. An agenda-setting authority can admit at most \(b\) candidates from the eligible slate before the election, seeking to prevent any candidate in a specified policy bloc \(J\) from having a chance to win. The number of voters can be millions while each listed type represents many people. Candidate choices and the control budget remain discrete; the population is what becomes continuous.
My lead anchor is Theorem 2, proved in the paper. In full, it states that for every \(Y\in\{\mathrm{FO},\mathrm{RC},\mathrm{RV}\}\), RCAC for \(\mu_Y\circ\phi\) is NP-hard when \(\phi\in\{\mathrm{Borda},\mathrm{Maximin},\mathrm{Copeland}_\alpha\}\), and RCDC is NP-hard when \(\phi\in\{\mathrm{Borda},\mathrm{Copeland}_\alpha\}\). I rely on its RCAC-Maximin case, in particular under \(\mu_{RC}\).
I expect CRCA-Maximin to be NP-hard, in Class B: hardness transfers. Given a discrete election with \(n_t\) voters of each ranking type \(t\), set \(\mu_t=n_t/n\), where \(n=\sum_t n_t\). Every pairwise mass is the corresponding vote count divided by \(n\), so every Maximin score is scaled by the same positive factor. Winner sets, tie behavior, available candidate additions, and the answer to the control question are preserved. This is a polynomial mapping from explicit voter profiles to the continuous input. The continuous decision problem also has an evident polynomial verification procedure for a proposed \(A\), using exact rational arithmetic, so I would expect it to be NP-complete under this encoding.
A useful parameterized companion is CRCA-Maximin parameterized by \(\kappa=|J|\): it asks the same question with the same solution, but asks for complexity as a function of \(\kappa\). Its anchor is Theorem 5, proved in the paper: RCAC for \(\mu_Y\circ\mathrm{Maximin}\) is FPT with respect to \(k=|J|\), for every \(Y\in\{\mathrm{FO},\mathrm{RC},\mathrm{RV}\}\); the paper gives an \(O^*(2^k)\) algorithm. I expect the continuous version to be FPT as well, with running time \(2^\kappa\operatorname{poly}(m,\tau,L)\), where \(m=|R\cup D|\). The algorithm’s key steps compare pairwise scores and track which distinguished candidates can be made to fall below a guessed Maximin threshold. With rational masses, those scores become rational comparisons computable in polynomial time in \(\tau\) and \(L\).
The authors should recognize both questions as about their problem: the voter multiset becomes a distribution over complete preference types, while candidate addition, Maximin, and the resolute objective remain the same. This case covers RCAC for Maximin, using Theorems 2 and 5. It does not claim a mirror for the paper’s vote-addition or vote-deletion results, its other voting rules, or its artificial tie-breaking construction. The random-candidates rule is inherited from the paper; I am not making outcomes themselves the continuous object.
The main follow-up question is whether the transferred hardness persists when the support size \(\tau\) is bounded or the rankings have a natural restriction. That would help identify whether the hardness is carried mainly by the candidate agenda or still requires a rich population of types. For the parameterized version, the paper’s kernelization question also transfers: is there a polynomial kernel in \(\kappa\) for rational-mass inputs, or do the type list and mass bit lengths prevent one?
My weakest point is that this mirror gives no reason to expect the hardness to disappear. Candidate addition is the combinatorial action, and the hardness reduction embeds directly into a normalized voter distribution. The continuous model may therefore look like a high-multiplicity restatement whose benefit is its population representation and parameter landscape, rather than a new tractable algorithm. That makes it a boundary case, but under the programme’s scope, an honest boundary case is still a worthwhile mirror.
The strongest case against is about marginal value, not validity. For RCAC under Maximin, once the rankings and their masses are given, the election’s relevant data are the pairwise support values \(M_\mu(a,b)\). Candidate addition still asks which finite subset of \(D\) to choose; there is no decision variable over voter mass for continuous optimization to act on. Theorem 2’s mirror therefore appears to replace integer vote counts with rational pairwise shares while leaving the control problem’s structure intact. A good mirror, perhaps, but a modest one.
That objection does not defeat the anchor. Candidate addition is a plausible action in a large electorate with recurring ballot types, and a distribution over complete rankings is a sensible high-multiplicity input. The paper’s discrete profiles map directly to rational masses, with Maximin winners and the \(\mu_{RC}\) resolute objective preserved. Theorem 2 thus has a well-posed continuous question. The fact that hardness may persist is not a reason to reject it.
Theorem 5’s parameterized mirror also survives. Its Maximin thresholds can be taken from the finitely many pairwise masses \(M_\mu(q,q')\); comparisons and the dynamic program’s updates can use exact rational arithmetic. That makes an \(O^*(2^\kappa)\)-style algorithm plausible, with polynomial dependence on \(m,\tau,L\). The mirror has no obvious continuum degeneracy or identity loss.
A stronger version could model a known slate of eligible candidates and recurring preference types in a large electorate. That improves the scenario, but it does not remove the main criticism: the continuous population supplies weighted pairwise data, while the intervention remains a discrete candidate choice. Still, under ChoCo’s stated scope, that is a limitation of the contribution’s likely novelty, not a fundamental defect in the mirror. I cannot honestly defeat either anchor; the negative case is weak, and the reader should regard both as surviving.
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.