New Approximations for Coalitional Manipulation in Scoring Rules (d4-journals-jair-2019-0002)

Given \(m+1\) candidates, scoring vector \(\alpha\), target \(p\), rational nonmanipulator distribution \(\nu\) of mass \(1-\rho\) over complete rankings, and rational manipulator mass \(\rho\) of one repeated true type with admissible \(p\)-first reports, choose a distribution \(q\) over those reports so that \(\mu^q=\nu+\rho q\) minimizes \(T_\infty(q)=\max_{c\ne p}\operatorname{sc}_{\mu^q}(c)\), equivalently the score margin, or decide whether \(p\) is a co-winner.

Let \(C=\{p,c_1,\ldots,c_m\}\), with \(m\ge1\), and use positional scoring with an input vector \(\alpha_0\ge\cdots\ge\alpha_m\ge0\) of integers satisfying \(\alpha_0\le m^{O(1)}\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
The input consists of a rational nonmanipulator measure \(\nu\) of mass \(1-\rho\), where \(0<\rho\le1\), and manipulator mass \(\rho\) sharing one strict complete true ranking with \(p\) first. Every strict complete ranking with \(p\) first is an admissible report, with no further restriction from the true ranking.
Choose a rational probability distribution \(q\) over admissible reports, represented by its positive support, and set \(\mu^q=\nu+\rho q\). Scores are mass-weighted positional scores.
Define \(T_\infty(q)=\max_{c\ne p}\operatorname{sc}_{\mu^q}(c)\) and \(T^*=\min_qT_\infty(q)\). The score of \(p\) is fixed at \(\operatorname{sc}_\nu(p)+\rho\alpha_0\); equality with a competitor counts as winning.
For a fixed constant \(d\ge2\), put \(\beta=\min\{m-1,\lceil d\sqrt{m\ln m}\rceil\}\) and \(g(\alpha)=\max_{1\le j\le m-\beta}(\alpha_j-\alpha_{j+\beta})\).

Can a randomized algorithm running in time polynomial in \(m,\tau,L\) return \(q\) satisfying \(T_\infty(q)\le T^*+\rho g(\alpha)\) with exponentially small failure probability, or is achieving this additive guarantee NP-hard?

For indivisible unweighted manipulators, a randomized polynomial-time algorithm achieves additive error \(kg(\alpha)\), with exponentially small failure probability ([Keller–Hassidim–Hazon, 2019](https://www.ariel.ac.il/wp/noam-hazon/wp-content/uploads/sites/317/2021/02/19.jair_.new_approx_borda.pdf)).
For divisible votes, co-winner feasibility and minimum total manipulator weight are polynomial-time solvable; these results address different objectives from the fixed-mass competitor-score approximation above ([Xia–Conitzer–Procaccia, 2010](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf)).

Result

The problem is exactly solvable in deterministic polynomial time. An algorithm can return a rational distribution \(q^*\), supported on at most \(m^2\) admissible reports, such that
\(T_\infty(q^*)=T^*\).

Consequently, the requested additive guarantee holds with failure probability zero.

1. Candidate–position marginals

Write \(b_i=\operatorname{sc}_\nu(c_i)\) for each \(i\in\{1,\ldots,m\}\). These rational numbers are computable from the given support in polynomial time.

For a distribution \(q\) over admissible reports, define
\(x_{ij}=\Pr_{R\sim q}[c_i\text{ occupies position }j\text{ among the competitors}]\),
where \(j\in\{1,\ldots,m\}\); that position awards score \(\alpha_j\).

Every report places each competitor in exactly one position and each position contains exactly one competitor. Therefore its marginal matrix \(X=(x_{ij})\) satisfies

\(x_{ij}\ge0,\qquad \sum_{j=1}^m x_{ij}=1\quad\text{for every }i,\qquad \sum_{i=1}^m x_{ij}=1\quad\text{for every }j.\)

Such a matrix is called doubly stochastic. Linearity of mass-weighted scores gives

\(\operatorname{sc}_{\mu^q}(c_i)=b_i+\rho\sum_{j=1}^m\alpha_jx_{ij}.\)

Thus the objective depends only on these marginals.

2. A polynomial-size linear program

Consider the following rational linear program, with variables \(t\) and \(x_{ij}\):

\(\displaystyle \text{minimize }t\)

subject to

\(\displaystyle b_i+\rho\sum_{j=1}^m\alpha_jx_{ij}\le t\qquad(i=1,\ldots,m),\)

\(\displaystyle \sum_{j=1}^m x_{ij}=1\qquad(i=1,\ldots,m),\)

\(\displaystyle \sum_{i=1}^m x_{ij}=1\qquad(j=1,\ldots,m),\)

\(\displaystyle x_{ij}\ge0\qquad(i,j=1,\ldots,m),\qquad 0\le t\le\alpha_0.\)

The bound on \(t\) loses no relevant solution: the total society mass is one, and every positional score lies between zero and \(\alpha_0\), so every candidate’s total score lies in that interval.

The program is feasible. Indeed, take \(x_{ij}=1/m\) and \(t=\alpha_0\). For every competitor,

\(\displaystyle b_i+\frac{\rho}{m}\sum_{j=1}^m\alpha_j \le(1-\rho)\alpha_0+\rho\alpha_0=\alpha_0.\)

The feasible region is closed and bounded, because \(0\le x_{ij}\le1\) and \(0\le t\le\alpha_0\).

We use the standard rational linear-programming theorem: a linear program with binary-encoded rational data can be solved deterministically in time polynomial in its encoding length, returning an exact rational optimum of polynomial bit length whenever an optimum exists. This is the classical polynomial-time solvability of rational linear programming. [Khachiyan, 1979](https://www.mathnet.ru/eng/dan42319)

Here there are \(m^2+1\) variables and polynomially many constraints. All coefficients have polynomial bit length:

• Each \(b_i\) is a sum of at most \(\tau\) input masses multiplied by input scores. Using the product of the input denominators as a common denominator gives a polynomial bit-length bound.
• The remaining coefficients are \(\rho\), the scores, their products, and constants.
• The hypothesis \(\alpha_0\le m^{O(1)}\) ensures polynomial score encoding length.

Therefore an exact rational optimal solution \((X^*,t_{\mathrm{LP}})\) is computable in time polynomial in \(m,\tau,L\).

It remains to construct the required distribution over actual reports.

3. Constructive rational decomposition

We prove that every rational doubly stochastic matrix \(X\) can be decomposed, in polynomial time, into at most \(m^2\) permutation matrices with positive rational coefficients.

Initialize a residual matrix \(R=X\). Its row sums and column sums all equal \(r=1\). While \(r>0\), form a bipartite graph whose left vertices are competitors, whose right vertices are positions, and whose edges are precisely the pairs \((i,j)\) with \(R_{ij}>0\).

For any set \(S\) of left vertices, let \(N(S)\) denote its neighborhood. Since each row sums to \(r\),

\(\displaystyle |S|r=\sum_{i\in S}\sum_{j\in N(S)}R_{ij}.\)

Nonnegativity and the column sums imply

\(\displaystyle \sum_{i\in S}\sum_{j\in N(S)}R_{ij} \le\sum_{j\in N(S)}\sum_{i=1}^mR_{ij}=|N(S)|r.\)

Dividing by \(r>0\) gives \(|S|\le|N(S)|\). Hall’s marriage theorem therefore guarantees a perfect matching, which can be found by a polynomial-time bipartite matching algorithm.

Let \(P\) be its permutation matrix and set

\(\displaystyle \lambda=\min\{R_{ij}:P_{ij}=1\}>0.\)

Record the pair \((\lambda,P)\) and replace \(R\) by \(R-\lambda P\). This preserves nonnegativity, and every row sum and column sum becomes \(r-\lambda\).

At least one positive entry becomes zero in every iteration; no zero entry becomes positive. Hence there are at most \(m^2\) iterations. The process can continue whenever \(r>0\), by the matching argument above, so it terminates with \(r=0\). Nonnegativity then forces \(R=0\). Consequently,

\(\displaystyle X=\sum_{\ell=1}^{s}\lambda_\ell P_\ell,\qquad \lambda_\ell>0,\qquad \sum_{\ell=1}^{s}\lambda_\ell=1,\qquad s\le m^2.\)

Each \(P_\ell\) specifies an admissible report: put \(p\) first and assign each competitor to its matched position. Assign probability \(\lambda_\ell\) to that report. The resulting distribution has marginal matrix exactly \(X\).

Bit complexity. Let \(D\) be the product of the denominators of the entries of \(X\). Its bit length is at most the sum of their denominator bit lengths. Throughout the algorithm, every residual entry and every \(\lambda_\ell\) is an integer multiple of \(1/D\) lying between zero and one. Thus their numerators and denominators have polynomial bit length. Together with the polynomial number of matching computations, this proves polynomial running time and polynomial output length.

4. Equality with the target optimum

For every rational admissible distribution \(q\), its marginal matrix makes the linear program feasible with \(t=T_\infty(q)\). Therefore

\(\displaystyle t_{\mathrm{LP}}\le T_\infty(q).\)

Conversely, apply the decomposition above to the rational optimal matrix \(X^*\). It returns an admissible rational distribution \(q^*\) whose competitor scores satisfy

\(\displaystyle T_\infty(q^*) =\max_{1\le i\le m}\left(b_i+\rho\sum_{j=1}^m\alpha_jx^*_{ij}\right) \le t_{\mathrm{LP}}.\)

Applying the first inequality to \(q^*\) proves equality. Since the first inequality holds for every admissible \(q\), the distribution \(q^*\) attains the minimum, and

\(\displaystyle T_\infty(q^*)=t_{\mathrm{LP}}=T^*.\)

Finally, \(0\le\beta\le m-1\), so the maximum defining \(g(\alpha)\) is nonempty. Monotonicity of the scoring vector gives \(\alpha_j-\alpha_{j+\beta}\ge0\), hence \(g(\alpha)\ge0\). Thus

\(\displaystyle T_\infty(q^*)=T^*\le T^*+\rho g(\alpha).\)

This also covers \(m=1\), when \(\beta=0\) and \(g(\alpha)=0\). The deterministic algorithm is a randomized algorithm that ignores its random bits, with failure probability zero. The decisive hypotheses are divisibility and the admissibility of every report placing \(p\) first: they allow every rational doubly stochastic marginal matrix to be realized.

⟨structured verdict parsed — rendered above⟩

Verdict

The output proves the target exactly. The marginal formulation, rational linear program, and constructive decomposition establish a deterministic algorithm running in time polynomial in \(m,\tau,L\). Its output attains \(T^*\), so the requested additive guarantee holds with failure probability zero.

No major or minor mathematical issues were found.

Step-by-step verification

1. Candidate–position marginals

The indexing is consistent: since \(p\) occupies the first overall position and receives \(\alpha_0\), competitor position \(j\) receives \(\alpha_j\).

For every admissible report, each competitor occupies exactly one competitor position, and each such position contains exactly one competitor. Taking expectations therefore gives precisely the stated nonnegativity, row-sum, and column-sum constraints.

The score identity
\[ \operatorname{sc}_{\mu^q}(c_i) =b_i+\rho\sum_{j=1}^{m}\alpha_jx_{ij} \]
correctly follows from linearity of mass-weighted scoring. No independence assumption is needed.

At this stage, the matrix constraints provide a necessary condition for realizability. Section 3 supplies the converse, so the proof does not leave that requirement unverified.

2. Linear-program formulation and complexity

The competitor inequalities correctly express an upper bound on every competitor’s score. Minimizing \(t\) therefore expresses the intended maximum-score objective, subject to the subsequent realizability argument.

The restriction \(0\le t\le\alpha_0\) preserves the target optimum. All masses and scores are nonnegative, total society mass is one, and every positional score is at most \(\alpha_0\).

The proposed feasible point is valid:
\[ b_i+\frac{\rho}{m}\sum_{j=1}^{m}\alpha_j \le (1-\rho)\alpha_0+\rho\alpha_0 =\alpha_0. \]
The row-sum constraints and nonnegativity imply \(x_{ij}\le1\), so the feasible region is indeed closed and bounded.

The invoked rational linear-programming theorem is correctly stated for this application: binary rational data admit deterministic polynomial-time optimization with an exact rational optimal solution of polynomial encoding length. The cited reference is [Khachiyan’s polynomial-time linear-programming paper](https://www.mathnet.ru/eng/dan42319). Here the hypotheses are satisfied: the program has rational coefficients, polynomial size, and a nonempty bounded feasible region.

The coefficient-size argument is sound. Summing the input rational masses using a product of their denominators yields polynomial bit length, because the sum of their encoded denominator lengths is bounded by the input length. Multiplication by the input scores preserves a polynomial bound. The same reasoning applies to \(\rho\), whether supplied explicitly or recovered from the mass of \(\nu\).

Thus the claimed exact LP computation has the required polynomial running time.

3. Constructive decomposition

The residual invariant is correct: all row sums and column sums equal the same nonnegative value \(r\).

For \(r>0\), the neighborhood calculation establishes
\[ |S|\le |N(S)| \]
for every subset \(S\) of the left vertices. These are exactly the hypotheses of Hall’s marriage theorem for a matching covering the left side. Since both sides have \(m\) vertices, such a matching is perfect. The application is therefore justified.

Every matched entry is positive, so the selected \(\lambda\) is positive. Subtracting \(\lambda P\):

• preserves entrywise nonnegativity;
• reduces every row sum and column sum by \(\lambda\);
• eliminates at least one positive entry;
• never creates a new positive entry.

Consequently, at most \(m^2\) iterations occur. The matching argument remains applicable whenever \(r>0\), so the process cannot stop prematurely. At termination, zero row sums and nonnegativity force the residual matrix to be zero.

The recorded coefficients sum to one because the common row sum starts at one and ends at zero. Each permutation specifies an admissible report under the task’s unrestricted admissibility condition.

The bit-complexity argument also checks out. A common denominator \(D\) for the initial matrix remains a common denominator throughout subtraction. Residual entries and recorded coefficients stay between zero and one, so their numerators require at most polynomially many bits. Polynomially many matching computations and rational arithmetic operations therefore produce a polynomial-length output in polynomial time.

4. Equality with the target optimum

For every admissible rational distribution, its marginal matrix gives an LP-feasible point with \(t=T_\infty(q)\). Hence
\[ t_{\mathrm{LP}}\le T_\infty(q). \]

Conversely, decomposition of the exact rational optimal matrix produces an admissible rational distribution satisfying
\[ T_\infty(q^*)\le t_{\mathrm{LP}}. \]

Applying the first inequality to this same distribution establishes equality. This also proves that the minimum over rational distributions is attained; the proof does not assume attainment without justification.

5. Additive guarantee and edge cases

The range defining \(g(\alpha)\) is nonempty because \(0\le\beta\le m-1\). Monotonicity gives \(g(\alpha)\ge0\), so exact optimality implies the requested additive bound.

The stated treatment of \(m=1\) is correct: \(\beta=0\) and \(g(\alpha)=0\). The argument also accommodates \(\rho=1\), zero scores, and repeated scoring-vector entries without requiring strict inequalities.

A deterministic algorithm qualifies as a randomized algorithm that ignores its random bits. Zero failure probability satisfies the requested exponentially small failure bound.

Required feedback

None. The write-up resolves the assigned objective and requires no mathematical repair.

⟨structured verdict parsed — rendered above⟩