| paper | d4-conf-ijcai-2011-0420 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, both with input \(\alpha\) and for every fixed rational \(\alpha\in[0,1]\). · 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 rational distribution \(\nu\) over nonmanipulator rankings with total mass \(1-\varepsilon\), a strategic type of mass \(\varepsilon>0\) with true ranking \(R^\star\) and utility \(u\), rational \(q\), and rational \(\alpha\in[0,1]\), does there exist a ranking \(L\) for the strategic type such that the average utility of the Copeland\(_\alpha\) winners under the resulting society \(\mu_L=\nu+\varepsilon\delta_L\) is at least \(q\)? Pairwise contests are decided by comparing ranking masses, with equal masses counted as ties.
A society represented by rational masses over ranking types, including a mass-\(\varepsilon\) strategic type whose members submit one common report. The decision is whether some report makes the average utility of the Copeland\(_\alpha\) winners reach \(q\).
The exact hardness embedding allows the strategic mass share \(\varepsilon\) to shrink with the electorate; it does not establish hardness when that share is bounded below.
fatal: False
The proposed model covers the Maximin hardness in Theorem 1 and the Copeland\(_\alpha\) hardness in Theorem 2. It leaves the Bucklin and Plurality with Runoff algorithms, and the STV and Ranked Pairs hardness results, outside the proponents’ claim.
I would mirror the paper’s one-voter RANDMANIPULATION problem directly, keeping the named manipulator as one agent. For a finite candidate set \(C\), let the nonmanipulators have a rational distribution \(\nu\) over rankings, with total mass \(1-\varepsilon\). The marked manipulator has true ranking \(R^\star\), utility \(u\), and mass \(\varepsilon>0\). A type includes the ranking and, for the marked type, its strategic role and utility. The manipulator chooses one reported ranking \(L\in\mathcal L(C)\), producing the society
\[
\mu_L=\nu+\varepsilon\delta_L.
\]
For the chosen rule, let \(W(\mu_L)\) be the set of highest-scoring candidates under these masses. The decision problem, given rational \(q\), asks whether some \(L\) has
\[
\frac{1}{|W(\mu_L)|}\sum_{c\in W(\mu_L)}u(c)\ge q.
\]
Its optimization version finds a report maximizing that expected utility. Masses, \(\varepsilon\), \(u\), and \(q\) are encoded in binary. This keeps the paper’s ballot choice, utility objective, and uniform random tie-breaking; only the electorate is represented by type masses.
A plausible regime is a large election in which many voters share a relatively small number of rankings, while a singled-out voter can matter because relevant pairwise margins are close to ties. This is an instance regime, not a claim about every election. The paper’s hard instances can be placed in a high-multiplicity regime without changing the manipulation problem: add \(k\) pairs of nonmanipulators whose rankings are reverses of each other. Every pairwise contest gains \(k\) votes for each side. Thus all Copeland wins, losses, and ties remain the same; every Maximin pairwise count rises by \(k\), preserving the ordering of Maximin scores after any report. The number of ranking types grows by at most two, while the electorate grows by \(2k\). The manipulator’s share becomes \(1/(N+2k)\), but the margins are diluted by the same normalization. So the electorate can be arbitrarily large relative to its support while that individual remains pivotal.
My lead anchor is Theorem 1, proved in this paper: Maximin-RANDMANIPULATION is NP-complete. The proof establishes hardness already with utility \(u(w)=0\) and \(u(c)=1\) for every other candidate. Given a directed graph \(G\) with \(s\) vertices and a feedback-vertex-set threshold \(t\), it constructs candidates \(c_1,\ldots,c_s,w\) and a threshold \(q=(s-t)/(s-t+1)\). A vote reaches that expected utility exactly when the graph has a feedback vertex set of size at most \(t\). This is the Continuous Maximin-RANDMANIPULATION question: given \(C,\nu,\varepsilon,R^\star,u,q\), is there a ranking \(L\) for which the Maximin winners of \(\mu_L\) have average utility at least \(q\)? I expect hardness to transfer. An \(N\)-voter instance embeds by assigning each nonmanipulator’s ranking mass \(n_t/N\) and setting \(\varepsilon=1/N\); the continuous scores then have exactly the same winners as the discrete counts. The graph combinatorics live in the alternatives, so this is a Class B case. It also raises questions about parameterizing by support size \(\tau\), or restricting the manipulator to a fixed minimum population share.
A second substantial anchor is Theorem 2, also proved here: for every rational \(\alpha\in[0,1]\), Copeland\(_\alpha\)-RANDMANIPULATION is NP-complete. The reduction from Independent Set constructs candidates for graph vertices, additional candidates \(Z\), and a candidate \(w\). The manipulator has utility \(1\) on the graph candidates and \(0\) on \(Z\cup\{w\}\), with threshold \(q=t/(t+1)\). A report meets the threshold exactly when the input graph has an independent set of size at least \(t\). The corresponding Continuous Copeland\(_\alpha\)-RANDMANIPULATION problem uses the same mass-transfer model and asks whether some \(L\) makes the average utility of the Copeland\(_\alpha\) winners of \(\mu_L\) at least \(q\). I again expect hardness to transfer, for every fixed rational \(\alpha\): pairwise comparisons of mass shares preserve the discrete wins, losses, and ties in the embedded instances. This is a useful robustness result across Copeland tie conventions. Further questions include whether hardness persists when \(\varepsilon\) is bounded below independently of \(m\), and what changes if a manipulator may split its mass across different reports.
For both decision problems, a report \(L\) is a polynomial-size certificate, and Maximin and Copeland winner sets can be computed with exact rational arithmetic. Thus the rational-mass versions are in NP as well as NP-hard. The paper’s discrete hardness embeds exactly, so these mirrors are expected to be NP-complete, not made easy by the continuous representation.
The main soft spot is the pivotal individual’s small positive mass: in a strict atomless limit, a unilateral deviation has zero effect. This mirror therefore retains the finite-agent feature the paper studies, represented as a positive rational atom within a high-multiplicity society. The near-tie regime is stylized, but the paper is specifically about manipulation under ties, and the balanced-pair construction shows that high multiplicity and pivotality can coexist. I would scope the case to Theorems 1 and 2; I would not stretch it to the Bucklin, Plurality with Runoff, STV, or Ranked Pairs results.
The strongest objection applies to both anchors: Theorem 1, Maximin-RANDMANIPULATION, and Theorem 2, Copeland\(_\alpha\)-RANDMANIPULATION, are about one voter’s pivotal report. In an atomless population, one voter has mass zero. Changing that voter’s ranking leaves every pairwise margin, winner set, and expected utility unchanged. Exact ties stay exact ties. So the genuinely atomless version of either unilateral manipulation problem is degenerate.
The proposed \(\varepsilon\)-atom avoids that degeneracy, but it preserves the exceptional voter rather than making the strategic unit high multiplicity. Adding balanced reverse-vote pairs can make the electorate arbitrarily large while preserving the discrete winners, as the proponent says. Yet the extra mass is passive; the strategic role still belongs to one marked voter. If that voter’s share is \(1/N\), it vanishes as \(N\) grows. The construction shows an exact encoding in population proportions, not that the individual’s manipulation has become a mass-level action.
For Theorem 1, the Feedback Vertex Set reduction uses a single ranking to decide which candidates can reach the Maximin winning score. For Theorem 2, the Independent Set reduction uses a single ranking to break selected pairwise ties. With zero-mass influence, neither choice changes the election. Give the strategic actor a fixed positive mass instead, and the model now describes a coordinated bloc that submits a common ranking. If its members can report separately, its action is a distribution of mass over rankings. Either version is a coalition problem; the paper’s one-voter theorems do not establish its complexity.
That distinction defeats the proponent’s claimed transfer for both anchors. The reductions preserve outcomes when a one-vote share shrinks along with the other margins. They do not show that either theorem survives when the strategic mass is bounded away from zero, or when that mass can split across reports. A continuous coalition version would need its own formulation and results.
This is a serious case against the unilateral mirrors, but it does not support the universal claim that no worthwhile continuous mirror exists. A fixed positive mass of voters with the same preferences and utility, coordinating their reports, is a coherent population model. The paper itself identifies coalitional manipulation under randomized tie-breaking as a research direction, so the authors would likely recognize that question. Under the programme’s rules, that is a live stronger mirror, not a reason to dismiss it. The honest negative case is therefore limited: the proponent has not shown that the paper’s one-voter hardness results transfer to a continuous population, but the broader claim that no scenario is worthwhile remains weak.
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.