d4-conf-aaai-2006-0054 (d4-conf-aaai-2006-0054)

Given candidates \(C\), a target \(p\in C\), rational \(\beta\in[0,1]\), and approval types \(A_i\subseteq C\) with positive rational masses \(\mu_i\) summing to \(1\), is there a mass transfer of total cost at most \(\beta\) that makes \(p\) a winner? Each unit of mass may be bribed at unit cost and assigned any approval ballot.

Given a finite candidate set \(C\) with \(m=|C|\geq 1\), a target \(p\in C\), and a binary rational budget \(\beta\in[0,1]\), consider approval voting with divisible voter mass.
A society is given by its support: the list of \(\tau\) distinct approval types \(A_i\subseteq C\) with positive binary rational masses \(\mu_i\) satisfying \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number \(2^m\) of possible ballots; let \(L\) be the total input bit length.
An action may split each type's mass into arbitrary nonnegative real portions, retain any portion at its original ballot for free, and reassign the remaining portions to any approval ballots \(B\subseteq C\), including ballots absent from the support. Empty and full approval ballots are permitted.
Reassigning mass \(x\) costs \(x\), independently of how many approvals change; total mass is conserved. Approval scores are computed using mass, and all candidates tied for maximum score are winners.

Is deciding whether an action of cost at most \(\beta\) makes \(p\) a winner solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?

For discrete voters, unit-cost replacement of entire approval ballots is NP-complete, while approval manipulation, including its weighted version, is in P ([Faliszewski–Hemaspaandra–Hemaspaandra](https://arxiv.org/pdf/cs/0608081)).
Continuous priced bribery under ranking-based scoring protocols is in P ([Koutecký–Melissinos–Vu–Sabater](https://arxiv.org/html/2608.25444v1)); that result concerns rankings rather than unrestricted approval ballots. No result settling the exact formulation above was identified.

Result

The decision problem is polynomial-time solvable in \(m,\tau,L\). A successful action exists exactly when a rational linear program with at most \(\tau\) variables and \(2\tau+m\) inequalities is feasible.

The argument uses the unrestricted approval ballots and the stated cost per unit of reassigned mass.

1. A canonical form for successful actions

Lemma. If an action makes \(p\) a winner, there is an action of no greater cost making \(p\) a winner in which every reassigned portion receives ballot \(\{p\}\).

Proof. Consider any reassigned portion of mass \(z\) whose destination ballot is \(B\). Changing its destination to \(\{p\}\) changes its contribution to \(p\)’s score from either \(0\) or \(z\) to \(z\). For each rival \(c\ne p\), its contribution changes from either \(0\) or \(z\) to \(0\).

Consequently, this replacement weakly increases \(p\)’s score and weakly decreases every rival’s score. Its cost remains \(z\), because the reassignment cost is independent of the destination ballot.

Perform this replacement for every reassigned portion. If any such portion originally had ballot \(\{p\}\), retain it for free instead. This preserves the resulting scores and weakly decreases the cost. Since every inequality asserting that \(p\)’s score is at least a rival’s score is preserved, \(p\) remains a winner. \(\square\)

Thus it suffices to choose how much mass to take from each original type; no enumeration of destination ballots is necessary.

2. The linear program

For each type \(i\) and candidate \(c\), define the approval indicator

\[ a_{ic}= \begin{cases} 1,&c\in A_i,\\ 0,&c\notin A_i. \end{cases} \]

The original score of \(c\) is \(s_c=\sum_{i=1}^{\tau}\mu_i a_{ic}\).

Let \(I=\{i:A_i\ne\{p\}\}\). For each \(i\in I\), introduce a real variable \(x_i\), representing the mass reassigned from \(A_i\) to \(\{p\}\). Require

\[ 0\le x_i\le\mu_i\qquad(i\in I) \]

and

\[ \sum_{i\in I}x_i\le\beta. \]

After these reassignments, the scores are

\[ s'_p=s_p+\sum_{i\in I}(1-a_{ip})x_i, \]

and, for every \(c\ne p\),

\[ s'_c=s_c-\sum_{i\in I}a_{ic}x_i. \]

Indeed, reassignment adds approval of \(p\) exactly when the source ballot did not approve \(p\), and removes approval of \(c\) exactly when the source ballot approved \(c\).

Subtracting the two score expressions shows that \(s'_p\ge s'_c\) is equivalent to

\[ \sum_{i\in I}(1-a_{ip}+a_{ic})x_i\ge s_c-s_p. \]

Impose this inequality for every \(c\in C\setminus\{p\}\). Each coefficient \(1-a_{ip}+a_{ic}\) belongs to \(\{0,1,2\}\). These non-strict inequalities express precisely the requested winner condition, including ties.

3. Proof of equivalence

From an action to a feasible point. Suppose an action of cost at most \(\beta\) makes \(p\) a winner. Apply the lemma. Let \(x_i\) be the mass reassigned from each type \(i\in I\). Availability gives \(0\le x_i\le\mu_i\), and the action’s cost is \(\sum_{i\in I}x_i\le\beta\). Its winning score inequalities give all the remaining linear constraints by the calculation above.

From a feasible point to an action. Conversely, suppose the linear constraints have a feasible solution. For each \(i\in I\), retain mass \(\mu_i-x_i\) at \(A_i\) and reassign mass \(x_i\) to \(\{p\}\). Retain every original \(\{p\}\) type entirely.

This action is permitted by divisibility. It conserves mass because each original mass \(\mu_i\) is partitioned into portions summing to \(\mu_i\). Its cost is \(\sum_{i\in I}x_i\le\beta\). The calculated score formulas and the final constraints imply \(s'_p\ge s'_c\) for every rival. Hence \(p\) is a winner.

This proves the equivalence in both directions.

4. Encoding size and running time

Write \(n=|I|\le\tau\). The formulation has \(n\) variables, \(2n\) bound inequalities, one budget inequality, and \(m-1\) winner inequalities: altogether \(2n+m\) inequalities.

Its rational data have polynomial encoding length. To verify the only potentially nontrivial point, write \(\mu_i=u_i/v_i\) with positive integer denominators and set \(D=\prod_{i=1}^{\tau}v_i\). The binary length of \(D\) is at most one plus the sum of the denominator bit lengths, hence is \(O(L)\). Each score can be written as \(s_c=N_c/D\), where \(0\le N_c\le D\), since the total mass is \(1\). Thus every difference \(s_c-s_p\) also has an \(O(L)\)-bit rational representation. These quantities can be computed by polynomial-time integer arithmetic.

We now apply the standard rational linear-programming theorem: feasibility over real variables of finitely many non-strict linear inequalities with binary rational coefficients is decidable in time polynomial in the system’s encoding length. This is the polynomial-time linear-programming result of [Khachiyan](https://www.mathnet.ru/eng/dan42319). All its hypotheses hold here, so the resulting algorithm runs in time polynomial in \(m,\tau,L\).

For \(m=1\), there are no winner inequalities, and retaining all mass already succeeds. The same formulation correctly accepts.

⟨structured verdict parsed — rendered above⟩

The proof resolves the exact problem: deciding whether the permitted action can make \(p\) a winner is polynomial-time solvable in \(m,\tau,L\). I found no mathematical gaps or false steps.

1. Canonical-form lemma

The lemma is correct.

For any reassigned portion of mass \(z\), replacing its destination ballot by \(\{p\}\) weakly increases its contribution to \(p\)’s score and weakly decreases its contribution to every rival’s score. Therefore every winning inequality remains satisfied.

The cost argument also holds: changing the destination does not increase the charged mass. If the source ballot was already \(\{p\}\), retaining that portion produces the same final scores for free.

This transformation applies to every permitted action. Although portions may have arbitrary real masses, there are only finitely many source and destination ballot types, so portions with identical source and destination can be aggregated. No assumption about rational action masses is needed.

2. Variables, constraints, and score calculations

The variable domain is correct. For each \(i\in I\), the bounds \(0\le x_i\le\mu_i\) express exactly the available mass. Omitting original \(\{p\}\) types is justified by the lemma.

The budget constraint correctly counts reassigned mass once, independently of the number of approvals changed.

Both score formulas are correct:

• Reassignment increases \(p\)’s score by \(x_i\) precisely when \(a_{ip}=0\).
• Reassignment decreases a rival’s score by \(x_i\) precisely when \(a_{ic}=1\).

Consequently,
\(s'_p-s'_c=s_p-s_c+\sum_{i\in I}(1-a_{ip}+a_{ic})x_i\),
which gives exactly the stated winner constraint. The coefficients belong to \(\{0,1,2\}\), and the non-strict inequalities correctly permit ties.

3. Equivalence with permitted actions

Both directions are established.

A successful action yields a feasible point after canonicalization: the availability bounds, budget constraint, and winner inequalities all follow from the resulting action.

Conversely, a feasible point gives a permitted action by partitioning each source mass into retained and reassigned portions. The construction conserves total mass, respects the budget, and satisfies every required score comparison.

There is no integrality or rationality gap: the task permits arbitrary real portions, and the linear program asks for feasibility over real variables.

4. Encoding size and polynomial running time

The constraint count is correct: \(2n\) bounds, one budget constraint, and \(m-1\) winner constraints total \(2n+m\), where \(n\le\tau\).

The denominator calculation is also correct. For \(D=\prod_i v_i\), its binary length is \(O(L)\). Each score has an integer numerator between \(0\) and \(D\), so each score difference has an \(O(L)\)-bit rational representation, including its sign. Computing these quantities uses polynomial-time integer arithmetic.

There are polynomially many matrix entries, each with polynomial encoding length. Thus the entire explicitly constructed system has polynomial encoding length.

The stated rational linear-programming feasibility theorem is precise and applicable: the system is finite, its coefficients are binary rationals, its variables are real, and every constraint is non-strict. Exact feasibility, including boundary-only feasible sets, is covered by the standard polynomial-time result. The cited [Khachiyan paper](https://www.mathnet.ru/eng/dan42319) establishes polynomial-time linear-inequality feasibility; its integer-coefficient formulation gives the rational version by routine denominator clearing.

5. Edge cases and scope

The formulation handles the relevant boundary cases:

• For \(m=1\), retaining all mass succeeds.
• If \(I\) is empty, all mass already approves exactly \(\{p\}\), and the system accepts.
• For \(\beta=0\), the bounds force every reassigned mass to be zero.
• Empty and full source ballots satisfy the same score formulas.
• The destination \(\{p\}\) is allowed even when absent from the support.

The proof addresses the supplied support representation directly and never enumerates all possible approval ballots.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩