Answer: Exact computation is polynomial-time in \(m,\tau,L\). Both guarantees hold; coalition utility gain is at most \(\eta/(m+1)\).
Corollary 4.6 — class: algorithmic
Given fixed \(k\), rational \(\alpha,\eta>0\), and a finite-support rational society \(\mu\) over complete types \((u,r)\), where \(u\) records a voter’s true utility type and \(r\in\Sigma_k\) is their current reported ranking, let \(\nu_r=\sum_u\mu_{u,r}\). For each candidate \(j\), let \(d_j(\nu)\) be the minimum mass of reports that must change to make \(j\) win plurality under the paper’s tie-breaking rule; transfers must preserve \(u\) and respect the available mass of each type. Can one compute the exact lottery \(G(j)=[1-\rho d_j(\nu)]_+/\sum_\ell[1-\rho d_\ell(\nu)]_+\), with \(\rho=\eta/[k(k+1)\alpha^2]\), in time polynomial in \(k,\tau,L\), and establish that every supported outcome is within mass \(1/\rho\) of a plurality win and no coalition of mass at most \(\alpha\) can increase its integrated expected true utility by more than \(\eta\)?
Fix \(m=k\ge2\) candidates, strict reported rankings \(r\in\Sigma_k\), and binary rational parameters \(0<\alpha<1\) and \(\eta>0\). A true utility type is a vector \(u\in\mathbb Q^k\cap[0,1]^k\); true utilities remain fixed when reports change.
A society is given by its support: the list of its \(\tau\) types \((u,r)\) with positive binary rational masses \(\mu_{u,r}\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length, including utilities and parameters. State running times in \(m,\tau,L\).
Write \(\nu_r=\sum_u\mu_{u,r}\). Use plurality with the smallest candidate index winning ties.
A report change is a nonnegative real transfer array \(x_{u,r,s}\) satisfying \(\sum_s x_{u,r,s}=\mu_{u,r}\), where destination rankings \(s\in\Sigma_k\) need not occur in the input. Its changed mass is \(\sum_{u,r}\sum_{s\ne r}x_{u,r,s}\), and its resulting report masses are \(\nu'_s=\sum_{u,r}x_{u,r,s}\).
Define \(d_j(\nu)\) as the infimum changed mass over transfers making \(j\) the plurality winner. Set \(\rho=\eta/[k(k+1)\alpha^2]\) and \(G_\mu(j)=\max\{1-\rho d_j(\nu),0\}/\sum_{\ell=1}^k\max\{1-\rho d_\ell(\nu),0\}\).
A coalition selects masses \(0\le c_{u,r}\le\mu_{u,r}\) with \(\sum_{u,r}c_{u,r}\le\alpha\), redistributes only those reports while preserving each true utility type, and leaves all other reports fixed. Its integrated expected utility under a lottery \(G\) is \(U_c(G)=\sum_{u,r}c_{u,r}\sum_{j=1}^k u_jG(j)\).
Is exact computation of \(G_\mu\) possible in time polynomial in \(m,\tau,L\), or is it NP-hard?
Does this lottery always have both guarantees: every \(j\) with \(G_\mu(j)>0\) can be made a plurality winner by changing mass at most \(1/\rho\), and every coalition deviation producing \(\mu'\) satisfies \(U_c(G_{\mu'})-U_c(G_\mu)\le\eta\)?
For finite electorates and fixed \(k\), the analogous lottery is polynomial-time computable for efficiently computable rules invariant under voter permutations; a related discrete construction also bounds total coalition utility gain ([Birrell–Pass](https://www.cs.cornell.edu/~rafael/papers/IJCAI11.pdf)).
No result settling this exact continuous formulation was located in the literature search.
Exact computation is possible in time polynomial in \(m,\tau,L\), even when \(m\) varies. Both guarantees hold. In fact, every admissible coalition deviation satisfies the stronger bound
\[ U_c(G_{\mu'})-U_c(G_\mu)\le \frac{\eta}{m+1}. \]
The proof below accounts explicitly for divisible masses, unsupported destination rankings, and possibly unattained winning-cost infima.
Write \(p_i=\sum_{(u,r):\,r\text{ ranks }i\text{ first}}\mu_{u,r}\). Thus \(p\) belongs to the probability simplex \(\Delta_m\), and plurality depends only on \(p\).
For \(p,z\in\Delta_m\), define their total variation distance by
\[ \delta(p,z)=\frac12\sum_{i=1}^m|p_i-z_i| =\sum_{i=1}^m(p_i-z_i)_+, \]
where \(a_+=\max\{a,0\}\).
Transport lemma. Starting from the given society, the minimum changed report mass needed to obtain first-place masses \(z\) is exactly \(\delta(p,z)\). This is achievable while preserving true utilities.
Proof. In any transfer, the mass whose original and destination rankings both place \(i\) first is at most \(\min\{p_i,z_i\}\). Consequently, at least
\[ 1-\sum_i\min\{p_i,z_i\}=\delta(p,z) \]
changes its first-place candidate. Every such transfer changes its ranking, proving the lower bound.
For achievability, put \(a_i=(p_i-z_i)_+\), \(b_i=(z_i-p_i)_+\), and \(h=\sum_i a_i=\sum_i b_i\). If \(h=0\), leave all reports unchanged.
Otherwise, for every surplus candidate \(i\), select the fraction \(a_i/p_i\) of each input type whose ranking places \(i\) first. Redistribute each selected portion among deficit candidates \(j\) in proportions \(b_j/h\), using any fixed ranking placing \(j\) first. Surplus and deficit candidates are distinct, so all selected reports change. Each transfer retains its source utility vector. The resulting first-place masses are \(z\), and the changed mass is exactly \(h=\delta(p,z)\). \(\square\)
Define the closed weak-winner region
\[ W_j=\{z\in\Delta_m:z_j\ge z_i\text{ for every }i\}. \]
Under the prescribed tie-breaking, the actual winner region additionally requires \(z_j>z_i\) whenever \(i<j\).
Claim. The winning-cost infimum is
\[ d_j(p)=\min_{z\in W_j}\delta(p,z). \]
Proof. The minimum exists because \(W_j\) is nonempty and compact and \(\delta(p,\cdot)\) is continuous. Every profile where \(j\) actually wins lies in \(W_j\), so the transport lemma gives the lower bound.
Conversely, let \(z\in W_j\) attain the displayed minimum. Let \(e_j\) assign all mass to candidate \(j\), and, for \(0<\varepsilon<1\), put \(z^\varepsilon=(1-\varepsilon)z+\varepsilon e_j\). For every \(i\ne j\),
\[ z^\varepsilon_j-z^\varepsilon_i =(1-\varepsilon)(z_j-z_i)+\varepsilon>0. \]
Thus \(j\) is the unique plurality winner. Moreover,
\[ \delta(p,z^\varepsilon) \le \delta(p,z)+\delta(z,z^\varepsilon) =\delta(p,z)+\varepsilon\delta(z,e_j) \le \delta(p,z)+\varepsilon. \]
The transport lemma realizes these profiles, and letting \(\varepsilon\) approach zero proves the upper bound on the infimum. \(\square\)
In particular, the infimum depends only on first-place masses, although its attainment can depend on tie-breaking.
Fix \(j\), and define, for \(t\ge0\),
\[ F_j(t)=\sum_{i\ne j}(p_i-p_j-t)_+. \]
The function \(F_j(t)-t\) is continuous and strictly decreasing. Its value at zero is nonnegative, and \(F_j(1-p_j)=0\). Hence there is a unique \(t_j\in[0,1-p_j]\) satisfying \(F_j(t_j)=t_j\).
Claim. We have \(d_j(p)=t_j\).
Proof. Let \(z\in W_j\), and set \(t=\delta(p,z)\). Each coordinate changes by at most \(t\), so \(z_j\le p_j+t\). Since \(z_i\le z_j\),
\[ (p_i-p_j-t)_+\le(p_i-z_i)_+. \]
Summing over \(i\ne j\) gives \(F_j(t)\le t\). Strict decrease of \(F_j(t)-t\) therefore implies \(t\ge t_j\).
For the reverse inequality, define
\[ z_j=p_j+t_j,\qquad z_i=p_i-(p_i-p_j-t_j)_+=\min\{p_i,p_j+t_j\}\quad(i\ne j). \]
All coordinates are nonnegative, and
\[ \sum_i z_i=1+t_j-F_j(t_j)=1. \]
Also \(z_j\ge z_i\), so \(z\in W_j\). Candidate \(j\) gains mass \(t_j\), and all other candidates together lose exactly \(F_j(t_j)=t_j\). Therefore \(\delta(p,z)=t_j\), proving the claim. \(\square\)
To compute this root exactly, observe that
\[ F_j(t)= \max_{S\subseteq[m]\setminus\{j\}} \left(\sum_{i\in S}p_i-|S|p_j-|S|t\right). \]
Consequently, \(F_j(t)\le t\) is equivalent to
\[ t\ge \frac{\sum_{i\in S}p_i-|S|p_j}{|S|+1} \quad\text{for every }S\subseteq[m]\setminus\{j\}. \]
For a fixed cardinality, the largest numerator uses the largest available scores. Let \(b_{j,1}\ge\cdots\ge b_{j,m-1}\) be the scores excluding \(p_j\), and let \(B_{j,q}=\sum_{h=1}^q b_{j,h}\), with \(B_{j,0}=0\). We obtain the formula
\[ \boxed{ d_j(p)= \max_{0\le q\le m-1} \frac{B_{j,q}-q p_j}{q+1}. } \]
The term for \(q=0\) is zero, so the maximum is always nonnegative.
Aggregate the first-place masses and sort them once. For each candidate \(j\), traverse this sorted list while skipping \(j\), calculate its prefix sums, and evaluate the formula above. This uses \(O(\tau+m^2+m\log m)\) arithmetic operations, in addition to reading the input.
Here is an explicit polynomial bound on the required bit operations.
Index the support by \(t\), and write \(\mu_t=A_t/B_t\) with positive integer denominators. Set \(D=\prod_t B_t\). Its bit length is \(O(L)\), and each first-place mass can be represented as \(p_i=n_i/D\), where \(0\le n_i\le D\).
The distance formula then represents each optimum as
\[ d_j=\frac{N_j}{D h_j}, \qquad N_j\ge0,\qquad 1\le h_j\le m, \]
with \(N_j\) of bit length \(O(L+\log m)\). These representations are obtained by comparing the prefix-sum fractions exactly.
Write \(\rho=A/B\), where \(A,B\) are positive integers of bit length \(O(L+\log m)\). Let \(Q=m!\), and define integer weights
\[ W_j= \max\{BDh_j-AN_j,0\}\frac{Q}{h_j}. \]
Because \(h_j\) divides \(Q\),
\[ \frac{W_j}{BDQ}=\max\{1-\rho d_j,0\}. \]
Thus the exact output is
\[ G_\mu(j)=\frac{W_j}{\sum_{\ell=1}^mW_\ell}. \]
The denominator is positive: the current plurality winner has \(d_j=0\), hence unnormalized weight one.
All integers used here have bit length \(O(L+m\log(m+1))\). Using ordinary quadratic-time integer arithmetic gives, for example, the valid bound
\[ O\!\left( L+(\tau+m^2)\bigl(L+m\log(m+1)\bigr)^2 \right) \]
bit operations. No enumeration of the \(m!\) rankings is required; \(m!\) above is merely a common-denominator integer.
If \(G_\mu(j)>0\), then \(1-\rho d_j>0\), so \(d_j<1/\rho\).
Choose \(0<\varepsilon<\min\{1,1/\rho-d_j\}\). Section 2 and the transport lemma provide an actual report change making \(j\) the unique winner at cost at most \(d_j+\varepsilon<1/\rho\).
Thus the first guarantee holds despite possible nonattainment of \(d_j\).
First, distances to the fixed set \(W_j\) are Lipschitz:
\[ |d_j(p)-d_j(q)|\le\delta(p,q). \]
Indeed, if \(z\in W_j\) minimizes the distance from \(q\), the triangle inequality gives \(d_j(p)\le\delta(p,q)+d_j(q)\); interchange \(p\) and \(q\) for the reverse bound.
Let \(w_j(p)=(1-\rho d_j(p))_+\) and \(Z(p)=\sum_jw_j(p)\). The positive-part function is Lipschitz with constant one, so
\[ |w_j(p)-w_j(q)|\le\rho\delta(p,q). \]
Also \(Z(p)\ge1\) for every profile. Set \(A_0=\sum_j|w_j(q)-w_j(p)|\). Normalization therefore satisfies
\[ \begin{aligned} \sum_j|G_q(j)-G_p(j)| &\le \frac{A_0+|Z(q)-Z(p)|}{Z(q)}\\ &\le 2A_0. \end{aligned} \]
Hence
\[ \delta(G_p,G_q)\le A_0\le m\rho\delta(p,q). \]
Now consider an admissible coalition. Write \(c=\sum_{u,r}c_{u,r}\le\alpha\), and let \(p'\) be the resulting first-place masses. Only selected mass can change reports, so the transport lower bound implies \(\delta(p,p')\le c\).
Define its aggregate candidate utilities by \(a_j=\sum_{u,r}c_{u,r}u_j\). Because true utilities remain fixed and lie in \([0,1]\), these same coefficients describe its utility before and after the deviation, and \(0\le a_j\le c\). Therefore
\[ \begin{aligned} U_c(G_{\mu'})-U_c(G_\mu) &=\sum_j a_j\bigl(G_{\mu'}(j)-G_\mu(j)\bigr)\\ &\le c\sum_{j:\,G_{\mu'}(j)>G_\mu(j)} \bigl(G_{\mu'}(j)-G_\mu(j)\bigr)\\ &=c\,\delta(G_\mu,G_{\mu'})\\ &\le m\rho c^2\\ &\le m\rho\alpha^2 =\frac{\eta}{m+1} \le\eta. \end{aligned} \]
This proves the second guarantee for every admissible deviation.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The distance formula, exact polynomial-time computation, and both guarantees are correct as written. The stronger coalition bound is also justified. I found no major or minor mathematical issues.
Plurality depends only on the vector \(p\) of first-place masses. The transport lemma correctly identifies the minimum changed report mass for reaching any \(z\in\Delta_m\) as \(\delta(p,z)\).
The lower bound is valid: mass retaining first-place candidate \(i\) cannot exceed \(\min\{p_i,z_i\}\), and every change of first-place candidate necessarily changes the ranking.
The construction attains the bound. A surplus candidate has \(p_i>0\), so the fraction \(a_i/p_i\) is defined and lies in \([0,1]\). When \(h>0\), the proportions \(b_j/h\) sum to one. Surplus and deficit candidates are distinct, ensuring every selected portion changes its ranking. Unsupported destination rankings are permitted by the task, and each transfer preserves its source utility vector. The case \(h=0\) is explicitly handled.
The actual winner region is described correctly: candidate \(j\) must strictly exceed every lower-index candidate and may tie higher-index candidates.
The closed region \(W_j\) is nonempty and compact, so the continuous distance function attains its minimum there. Since the actual winner region is contained in \(W_j\), this minimum is a lower bound on the winning-cost infimum.
The perturbation \(z^\varepsilon=(1-\varepsilon)z+\varepsilon e_j\) remains in the simplex and makes \(j\) the unique winner. The displayed coordinate differences and distance bound are correct. Consequently, actual winning profiles approach the closed-region minimum arbitrarily closely. This establishes the claimed equality of infima without assuming that the actual winning cost is attained.
Each summand of \(F_j\) is continuous and nonincreasing; subtracting \(t\) makes \(F_j(t)-t\) strictly decreasing. At \(t=0\), its value is nonnegative. At \(t=1-p_j\), every summand vanishes because \(p_i\le1\), and the difference is nonpositive. Thus the asserted unique root exists, including the endpoint cases.
For the lower bound, \(\delta(p,z)=t\) bounds each coordinate’s absolute change by \(t\), so \(z_j\le p_j+t\). Together with \(z_i\le z_j\), this justifies the positive-part inequality. Summation gives \(F_j(t)\le t\), and strict decrease yields \(t\ge t_j\).
The proposed attaining vector is nonnegative, sums to one by the root equation, and belongs to \(W_j\). Candidate \(j\) gains exactly \(t_j\), while the remaining candidates lose that same total mass. Its total variation distance is therefore exactly \(t_j\). The identity \(d_j(p)=t_j\) follows.
The subset expression for \(F_j(t)\) is correct: maximizing over subsets includes exactly the positive contributions, with zero contributions immaterial.
Rearranging each subset inequality gives the stated denominator \(|S|+1\). For a fixed cardinality \(q\), the largest numerator uses the \(q\) largest scores excluding \(j\). The \(q=0\) term supplies zero, covering cases in which all nonempty-subset expressions are negative.
These observations justify the displayed maximum formula exactly. No subsets or destination rankings need to be enumerated.
Aggregation, one sort, and one prefix-sum traversal per candidate give the stated arithmetic-operation bound.
The product denominator \(D\) has bit length \(O(L)\), since the denominator encodings are included in the input length. The common-denominator numerators \(n_i\) satisfy \(0\le n_i\le D\). The selected distance fraction has denominator \(Dh_j\), with \(1\le h_j\le m\), and numerator bit length \(O(L+\log m)\).
Computing \(\rho\) from the binary rational parameters preserves the claimed polynomial bit bound. The factorial \(Q=m!\) has bit length \(O(m\log(m+1))\), and every \(h_j\) divides it. The integer-weight identity is algebraically correct, so normalizing the \(W_j\) produces the exact lottery.
The normalization denominator is positive because the current plurality winner has winning cost zero and hence unnormalized weight one.
The stated bit-operation bound covers aggregation, exact fraction comparisons, factorial construction, integer weights, and normalization using ordinary quadratic-time integer arithmetic. Sorting is absorbed by the \(m^2\) term for \(m\ge2\). Reading the utility coordinates and full rankings is covered by the input-reading term. The algorithm is polynomial in \(m,\tau,L\).
Positive lottery weight implies the strict inequality \(d_j<1/\rho\). Hence the specified positive \(\varepsilon\) exists.
The earlier perturbation and transport construction produce an actual winning report change with cost at most \(d_j+\varepsilon<1/\rho\). This proves the requested weak budget bound and correctly handles potentially unattained infima.
The distance-to-\(W_j\) Lipschitz inequality follows from the triangle inequality and the established minimum characterization. Applying the positive-part function gives the stated weight bound.
The normalization estimate uses a valid decomposition, \(|Z(q)-Z(p)|\le A_0\), and \(Z(q)\ge1\). The conversion from the lottery’s \(L^1\) difference to total variation correctly includes the factor \(1/2\), yielding \(\delta(G_p,G_q)\le m\rho\delta(p,q)\).
A coalition of selected mass \(c\) changes at most that mass, so the transport lower bound gives \(\delta(p,p')\le c\). Fixed true utilities ensure that the same coefficients \(a_j\) describe utility before and after the deviation, with \(0\le a_j\le c\).
Bounding the positive lottery changes gives exactly the displayed utility estimate. The final substitution is correct because \(m=k\):
\(m\rho\alpha^2=\eta/(m+1)\le\eta\).
These arguments apply to real-valued deviations: the geometric and utility estimates do not require the resulting masses to remain rational.
No additional clarification or repair is needed.
⟨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.