Answer: Exactly solvable in deterministic polynomial time, returning an allocation with \(T(x)=T^*\) and zero failure probability.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a randomized Monte Carlo al- gorithm for Borda-UCM which provides an O(k√m log m)- additive approximation to T ∗with an exponentially-small failure probability. In other words, if there exists a strategy enabling p to win by a margin of Ω(k√m log m) compared to the score of the highest-scoring non-preferred candidate, our method will find a strategy enabling p to win (albeit with a possibly smaller margin).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C=\{p,c_1,\ldots,c_m\}\), rational nonmanipulator masses \(\mu_\pi\) on \(\tau\) rankings summing to \(1-\alpha\), and a coordinated bloc of mass \(\alpha\), compute the minimum possible maximum final Borda score among candidates \(c\ne p\). Each unit of bloc mass must report a complete ranking with \(p\) first. Also determine whether the minimum is at most \(b_p+m\alpha\), where \(b_p\) is the nonmanipulators’ Borda score mass for \(p\).
Let \(C=\{p,c_1,\ldots,c_m\}\), with \(m\geq1\), use Borda, and count ties as wins for \(p\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each a binary rational; \(\tau\) is the support size, not the number of possible rankings.
Here the types are strict complete rankings, the nonmanipulator masses satisfy \(\sum_\pi\mu_\pi=1-\alpha\), and the coordinated bloc has binary rational mass \(0<\alpha\leq1\); the total electorate has mass one. Let \(L\) be the total input bit length.
Write \(B_\pi(c)\) for the Borda score and \(b_c=\sum_\pi\mu_\pi B_\pi(c)\).
A bloc allocation assigns nonnegative masses \(x_\rho\) summing to \(\alpha\) to strict complete rankings \(\rho\) with \(p\) first; its mass may be split arbitrarily among such rankings.
Define \(T(x)=\max_{1\leq i\leq m}(b_{c_i}+\sum_\rho x_\rho B_\rho(c_i))\) and \(T^*=\min_x T(x)\). A winning allocation exists exactly when \(T^*\leq b_p+m\alpha\).
Does this problem admit a randomized algorithm, polynomial in \(m,\tau,L\), returning a bloc allocation with \(T(x)\leq T^*+O(\alpha\sqrt{m\log(m+1)})\) and failure probability \(\exp(-\Omega(m))\), or is achieving this additive guarantee NP-hard?
For discrete unweighted blocs of \(k\) voters, a polynomial-time randomized algorithm achieves additive error \(O(k\sqrt{m\log m})\) with exponentially small failure probability ([source](https://www.ariel.ac.il/wp/noam-hazon/wp-content/uploads/sites/317/2021/02/17.aamas_.new_approx_borda.pdf)).
For divisible votes, exact co-winner feasibility and minimum required coalition weight are polynomial-time solvable for positional scoring rules; these use different objectives from the fixed-mass maximum rival score ([source](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf)).
The problem is exactly solvable in deterministic polynomial time. Consequently, the requested additive guarantee holds with zero error and zero failure probability.
The proof directly optimizes the fixed-mass maximum rival score. It also constructs an optimal allocation supported on at most \(m^2\) strict rankings.
With \(p\) first, every bloc ranking assigns the scores \(0,1,\ldots,m-1\) bijectively to the rivals.
For \(1\leq i\leq m\) and \(0\leq j\leq m-1\), introduce a variable \(y_{ij}\), representing the bloc mass that assigns score \(j\) to candidate \(c_i\). Consider the linear program
\( \displaystyle \begin{aligned} \text{minimize}\quad &t\\ \text{subject to}\quad &y_{ij}\geq0 && (1\leq i\leq m,\ 0\leq j\leq m-1),\\ &\sum_{j=0}^{m-1}y_{ij}=\alpha && (1\leq i\leq m),\\ &\sum_{i=1}^{m}y_{ij}=\alpha && (0\leq j\leq m-1),\\ &b_{c_i}+\sum_{j=0}^{m-1}j\,y_{ij}\leq t && (1\leq i\leq m),\\ &0\leq t\leq m. \end{aligned} \)
The bounds on \(t\) do not restrict the original optimization. Indeed, nonnegativity of Borda scores gives \(T(x)\geq0\), while
\( \displaystyle b_{c_i}+\sum_\rho x_\rho B_\rho(c_i) \leq m(1-\alpha)+(m-1)\alpha =m-\alpha\leq m. \)
The linear program is nonempty: set \(y_{ij}=\alpha/m\) and \(t=m\). It is bounded because every \(y_{ij}\) lies in \([0,\alpha]\), and \(t\) lies in \([0,m]\). Thus it attains its minimum.
Every bloc allocation induces a feasible matrix by setting
\( \displaystyle y_{ij}=\sum_{\rho:\,B_\rho(c_i)=j}x_\rho. \)
Each candidate receives exactly one score in each ranking, giving the row equations. Each score is assigned to exactly one rival in each ranking, giving the column equations. Moreover,
\( \displaystyle \sum_{j=0}^{m-1}j\,y_{ij} =\sum_\rho x_\rho B_\rho(c_i). \)
Hence \(t=T(x)\) makes this matrix a feasible linear-program solution.
The essential converse is proved next.
Lemma. Let \(Y\) be a nonnegative \(m\)-by-\(m\) matrix whose row and column sums all equal \(\alpha>0\). In polynomial time, one can construct positive rational masses \(\delta_1,\ldots,\delta_q\) and permutation matrices \(P_1,\ldots,P_q\) satisfying
\( \displaystyle Y=\sum_{\ell=1}^{q}\delta_\ell P_\ell, \qquad \sum_{\ell=1}^{q}\delta_\ell=\alpha, \qquad q\leq m^2, \)
provided the entries of \(Y\) are rational.
Proof. Maintain a nonnegative residual matrix \(R\) whose row and column sums have a common value \(r\). Initially \(R=Y\) and \(r=\alpha\).
If \(r=0\), nonnegativity and the row equations imply \(R=0\), so the procedure terminates.
Suppose \(r>0\). Form a bipartite graph with candidates on one side and score positions on the other, placing an edge \((i,j)\) precisely when \(R_{ij}>0\). For a set \(S\) of candidate vertices, let \(N(S)\) be its neighboring score vertices. Then
\( \displaystyle r|S| =\sum_{i\in S}\sum_jR_{ij} =\sum_{j\in N(S)}\sum_{i\in S}R_{ij} \leq\sum_{j\in N(S)}\sum_iR_{ij} =r|N(S)|. \)
Dividing by \(r>0\) gives Hall’s condition. Hall’s marriage theorem therefore supplies a perfect matching. Such a matching can be found in polynomial time.
Let \(P\) be its permutation matrix and define
\( \displaystyle \delta=\min\{R_{ij}:P_{ij}=1\}>0. \)
Record the pair \((\delta,P)\), and replace \(R\) by \(R-\delta P\). All entries remain nonnegative, and every row and column sum becomes \(r-\delta\). At least one positive entry becomes zero, and no zero entry becomes positive.
There are at most \(m^2\) initially positive entries, so there are at most \(m^2\) iterations. At termination the residual is zero. Summing the updates gives the claimed matrix decomposition; summing the decreases in the common row sum gives \(\sum_\ell\delta_\ell=\alpha\). The arithmetic bit complexity is addressed below. \(\square\)
For each permutation matrix \(P_\ell\), construct a strict ranking \(\rho_\ell\): put \(p\) first, followed by the rivals in decreasing order of their assigned scores. This is well-defined because the matching assigns every score exactly once.
Give \(\rho_\ell\) mass \(\delta_\ell\), adding masses if the same ranking occurs more than once. The resulting allocation has total mass \(\alpha\), and for each rival,
\( \displaystyle \sum_{\ell=1}^{q}\delta_\ell B_{\rho_\ell}(c_i) =\sum_{j=0}^{m-1}j\,y_{ij}. \)
Thus the decomposition preserves every rival’s score exactly.
Let \(v\) be the linear-program optimum.
Section 1 shows that every allocation gives a feasible solution with objective value \(T(x)\). Therefore \(v\leq T^*\).
Conversely, apply Section 2 to the matrix in an optimal linear-program solution. The resulting allocation satisfies
\( \displaystyle T(x)= \max_i\left(b_{c_i}+\sum_jj\,y_{ij}\right) \leq v. \)
By the definition of \(T^*\),
\( \displaystyle T^*\leq T(x)\leq v\leq T^*. \)
Consequently, \(T(x)=v=T^*\).
This proves exact equivalence for the stated fixed-mass objective, including recovery of an optimal allocation.
First compute all baseline scores from the supplied support. This requires reading only the \(\tau\) listed rankings and performing \(O(\tau m)\) rational arithmetic operations. A common denominator for the input masses can be obtained by multiplying their denominators; its bit length is at most the sum of their encoded denominator lengths. Since Borda scores are integers bounded by \(m\), the resulting baseline scores have bit length polynomial in \(L+\log(m+1)\).
The linear program has \(m^2+1\) variables and \(O(m^2)\) constraints, with rational data of polynomial encoding length. We use the standard polynomial-time theorem for rational linear programming: a nonempty bounded linear program with binary-encoded rational coefficients admits an exact rational optimizer computable in polynomial time, with polynomial output bit length. Its hypotheses were verified in Section 1.
The decomposition also uses polynomial-size numbers. Let \(D\) be the product of the denominators of all entries of the optimal matrix and of \(\alpha\). Its bit length is polynomial because there are polynomially many entries, each of polynomial bit length. Initially every matrix entry is an integer multiple of \(1/D\). Every subsequent subtraction and every extracted mass retains this property. All residual entries and extracted masses lie in \([0,1]\), so their numerators over denominator \(D\) remain bounded by \(D\).
There are at most \(m^2\) matching computations and matrix updates. Thus decomposition takes polynomial bit time. The output consists of at most \(m^2\) rankings, each of length \(m+1\), together with polynomial-bit rational masses.
The complete algorithm therefore runs in time polynomial in \(m,\tau,L\). It never enumerates the possible rankings.
The algorithm returns \(x\) satisfying \(T(x)=T^*\). In particular,
\( \displaystyle T(x)\leq T^*+O\!\left(\alpha\sqrt{m\log(m+1)}\right). \)
Its failure probability is zero, which satisfies the requested exponentially small bound. A deterministic algorithm is also a randomized algorithm that ignores its random bits.
The cited scheduling paper establishes exact polynomial-time solvability for divisible-vote co-winner feasibility and minimum coalition weight in its Theorem 3.4. [Xia, Conitzer, and Procaccia](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf). The linear program above separately establishes exact solvability of the fixed-mass maximum rival score asked here.
Finally, since ties count as wins and \(p\)’s final score is always \(b_p+m\alpha\), the optimal allocation makes \(p\) a winner exactly when \(T^*\leq b_p+m\alpha\); this comparison is also exact in polynomial time.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the assigned problem. It establishes an exact deterministic polynomial-time algorithm for the fixed-mass maximum rival score, including an explicit optimal bloc allocation. No major or minor issues were found.
With \(p\) first, Borda assigns the rivals precisely the scores \(0,\ldots,m-1\), each once. Therefore the interpretation of \(y_{ij}\) is correct.
For an allocation, each rival receives total mass \(\alpha\), and each score position is used by total mass \(\alpha\). These give exactly the stated row and column equations. The identity
\[
\sum_j j\,y_{ij}=\sum_\rho x_\rho B_\rho(c_i)
\]
correctly preserves every rival’s bloc contribution.
The bound on \(t\) is valid: nonmanipulator mass is \(1-\alpha\), its scores are at most \(m\), and bloc scores for rivals are at most \(m-1\). Thus every rival’s final score lies between zero and \(m-\alpha\). Restricting \(t\) to \([0,m]\) cannot remove an optimal allocation.
The proposed feasible point \(y_{ij}=\alpha/m,\ t=m\) satisfies all constraints. Every feasible matrix entry lies in \([0,\alpha]\). The feasible region is closed and bounded, so the linear objective attains its minimum.
Assessment: Correct.
The residual invariant is correctly specified: nonnegative entries, with every row and column summing to a common value \(r\).
For \(r>0\), the displayed calculation establishes Hall’s condition for every subset of the candidate vertices. The bipartite sides both have size \(m\), so Hall’s marriage theorem supplies the required perfect matching. Its hypotheses are satisfied.
Every matched entry is positive, hence the selected minimum \(\delta\) is positive. Subtracting \(\delta P\) preserves nonnegativity and decreases every row and column sum by exactly \(\delta\). At least one positive entry disappears, and no new positive entry appears.
Consequently, the algorithm performs at most \(m^2\) iterations. It cannot stop with positive common row sum, because Hall’s argument would supply another matching. When the common row sum is zero, nonnegativity forces the residual matrix to be zero.
The resulting decomposition and the identity \(\sum_\ell\delta_\ell=\alpha\) follow from the recorded updates.
Assessment: Correct; neither termination nor the support bound has a gap.
Every permutation matrix assigns each rival a distinct score from \(0,\ldots,m-1\). Placing \(p\) first and ordering the rivals by decreasing assigned score gives exactly those Borda scores.
The extracted masses are positive, sum to \(\alpha\), and preserve every rival’s score contribution. Combining duplicate rankings preserves these properties and cannot increase support size.
Assessment: Correct. The construction satisfies the required allocation format.
The allocation-to-matrix construction establishes \(v\leq T^*\). Decomposing an optimal matrix produces an allocation with \(T(x)\leq v\). The displayed chain
\[
T^*\leq T(x)\leq v\leq T^*
\]
therefore establishes equality throughout.
The rational matrix needed for algorithmic recovery is supplied by the exact rational linear-programming theorem invoked in Section 4. This is consistent with the decomposition lemma’s rationality hypothesis.
Assessment: Correct. The argument directly addresses the fixed-mass objective.
The baseline computation uses only the listed support. Multiplying input denominators gives a common denominator whose bit length is bounded by their total encoded length. Integer Borda scores introduce only polynomial additional bit length.
The LP has polynomially many variables and constraints and polynomial-length rational coefficients. The stated standard theorem for rational linear programming applies: the feasible region is nonempty and bounded, and an exact rational optimizer of polynomial encoding length can be computed in polynomial time.
The decomposition’s denominator argument is also valid. All residual entries and extracted masses remain integer multiples of \(1/D\); subtraction introduces no additional denominators. Their values remain in \([0,1]\), so their numerators have polynomial bit length. Polynomially many matching computations and matrix updates therefore give polynomial bit time.
The output contains at most \(m^2\) rankings and polynomial-length rational masses.
Assessment: Correct, including the encoding and output-size requirements.
The argument covers \(m=1\): there is one rival score position, with score zero, and decomposition returns the sole permissible ranking.
It also covers \(\alpha=1\), when all nonmanipulator masses are absent and baseline scores are zero. No step requires positive nonmanipulator mass. Division by \(r\) occurs only after explicitly assuming \(r>0\).
Exact optimality implies the requested additive guarantee. Zero failure probability satisfies the exponentially small failure bound, and a deterministic algorithm can be viewed as a randomized algorithm that ignores its random bits.
The final co-winner comparison is correct because every permissible bloc ranking gives \(p\) score \(m\).
Assessment: Correct.
The scheduling-paper attribution is accurate: Theorem 3.4 states exact polynomial-time solvability of divisible-vote manipulation and minimum coalition weight. The prover uses this only as context; its fixed-mass optimization argument is independent. [Xia, Conitzer, and Procaccia, Theorem 3.4](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf).
No additional mathematical clarification or repair is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.