| paper | d4-conf-ecai-2012-0043 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Both the co-winner and unique-winner continuous manipulation problems are in \(\mathrm{P}\). The algorithm runs in \(3^{\binom m2}\operatorname{poly}(m!,m,\tau,L)\) bit operations, hence in \(\operatorname{poly}(\tau,L)\) time for \(m=4\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Fix \(C=\{p,a,b,c\}\). An instance gives binary-rational masses \(\mu_{\succ,w}\) of sincere voter types, each with ranking \(\succ\) and positive integer weight \(w\), and masses \(\nu_w\) of manipulable types with weight \(w\); the masses together sum to \(1\), and the input has support size \(\tau\). For each weight \(w\) and reported ranking \(\pi\), choose \(x_{w,\pi}\ge 0\) with \(\sum_{\pi}x_{w,\pi}=\nu_w\). Define \(M_x(i,j)=\sum_{\succ,w}w\mu_{\succ,w}\sigma_{\succ}(i,j)+\sum_{w,\pi}w x_{w,\pi}\sigma_{\pi}(i,j)\), where \(\sigma_{\rho}(i,j)=1\) if \(\rho\) ranks \(i\) above \(j\), and \(-1\) otherwise. Decide whether a feasible \(x\) makes \(p\) a Copeland\(_1\) co-winner, or, in the unique-winner variant, the sole winner.
Each infinitesimal unit of mass retains its type’s integral ballot weight; the decision variables \(x_{w,\pi}\) assign each manipulator type’s mass among reported rankings. The objective is feasibility: whether those assignments make \(p\) win under Copeland\(_1\).
The mirror covers Theorem 2 for four-candidate Copeland\(_1\) manipulation, in both co-winner and unique-winner variants. It leaves the unary-weight result in Theorem 9 and the discussion of other candidate counts aside.
The strongest mirror is Fractional Four-Candidate Llull Manipulation.
Its anchor is Theorem 2, proved in this paper: weighted coalitional manipulation for Copeland\(_1\) with four candidates is solvable in polynomial time in both the nonunique-winner model, where the target may tie for first, and the unique-winner model, where the target must win outright.
Here is the continuous problem. Fix \(C=\{p,a,b,c\}\). The input gives rational population masses for sincere voter types \((\succ,w)\), where \(\succ\) is a ranking of \(C\) and \(w\) is a positive integer voting weight, and rational masses for manipulable voter types \(w\). These masses sum to \(1\) and are given in binary; let \(\tau\) be the number of supported types. A type includes its role and weight, and includes a ranking when that ranking matters. The manipulator’s true ranking is absent because it is absent from the paper’s WCM input.
For each manipulator weight \(w\) and reported ranking \(\pi\), choose mass \(x_{w,\pi}\ge 0\), with \(\sum_{\pi}x_{w,\pi}=\nu_w\), where \(\nu_w\) is the input mass of that type. For candidates \(i,j\), the resulting pairwise margin is
\[
M_x(i,j)=\sum_{(\succ,w)}w\mu_{\succ,w}\,\sigma_{\succ}(i,j)
+\sum_{w,\pi}w x_{w,\pi}\,\sigma_{\pi}(i,j),
\]
where \(\sigma_{\succ}(i,j)=1\) if \(\succ\) ranks \(i\) above \(j\), and \(-1\) otherwise. Under Copeland\(_1\), candidate \(i\)’s score is \(\left|\{j\ne i:M_x(i,j)\ge 0\}\right|\): a pairwise tie awards a point to each candidate. Given a requested mode—co-winner or unique winner—decide whether there is an allocation \(x\) that makes \(p\) win in that mode. A feasible rational allocation is a solution. There is no cost objective, just as in WCM: the question is whether the coalition can make its target win.
The regime is a large ranked-ballot federation with four candidates, a few voting-weight tiers, and many members sharing the same ranking and weight. For example, the population could have hundreds of thousands of members but only a few dozen supported sincere and manipulator types. The coalition is the organized group whose reports may be chosen to help \(p\). In a finite election with \(N\) voters, assigning mass \(1/N\) to each voter’s type reproduces the original weighted margins up to a common factor. The continuum permits rational type masses rather than requiring each type’s count to be an integer. The election outcome and manipulation objective remain the paper’s; the population is what has become continuous.
I expect this mirror to be tractable. There are only six pairwise contests. Enumerate their win, tie, or loss outcomes; for each pattern, the winner condition is fixed and the margins impose linear constraints on \(x\). Each case is rational linear feasibility, so for four candidates the continuous problem has a polynomial-time LP route in \(\tau\) and the input bit length. This is a clean Class A question, though it would be a new continuous formulation rather than the paper’s proof.
The case for author recognition is that the same coalition chooses among the same rankings to secure the same target’s victory under the same rule; only the counts of indistinguishable weighted agents may be fractional. That is a natural high-multiplicity version of their problem. The paper’s algorithmic result makes this an appropriate mirror, though it does not deliver the programme’s more revealing test of whether discrete hardness disappears.
That is also the weakest point. Theorem 2 is already a discrete polynomial-time result, not a hardness anchor. And fractional \(x\) allows a cohort to split across rankings, whereas every individual manipulator in the paper casts one ballot. The mirror is strongest in the stated regime where cohorts are genuinely large and repeated types make population fractions meaningful; it should not be presented as a model of every weighted WCM instance.
Theorem 2 is a genuine computational anchor: it gives a polynomial-time result for weighted coalitional manipulation under Copeland\(_1\) with four candidates. I do not see a defensible way to deny it a continuous mirror.
The strongest objection is that the paper treats each manipulator as an indivisible voter with an integer weight, while a mass model lets a cohort split across reported rankings. That changes the feasible set. But it is the intended high-multiplicity move, and it does not make the model implausible. A large coalition with a few weight classes can be represented by its mass at each weight; its members’ chosen ballots determine how that mass is distributed. An unweighted electorate with a large coordinated coalition is an even simpler scenario. The outcome depends on aggregate pairwise margins, not on who cast each ballot.
The proposed mirror also survives the technical objection that Copeland winners involve discrete outcomes. With four candidates there are six pairwise contests. Enumerating their win, tie, and loss patterns gives a constant number of cases; each case imposes linear constraints on the mass assigned to manipulator ballots. Rational feasibility then gives a direct computational question in the support size and input bit length. This is a recognized fractional version of the same manipulation task, not continuity of the outcome space or an axiomatic detour.
One can argue that the mirror may be modest: the candidate set is fixed, and the continuous formulation appears to need only finite-dimensional linear feasibility. That limits the likely methodological payoff. It does not establish that the question is unworthy, and the paper’s discrete polynomial-time result cannot itself count against a well-posed continuous question. High-multiplicity work supports the regime, and no identity or degeneracy issue defeats it.
So the negative case is weak at its central point. The mirror changes the feasible set through divisible mass, but that change is precisely what the programme studies. I would expect Theorem 2 to survive as an anchor.
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.