| paper | d4-conf-atal-2011-0073 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(\mathrm P\), with running time polynomial in \(m,\tau,L\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), a rational scoring vector \(\alpha\), target \(p\), established masses \(\mu_{\pi,w}\) over ranking–weight types, and strategic masses \(\rho_j\) with per-agent weights \(\beta_j\), define \(B(c)=\sum_{(\pi,w)}\mu_{\pi,w}w\alpha_{\operatorname{pos}_{\pi}(c)}\). Decide whether there are allocations \(x_{j,\sigma}\ge 0\) over complete rankings \(\sigma\), with \(\sum_{\sigma}x_{j,\sigma}=\rho_j\) for every \(j\), such that \(B(p)+\sum_{j,\sigma}x_{j,\sigma}\beta_j\alpha_{\operatorname{pos}_{\sigma}(p)}\ge B(c)+\sum_{j,\sigma}x_{j,\sigma}\beta_j\alpha_{\operatorname{pos}_{\sigma}(c)}\) for every \(c\in C\).
Established mass stays at its ranking–weight type; each strategic weight class distributes its mass across rankings. For class \(j\), candidate-by-position aggregate mass is a \(\rho_j\)-scaled doubly stochastic matrix. Birkhoff–von Neumann gives an exact representation by mixtures of complete rankings, yielding a polynomial-size LP that checks whether the target can win.
It mirrors Theorem 1’s manipulation feasibility question for weighted voters under fixed scoring protocols, including veto protocols. It leaves the paper’s partition-heuristic branch counts, runtime curves, and empirical scaling claims unexplained.
The strongest honest anchor is Theorem 1, proved in the paper. It says that for a \(k\)-candidate scoring protocol with current candidate scores \(s_1,\ldots,s_k\), target \(c_1\), and manipulators of weights \(w_1,\ldots,w_m\), a successful manipulation exists exactly when there is a \((k-1)\)-way permutation partition of the tuple \((s_2,\ldots,s_k)\) and the tuples \((w_i\alpha_2,\ldots,w_i\alpha_k)\), one per manipulator, whose largest part is at most \(s_1+\alpha_1\sum_i w_i\). The theorem is a computational characterization, not a theorem that manipulation is NP-hard or in P; the paper uses it to run partition algorithms and report experimental branch counts. Those empirical findings are not complexity classifications.
Here is a plausible high-multiplicity regime: a large platform or association holds a fixed-slate election among millions of members. Many established voters share the same ranking and voting weight, so the number \(\tau\) of established ranking–weight types is far smaller than the population. A coordinated bloc controls a macroscopic share of voters, drawn from a small number \(J\) of weight classes. Each type is complete for this problem: it records the voter’s ranking, weight, and whether the ballot is coalition-controlled. The coalition’s ranking is its decision, as in the paper’s manipulation problem.
Call the mirror Continuous Weighted Scoring Manipulation. An instance gives candidates \(C\), a rational scoring vector \(\alpha\), target \(p\), established masses \(\mu_{\pi,w}\) over ranking–weight types, and strategic masses \(\rho_j\) with per-voter weights \(\beta_j\), normalized so all masses sum to one. The established score of \(c\) is
\[
B(c)=\sum_{(\pi,w)}\mu_{\pi,w}w\alpha_{\operatorname{pos}_\pi(c)}.
\]
The decision is whether there are rational masses \(x_{j,\sigma}\ge 0\), assigning strategic class \(j\) to reports \(\sigma\), such that \(\sum_\sigma x_{j,\sigma}=\rho_j\) and
\[
B(p)+\sum_{j,\sigma}x_{j,\sigma}\beta_j\alpha_{\operatorname{pos}_\sigma(p)}
\ \ge\
B(c)+\sum_{j,\sigma}x_{j,\sigma}\beta_j\alpha_{\operatorname{pos}_\sigma(c)}
\quad\text{for every }c\in C.
\]
A solution is such an allocation of strategic mass to complete rankings. Equivalently, one can maximize \(p\)’s minimum score margin over the other candidates and ask whether the optimum is nonnegative.
This preserves the paper’s question—can a coalition choose its reports so the target wins?—while making a large homogeneous bloc divisible. Each voter still casts a complete ranking. The fractional quantities are only the aggregate mass assigned to rankings. In fact, for each strategic weight class, candidate-by-position mass forms a scaled doubly stochastic matrix; the Birkhoff–von Neumann theorem decomposes it into whole rankings. The resulting feasibility problem has a polynomial-size LP, so I expect this mirror to be tractable (Class A), in time polynomial in \(m,\tau,J\), and the input bit length. That is a genuine continuization of the population: it removes the partitioning effect of indivisible strategic voters, rather than changing the outcome rule.
The mirror covers Theorem 1’s weighted scoring-manipulation characterization across scoring protocols. It does not claim to explain the paper’s measured runtime curves, its phase-transition discussion, or its conclusions about how well particular heuristics perform. Further questions include the finite-population integrality gap, how much strategic mass is needed to make \(p\) win, and how ballot restrictions or reporting costs affect tractability.
The weak point is that the continuous question assumes a large, divisible coalition with few repeated weight classes. If the application has only a few named manipulators, or the coalition’s weight classes grow nearly one-for-one with the population, this is a poor high-multiplicity mirror. I think the large-cohort regime is credible for platform or association elections, but that assumption is doing real work.
Theorem 1 is the only serious anchor, but it is a reduction to permutation partition, not a complexity classification. The paper’s other central findings are experimental branch counts for particular partition heuristics. A continuous model of manipulation would not explain those measurements, which depend on indivisible voter weights and the search behavior of CKK, SNP, and RNP. That limits how much of the paper it mirrors.
It does not defeat the stronger mirror, though. A large association with a coordinated bloc and a few repeated weight classes is a coherent high-multiplicity regime. The manipulation objective does not track individual voters, and identical coalition members are interchangeable under the paper’s model. For each weight class, aggregate rankings can be represented by a doubly stochastic matrix of candidate-by-position masses. By Birkhoff–von Neumann, that matrix decomposes into whole rankings, so the continuous feasibility question is an exact polynomial-size LP.
That LP is a substantial change from the paper’s integer partition instances, but the programme explicitly treats the high-multiplicity version as a worthwhile question in its own right. It also gives a concrete bridge to the finite problem through rounding or an additive approximation. Calling it too easy, or saying it does not reproduce the paper’s runtime curves, would not establish that it is unworthy of study.
So the negative case is weak. The best objection is that this mirror extends one formal reduction while leaving the paper’s empirical claims untouched. I cannot honestly show that the improved mirror fails: Theorem 1 supports a plausible continuous computational question, and no fundamental modeling obstacle rules it out.
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.