| paper | d4-conf-aaai-2012-0131 |
| 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: Constructive Schulze addition is $\mathrm{NP}$-complete; destructive Schulze addition is in $\mathrm{P}$; constructive and destructive ranked-pairs addition are both $\mathrm{NP}$-complete. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given old alternatives \(C\), possible additions \(C'\), a rational mass distribution \(\mu\) over complete rankings of \(C\cup C'\), a favored alternative \(c\in C\), a quota \(k\), and the rule and control mode, is there a set \(S\subseteq C'\) with \(|S|\le k\) such that, after restricting each ranking to \(C\cup S\), \(c\) is the unique winner in the constructive case or is no longer the unique winner in the destructive case?
The society is a distribution \(\mu\) over supported ranking types, with \(\tau\) types and binary-rational masses. The controller chooses a discrete subset \(S\subseteq C'\); each type’s ranking is restricted to the resulting agenda, and Schulze or ranked pairs determines the outcome from the induced pairwise margins.
The mirror covers Theorem 3’s constructive add-alternative hardness for Schulze and ranked pairs, and its destructive add-alternative hardness for ranked pairs. It leaves Theorem 4’s delete-alternative results and the paper’s manipulation, vote-control, and bribery results aside.
The strongest honest case is for two mirrors, anchored in Theorem 3 and Theorem 4. In both, only the population becomes continuous; adding or deleting candidates remains a discrete choice. That fits the programme’s scope and gives a clean example of hardness that survives continuization.
A plausible regime is a large party or association election over a fixed shortlist, where millions of members share a relatively small set of complete rankings. A type is one such ranking, and \(\mu_t\) is its fraction of the electorate: \(\mu_t\in\mathbb{Q}_{\ge0}\), \(\sum_t\mu_t=1\), with support size \(\tau\ll n\). For \(a,b\), the normalized pairwise margin is
\[
D_\mu(a,b)=\sum_t \mu_t\,\sigma_t(a,b),
\]
where \(\sigma_t(a,b)=1\) if type \(t\) ranks \(a\) above \(b\), and \(-1\) otherwise. The rules still operate on the resulting weighted majority graph, with the paper’s fixed tie-breaking convention for ranked pairs.
Theorem 3, proved in the paper using reductions from X3C, says that constructive control by adding alternatives is NP-hard for both Schulze and ranked pairs, and destructive control by adding alternatives is NP-hard for ranked pairs. “Resist” means NP-hard in the paper. Its continuous mirror is Add-Alternative Control over a Mass Society: the instance gives old alternatives \(C\), possible additions \(C'\), a mass distribution \(\mu\) over complete rankings of \(C\cup C'\), a favored candidate \(c\in C\), a rule \(r\), a mode, and quota \(k\). Choose \(S\subseteq C'\) with \(|S|\le k\); restrict each ranking to \(C\cup S\); then apply \(r\). Constructively, ask whether \(c\) can be made the unique winner; destructively, whether \(c\) can be made no longer the unique winner. Equivalently, minimize \(|S|\) subject to the chosen goal. A solution is the set \(S\).
I expect Class B: hardness transfers. Given any explicit finite profile with \(n_t\) voters of type \(t\), set \(\mu_t=n_t/n\). Every pairwise margin is scaled by the same positive factor \(1/n\). Ranked pairs therefore sees the same edge order and ties, and Schulze sees the same comparisons between strongest-path values. Each candidate subset \(S\) has exactly the same effect in the two models. Mapping an explicit profile to these rational masses is polynomial time, so the paper’s NP-hardness carries over; the continuous version is also in NP because a candidate subset is a polynomial-size certificate and the winner can be computed in polynomial time. The proof therefore gives NP-completeness for this version under standard binary encodings. Repeating every ballot many times leaves \(\mu\) unchanged, so the same instances can sit in a regime with \(n\gg\tau\). Questions for a prover include whether there are algorithms parameterized by \(k+\tau\), and whether the unproved destructive Schulze variant has a different complexity.
Theorem 4, also proved in the paper by an X3C reduction, says that ranked pairs resists both constructive and destructive control by deleting alternatives. Its mirror is Delete-Alternative Control over a Mass Society: given candidates \(C\), a rational mass distribution \(\mu\) over rankings of \(C\), candidate \(c\), a quota \(k\), and the fixed ranked-pairs tie-break, choose \(D\subseteq C\setminus\{c\}\) with \(|D|\le k\). Restrict rankings to \(C\setminus D\) and run ranked pairs. Ask whether \(c\) can be made the unique winner or can be made no longer the unique winner; equivalently, minimize \(|D|\) subject to the selected goal. The solution is \(D\). The same normalization argument gives an exact reduction from the paper’s discrete problem, so I again expect Class B. Further questions include whether small \(k\) yields an FPT algorithm and how the hardness behaves as a function of \(\tau\).
These mirrors cover only Theorems 3 and 4, not the paper’s results on manipulation, vote control, or bribery. In those problems the action itself changes voters, so allowing fractional mass to act may change the feasible solutions; the scaling argument above does not transfer their hardness. The weakest point in this case is that the two mirrors offer little prospect of a tractability gain: they are close to an exact high-multiplicity reformulation, with the combinatorics still residing in the candidate agenda. But that is also a useful Class B boundary. The paper studies explicit finite profiles; it does not itself pose these rational mass distributions as the society. Existing high-multiplicity election and control work supports the regime’s plausibility rather than creating a collision with this mirror.
The strongest objection to both anchors is that their computational state is the weighted majority graph, not the population as such. In Theorem 3, adding alternatives changes which pairwise contests are present; in Theorem 4, deleting alternatives does the same. For a mass distribution \(\mu\), the relevant margins are \(D_\mu(a,b)=\sum_t\mu_t\sigma_t(a,b)\). Once those are known, the full type distribution is irrelevant to either rule’s winner. The intervention selects a finite set of alternatives; it never moves, targets, or allocates voter mass.
That remains true for the best version of the mirrors. Give voters complete rankings over the full candidate universe, restrict those rankings after each addition or deletion, and use fixed tie-breaking. This is a sensible model, and it avoids the weak objection that voters cannot rank absent candidates. But every rational \(\mu\) has a common denominator \(N\), so it corresponds to integer ballot counts \(N\mu_t\). For every agenda choice, the resulting margins are scaled by the same positive factor; ranked pairs preserves their ordering and ties, and Schulze preserves its path comparisons. Thus these mirrors reduce to control over a weighted majority graph. Their continuous masses supply a compact encoding, but no fractional population decision or new population-dependent constraint.
That gives a reason to rank these mirrors low in a continuization programme: they offer little access to the continuous-optimization machinery that motivates the programme, and their apparent population dimension disappears behind a sufficient statistic of \(O(m^2)\) margins. Adding mass-dependent intervention costs or fractional candidate choices might restore a population-sensitive problem, but those would change the control questions rather than sharpen these mirrors.
This is a prioritization argument, not a decisive rejection. The programme explicitly treats high-multiplicity models as worthwhile, and compact rational masses can be a meaningful input regime even when the answer factors through margins. Theorems 3 and 4 therefore survive the admissibility test: I cannot honestly say that no worthwhile mirror exists for either. The negative case is weak precisely where it needs to be strongest.
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.