| paper | Obvious Manipulability of Voting Rules |
| authors | H. Aziz, Alexa Lam |
| venue | ALDT 2021 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Both \(k\)-approval and positional scoring with an input binary rational vector are polynomial-time solvable. An improving report can also be produced in polynomial time, using at most \(dm\) exact rational linear-programming optimizations. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 5
statement extracted from the paper’s text layer
Given candidates \(O\), a finite ranking-type set \(T\subseteq L(O)\), rational focal mass \(\alpha\in(0,1]\), focal true ranking \(r\in T\), a fixed deterministic tie-break order, and a \(k\)-approval or positional scoring rule, choose a report \(r'\in T\). For every residual distribution \(\nu\in\Delta(T)\), the resulting society is \(\mu_{\nu,r'}=\alpha e_{r'}+(1-\alpha)\nu\). Define \(B_\alpha(r')\) and \(W_\alpha(r')\) as the focal type's best and worst possible winners under \(r\), over all \(\nu\). Decide whether some \(r'\) satisfies \(W_\alpha(r')\succ_r W_\alpha(r)\) or \(B_\alpha(r')\succ_r B_\alpha(r)\), and output such a report.
A high-multiplicity voting society over complete ranking types, with a focal homogeneous mass \(\alpha\) transferring from \(r\) to \(r'\), residual mass represented by \(\nu\), and objective to improve the focal mass's best or worst winner under the paper's zero-information criterion. For explicit \(T\), possible-winner checks are LP feasibility problems over residual masses and score inequalities.
A fixed \(\alpha\) is a coordinated weighted coalition rather than a unilateral atom, so the finite individual-manipulation theorem and its \(1/N\)-scale behavior do not transfer literally.
fatal: False
The mirror covers Corollary 5 and Theorem 6, with a related fractional-mass investigation of Theorem 3; it leaves most NOM/OM structural theorems, randomized tie-breaking, and the experiments aside.
The strongest positive case is an algorithmic one. This paper has no NP-hardness anchor, so I would not pretend that it supports a Class B or C claim. Its usable anchors are the polynomial-time results in Section 6.
The paper’s strongest anchor is Corollary 5, proved in the paper, which states that OM can be solved in polynomial time for \(k\)-approval. Here OM is the problem whose input is \(n\), the outcomes, a voter’s truthful preference, a fixed tie-break order, and the voting rule; the task is to find a report \( \succ'_i \) such that either the voter’s worst possible outcome or best possible outcome becomes strictly better than under truthful reporting. The corollary relies on the greedy polynomial algorithm for \(k\)-approval CCUM cited from Zuckerman et al., but the application to obvious manipulation is established here.
I would mirror it by the following problem.
Continuous \(k\)-Approval Obvious Mass Manipulation. The candidates are \(O\), \(k\) is fixed, and \(T\subseteq L(O)\) is the finite set of complete ranking types. A society is a distribution over \(T\). A focal homogeneous cohort has mass \( \alpha\in(0,1] \), true ranking \(r\in T\), and may transfer its mass from \(r\) to a reported ranking \(r'\). The remaining population has an arbitrary distribution \( \nu\in\Delta(T) \), so the post-report society is
\[ \mu_{\nu,r'}=\alpha e_{r'}+(1-\alpha)\nu . \]
The \(k\)-approval score is
\[ S_\mu(c)=\sum_{t\in T}\mu_t\,\mathbf 1[c\text{ is among the top }k\text{ positions of }t], \]
and the winner is the score-maximizing candidate, resolved by the paper’s fixed deterministic tie-break order. Define \(B_\alpha(r')\) and \(W_\alpha(r')\) as, respectively, the best and worst winner under the focal cohort’s true ranking \(r\), ranging over every residual distribution \( \nu \). The task is to output a report \(r'\) satisfying
\[ W_\alpha(r')\succ_r W_\alpha(r) \quad\text{or}\quad B_\alpha(r')\succ_r B_\alpha(r), \]
or correctly report that no such report exists.
This is a direct population mirror of the paper’s zero-information notion. Candidates remain indivisible and discrete; only the electorate becomes a mass distribution. The action is a genuine mass transfer, not a fractional outcome.
The natural regime is a large electorate with relatively few complete preference types: for example, millions of voters generated by a small number of demographic, organizational, or policy cohorts, with a constituency or coordinated bloc controlling the report of one repeated type. One can have \(N\) large, \( \tau=|T|\ll N \), and a focal mass \( \alpha N \) consisting of many interchangeable agents with the same ranking and the same reporting authority. This is a plausible high-multiplicity setting, not merely a relabeling of named individuals.
I expect this problem to be Class A in the explicit-type model. For each candidate and report, the possible-winner question is a linear feasibility problem over \( \nu_t \), with constraints \( \nu_t\ge0 \), \( \sum_t\nu_t=1 \), and linear score comparisons. Thus best and worst outcomes can be computed by LP, and a suitable report can be found by enumerating the explicit report types. For \(k\)-approval, the same calculation has a capacitated approval/disapproval interpretation and should admit the analogue of the paper’s greedy CCUM procedure.
The continuous answer need not reproduce the paper’s exact threshold. Theorem 3 says, proved in this paper, that finite \(k\)-approval is obviously manipulable exactly when
\[ n\le \frac{m-2}{m-k}. \]
Its proof depends on pigeonhole arguments about indivisible disapproval votes. In the mass version, residual disapproval can be split fractionally across candidates. Determining exactly which values of \( \alpha \), \(m\), and \(k\) still permit an obvious mass manipulation is therefore a meaningful continuization question. It may show that much of the finite OM region disappears under fractional population mass, which would be an informative Class A result rather than a defect.
A second, broader anchor is Theorem 6, also proved in the paper. It states that, for every positional scoring rule, solving OM has a polynomial-time reduction to CCUM. The paper obtains this by using CCUM calls to compute the truthful and unrestricted best cases, and, for worst-case manipulation, by constructing a canonical misreport that places outcomes better than the truthful worst case above the bad outcomes and then checking whether any bad outcome remains achievable.
The corresponding continuous problem is Continuous Positional-Scoring Obvious Mass Manipulation. The instance is the same as above, but with an arbitrary rational scoring vector \(s=(s_1,\ldots,s_m)\), and
\[ S_\mu(c)=\sum_{t\in T}\mu_t\,s_{\operatorname{pos}_t(c)}. \]
The task is again to find \(r'\) improving the focal type’s best or worst winner over all residual distributions \( \nu \). Its natural auxiliary problem is Mass-CCUM: given a committed mass vector \( \lambda \), a free mass \(1-\|\lambda\|_1\), and a distinguished candidate \(c\), decide whether some \( \eta\in\Delta(T) \) makes \(c\) win in
\[ \lambda+(1-\|\lambda\|_1)\eta. \]
For an explicit type universe this is an LP feasibility problem, so the continuous analogue of Theorem 6 should again be Class A in \( (m,\tau,L) \). With rankings represented implicitly rather than by an explicit type table, the interesting follow-up is whether the required feasibility and pricing problems can be solved without expanding all \(m!\) rankings. That is precisely the kind of continuous-optimization question the ChoCo programme is meant to expose.
The weakest point is that a positive-mass report is not literally a unilateral manipulation by one infinitesimal voter. If \( \alpha\to0 \) while \(m\) stays fixed, the manipulation’s effect vanishes and the mirror may become trivial. The proposed model therefore mirrors the paper most faithfully as manipulation by a homogeneous cohort or coordinated type mass. That is a genuine modification, but it is the natural one forced by making the population itself continuous: the paper’s voter becomes a repeated type whose mass can be transferred. The candidates, rankings, scoring rule, fixed tie-break, zero-information uncertainty, and best/worst-case objective all remain intact.
So the positive verdict is modest but credible: Corollary 5 and Theorem 6 support a precise continuous-population research problem, probably tractable in the explicit-type representation, with nontrivial open questions about fractional disapproval, the fate of Theorem 3’s threshold, and compact pricing over ranking types.
The negative case is fairly strong against these anchors, though not literally airtight against every conceivable voting variant. Voting plainly has high-multiplicity regimes. The problem is more specific: a faithful continuum destroys the paper’s strategic object, while the proposed nonzero-mass repair changes it into coalition manipulation.
Corollary 5 concerns one voter. In a population of \(N\) voters represented by normalized mass, that voter has mass \(1/N\). Changing their report changes every candidate’s normalized score by at most \(O(1/N)\), so in the atomless limit the report has no effect:
\[ \mu'=\mu+\frac{1}{N}(e_{r'}-e_r)\longrightarrow \mu. \]
Thus unilateral obvious manipulation disappears. Away from exact score ties, the winner is unchanged; at ties, any surviving effect is a boundary artifact of the deterministic tie-break. Preserving the finite-voter phenomenon would require retaining \(1/N\)-scale information, which is no longer a pure continuous-population model.
The proponent’s repair—give the focal “voter” a fixed mass \(\alpha>0\)—does produce a nontrivial problem, but it is not a forced consequence of continuization. It replaces one strategic agent by a coordinated bloc of \(\alpha N\) agents. If the bloc does not coordinate, only one unit of mass moves and the effect vanishes. If it does coordinate, the problem is weighted coalitional manipulation with a common preference, not obvious manipulability as defined in the paper. That is a legitimate new problem, but the paper’s Corollary 5 no longer anchors it.
There is a second mismatch in the proposed model. Since the residual distribution \(\nu\) ranges over all of \(\Delta(T)\), the society itself is not really an input: it is quantified away. The model asks whether a focal bloc can improve its outcome against every possible remaining society. If one instead supplies an actual residual distribution, then one must specify what uncertainty set replaces the paper’s finite set of possible profiles. A neighbourhood, moment class, or rational grid would each create a different robust-manipulation problem; none is dictated by the paper.
The LP formulation therefore does not rescue the mirror. For fixed \(k\), the residual population can be represented by fractional approval incidences, and the resulting feasibility calculation is essentially the paper’s CCUM capacity argument written with real numbers. For general positional scoring, preserving the full voting domain requires \(T=L(O)\), so \(\tau=m!\); “polynomial in \(\tau\)” is then an explicit expansion of the exponential ranking domain, not a compact continuous algorithm. Restricting \(T\) gives a smaller problem, but changes the voting rule’s domain.
The same objection applies even more strongly to Theorem 6. Its content is a reduction from obvious manipulation to CCUM, not a theorem about a population distribution. Replacing integer manipulator votes by fractional mass yields a generic LP relaxation of CCUM. It may be mathematically sensible, but it is not a continuous form of the paper’s individual-level result. To make it genuinely distributional one must add a specified base society and an uncertainty or intervention model; that added model carries the substantive research question.
Theorem 3 does not repair this. Its threshold is driven by indivisible disapproval votes and a finite number of other voters. In the faithful limit, the single voter disappears. With fixed \(\alpha\), one obtains a threshold for a positive-mass coalition, which may be interesting, but it is a new weighted-coalition question rather than a continuization of the paper’s theorem.
So the strongest negative verdict is: neither named anchor survives as the same problem under population continuization. A worthwhile mass-coalition study may well be possible, but it would use this paper only as inspiration. I cannot honestly claim that no related continuous voting question could be valuable; I can claim that the proposed mirrors do not preserve the paper’s central individual, zero-information notion.
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.