Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule (d4-conf-ijcai-2009-0144)

Given three candidates \(A,B,C\), target \(C\), a fixed electorate distribution \(\nu\) of mass \(1-\lambda\), and a manipulating electorate distribution \(\mu\) of mass \(\lambda\) over finitely many voter types with per-agent veto weights, does there exist a mass assignment \(x_{t,j}\ge 0\) satisfying \(x_{t,A}+x_{t,B}+x_{t,C}=\lambda\mu_t\) for every manipulating type \(t\), such that \(C\)'s final veto weight is no greater than those of \(A\) and \(B\)?

There are \(m=3\) candidates \(A,B,C\), with target \(C\). Use weighted veto, with ties resolved in favor of \(C\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here count fixed and manipulating types separately, and let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
The input includes a binary rational \(\lambda\in[0,1]\). Fixed types \(s\) have masses \(\nu_s>0\) summing to \(1-\lambda\), positive binary rational weights \(w_s\), and fixed vetoed candidates \(v_s\in\{A,B,C\}\).
Manipulating types \(t\) have positive binary rational weights \(w_t\) and conditional proportions \(\mu_t>0\) summing to \(1\); their actual masses are \(\lambda\mu_t\). When \(\lambda=0\), the manipulating support is empty; when \(\lambda=1\), the fixed support is empty.
Manipulating mass may be divided arbitrarily among veto choices: \(x_{t,j}\in\mathbb R_{\ge0}\) and \(\sum_{j\in\{A,B,C\}}x_{t,j}=\lambda\mu_t\). Define \(V_j=\sum_{s:v_s=j}w_s\nu_s+\sum_t w_tx_{t,j}\); success means \(V_C\le V_A\) and \(V_C\le V_B\).

Is this continuous weighted-veto manipulation decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

Discrete successful manipulation is equivalent to two-way number partitioning with a prescribed discrepancy bound; discrete three-candidate weighted veto manipulation is [NP-complete](https://www.eecs.harvard.edu/cs286r/courses/fall11/papers/CSL07.pdf).
[Xia, Conitzer and Procaccia](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf) establish polynomial-time solvability of divisible weighted coalitional manipulation for every positional scoring rule. Their divisible-vote formulation describes the same feasible veto allocations as the mass formulation above, so this target is already settled.

Result

The problem is in \(\mathrm P\). In fact, a successful manipulation exists exactly when

\[ \max\{F_C-F_A,0\}+\max\{F_C-F_B,0\}\le M, \]

where \(F_j=\sum_{s:v_s=j}w_s\nu_s\) is the fixed veto weight of candidate \(j\), and \(M=\lambda\sum_t w_t\mu_t\) is the total manipulating weight. Empty sums equal zero.

Let \(\tau_{\mathrm F}\) and \(\tau_{\mathrm M}\) count supported fixed and manipulating types separately, and let \(\tau=\tau_{\mathrm F}+\tau_{\mathrm M}\). An exact decision algorithm takes \(O((m+\tau_{\mathrm F}+\tau_{\mathrm M})L^2)\) bit operations using schoolbook integer arithmetic. For the stipulated \(m=3\), this is \(O((\tau+1)L^2)\).

Proof of the feasibility criterion

Define \(d_A=\max\{F_C-F_A,0\}\) and \(d_B=\max\{F_C-F_B,0\}\).

Necessity. Consider any successful allocation, and write \(Y_j=\sum_t w_tx_{t,j}\) for its manipulating veto weight on candidate \(j\). Nonnegativity and the mass constraints give

\[ Y_A+Y_B+Y_C =\sum_t w_t\sum_jx_{t,j} =\lambda\sum_t w_t\mu_t =M. \]

Success implies \(F_A+Y_A\ge F_C+Y_C\). Hence \(Y_A\ge F_C-F_A+Y_C\ge F_C-F_A\). Together with \(Y_A\ge0\), this yields \(Y_A\ge d_A\). The same argument gives \(Y_B\ge d_B\). Consequently, \(M=Y_A+Y_B+Y_C\ge d_A+d_B\).

Sufficiency when \(M>0\). Suppose \(d_A+d_B\le M\), and set \(q=d_A/M\). Then \(0\le q\le1\). For every manipulating type, choose

\[ x_{t,A}=\lambda\mu_tq,\qquad x_{t,B}=\lambda\mu_t(1-q),\qquad x_{t,C}=0. \]

These allocations are nonnegative and sum to \(\lambda\mu_t\) for each type. Their weighted totals are

\[ Y_A=qM=d_A,\qquad Y_B=(1-q)M=M-d_A\ge d_B,\qquad Y_C=0. \]

Thus \(V_C=F_C\), while \(V_A=F_A+d_A\ge F_C\) and \(V_B=F_B+M-d_A\ge F_C\). Candidate \(C\) therefore wins, including when equality occurs, because ties favor \(C\).

The case \(M=0\). The criterion becomes \(d_A=d_B=0\), which is equivalent to \(F_C\le F_A\) and \(F_C\le F_B\). These are exactly the success conditions without manipulating weight. Under the input assumptions, positive \(\lambda\) would imply \(M>0\), so this case has \(\lambda=0\) and empty manipulating support.

This also covers both endpoint inputs: when \(\lambda=0\), the algorithm checks the fixed election; when \(\lambda=1\), all fixed veto weights vanish and manipulation always succeeds.

Exact arithmetic and running time

The algorithm computes the three fixed totals, the manipulating total, and the two deficits, then tests the criterion. It processes only supported types.

To justify the bit bound, write each input rational as an integer numerator divided by a positive integer denominator. Let \(D\) be the product of all input denominator occurrences. Since their total encoding length is at most \(L\), the integer \(D\) has \(O(L)\) bits.

Every term \(w_s\nu_s\), and every term \(\lambda w_t\mu_t\), has a denominator dividing \(D\): its factors use distinct input occurrences, each included in that product. Thus all totals can be represented over the common denominator \(D\). Their numerators have \(O(L)\) bits: each term combines input numerators and denominator factors of total bit length \(O(L)\), and summing at most \(\tau\) terms adds only \(O(\log(\tau+1))\) bits. The explicit support encoding ensures \(\tau=O(L)\).

Computing \(D\), converting the terms to this denominator, summing, and comparing requires \(O(\tau+1)\) integer operations on \(O(L)\)-bit integers. Schoolbook multiplication and division take \(O(L^2)\) bit operations each, proving the claimed bound for \(m=3\).

For completeness, the same argument works for any explicitly represented \(m\ge2\): success is equivalent to

\[ \sum_{j\ne C}\max\{F_C-F_j,0\}\le M. \]

Necessity follows by summing the rival deficits. For sufficiency, assign each rival its deficit, put any leftover manipulating weight on one rival, and realize these totals by giving every manipulating type the same proportions. Computing these deficits gives the stated \(O((m+\tau_{\mathrm F}+\tau_{\mathrm M})L^2)\) decision bound.

The three-candidate witness above is rational, with \(O(L)\) bits per entry, and can also be constructed within \(O((\tau+1)L^2)\) bit operations.

Connection with divisible votes

Theorem 3.4 of [Xia, Conitzer and Procaccia, *A Scheduling Approach to Coalitional Manipulation*](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf) establishes exact polynomial-time solvability of divisible weighted coalitional manipulation for positional scoring rules.

Here the correspondence is explicit. Replace each fixed type by one fixed vote of effective weight \(w_s\nu_s\), and each manipulating type by one divisible vote of effective weight \(\lambda w_t\mu_t\). When \(\lambda>0\), an allocation determines veto probabilities \(p_{t,j}=x_{t,j}/(\lambda\mu_t)\), and conversely these probabilities determine the allocation. Each veto choice can be represented by a ranking with that candidate last.

Weighted veto selects candidates with minimum veto weight, so the paper’s co-winner condition agrees with ties favoring \(C\). The direct proof above additionally supplies the exact criterion and support-sensitive bit bound.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem correctly: continuous weighted-veto manipulation is in \(\mathrm P\), with the stated support-sensitive running time. No major or minor mathematical issues were found.

• Definitions and feasibility criterion. The quantities \(F_j\) and \(M\) correctly represent fixed veto weight and total available manipulating veto weight. The claimed criterion

\[ \max\{F_C-F_A,0\}+\max\{F_C-F_B,0\}\le M \]
uses precisely the non-strict success inequalities required by ties favoring \(C\). It does not impose indivisibility or any unstated restriction on the allocations.

• Necessity. The identity \(Y_A+Y_B+Y_C=M\) follows directly from the per-type mass constraints and finite summation. Success gives \(Y_A\ge F_C-F_A+Y_C\). Since \(Y_C\ge0\) and \(Y_A\ge0\), the inference \(Y_A\ge d_A\) is valid even when \(F_C-F_A<0\). The corresponding inference for \(B\) is also valid. Summing these bounds proves the necessary inequality without discarding any potentially successful allocations.

• Sufficiency for positive manipulating weight. Under \(M>0\) and \(d_A+d_B\le M\), the defined fraction \(q=d_A/M\) lies in \([0,1]\). Every proposed allocation is nonnegative and has the required total mass for its type. Using the same fraction for all types is permitted despite their different weights. The displayed weighted totals are correct, and \(M-d_A\ge d_B\) follows from the assumed criterion. Both rival veto totals are consequently at least \(F_C\), while the target receives no manipulating veto weight. This proves success, including equality cases.

• Zero weight and endpoints. If \(M=0\), nonnegativity makes the criterion equivalent to \(d_A=d_B=0\), hence to success in the fixed election. Under the promised input conditions, \(\lambda>0\) entails a nonempty manipulating support with strictly positive weights and proportions, so it entails \(M>0\). Thus the prover correctly associates \(M=0\) with \(\lambda=0\). At \(\lambda=1\), the fixed support is empty, all deficits vanish, and the positive-weight construction applies. Both endpoints are covered.

• Exact arithmetic and bit complexity. The common-denominator argument is valid. Each term uses distinct input denominator occurrences, so its denominator divides their product \(D\), including when different occurrences happen to have equal numerical values. The product \(D\), term denominators, and scaled numerators all have \(O(L)\) bits. Summation adds at most \(O(\log(\tau+1))\) bits, which remains within \(O(L)\) because the support is explicitly listed.

Constructing \(D\), forming and scaling the terms, accumulating totals, and comparing deficits require \(O(\tau+1)\) arithmetic operations for three candidates. Schoolbook multiplication and division on these integers cost \(O(L^2)\) per operation. Therefore the stated \(O((\tau+1)L^2)\) decision bound is justified. The algorithm counts supported fixed and manipulating types separately as requested.

• Additional claims. The extension to explicitly represented \(m\ge2\) is consistent with the proof: summing the rival deficits proves necessity, and the stated common-proportion allocation realizes the chosen rival totals when \(M>0\). The already discussed zero-weight case extends directly. Processing the candidate totals and supported types gives the claimed \(O((m+\tau_{\mathrm F}+\tau_{\mathrm M})L^2)\) bound.

The rational-witness claim is also sound. The computed deficits and \(M\) have rational representations of \(O(L)\) bits; forming \(q\), its complement, and the displayed per-type products preserves that bound up to constant factors. Constructing the three entries per supported manipulating type fits the stated running time.

• Cited theorem and correspondence. The citation is accurate: Theorem 3.4 states exact polynomial-time solvability of the divisible weighted manipulation and optimization problems for positional scoring rules. The paper defines divisible votes as convex combinations of rankings and uses a co-winner success condition. These match the prover’s effective-weight translation and target-favoring ties. Veto depends only on the last-ranked candidate, so representing each veto choice by a ranking loses no relevant information. [Xia, Conitzer and Procaccia, *A Scheduling Approach to Coalitional Manipulation*](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf)

The direct argument independently establishes the classification and running time. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩