| paper | Junta distributions and the average-case complexity of manipulating elections |
| authors | Ariel D. Procaccia, J. Rosenschein |
| venue | ATAL 2006 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm P\). For \(m=3\), the decision takes \(O(\tau L^2)\) bit operations; the corresponding unrestricted divisible-mass problem for variable \(m\) takes \(\operatorname{poly}(m,\tau,L)\) time. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given \(3\) candidates \(C=\{p,a,b\}\), a sensitive scoring vector, rational nonmanipulator types with masses \(\nu_r\), weights \(w_r\), and fixed rankings \(\rho_r\), and rational manipulator types with masses \(\mu_t\) and weights \(u_t\), does there exist \(x_{t,\pi}\ge 0\) for rankings \(\pi\in\mathcal{L}(C)\) such that \(\sum_{\pi}x_{t,\pi}=\mu_t\) for every \(t\), and \(p\) wins under adversarial tie-breaking when \(S_x(c)=\sum_r\nu_rw_rs(\rho_r,c)+\sum_{t,\pi}x_{t,\pi}u_ts(\pi,c)\)?
A high-multiplicity weighted coalitional-manipulation model with voter types carrying mass, integral rankings chosen by each infinitesimal voter, mass-assignment variables \(x_{t,\pi}\), and a linear scoring feasibility objective.
With no type-specific constraints, manipulator types may collapse to their aggregate weighted capacity \(W=\sum_t \mu_t u_t\), making the mirror a thin divisible-capacity relaxation rather than a type-sensitive continuation.
fatal: False
It covers the weighted coalitional manipulation hardness in Proposition 1, and naturally the analogous SCWM result in Corollary 1, under a high-multiplicity fractional-report regime; it leaves the junta-distribution, average-case, uniform-distribution, and uncertainty results untouched.
My strongest case is a one-anchor Class A mirror of the paper’s weighted coalitional manipulation problem.
The anchor is Proposition 1, proved in this paper: “Let \(P\) be a sensitive scoring protocol. Then CWM in \(P\) is NP-hard, even with 3 candidates.” Here a sensitive scoring protocol has scores \(\alpha_1\ge\cdots\ge\alpha_{|C|-1}>\alpha_{|C|}=0\). The proof reduces Partition to manipulation with three candidates, using the manipulators’ encoded weights as the integers whose two-way partition must be found. The paper subsequently derives the analogous SCWM statement as Corollary 1.
My continuous mirror would be Continuous Weighted Coalitional Manipulation for Sensitive Scoring.
Fix a sensitive scoring vector and three candidates \(C=\{p,a,b\}\), where \(p\) is preferred. An instance consists of a finite collection of voter types. A nonmanipulator type \(r\) specifies a complete ranking \(\rho_r\), a voting weight \(w_r\), and population mass \(\nu_r\). A manipulator type \(t\) specifies its voting weight \(u_t\) and population mass \(\mu_t\); if sincere preferences are recorded in the application, they are part of the type as well. Types are complete descriptions: agents with the same type are indistinguishable for the manipulation problem.
The masses are rational, nonnegative, and sum to one. The nonmanipulators contribute the fixed score
\[ B(c)=\sum_r \nu_r w_r s(\rho_r,c). \]
The coalition chooses, for every manipulator type \(t\), how much of its mass reports each complete ranking \(\pi\in\mathcal L(C)\). The decision variables are \(x_{t,\pi}\ge 0\), subject to
\[ \sum_{\pi\in\mathcal L(C)}x_{t,\pi}=\mu_t \qquad\text{for every }t. \]
The resulting score is
\[ S_x(c)=B(c)+ \sum_t\sum_{\pi\in\mathcal L(C)} x_{t,\pi}u_t s(\pi,c). \]
The question is whether there exists such an \(x\) making \(p\) win under the paper’s adversarial tie-breaking convention. Equivalently, maximize the winning margin
\[ \delta^*= \max_x\min_{c\ne p}\bigl(S_x(p)-S_x(c)\bigr), \]
and answer yes exactly when \(\delta^*>0\). For co-winner semantics, replace \(>0\) by \(\ge0\). A solution is the mass-assignment \(x\), not merely a yes/no certificate.
This is a genuine population continuization. Each infinitesimal voter still submits an integral ranking \(\pi\); \(x_{t,\pi}\) records the mass of type \(t\) assigned to that ranking. We are not giving voters fractional scores or fractional outcomes. Rational \(x\) can be implemented by clearing denominators in a sufficiently large finite electorate.
A plausible regime is a large professional association, platform community, or membership organization choosing among three proposals. Millions of members fall into a small number of repeated cohorts determined by role, membership tier, and preference ranking. Members in the same cohort have the same voting weight and are coordinated by the same campaign. Thus \(N\) may be in the millions while the number of distinct types \(\tau\) is dozens or hundreds, with each type having substantial multiplicity. That is a sensible high-multiplicity version of the paper’s coalition: the candidates, scoring rule, preferred candidate, weighted votes, and strategic objective are unchanged.
For fixed candidates, this mirror is an LP with \(|T_M|\,|C|!\) variables and \(O(|T_M|+|C|)\) constraints. Since \(|C|=3\) in the anchor, the six possible rankings are constant in number, so exact rational feasibility is polynomial in \(\tau\) and the input bit length. I therefore expect the continuous problem to be tractable.
The reason Proposition 1’s hardness should disappear is particularly revealing. Its reduction has only three candidates, so the combinatorics cannot live in the agenda. They live in the individually encoded weights \(k_i\) and the requirement that each weighted manipulator be assigned wholly to one side of a Partition. In the continuous population, a repeated type’s mass can be divided between reports. The feasible score region becomes a Minkowski sum of convex hulls, and the subset-sum obstruction becomes linear feasibility. This is exactly the sort of population-multiplicity hardness that continuization ought to dissolve.
The main follow-up questions are whether the LP remains efficient when the number of candidates is variable; how much finite-population rounding error is needed when the winning margin is small; and whether hardness returns if campaign rules require entire cohorts to cast the same report, impose minimum bloc sizes, or otherwise restore indivisibility.
My weakest point is that this mirror deliberately excludes the paper’s most pathological instances: a Partition reduction can give almost every manipulator a distinct, information-bearing weight. Those are not genuinely high-multiplicity populations. If a referee insists that each such individual must remain indivisible, the LP is only a relaxation, not the right model. I would also not claim to continuize the paper’s Theorem 1 about junta-distribution average-case susceptibility: its \(\mu_n\) is an outer distribution over finite instances, not the society itself. My claim is narrower but defensible: Proposition 1 identifies a natural, named, fixed-agenda hardness result whose obstruction is population multiplicity, and its high-multiplicity population analogue is a precise and plausibly tractable continuous problem.
The strongest objection is that the proposed LP does not actually continuize the hardness mechanism of Proposition 1. It replaces the paper’s strategic units by independently splittable agents.
In the reduction, each manipulator carrying weight \(2(\alpha_1+\alpha_2)k_i\) is one indivisible voting unit. It must cast one ranking, and the reduction asks whether those units can be divided into two integral sides of equal total weight. The paper explicitly interprets a weight-\(k_i\) voter as \(k_i\) voters who vote unanimously. By allowing \(x_{t,\pi}\) to split a type’s mass between rankings, the proposed model removes precisely that unanimity constraint. Its feasible region is a convexification of CWM, not a population version preserving its strategic objects.
The obvious repair is to regard weighted voters as institutional blocs—shareholder blocks, unions, or membership tiers—and require each bloc type to choose one report. But then the continuous mass does not remove the relevant indivisibility. One can retain types with weights proportional to the \(k_i\) and require each type’s mass to act coherently; the Partition choice remains at the type or bloc level. This is either essentially the original problem with replicated blocs or a new bloc-coordination problem, not the proposed fractional mirror.
Conversely, if the agents really are many ordinary members with per-person weights, then the population distribution contributes almost nothing. In the three-candidate setting, every manipulator type has the same six possible reports and no type-dependent utility, price, or admissibility constraint. All manipulator types collapse to their aggregate weighted capacity
\[ W=\sum_t \mu_t u_t, \]
while the nonmanipulators collapse to the initial score vector \(B\). The alleged society over types therefore disappears from the decision problem, leaving a constant-size fractional feasibility calculation. That is a valid relaxation, but a very thin one: it studies divisible strategic capacity, not a computational problem whose structure depends on a continuous society.
Adding constraints that make types matter—bloc unanimity, type-specific permissible reports, utilities, or campaign costs—would produce interesting models, but those are new manipulation problems rather than continuizations anchored by Proposition 1 or Corollary 1.
This negative case is nevertheless not decisive. The programme explicitly permits a high-multiplicity regime in which repeated agents of one complete type may act independently, and a large association with repeated weighted membership cohorts is plausible. Under that reading, the proposed LP is a legitimate Class A mirror, and the disappearance of Partition is precisely the sort of population-multiplicity phenomenon ChoCo seeks. So the honest conclusion is that the negative case can challenge the mirror’s richness and fidelity to the weighted-bloc interpretation, but it cannot sustain the universal claim that no worthwhile continuous mirror exists.
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.