| paper | d4-conf-atal-2013-0062 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | low |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm P\), with running time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 2
statement extracted from the paper’s text layer
Given \(m\) candidates, a target \(c\), a rational coalition mass \(\alpha\), and a distribution \(\nu\) over \(\tau\) nonmanipulator rankings with total mass \(1-\alpha\), does there exist a rational assignment \(y_\pi \geq 0\) of coalition mass to rankings \(\pi\), with \(\sum_\pi y_\pi=\alpha\), such that \(c\) is the unique Schulze winner under the resulting pairwise margins and path strengths?
A society of total mass \(1\) consists of nonmanipulator ranking types with distribution \(\nu\) and a coordinated coalition of mass \(\alpha\) targeting \(c\). The decision variables \(y_\pi\) distribute that coalition mass across complete rankings; each unit of mass casts one integral ranking, and the objective is to make \(c\) the unique Schulze winner.
The mirror covers Corollary 2’s unique-winner UCM result; it leaves the weighted co-winner result, the co-winner UCM result, and the paper’s analysis of unique-winner versus co-winner conditions outside its scope.
My lead is a continuous version of unweighted unique-winner coalitional manipulation. The anchor is Corollary 2, proved in this paper: for Schulze’s rule, given a nonmanulator profile, a preferred candidate, and any number of unweighted manipulators, it is possible to decide in polynomial time whether the manipulators can make that candidate the unique winner. The proof reduces the question to co-winner manipulation with one fewer manipulator and uses the resolvability property attributed to Schulze [16].
Call the mirror Schulze Unique-Winner Mass Manipulation. An instance has \(m\) candidates, a target \(c\), a rational coalition mass \(\alpha\), and a distribution \(\nu\) over the \(\tau\) nonmanipulator rankings, with total mass \(1-\alpha\). The population has total mass \(1\). Nonmanipulator types are complete rankings; manipulators share the target \(c\) and unit voting weight, and their sincere rankings are irrelevant to the problem as the paper defines it. Each manipulator still casts one strict ranking. The decision variable is \(y_\pi\geq 0\), the mass of manipulators assigned to ranking \(\pi\), with \(\sum_\pi y_\pi=\alpha\). The question is whether there is a rational assignment \(y\) for which \(c\) is the unique Schulze winner of the resulting society.
Precisely, the pairwise margin for \(x,y\) is the mass ranking \(x\) above \(y\) minus the mass ranking \(y\) above \(x\), summed over \(\nu\) and the assigned manipulator mass. Schulze path strengths are the maximum, over directed paths, of the minimum margin on each path. A solution is an assignment \(y\) for which \(S(c,x)>S(x,c)\) for every other candidate \(x\). The mass assigned to each report can be fractional because it represents many agents: each agent in that mass still casts an integral ranking.
This is a plausible high-multiplicity regime: a large membership organization has many voters but relatively few distinct rankings, and a coordinated bloc supports one target candidate. The input size should be measured in \(m,\tau\), and the binary bit length \(L\) of the masses. The authors should recognize the question: it keeps their agents, ballots, target, Schulze rule, and unique-winner criterion, while representing repeated voter types by their proportions.
I would provisionally expect Class A, with low confidence: the paper’s constructive results suggest that the relevant strategy may have substantial graph structure. Its Theorem 1 is useful supporting evidence: in a finite profile where \(c\) is a co-winner, any chosen subprofile can be replaced by votes with one common ranking while preserving \(c\)’s co-winner status. The paper does not prove that this compression extends to real masses and preserves *unique* victory, so it is a lead for investigation, not a result for the mirror.
The soft spot is the change in input representation. Corollary 2 is polynomial for an explicitly listed electorate; expanding binary-rational masses into individual voters could take time proportional to a large denominator. Also, the discrete proof uses a one-vote tie-breaking step, whose analogue at fixed coalition mass needs proof. So the paper’s P result does not establish a bit-polynomial algorithm in \(m,\tau,L\). The central follow-up is whether its construction can be adapted to rational mass directly, or whether binary mass precision makes this continuous problem hard. This case covers Corollary 2’s unique-winner UCM result, not the rest of the paper.
The strongest objection is that Corollary 2’s polynomial result does not give a continuous algorithmic insight. Its unique-winner step relies on discrete resolvability: take a co-winner solution with one fewer manipulator, then use one more vote to break ties. At fixed coalition mass, there is no last manipulator to add. The paper’s Theorem 1 gives some structural evidence for co-winner manipulation, but it does not establish that a real-valued coalition can turn a tie into a strict win while preserving the same total mass. So the proponent’s Class A expectation is speculation, not a transfer of the paper’s proof.
That weakens the case for mirroring *Corollary 2 as stated*, but it does not defeat the better mirror. A direct question—whether a coalition of rational mass \(\alpha\) can distribute its reports across rankings so that its target becomes the unique Schulze winner—is well-posed and recognizably about the same computational problem. A large membership organization with a coordinated bloc supplies a plausible high-multiplicity regime. The fact that every rational instance can be scaled to a finite election does not dismiss it: the relevant question is whether it can be solved in time polynomial in \(m,\tau,L\), without expanding large binary denominators.
Nor can I make the universal negative case by claiming that manipulators are inherently individuated. The paper’s UCM model uses their shared target and permits arbitrary reports; it does not use their identities or sincere rankings. The paper also contains no continuous computational treatment that settles this mass version. The one-vote argument makes the unique-winner mirror’s relationship to Corollary 2 uncertain, but it does not make the mass problem unworthy. The honest negative case is weak: it challenges the suggested tractability and the directness of the analogy, but it does not defeat the continuous mirror itself.
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.