d4-conf-aaai-2011-0313 (d4-conf-aaai-2011-0313)

Given \(C=\{a,b,c,p\}\), rational nonmanipulator masses \(\mu_{w,\pi}\) over weight-and-ranking types \((w,\pi)\), and rational manipulator masses \(\lambda_w\) for each strength class on the same population scale, does there exist \(x_{w,\pi}\geq 0\) with \(\sum_{\pi\in L(C)}x_{w,\pi}=\lambda_w\) for every \(w\), such that \(p\) wins under Nanson's rule? In each round, compute weighted Borda scores on the remaining candidates using contributions \(w(\mu_{w,\pi}+x_{w,\pi})\), then eliminate candidates below the average score.

Let \(C=\{a,b,c,p\}\), with \(m=4\), and let \(L(C)\) denote the strict rankings of \(C\). Strengths \(w\) are positive integers encoded in binary. Inputs are nonnegative binary rational nonmanipulator masses \(\mu_{w,\pi}\) and manipulator masses \(\lambda_w\), on a common population scale, with positive combined mass; masses need not sum to one.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here types are tagged as nonmanipulator \((w,\pi)\) or manipulator \(w\); \(\tau\) is the support size, not the number of possible types. Omitted masses are zero. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\), with \(m=4\) fixed.
A manipulation consists of real masses \(x_{w,\pi}\geq 0\) satisfying \(\sum_{\pi\in L(C)}x_{w,\pi}=\lambda_w\) for every strength class. These assignments are fixed throughout the election.
In each round, restrict every ranking to the surviving candidates and recompute weighted Borda scores, using effective weight \(w(\mu_{w,\pi}+x_{w,\pi})\). Simultaneously eliminate exactly the candidates strictly below the arithmetic mean of the surviving candidates' scores. A sole survivor wins; if all surviving scores are equal, select the first survivor in the fixed order \(p\succ a\succ b\succ c\).

Is deciding whether such a manipulation makes \(p\) win in \(\mathrm{P}\), or is it NP-hard?

For indivisible weighted voters, Nanson coalitional manipulation is NP-complete with four candidates and polynomial-time solvable with at most three. [Verified discrete results](https://archive.illc.uva.nl/COMSOC/IJCAI-2011/papers/narodytska-walsh-xia.pdf).
No result settling this exact divisible-mass problem was located in the literature search.

Theorem

The decision problem is in \(\mathrm{P}\) for \(\mspace{1mu}m=4\). A polynomial-time algorithm tests at most \(26\) rational linear programs, each with \(25\) variables and at most \(40\) constraints. The algorithm handles strict elimination inequalities exactly and uses one fixed manipulation throughout all rounds.

1. Aggregate the effective weights

For each ranking \(\pi\in L(C)\), define the nonmanipulator effective weight
\[ A_\pi=\sum_w w\mu_{w,\pi}. \]
Define the total manipulator effective weight and total effective weight by
\[ B=\sum_w w\lambda_w, \qquad W=\sum_{\pi\in L(C)}A_\pi+B. \]
The hypotheses imply \(W>0\).

Given a legal manipulation, let
\[ y_\pi=\sum_w wx_{w,\pi}. \]
Then
\[ y_\pi\geq 0, \qquad \sum_{\pi\in L(C)}y_\pi=B. \]

Conversely, every vector satisfying these two conditions is induced by a legal manipulation. If \(B>0\), set
\[ x_{w,\pi}=\lambda_w\frac{y_\pi}{B}. \]
Indeed,
\[ \sum_\pi x_{w,\pi}=\lambda_w, \qquad \sum_w wx_{w,\pi} =\frac{y_\pi}{B}\sum_w w\lambda_w =y_\pi. \]
If \(B=0\), positivity of the strengths and nonnegativity of the masses imply that every \(\lambda_w=0\), and the only feasible aggregate vector is \(y=0\).

Thus the exact set of achievable effective profiles is
\[ \left\{(A_\pi+y_\pi)_{\pi\in L(C)}: y_\pi\geq 0,\ \sum_\pi y_\pi=B\right\}. \]
This aggregation respects every strength-class constraint. The resulting full-ranking assignments remain fixed throughout the election.

2. Express each round by linear inequalities

For a nonempty survivor set \(S\subseteq C\), a candidate \(c\in S\), and a ranking \(\pi\), define
\[ b_S(c,\pi) = \left|\{d\in S:\ c\text{ precedes }d\text{ in }\pi\}\right|. \]
This is precisely the Borda score of \(c\) in the restriction of \(\pi\) to \(S\).

Consequently, the weighted score is the affine function
\[ s_S(c;y)=\sum_{\pi\in L(C)} b_S(c,\pi)(A_\pi+y_\pi). \]

Write \(k=|S|\). Every restricted ranking assigns the scores \(0,\ldots,k-1\), so
\[ \sum_{c\in S}s_S(c;y) = W\frac{k(k-1)}2. \]
The arithmetic mean is therefore \(W(k-1)/2\), independently of \(y\).

Define the scaled deviation from the mean by
\[ D_S(c;y)=2s_S(c;y)-(k-1)W. \]
A candidate is eliminated exactly when \(D_S(c;y)<0\); it survives exactly when \(D_S(c;y)\geq 0\).

Also,
\[ \sum_{c\in S}D_S(c;y)=0. \]
Hence, if the scores are not all equal, there is both a negative deviation and a positive deviation: otherwise their zero sum would force every deviation to be zero. Every nonterminal round therefore removes a nonempty proper subset of the survivor set.

3. Enumerate all potentially winning histories

Any election won by \(p\) has a strictly decreasing survivor history
\[ C=S_0\supsetneq S_1\supsetneq\cdots\supsetneq S_r, \qquad p\in S_i, \]
followed by either a sole survivor or an all-equal score tie.

Both terminal cases are expressed by
\[ D_{S_r}(c;y)=0 \qquad(c\in S_r). \]
For a singleton this holds automatically. For a larger set it says that every score equals the arithmetic mean, so the specified tie-breaking order selects \(p\).

There are exactly \(26\) such combinatorial histories. To count them, choose which of the three opponents are eliminated, then partition those opponents into an ordered sequence of nonempty simultaneous-elimination blocks:

• No opponent eliminated: \(1\) history.
• One opponent eliminated: \(3\) histories.
• Two opponents eliminated: \(3(1+2)=9\) histories.
• Three opponents eliminated: \(1+6+6=13\) histories.

The total is \(1+3+9+13=26\). Histories that cannot occur will be rejected by their feasibility conditions.

4. Test a history using a common strictness slack

Fix an enumerated history. Introduce the \(24\) variables \(y_\pi\) and one variable \(\delta\). Maximize \(\delta\) subject to
\[ y_\pi\geq 0,\qquad \sum_\pi y_\pi=B,\qquad 0\leq\delta\leq 1, \]
and, for every transition \(S_i\supsetneq S_{i+1}\),
\[ D_{S_i}(c;y)\leq-\delta \qquad(c\in S_i\setminus S_{i+1}), \]
\[ D_{S_i}(c;y)\geq 0 \qquad(c\in S_{i+1}). \]
Finally impose
\[ D_{S_r}(c;y)=0 \qquad(c\in S_r). \]

Accept this history exactly when the linear program is feasible and its maximum satisfies \(\delta^\ast>0\).

This is an exact treatment of strict inequalities. It does not replace them with weak inequalities or choose a fixed numerical tolerance.

5. Prove equivalence

Every winning manipulation is accepted

Let a legal manipulation make \(p\) win, and form its aggregate vector \(y\). Its actual survivor history appears among the \(26\) histories.

Every eliminated candidate has strictly negative deviation. If the history has any transitions, define
\[ \eta= \min_{\substack{0\leq i<r\\c\in S_i\setminus S_{i+1}}} \bigl(-D_{S_i}(c;y)\bigr). \]
This is the minimum of a finite nonempty collection of positive numbers, hence \(\eta>0\). Choosing \(\delta=\min\{1,\eta\}\) satisfies every elimination inequality.

Every retained candidate has nonnegative deviation, and the actual terminal set satisfies the terminal equalities. Thus the program has a feasible point with \(\delta>0\).

If there are no transitions, the terminal equalities hold already at \(C\), and \(\delta=1\) is feasible.

Every accepted history yields a winning manipulation

Conversely, suppose a history has a feasible solution with \(\delta>0\). Lift \(y\) to a legal manipulation using Section 1.

At each prescribed transition, every candidate designated for elimination has negative deviation, and every candidate designated to survive has nonnegative deviation. Therefore the election eliminates exactly the prescribed set.

Induction over the transitions shows that the actual survivor sets are precisely \(S_0,\ldots,S_r\). At \(S_r\), either \(p\) is the sole survivor, or all scores are equal and the fixed order selects \(p\). Hence the manipulation wins.

These implications prove correctness of the algorithm.

6. Bit complexity and running time

All aggregation uses only the \(\tau\) supported input types. There is no enumeration of possible strength values.

To bound the bit lengths, let \(Q\) be the product of all denominators occurring in the input masses. Its bit length is at most proportional to \(L\). Multiplying a mass by its binary-encoded strength and expressing it over denominator \(Q\) produces a numerator with \(O(L)\) bits. Summing at most \(\tau\) such terms adds at most \(O(\log(\tau+1))\) bits. Consequently, all \(A_\pi\), \(B\), and \(W\) have \(O(L)\)-bit rational representations, since \(\tau\leq L\).

For \(m=4\), each linear program has:

• \(24\) aggregate variables and the slack variable;
• at most \(4+3+2=9\) transition constraints;
• at most \(4\) terminal equalities;
• \(24\) nonnegativity constraints, one mass equality, and two slack bounds.

Thus it has \(25\) variables and at most \(40\) constraints, with total encoding length \(O(L)\).

Each feasible region is closed and bounded, because \(0\leq y_\pi\leq B\) and \(0\leq\delta\leq1\). Therefore a feasible program attains a finite optimum. The standard rational linear-programming theorem gives exact feasibility and optimization in time polynomial in the program’s binary encoding length; equalities and lower-dimensional feasible regions are allowed. See the [MIT notes on polynomial-time linear programming](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).

If \(T_{\mathrm{LP}}(n,q,\ell)\) denotes such a polynomial running-time bound, the running time for the stated \(m=4\) problem is
\[ O\!\left( \tau\,\operatorname{poly}(L) + 26\,T_{\mathrm{LP}}(25,40,O(L)) \right). \]
In particular, it is polynomial in \(\tau\) and \(L\).

For completeness, the same construction for arbitrary \(m\), with \(p\) first in the terminal tie order, uses \(m!+1\) variables and \(m!+O(m^2)\) constraints per history. There are at most \(m^{m-1}\) histories: label each opponent by its elimination round or by zero if it survives. This gives the bound
\[ \tau\,\operatorname{poly}(m!,m,L) + m^{m-1}\operatorname{poly}(m!,m,L). \]
Fixing \(m=4\) makes every dependence on \(m\) constant.

The crucial use of divisibility is Section 1: arbitrary aggregate ranking weights are achievable. Indivisible weighted voters do not have that property.

⟨structured verdict parsed — rendered above⟩

The prover’s output resolves the assigned problem: deciding whether a divisible-mass manipulation makes \(p\) win is in \(\mathrm{P}\) for \(m=4\). The argument is correct and rigorous. I found no major or minor mathematical issues.

• Aggregation preserves exactly the feasible manipulations.

The quantities \(A_\pi\), \(B\), and \(W\) use effective weights, as required by the election rule. Positive strengths, nonnegative masses, and positive combined mass imply \(W>0\).

Every legal manipulation produces nonnegative \(y_\pi\) satisfying \(\sum_\pi y_\pi=B\). Conversely, when \(B>0\), the proposed assignment
\[ x_{w,\pi}=\lambda_w\frac{y_\pi}{B} \]
satisfies both the strength-class mass constraints and the required effective ranking weights. Both identities in Section 1 are correct.

The case \(B=0\) is handled correctly: positive strengths force every manipulator mass to vanish, and nonnegativity forces \(y=0\). Omitted strength classes can receive zero assignments.

This establishes the claimed equivalence without assuming that population masses sum to one. Because the lift specifies full rankings once, it also preserves the requirement that assignments remain fixed throughout the election.

• The round-score and elimination formulas are correct.

The definition of \(b_S(c,\pi)\) counts surviving candidates ranked below \(c\), so it gives precisely the restricted Borda score under the stated convention.

The score formula is affine in the aggregate variables. For any feasible \(y\), total effective weight remains \(W\), and each restricted ranking contributes total Borda score \(k(k-1)/2\). Consequently, the score-sum identity and mean \(W(k-1)/2\) are correct.

The resulting deviation \(D_S(c;y)\) is negative exactly for candidates strictly below the mean. Equality correctly causes survival.

The deviations sum to zero. Therefore, if they are not all zero, at least one is negative and at least one is positive. This justifies the assertion that every nonterminal round removes a nonempty proper subset. It also excludes an unaccounted nonterminal round with no elimination.

• The history enumeration is exhaustive, and the count is correct.

A candidate cannot return after elimination, so every election won by \(p\) has \(p\) in every survivor set. Each nonterminal transition strictly decreases that set.

The terminal conditions cover exactly the stated winning possibilities. For a singleton, the deviation is automatically zero. For a larger terminal set, all deviations being zero is equivalent to all scores being equal. Since \(p\) survives and is first in the fixed order, this tie selects \(p\).

The count of histories correctly treats each simultaneous elimination as a nonempty block:

• Eliminating no opponents gives \(1\) history.
• Eliminating one opponent gives \(3\) histories.
• Eliminating two opponents gives \(3(1+2)=9\) histories.
• Eliminating all three gives \(1+6+6=13\) histories.

Thus there are \(26\) combinatorial histories. This enumeration includes immediate termination, simultaneous eliminations, and termination while opponents remain. It need not assert that every enumerated history is realizable; the feasibility tests address that.

• The common slack handles strict inequalities exactly.

For each transition, the constraints partition the current survivors into precisely the candidates to eliminate and those to retain. With \(\delta>0\), the former have strictly negative deviations and the latter have nonnegative deviations.

The completeness argument correctly takes the minimum over a finite, nonempty collection of positive elimination margins. Hence its \(\eta\) is positive even when the manipulation uses arbitrary real masses. Choosing \(\delta=\min\{1,\eta\}\) satisfies every strict elimination requirement.

The upper bound \(\delta\leq1\) does not exclude any winning history: the construction explicitly supplies a positive admissible slack regardless of the population scale.

The no-transition case is checked separately and correctly. There are no elimination constraints involving \(\delta\), so feasible terminal equalities permit \(\delta=1\).

Conversely, a feasible solution with positive slack forces exactly the prescribed eliminations. Each prescribed transition has an eliminated candidate with negative deviation, so an all-equal terminal event cannot interrupt that transition. The induction and final tie-breaking argument are therefore valid.

• The linear-programming invocation applies, including degenerate cases.

All coefficients, right-hand sides, and objective coefficients are rational. The constraints are non-strict linear inequalities or equalities; strictness is tested through the optimum.

Nonnegativity and \(\sum_\pi y_\pi=B\) imply \(0\leq y_\pi\leq B\). Together with \(0\leq\delta\leq1\), this makes every nonempty feasible region closed and bounded. A feasible program therefore attains its optimum.

Section 6 states the relevant theorem sufficiently precisely: rational linear-programming feasibility and exact optimization are polynomial in binary encoding length, with equalities and lower-dimensional feasible regions permitted. Its hypotheses are satisfied here. The [cited MIT notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial-time LP algorithms, treatment of lower-dimensional feasibility, and recovery of exact optima.

Thus comparing \(\delta^\ast\) with zero is an exact decision operation. The argument does not depend on floating-point tolerances or an assumed positive numerical margin.

• The size and running-time bounds are valid.

The denominator product \(Q\) has bit length bounded by the sum of the input denominator lengths, hence \(O(L)\). Multiplication by an encoded strength and conversion to denominator \(Q\) preserve an \(O(L)\) numerator-length bound. Summation adds at most \(O(\log(\tau+1))\) bits, which remains \(O(L)\). Therefore the aggregate constants have the asserted encoding size.

For \(m=4\), there are \(24\) ranking variables and one slack variable. A history has at most \(9\) transition constraints and at most \(4\) terminal equalities. Including \(24\) nonnegativity constraints, one mass equality, and two slack bounds gives the valid upper bound of \(40\) constraints, counting an equality as one constraint.

The bound remains valid when some constraints are redundant, including singleton terminal equalities and the case \(B=0\).

Aggregation processes only supported input types. It does not enumerate strengths or expand binary strengths into individual voters. Consequently, the stated running time is polynomial in \(\tau\) and \(L\) with \(m=4\) fixed.

The supplementary arbitrary-\(m\) history bound is also valid: there are at most \(m-1\) elimination rounds, and labeling each opponent by its elimination round or zero gives at most \(m^{m-1}\) labels. The stated variable and constraint bounds are consistent with this extension.

The proved content is the full polynomial-time classification requested by USER_TASK. No repair or additional mathematical clarification is needed.

⟨structured verdict parsed — rendered above⟩