d4-conf-atal-2010-0032

Answer: For $\alpha=0$, the problem is $\mathrm{NP}$-complete, even with $\tau=O(m^2)$. For $\alpha=1$, it is polynomial-time solvable in $m,\tau,L$ by a maximum-flow computation. · discrete side: hardness · adjudication: proved_with_minor_gaps

The anchor — hardness

Every anchor argued

The continuous mirror question

Given a candidate set $C$, target $p\in C$, $\alpha\in\{0,1\}$, a rational base mass distribution $\mu$ over strict rankings of $C$ with total mass $1-\kappa$, and rational controllable mass $\kappa>0$, decide whether there is a distribution $q$ over rankings with total mass $\kappa$ such that $p$ is a Copeland$_\alpha$ winner under the combined masses $\mu+q$. For each pair $a,b\in C$, define $M(a,b)=\sum_r(\mu_r+q_r)(\mathbf{1}[a\succ_r b]-\mathbf{1}[b\succ_r a])$; the score of $a$ is the number of $b$ with $M(a,b)>0$, plus $\alpha$ times the number with $M(a,b)=0$.

The model it lives in

The population consists of ranking types $r$ with mass $\mu_r+q_r$; the support of the fixed base society has size $\tau$, and the controllable bloc has total mass $\kappa$. The decision variables are the nonnegative report masses $q_r$, and the objective is to find any such allocation that makes the target a Copeland$_\alpha$ winner. The input masses are binary rationals, with natural parameters $m=|C|$, $\tau$, and bit length $L$.

What the mirror covers

The mirror covers Theorem 4.1's rational-voter constructive manipulation results for $\alpha\in\{0,1\}$. It leaves aside Theorem 5.2's irrational-voter model and the paper's other results.

Open questions for a prover

The case FOR (proponent)

My lead is the continuous population version of constructive Copeland manipulation. The anchor is Theorem 4.1, proved in this paper: for $\alpha\in\{0,1\}$, Copeland$_\alpha$-manipulation is NP-complete even when there are exactly two manipulators. The paper proves the two endpoint cases through Lemmas 4.3 and 4.4, reducing from X3C. The theorem’s hardness comes from combinatorial choices among candidates and pairwise contests.

A credible regime is a large election with many voters but relatively few distinct preference rankings, alongside a coordinated campaign or bloc able to direct a substantial share of ballots. Let $\mathcal R(C)$ be the rankings of candidate set $C$. The fixed voters have rational masses $\mu_r$ over rankings $r\in\mathcal R(C)$, with support size $\tau$. A controllable bloc has mass $\kappa$. The electorate is large relative to $\tau$, and members of the bloc share the same role and reporting options. This is a plausible high-multiplicity setting: the question is whether the bloc can make a target win, and mass is the natural unit for its influence.

Here is the continuous problem I would hand to a prover:

Continuous Copeland$_\alpha$-Manipulation, $\alpha\in\{0,1\}$ (lead). Given $C$, a target $p\in C$, a rational base society $\mu$ with total mass $1-\kappa$, and a rational $\kappa\ge 0$, decide whether there is a distribution $q$ over rankings in $\mathcal R(C)$, with $q_r\ge 0$ and $\sum_r q_r=\kappa$, such that $p$ is a Copeland$_\alpha$ winner in the society with masses $\mu_r+q_r$. For each pair $a,b$, its majority margin is
\[ M(a,b)=\sum_{r\in\mathcal R(C)}(\mu_r+q_r) \bigl(\mathbf 1[a\succ_r b]-\mathbf 1[b\succ_r a]\bigr). \]
The score of $a$ is the number of opponents $b$ with $M(a,b)>0$, plus $\alpha$ times the number with $M(a,b)=0$. A solution is such a $q$; ties for the overall winner are allowed, as in the paper. The input masses are binary rationals, and the natural complexity parameters include $m=|C|$, $\tau$, and their bit length $L$.

This is recognizably the authors’ manipulation problem: the same ballots, the same Copeland comparisons, the same target-winner objective, and a coalition choosing its reports. The continuous object is the electorate: its members can be represented by ranking types, and the coalition chooses how its mass is distributed across reported rankings. For a finite instance with $n$ fixed voters and two manipulators, normalization gives base mass $n/(n+2)$ and coalition mass $2/(n+2)$. Replicating that electorate scales both masses while preserving their proportions. The continuous question then permits the coalition’s mass to split across rankings.

I expect hardness to transfer (Class B), because the paper’s X3C construction encodes choices in the candidate agenda and pairwise-contest gadgets, rather than relying only on a large number of voters. That is a reason to investigate transfer, not a proof: the mirror’s winning condition is still defined by linear majority margins, but the Copeland scores depend on which margins are positive, negative, or tied.

The weakest point is that Theorem 4.1 concerns exactly two indivisible manipulator ballots. The continuous coalition can split its mass across many rankings, potentially erasing the all-or-nothing choices used by the reduction. The continuous problem is therefore a genuine relaxation question, not a consequence of the theorem. It generates concrete follow-ups: does the relaxation admit an algorithm polynomial in $m,\tau,L$, or does candidate-level hardness survive? What rounding or replication scale relates a rational continuous solution to a discrete coalition? And what happens at $\alpha=\tfrac12$, which the paper leaves open for rational voters?

This mirror covers Theorem 4.1’s rational-voter constructive manipulation result for $\alpha=0$ and $\alpha=1$. It does not cover Theorem 5.2’s separate irrational-voter model.

The case AGAINST (opponent, writing after the proponent)

Theorem 4.1 is a real computational anchor, so the “no result to mirror” objection is unavailable. The strongest case against it is about what scales. Its distinctive claim is hardness with *exactly two* manipulators; the paper separately notes that one-manipulator Copeland manipulation is in P. If those two agents stay fixed while the electorate grows, their normalized mass tends to zero. If the coalition keeps positive mass $\kappa$, its size grows with the electorate. That is cohort manipulation, not a continuous version of the theorem’s two-agent boundary.

The proposed replication argument does not close this gap: replicating the whole finite instance also replicates its manipulators, changing their number. And allowing $q$ to split coalition mass across rankings replaces two indivisible ballot choices with a divisible reporting supply. The X3C reduction therefore gives no direct bridge to the proposed problem; a finite-to-continuous dictionary or a new hardness argument would be needed.

That is a meaningful limit on the anchor, but it does not defeat the strongest mirror. A large coordinated bloc with a common target is a plausible population regime, and the paper’s definition of coalitional manipulation allows varying coalition sizes. Its continuous version preserves the manipulation objective and Copeland rule while making the electorate, including the controllable bloc, a mass distribution. The question of how that version behaves is computationally legitimate even if Theorem 4.1 does not settle it. The margin sign changes and the $\alpha$-valued ties remain meaningful in the continuum.

So the negative case can say that the proponent overstates the theorem’s direct connection to the continuous problem. It cannot honestly establish that no worthwhile mirror exists in any scenario. The strongest proposed mirror survives as a recognizable cohort-manipulation extension, and the case against it is weak at that point.

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.

paper	d4-conf-atal-2010-0032
authors	—
venue	?
filed under	unclassified
judged by	gpt-6-luna / xhigh (triple__luna__xhigh__c6r1)
judge confidence	medium
authors would recognise it	yes