| paper | Manipulating Elections by Changing Voter Perceptions |
| authors | Junlin Wu, Andrew Estornell, Lecheng Kong, Yevgeniy Vorobeychik |
| venue | IJCAI 2022 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given \(c_1,c_2\in\{0,1\}^d\), an integer \(1\le p<\infty\), a budget \(\epsilon\), voter types \(q^1,\ldots,q^\tau\in\{0,1\}^d\), and rational masses \(\mu_r\ge0\) summing to \(1\), does there exist \(\widetilde c_1\in\{0,1\}^d\) with \(\|\widetilde c_1-c_1\|_p\le\epsilon\) such that \(\sum_{r=1}^{\tau}\mu_r\mathbf{1}[\|\widetilde c_1-q^r\|_p\le\|c_2-q^r\|_p]\ge\tfrac12\), with the analogous destructive question defined by requiring \(c_1\) not to win?
A finite-support continuous society over complete issue-position types, with rational mass \(\mu_r\), a single globally manipulated candidate position \(\widetilde c_1\), an \(\ell_p\)-budget, and mass-weighted majority or scoring-rule winner conditions.
Theorem 1 does not establish hardness when the number of voter types is bounded, and with unrestricted support rational masses can encode the original electorate exactly, so the mirror may provide compression semantics without a tractability gain.
fatal: False
The mirror covers Theorem 1's binary two-candidate constructive and destructive control and Corollary 1's small-type algorithmic regime; it leaves the real-valued norm variants and constant-issue geometric results outside scope.
My lead anchor is Theorem 1, proved in this paper using the cited NP-completeness of BISC. It says that BVPM is NP-complete for constructive and destructive control with only two candidates and majority voting. This is an unusually good anchor for ChoCo because the combinatorics already live in the issue space, while the voter population can naturally be made high-multiplicity.
Call the mirror Population-BVPM. An instance consists of two candidates \(c_1,c_2\in\{0,1\}^d\), a target candidate \(c_1\), an integer \(1\le p<\infty\), and \(\tau\) voter types \(q^1,\ldots,q^\tau\in\{0,1\}^d\) with rational masses \(\mu_1,\ldots,\mu_\tau\), where \(\sum_{r=1}^{\tau}\mu_r=1\). Type \(q^r\) is the complete issue-position vector of a voter; its mass is the fraction of society at that position. The manipulator chooses one new perceived position \(\widetilde c_1\in\{0,1\}^d\), globally applying the same perception change to every voter, at cost \(\|\widetilde c_1-c_1\|_p\).
For constructive control, define
\[ W_\mu(\widetilde c_1) = \sum_{r=1}^{\tau} \mu_r\, \mathbf 1\!\left[ \|\widetilde c_1-q^r\|_p \le \|c_2-q^r\|_p \right], \]
with ties broken in the manipulator’s favour, exactly as in the paper. The optimization problem is to minimize \(\|\widetilde c_1-c_1\|_p\) subject to \(W_\mu(\widetilde c_1)\ge \tfrac12\). Its decision version asks whether a winning \(\widetilde c_1\) exists within budget \(\epsilon\). Destructive control is defined identically, requiring the target not to win.
The intended regime is a large electorate of recurring issue-profile cohorts: for example, millions of voters drawn from a finite collection of party, demographic, or ideological profiles. The meaningful comparison is \(N\gg\tau\): the number of people is huge, while the number of distinct issue-position types is moderate. This is not an artificial change to the manipulation model. The paper already assumes that the attacker changes one candidate’s perceived position, not each voter’s perception separately, and that rankings arise from spatial distance. Population-BVPM retains both assumptions exactly.
The discrete-to-continuous correspondence is exact. A finite election with \(n_r\) voters of type \(q^r\) becomes \(\mu_r=n_r/N\), and every candidate’s mass-weighted score is its original score divided by \(N\). Conversely, every rational mass vector can be realized by a sufficiently large finite electorate. Therefore Theorem 1’s hardness transfers immediately: the continuous problem is NP-complete when \(\tau\) is unrestricted. This should be understood as Class B hardness, not as continuum-specific hardness. The reduction’s essential choice is the subset of issues whose perceptions are flipped; that combinatorics lives in \(d\), rather than in the identities of individual voters.
My second anchor is Corollary 1, stated and justified in this paper. It says that BVPM is solvable in polynomial time when the number of distinct voter opinions is constant, for constructive and destructive control and arbitrary scoring rules. Its continuous mirror is Polarized Population-BVPM.
Here the instance has \(n\) candidates with binary issue positions, a scoring function \(f\), a target \(c_1\), at most \(k\) voter types \(q^1,\ldots,q^\tau\) with \(\tau\le k\), rational masses \(\mu_r\), and a norm-budget constraint. For a chosen \(\widetilde c_1\), let \(r_i(q^r,\widetilde c_1)\) be the rank of candidate \(c_i\) for type \(q^r\). The mass-weighted score is
\[ S_\mu(c_i;\widetilde c_1) = \sum_{r=1}^{\tau} \mu_r f\!\left(r_i(q^r,\widetilde c_1)\right). \]
The question is whether the manipulator can choose \(\widetilde c_1\) within budget so that \(S_\mu(c_1;\widetilde c_1)\ge S_\mu(c_i;\widetilde c_1)\) for every \(i\), or, in optimization form, what the minimum perception budget is.
This is a Class A direction for every fixed \(k\). The algorithm in the paper already replaces repeated voter opinions by weighted score contributions; replacing integer counts by rational masses changes only the arithmetic. Its enumeration over ranking-score scenarios has a dependence of the form
\[ O\!\left(n(d+\log n)+|f_{\mathrm{uniq}}|^k(d+n)\right), \]
up to rational-arithmetic costs, which is polynomial in the ordinary input size when \(k\) is fixed. The natural interpretation is precisely the paper’s “political polarization” setting: a small number of echo chambers, each containing a large mass of voters with an effectively uniform issue profile.
The resulting research question is therefore not merely “can we write the election with weights?” It is: where is the boundary between the two regimes? Population-BVPM asks whether Theorem 1’s NP-hardness survives mass aggregation; it does when type support is unrestricted. Polarized Population-BVPM asks how far the polynomial algorithm behind Corollary 1 extends when \(k\) is a parameter rather than a fixed constant. In particular, can the dependence on \(|f_{\mathrm{uniq}}|^k\) be improved, and is the problem fixed-parameter tractable in \(k\) for important scoring rules?
The weakest point is that the lead hardness result does not show hardness with a bounded number of types. The BISC reduction may use many distinct issue profiles, so the transferred NP-hardness could be entirely compatible with the paper’s tractability result for a genuinely polarized population. Also, the binary-action model means that the population is continuous but the perception vector remains discrete. I would not disguise either limitation. They are nevertheless acceptable under ChoCo’s scope: the programme continuizes the society, not necessarily every action space, and a problem may legitimately have Class B behaviour in the general regime and Class A behaviour for small \(\tau\).
I would therefore cover Theorem 1 and Corollary 1, but not stretch to claim that every real-valued result in the paper supplies a separate anchor. The paper supports a particularly clean mirror: exact high-multiplicity semantics, a hardness result whose combinatorics remain in the agenda of issues, and an explicit small-type regime where aggregation makes manipulation tractable.
The case against these anchors is that neither makes the population a computational object in the sense ChoCo is seeking. In both, the population is only a source of coefficients in an otherwise unchanged geometric control problem.
For Theorem 1, the proposed Population-BVPM is exactly a weighted reformulation of the paper’s finite problem. If \(\mu_r=a_r/N\), replicate type \(q^r\) exactly \(a_r\) times. Every feasible perception vector, voter outcome, majority comparison, budget, and optimum is preserved exactly. Conversely, every finite election produces such a rational mass vector. This is not merely hardness transfer: the two formulations have the same instances up to encoding and the same computational content.
More importantly, the theorem does not establish hardness in a genuinely high-multiplicity regime. Its reduction may use one distinct voter opinion per voter, so \(\tau\) can be as large as the electorate. When \(\tau\) is bounded, the paper already gives polynomial-time solvability through Corollary 1. Thus the proposed mirror has a choice between a large-support distribution that is simply the original discrete instance in normalized notation, and a small-support distribution whose algorithm is already supplied by the paper. The claimed \(N\gg\tau\) interpretation is a plausible application story, but it is not a property established by Theorem 1.
Corollary 1 is even less promising as a new continuous result. Its proof explicitly replaces repeated voter opinions by weighted score contributions. Substituting rational masses for integer counts changes only the arithmetic:
\[ \sum_q a_q f(r_q) \quad\longmapsto\quad \sum_q \mu_q f(r_q). \]
The enumeration and feasibility argument are already the algorithm for the mass formulation. Calling the parameter \(k\) a number of population types does not create a new continuous optimization problem; it creates a type-support parameterization of the existing perception-control problem. Moreover, the displayed dependence \(|f_{\mathrm{uniq}}|^k\) is an XP bound in \(k\), not an FPT result in \(k\) when the scoring rule has many distinct values. Improving it could be worthwhile, but that would be parameterized algorithmics for weighted BVPM, not a consequence of continuizing the society.
The strongest possible repairs do not rescue these anchors. Allowing a continuous distribution over voter positions rather than finite support introduces a representation problem: with finite mixtures one returns to weighted BVPM, while with a general density the main difficulty becomes integrating Voronoi-region indicators. That is a new computational-geometry problem whose complexity depends on the chosen density representation, not a canonical mirror of the paper. Allowing the manipulator to alter perceptions separately by type would make population mass decision-bearing, but it abandons the paper’s defining assumption that one global candidate-position change affects every voter identically; it is a new bribery or campaign model.
There is no honest objection based on identity or the absence of plausible repeated voters: political issue-profile cohorts are a perfectly credible high-multiplicity story. The negative case is therefore not airtight. But the proponent has shown at most that the paper admits a natural weighted restatement and that its existing small-opinion-type algorithm survives rational weighting. Neither anchor supplies an unaddressed continuous computational question, a mass-transfer structure, or a new optimization barrier for ChoCo.
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.