d4-conf-aaai-2008-0253 (d4-conf-aaai-2008-0253)

Given \(m\) candidates, a rational distribution \(\mu\) over supported types \(t=(v_t,g_t)\), where \(v_t\) is a complete ranking and \(g_t\) is its bribery price, a target \(p\), and a per-capita budget \(b\), choose transfers \(x_{t,r}\geq 0\) from source type \(t\) to ranking \(r\), subject to \(\sum_r x_{t,r}\leq\mu_t\) and \(\sum_{t,r}g_t x_{t,r}\leq b\). What is the maximum increase in \(p\)'s per-capita Borda performance, \(\mathrm{perf}_{\mu'}(p)-\mathrm{perf}_{\mu}(p)\), over the resulting societies \(\mu'\)?

Let \(C\) contain \(m\geq2\) candidates, with preferred candidate \(p\in C\), and let \(\mathcal R\) be all strict complete rankings of \(C\).
A society is given by its support: the list of \(\tau\) types \(t=(v_t,g_t)\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\), \(v_t\in\mathcal R\), and \(g_t\) is a nonnegative integer price encoded in binary. Here \(\tau\) is the support size, not the number of possible types or rankings.
Given a binary rational per-capita budget \(b\geq0\), a feasible action transfers divisible mass \(x_{t,r}\geq0\) to arbitrary rankings \(r\neq v_t\), with \(\sum_{r\neq v_t}x_{t,r}\leq\mu_t\) and \(\sum_{t,r\neq v_t}g_tx_{t,r}\leq b\); untransferred mass keeps its ranking.
The resulting ranking distribution is \(\mu'_r=\sum_{t:v_t=r}(\mu_t-\sum_{s\neq v_t}x_{t,s})+\sum_{t:v_t\neq r}x_{t,r}\). No mass is added or deleted.
For any ranking distribution \(\nu\), let \(\operatorname{score}_\nu(c)\) be its expected Borda score and define \(\operatorname{perf}_\nu(p)=\operatorname{score}_\nu(p)-\max_{c\neq p}\operatorname{score}_\nu(c)\). Ties are permitted.
Write \(\beta(x)=\operatorname{perf}_{\mu'}(p)-\operatorname{perf}_\mu(p)\) and \(\operatorname{OPT}=\max_{x\text{ feasible}}\beta(x)\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\) and any approximation parameters.

Does there exist a fixed polynomial \(q\) and an algorithm running in \(\operatorname{poly}(m,\tau,L)\) time that returns a feasible action \(x\) satisfying \(q(\beta(x))\geq\operatorname{OPT}\) on every instance, or is every such guarantee impossible unless \(\mathrm P=\mathrm{NP}\)?

For discrete unweighted priced Borda bribery with total-score performance gain, every fixed polynomial guarantee of this form is impossible unless \(\mathrm P=\mathrm{NP}\). [Brelsford et al.](https://cdn.aaai.org/AAAI/2008/AAAI08-007.pdf)
Continuous priced bribery under scoring rules has a polynomial-time algorithm for minimizing the cost of making a candidate a co-winner; that is a different objective from the gain approximation asked here. [Koutecký et al.](https://arxiv.org/html/2608.25444v1)

1. Result

The problem is exactly solvable in \(\operatorname{poly}(m,\tau,L)\) time. Consequently, the fixed polynomial \(\boxed{q(z)=z}\) satisfies the requested guarantee.

We prove this by constructing a polynomial-size linear program and recovering an explicit feasible action from its optimal solution. Divisibility of mass is essential to the recovery.

2. A compact linear program

Let \(a_{t,c}=m-\operatorname{rank}_{v_t}(c)\) be candidate \(c\)’s Borda score in type \(t\)’s original ranking. Write \(J=\{1,\ldots,m\}\) for the positions.

Introduce these variables:

• \(y_t\): mass of type \(t\) designated for reassignment.
• \(z_{t,c,j}\): designated mass of type \(t\) that places candidate \(c\) in position \(j\).
• \(h\): a lower bound on the resulting performance of \(p\).

For now, designated mass may reproduce its original ranking. We will remove such assignments during reconstruction.

Impose the constraints

\(\displaystyle 0\leq y_t\leq\mu_t \qquad\text{for every }t,\)

\(\displaystyle z_{t,c,j}\geq0 \qquad\text{for every }t,c,j,\)

\(\displaystyle \sum_{j\in J}z_{t,c,j}=y_t \qquad\text{for every }t,c,\)

\(\displaystyle \sum_{c\in C}z_{t,c,j}=y_t \qquad\text{for every }t,j,\)

\(\displaystyle \sum_t g_ty_t\leq b.\)

Thus each candidate appears once, and each position is occupied once, per unit of designated mass.

Define the following affine expression for candidate \(c\)’s resulting score:

\(\displaystyle S_c(y,z)=\sum_t(\mu_t-y_t)a_{t,c}+\sum_t\sum_{j\in J}(m-j)z_{t,c,j}.\)

The linear program maximizes \(h\), subject to the preceding constraints and

\(\displaystyle h\leq S_p(y,z)-S_c(y,z)\qquad\text{for every }c\neq p,\)

\(\displaystyle -(m-1)\leq h\leq m-1.\)

The last bounds are valid because every expected Borda score lies between \(0\) and \(m-1\).

This LP is nonempty: take \(y=z=0\) and \(h=\operatorname{perf}_{\mu}(p)\). It is bounded: every \(y_t\) and \(z_{t,c,j}\) lies between \(0\) and \(\mu_t\), and \(h\) has explicit bounds. Its feasible set is closed, so its optimum is attained. Denote its optimal objective value by \(H\).

We next prove that \(H\) is exactly the maximum achievable performance.

3. Every feasible action gives a feasible LP solution

Fix a feasible action \(x\). Define

\(\displaystyle y_t=\sum_{r\neq v_t}x_{t,r},\qquad z_{t,c,j}=\sum_{r\neq v_t}x_{t,r}\,\mathbf{1}\{\operatorname{rank}_r(c)=j\}.\)

Every strict complete ranking places each candidate in exactly one position and fills every position with exactly one candidate. Therefore, both families of marginal equalities hold.

The bounds on \(y_t\) and the budget constraint follow directly from feasibility of \(x\). Moreover,

\(\displaystyle S_c(y,z)=\sum_t(\mu_t-y_t)a_{t,c}+\sum_t\sum_{r\neq v_t}x_{t,r}\bigl(m-\operatorname{rank}_r(c)\bigr)=\operatorname{score}_{\mu'}(c).\)

Consequently, setting \(h=\operatorname{perf}_{\mu'}(p)\) satisfies every performance constraint and the bounds on \(h\). Hence

\(\displaystyle H\geq\max_{x\text{ feasible}}\operatorname{perf}_{\mu'}(p).\)

4. Every feasible LP solution yields an actual action

We first prove the decomposition needed for reconstruction.

Decomposition lemma. Suppose \(Z=(Z_{c,j})_{c\in C,j\in J}\) is nonnegative and every row sum and column sum equals \(y\geq0\). Then there are at most \(m^2\) rankings \(r_1,\ldots,r_k\) and positive weights \(\lambda_1,\ldots,\lambda_k\) such that

\(\displaystyle Z_{c,j}=\sum_{\ell=1}^k\lambda_\ell\,\mathbf{1}\{\operatorname{rank}_{r_\ell}(c)=j\},\qquad \sum_{\ell=1}^k\lambda_\ell=y.\)

For rational \(Z\), this decomposition is computable in polynomial time.

Proof. If \(y=0\), nonnegativity implies \(Z=0\), and the empty decomposition suffices.

Otherwise, construct a bipartite graph with candidates on one side and positions on the other, with edge \(cj\) exactly when \(Z_{c,j}>0\). For any candidate subset \(A\), let \(N(A)\) be its neighboring positions. Then

\(\displaystyle |A|y=\sum_{c\in A}\sum_{j\in N(A)}Z_{c,j}\leq\sum_{c\in C}\sum_{j\in N(A)}Z_{c,j}=|N(A)|y.\)

Since \(y>0\), this proves \(|A|\leq|N(A)|\). Hall’s matching theorem states that these inequalities for every \(A\) guarantee a matching covering all candidates. Both sides have size \(m\), so this matching is perfect.

The matching defines a ranking \(r\). Let \(\lambda\) be the smallest entry of \(Z\) on its matching edges, and subtract \(\lambda\) from each matching entry. The residual is nonnegative, and every row and column sum becomes \(y-\lambda\).

If the residual is nonzero, repeat the same argument with its new common row and column sum. Each iteration removes at least one positive entry and never creates a positive entry. Thus there are at most \(m^2\) iterations. At termination the residual is zero, giving the stated decomposition. Comparing any row sum before and after decomposition gives \(\sum_\ell\lambda_\ell=y\).

Each iteration uses a bipartite matching computation and rational subtraction, so it is constructive. The bit-complexity justification is given below. \(\square\)

Now fix a feasible LP solution \((y,z,h)\). Apply the lemma to each matrix \(Z_t=(z_{t,c,j})\). After combining repeated rankings, write its decomposition weights as \(\lambda_{t,r}\), with omitted weights understood to be zero. They satisfy

\(\displaystyle \sum_r\lambda_{t,r}=y_t.\)

Define the actual action by

\(\displaystyle x_{t,r}=\lambda_{t,r}\qquad\text{for }r\neq v_t.\)

The weight \(\lambda_{t,v_t}\) is left untransferred. Consequently,

\(\displaystyle \sum_{r\neq v_t}x_{t,r}=y_t-\lambda_{t,v_t}\leq\mu_t.\)

Because every price is nonnegative,

\(\displaystyle \sum_t\sum_{r\neq v_t}g_tx_{t,r}=\sum_tg_t(y_t-\lambda_{t,v_t})\leq\sum_tg_ty_t\leq b.\)

Thus the action is feasible, including when some prices or the budget are zero.

It also realizes the LP scores exactly. Type \(t\)’s untransferred mass is \(\mu_t-y_t+\lambda_{t,v_t}\). Its contribution to candidate \(c\)’s score is therefore

\(\displaystyle (\mu_t-y_t+\lambda_{t,v_t})a_{t,c}+\sum_{r\neq v_t}\lambda_{t,r}\bigl(m-\operatorname{rank}_r(c)\bigr)\)

\(\displaystyle =(\mu_t-y_t)a_{t,c}+\sum_r\lambda_{t,r}\bigl(m-\operatorname{rank}_r(c)\bigr)\)

\(\displaystyle =(\mu_t-y_t)a_{t,c}+\sum_{j\in J}(m-j)z_{t,c,j}.\)

Summing over types gives \(\operatorname{score}_{\mu'}(c)=S_c(y,z)\). Hence the reconstructed action satisfies

\(\displaystyle \operatorname{perf}_{\mu'}(p)=\min_{c\neq p}\bigl(S_p(y,z)-S_c(y,z)\bigr)\geq h.\)

Applying reconstruction to an optimal LP solution yields performance at least \(H\). Section 3 shows that every feasible action has performance at most \(H\). Therefore the reconstructed action \(x^*\) satisfies

\(\displaystyle \operatorname{perf}_{\mu'_{x^*}}(p)=H=\max_{x\text{ feasible}}\operatorname{perf}_{\mu'}(p).\)

Subtracting the fixed initial performance proves

\(\displaystyle \beta(x^*)=H-\operatorname{perf}_{\mu}(p)=\operatorname{OPT}.\)

5. Running time and output encoding

The LP has \(\tau m^2+\tau+1\) variables and \(O(\tau m^2)\) constraints, counting nonnegativity constraints. All coefficients and right-hand sides have encoding length polynomial in \(m,\tau,L\): Borda coefficients are integers of magnitude at most \(m-1\), and all remaining numerical data come from the input or rational sums of input data.

The standard polynomial-time theorem for rational linear programming computes an exact optimal rational solution of polynomial encoding length for an explicitly given, nonempty, bounded rational LP. All these hypotheses were verified above. Thus the LP can be constructed and solved in \(\operatorname{poly}(m,\tau,L)\) bit operations.

Reconstruction uses at most \(\tau m^2\) perfect-matching computations. An augmenting-path algorithm finds each matching in \(O(m^3)\) combinatorial operations, giving \(O(\tau m^5)\) such operations overall.

Rational arithmetic during reconstruction also has polynomial bit complexity. For each type, take the product \(D_t\) of the denominators of its initial LP matrix entries. Its bit length is at most the sum of those denominator lengths, hence polynomial. Every residual entry and every extracted weight remains an integer multiple of \(D_t^{-1}\), between \(0\) and \(1\). Their numerator and denominator lengths therefore remain polynomial throughout reconstruction.

The algorithm outputs at most \(\tau m^2\) nonzero transfers, each with an explicit ranking and rational mass; all omitted transfers are zero. This is a polynomial-size representation of the requested action. No approximation parameter is needed.

6. Relation to the cited results

The discrete inapproximability theorem concerns indivisible voters. The reconstruction above uses arbitrary fractional weights in mixtures of rankings, which are permitted by this task’s hypotheses. Thus the discrete theorem supplies no obstruction to this algorithm. See [Brelsford et al., Theorem 9](https://cdn.aaai.org/AAAI/2008/AAAI08-007.pdf).

The cited continuous result establishes polynomial-time minimum-cost winner-making for scoring protocols. Here the compact LP directly optimizes the margin against the strongest opponent at a fixed budget, settling the stated gain objective. See [Koutecký et al., Theorem 4](https://arxiv.org/html/2608.25444v1).

Finally, with \(q(z)=z\), the returned action satisfies \(\boxed{q(\beta(x^*))=\operatorname{OPT}}\) on every instance.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the task: it gives an exact polynomial-time algorithm and a polynomial-size feasible action. No major or minor mathematical issues were found.

• The compact LP has the correct variables and constraints.

For each type \(t\), the row and column equalities require the nonnegative matrix \(Z_t=(z_{t,c,j})\) to have common marginal mass \(y_t\). The constraint \(0\leq y_t\leq\mu_t\) leaves nonnegative untransferred mass, and \(\sum_t g_ty_t\leq b\) bounds the cost of designated mass.

Temporarily allowing designated mass to reproduce its original ranking is justified by the reconstruction: that mass is ultimately left untransferred, preserving scores and weakly decreasing cost. This uses exactly the stated hypothesis \(g_t\geq0\).

• The score expression and objective encode the intended performance.

The expression
\[ S_c(y,z)=\sum_t(\mu_t-y_t)a_{t,c} +\sum_t\sum_j(m-j)z_{t,c,j} \]
correctly combines original scores of untransferred mass with position scores of designated mass.

Because \(m\geq2\), the opponent set is nonempty, and
\[ \operatorname{perf}_{\mu'}(p) =\min_{c\neq p}\bigl(\operatorname{score}_{\mu'}(p) -\operatorname{score}_{\mu'}(c)\bigr). \]
Thus maximizing \(h\) under all opponent inequalities represents the desired maximum margin.

The bounds on \(h\) are valid: each expected score belongs to \([0,m-1]\), so performance belongs to \([-(m-1),m-1]\). Reconstruction subsequently verifies that every feasible LP score vector is realizable, so these bounds exclude no achievable optimum.

• Feasibility, boundedness, and attainment are established.

Taking \(y=z=0\) and \(h=\operatorname{perf}_{\mu}(p)\) satisfies every constraint, including when \(b=0\).

Nonnegativity and each row-sum equality imply \(z_{t,c,j}\leq y_t\leq\mu_t\). Together with the explicit bounds on \(h\), this makes the feasible set bounded. It is closed because all constraints are non-strict linear inequalities or equalities. Consequently, the nonempty feasible set is compact and the LP optimum is attained.

• The action-to-LP direction is exact.

The definitions of \(y_t\) and \(z_{t,c,j}\) from an action satisfy both marginal equalities because every destination ranking contains each candidate and each position exactly once.

The mass and budget inequalities follow directly from action feasibility. Expanding the position sums gives precisely the resulting expected scores, so choosing \(h=\operatorname{perf}_{\mu'}(p)\) is valid. Therefore every feasible action has performance at most \(H\).

• The decomposition lemma is fully justified.

The case \(y=0\) is correctly handled by nonnegativity.

For \(y>0\), the displayed calculation establishes Hall’s condition for every candidate subset. The theorem is stated in the form needed, and its hypotheses hold: the graph is finite and bipartite, with equally sized candidate and position sets. A matching covering all candidates is therefore perfect.

Every selected matching entry is positive. Subtracting their minimum \(\lambda\) preserves nonnegativity and reduces every row and column sum by \(\lambda\). If the residual is nonzero, its common sum is positive, permitting another application of the same argument.

Each iteration eliminates at least one positive entry and creates none. Hence there are at most \(m^2\) iterations. The final zero residual establishes the matrix decomposition, and comparison of row sums establishes \(\sum_\ell\lambda_\ell=y\).

• Reconstruction produces an admissible action with exactly the LP scores.

Removing the component assigned to \(v_t\) gives transferred mass \(y_t-\lambda_{t,v_t}\), which is nonnegative and at most \(\mu_t\). Its cost is at most the designated cost because prices are nonnegative.

The score calculation correctly includes the removed component in untransferred mass. The three displayed expressions are equal, establishing \(\operatorname{score}_{\mu'}(c)=S_c(y,z)\) for every candidate.

Consequently, reconstruction from an optimal LP solution gives performance at least \(H\). The action-to-LP direction gives the reverse bound. Together they prove exact optimality, rather than merely feasibility or winner-making.

• The bit complexity and output size are polynomial.

The stated variable count \(\tau m^2+\tau+1\) and constraint count \(O(\tau m^2)\) are correct. The affine score coefficients and constants have polynomial encoding length: they involve bounded Borda integers, input prices, and rational sums of input masses.

The invoked rational linear-programming theorem is stated with sufficient precision, and the explicitly represented LP satisfies its rationality, nonemptiness, and boundedness hypotheses. It therefore permits an exact optimal rational solution of polynomial encoding length.

The reconstruction bound of at most \(\tau m^2\) matching computations is correct. An \(O(m^3)\) augmenting-path implementation gives the claimed \(O(\tau m^5)\) combinatorial bound.

The common-denominator argument also checks out. Residual entries and extracted weights remain multiples of \(D_t^{-1}\), and they remain between zero and one because \(\mu_t\leq1\). Thus their encoding lengths remain polynomial. Explicitly listing at most \(\tau m^2\) transfers, each with a ranking and rational mass, is a valid polynomial-size action representation.

• The conclusion and contextual citations are consistent.

Subtracting the fixed initial performance preserves the optimizer, giving \(\beta(x^*)=\operatorname{OPT}\). Hence the fixed polynomial \(q(z)=z\) satisfies the requested guarantee on every instance. Zero budget, zero prices, ties, zero designated mass, and \(m=2\) are all covered.

The contextual descriptions match the cited statements: [Brelsford et al., Theorem 9](https://cdn.aaai.org/AAAI/2008/AAAI08-007.pdf) concerns the discrete priced-bribery gain guarantee, while [Koutecký et al., Theorem 4](https://arxiv.org/html/2608.25444v1) establishes polynomial-time continuous minimum-cost winner-making for scoring protocols. Neither citation supplies a missing step in this proof; the gain optimization is established by the LP and reconstruction themselves.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩