Answer: Polynomial-time solvable in \(m,\tau,L\): an optimal lottery \(p^\star\) and its exact rational distortion \(\delta^\star\) can be computed by rational linear programming.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximate] show that any RPSR for < alternatives is a convex combination of rules F:< for : 2 [<]: rule F:< (a) selects an agent uniformly at random and (b) select one of her : most-preferred alternatives uniformly at random. This result of [19] is in fact almost a direct corollary of a result of Barbera [9], which was in turn obtained from the characterization of Gibbard [20] of truthful rules.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given alternatives \(C\), finite ranking types \(T\subseteq S_C\), and rational masses \(\mu\in\Delta(T)\), compute a lottery \(p^\star\in\Delta(C)\) minimizing \(\delta(p,\mu)=\sup_u\max_{a\in C}W_u(a)/W_u(p)\), together with the optimum \(\delta^\star\), where \(W_u(a)=\sum_{t\in T}\int_0^{\mu_t}u_{t,z}(a)\,dz\) and each utility field is unit-sum and consistent with its ranking type; equivalently, by Theorem 1, the adversary may allocate each ranking mass among the finite top-\(k\) types \((t,k)\).
Let \(C\) be a nonempty set of \(m\) alternatives. A society is given by its support: a list \(T\) of \(\tau\) strict complete ranking types, each with positive mass \(\mu_t\) encoded as a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
For each \(t\), the adversary chooses a Lebesgue-measurable utility field \(u_{t,z}:C\to\mathbb R_{>0}\), indexed by \(z\in[0,\mu_t]\), satisfying \(\sum_{a\in C}u_{t,z}(a)=1\) and \(u_{t,z}(a)>u_{t,z}(b)\) whenever \(t\) ranks \(a\) above \(b\), almost everywhere.
Define \(W_u(a)=\sum_{t\in T}\int_0^{\mu_t}u_{t,z}(a)\,dz\), \(W_u(p)=\sum_{a\in C}p_aW_u(a)\), and \(\delta(p,\mu)=\sup_u\frac{\max_{a\in C}W_u(a)}{W_u(p)}\) for \(p\in\Delta(C)\).
Can an optimal lottery \(p^\star\in\arg\min_{p\in\Delta(C)}\delta(p,\mu)\) and its exact value \(\delta^\star\) be computed in time polynomial in \(m,\tau,L\), or is this problem NP-hard?
For a finite list of \(n\) agents, exact computation of the optimal lottery and its distortion is polynomial-time solvable using an LP with \(O(nm)\) variables, constraints, and nonzero coefficients ([Ebadian et al.](https://www.cs.toronto.edu/~nisarg/papers/distortion-computation.pdf)). No result explicitly settling the binary-rational support-input problem above was identified in the search.
The problem is polynomial-time solvable in \(m,\tau,L\). Both an optimal lottery and its exact distortion can be computed by a rational LP with \(O(\tau m)\) variables and \(O(\tau m^2)\) constraints and nonzero coefficients.
The proof below gives an explicit formulation. It uses the prefix-utility idea appearing in [Ebadian et al., Section 3](https://www.cs.toronto.edu/~nisarg/papers/distortion-computation.pdf), while proving the required equivalence for measurable utility fields and binary-rational type masses directly.
Write type \(t\)’s ranking as \(c_{t,1},\ldots,c_{t,m}\), from best to worst. Define
\(K_t=\{x\in\mathbb R_{\geq 0}^{C}:\sum_{a\in C}x(a)=1,\ x(c_{t,1})\geq\cdots\geq x(c_{t,m})\}.\)
This is a compact polytope. Define the compact welfare set
\(\mathcal W=\{\sum_{t\in T}\mu_t x_t:x_t\in K_t\text{ for every }t\}.\)
Every admissible utility field has welfare in \(\mathcal W\): its type average
\(\bar u_t(a)=\mu_t^{-1}\int_0^{\mu_t}u_{t,z}(a)\,dz\)
belongs to \(K_t\), because integration preserves the normalization, nonnegativity, and ranking inequalities.
Conversely, every point of \(\mathcal W\) is a limit of admissible welfare vectors. Indeed, fix \(x_t\in K_t\), and let
\(v_t(c_{t,j})=\dfrac{2(m-j+1)}{m(m+1)}.\)
This vector is positive, normalized, and strictly decreasing along the ranking. For \(0<\varepsilon<1\), the constant field
\(u_{t,z}^{\varepsilon}=(1-\varepsilon)x_t+\varepsilon v_t\)
is admissible, and its welfare tends to \(\sum_t\mu_t x_t\).
Thus \(\mathcal W\) is exactly the closure of the admissible welfare set. Consequently, for every continuous linear functional, its supremum over admissible welfare vectors equals its maximum over \(\mathcal W\).
We will apply this statement only to linear functionals, avoiding division at boundary points where a lottery’s welfare might vanish.
For each \(t\) and \(k\in\{1,\ldots,m\}\), define
\(e_{t,k}(a)=\dfrac{\mathbf 1\{a\in\{c_{t,1},\ldots,c_{t,k}\}\}}{k}.\)
We claim that
\(K_t=\operatorname{conv}\{e_{t,1},\ldots,e_{t,m}\}.\)
To prove this, take \(x\in K_t\), put \(x_j=x(c_{t,j})\), set \(x_{m+1}=0\), and define
\(\lambda_k=k(x_k-x_{k+1}).\)
The coefficients are nonnegative, and telescoping gives
\(\sum_{k=1}^{m}\lambda_k=\sum_{j=1}^{m}x_j=1.\)
For every position \(j\),
\(\sum_{k=j}^{m}\dfrac{\lambda_k}{k} =\sum_{k=j}^{m}(x_k-x_{k+1})=x_j.\)
Hence \(x=\sum_k\lambda_k e_{t,k}\). The reverse inclusion holds because every \(e_{t,k}\) belongs to the convex set \(K_t\).
Now fix \(p\in\Delta(C)\) and a finite \(d\geq 1\), and put \(q=dp\). For every admissible field, \(W_u(p)>0\), since every alternative has positive utility almost everywhere. Therefore
\(\delta(p,\mu)\leq d\)
is equivalent to
\(W_u(a)-\sum_{b\in C}q_bW_u(b)\leq 0 \quad\text{for every admissible field and every }a\in C.\)
By Section 1, this is equivalent to the same inequalities throughout \(\mathcal W\).
Let \(r_t(a)\) denote \(a\)’s position in ranking \(t\), and define
\(S_{t,k}=\sum_{j=1}^{k}q_{c_{t,j}}.\)
For a fixed \(a\), the maximum welfare excess separates across types. Each type’s linear objective is maximized at a prefix utility, so
\(\displaystyle \max_{W\in\mathcal W}\left(W(a)-\sum_{b\in C}q_bW(b)\right) = \sum_{t\in T}\mu_t \max_{1\leq k\leq m} \frac{\mathbf 1\{r_t(a)\leq k\}-S_{t,k}}{k}. \)
The separation is valid because the choices \(x_t\in K_t\) are independent; choosing a maximizer for each type simultaneously attains the sum of their maxima.
Thus the exact distortion condition is
\[\displaystyle \sum_{t\in T}\mu_t \max_{1\leq k\leq m} \frac{\mathbf 1\{r_t(a)\leq k\}-S_{t,k}}{k} \leq 0 \quad\text{for every }a\in C. \tag{1} \]
For every lottery, distortion is at least \(1\), because its welfare is a convex combination of the alternatives’ welfares.
The uniform lottery has welfare \(1/m\) on every admissible field, while every alternative has welfare at most \(1\). Its distortion is therefore at most \(m\). We may consequently restrict distortion guarantees to \([1,m]\).
Use variables \(q_a\), \(S_{t,k}\), and \(h_{t,a}\). Minimize
\(\displaystyle d=\sum_{a\in C}q_a\)
subject to:
\(q_a\geq 0\quad(a\in C),\qquad 1\leq\sum_{a\in C}q_a\leq m.\)
\(S_{t,1}=q_{c_{t,1}}\quad(t\in T),\)
\(S_{t,k}=S_{t,k-1}+q_{c_{t,k}} \quad(t\in T,\ 2\leq k\leq m).\)
\(k h_{t,a}+S_{t,k}\geq\mathbf 1\{r_t(a)\leq k\} \quad(t\in T,\ a\in C,\ 1\leq k\leq m).\)
\(\displaystyle\sum_{t\in T}\mu_t h_{t,a}\leq 0 \quad(a\in C).\)
\(-m\leq h_{t,a}\leq 1 \quad(t\in T,\ a\in C).\)
To verify equivalence with (1), define
\(\displaystyle H_{t,a}(q)= \max_{1\leq k\leq m} \frac{\mathbf 1\{r_t(a)\leq k\}-S_{t,k}}{k}. \)
Constraint 3 says precisely that \(h_{t,a}\geq H_{t,a}(q)\). Since every \(\mu_t>0\), Constraint 4 then implies (1).
Conversely, if (1) holds, choose \(h_{t,a}=H_{t,a}(q)\). Constraints 3 and 4 follow immediately. Because \(0\leq S_{t,k}\leq m\), every expression defining \(H_{t,a}(q)\) lies in \([-m,1]\). Thus Constraint 5 also holds.
The LP is feasible: take \(q_a=1\) for all \(a\). Then \(S_{t,k}=k\), and every prefix excess is nonpositive, so choosing \(h_{t,a}=H_{t,a}(q)\) satisfies all constraints.
Its feasible set is compact: the \(q\) variables and \(h\) variables are bounded, and the prefix equations bound every \(S_{t,k}\). Hence the LP attains its optimum.
Let an optimal LP solution have objective value \(d^\star\). Define
\(p_a^\star=q_a^\star/d^\star.\)
Since \(d^\star\geq 1\), this is well-defined and belongs to \(\Delta(C)\). The equivalence proved above gives
\(\delta(p^\star,\mu)\leq d^\star.\)
For the reverse optimality argument, take any lottery \(p\) with \(\delta(p,\mu)\leq m\). Set \(d=\delta(p,\mu)\) and \(q=dp\). The definition of the supremum implies every admissible welfare ratio is at most \(d\), so Section 2 applies. These variables extend to a feasible LP solution of objective \(d\). Therefore
\(d^\star\leq\delta(p,\mu).\)
If instead \(\delta(p,\mu)>m\), feasibility of the LP at objective \(m\) gives the same inequality. Thus \(d^\star\) is a lower bound on every lottery’s distortion. Applying this to \(p^\star\) proves
\(\delta(p^\star,\mu)=d^\star=\min_{p\in\Delta(C)}\delta(p,\mu).\)
This also proves existence of an optimal lottery, without assuming that any adversarial supremum is attained.
The LP has \(m+2\tau m=O(\tau m)\) variables. Constraint 3 contributes \(\tau m^2\) inequalities, each with two nonzero coefficients. All remaining constraints contribute \(O(\tau m)\) nonzero coefficients. Thus its total size is \(O(\tau m^2)\).
Apart from the input masses \(\mu_t\), all coefficients are integers of magnitude at most \(m\). Repeating the rational masses in the weighted constraints increases the encoding length only polynomially in \(m,\tau,L\).
The standard exact rational linear-programming theorem computes an optimal rational solution in time polynomial in the LP’s binary encoding length. Its hypotheses hold here: the LP is explicitly represented, rational, feasible, and bounded. In particular, optimal coordinates have polynomial bit length, as follows from determinant bounds for rational basic feasible solutions.
Finally, summing the optimal \(q_a^\star\) and dividing by \(d^\star\) take polynomial time in their bit lengths. No denominator-sized expansion into individual agents is required.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes polynomial-time exact computation for the binary-rational support model. The measurable-field reduction, LP formulation, and optimality argument are correct. No major or minor issues requiring repair were found.
The definition of \(K_t\) correctly relaxes strict positivity and strict ranking inequalities to their weak versions.
Every admissible field has a type average in \(K_t\). Its coordinates are measurable and bounded almost everywhere by normalization and positivity, so the integrals exist. Integration preserves normalization and the weak ranking inequalities. Division by \(\mu_t\) is valid because every mass is positive.
The approximation vector is correctly normalized:
\( \sum_{j=1}^{m}2(m-j+1)/(m(m+1))=1 \).
It is positive and strictly decreasing whenever there are distinct ranking positions. Mixing it with any \(x_t\in K_t\) therefore produces an admissible constant field for every \(0<\varepsilon<1\).
Consequently, both inclusions needed for the closure claim are justified: admissible welfare vectors belong to the closed set \(\mathcal W\), and every point of \(\mathcal W\) is approximated by admissible welfare vectors. Compactness follows from the finite product of compact polytopes and the continuous weighted-sum map.
The conclusion about continuous linear functionals is valid. Crucially, the output does not assume that welfare ratios remain continuous at boundary points with zero lottery welfare.
The proposed coefficients \( \lambda_k=k(x_k-x_{k+1}) \) are nonnegative. Both telescoping identities are correct:
Thus the decomposition proves the claimed convex-hull equality. The reverse inclusion follows from convexity and membership of each prefix vector.
The attribution to prefix utilities in [Ebadian et al., Section 3](https://www.cs.toronto.edu/~nisarg/papers/distortion-computation.pdf) is accurate. The output supplies its own decomposition and closure argument, so it does not depend on importing that paper’s treatment of strict utilities or supremum attainment.
For every admissible field and every lottery, \(W_u(p)>0\). A nonnegative lottery has at least one positive coordinate, and each alternative’s welfare is positive because its utility is positive almost everywhere on positive-mass intervals.
For finite \(d\), the equivalence between \(\delta(p,\mu)\leq d\) and the stated linear inequalities is therefore valid. Taking the closure preserves these inequalities by continuity.
For each fixed alternative, maximization separates across types because the feasible choices form a product and each mass is positive. Each type’s linear objective is maximized at a prefix vector. Evaluating that vector gives exactly
\( (\mathbf 1\{r_t(a)\leq k\}-S_{t,k})/k \).
Equation (1) consequently characterizes the distortion guarantee exactly. No exchange of a ratio supremum with a boundary maximum is used.
All five constraint families have the claimed meaning.
Constraint 3 is equivalent to \(h_{t,a}\geq H_{t,a}(q)\), since \(k>0\). Positive masses make Constraint 4 imply Equation (1). Conversely, choosing \(h_{t,a}=H_{t,a}(q)\) satisfies both families whenever Equation (1) holds.
The auxiliary bounds are valid: nonnegativity and \(\sum_aq_a\leq m\) give \(0\leq S_{t,k}\leq m\), so every prefix excess lies in \([-m,1]\). These bounds exclude no relevant solution.
The feasibility witness \(q_a=1\) is correct. Its prefix sums satisfy \(S_{t,k}=k\), making every prefix excess nonpositive.
The feasible set is closed and bounded: the \(q\) and \(h\) variables are explicitly bounded, and the prefix equations bound the \(S\) variables. Hence the LP attains its optimum.
The restriction to objective values in \([1,m]\) is justified by the universal lower bound \(1\) and the uniform lottery’s upper bound \(m\).
Since \(d^\star\geq1\), the recovered vector \(p^\star=q^\star/d^\star\) is well-defined and is a lottery. LP feasibility gives \(\delta(p^\star,\mu)\leq d^\star\).
For any lottery with finite distortion at most \(m\), setting \(d=\delta(p,\mu)\) is legitimate even when the adversarial supremum is unattained: every ratio is bounded above by its supremum. The preceding equivalences therefore produce a feasible LP solution of objective \(d\).
Lotteries with distortion greater than \(m\), including infinite distortion, are covered by \(d^\star\leq m\). Thus the comparison applies to every lottery, and the asserted equality and optimality follow.
The variable count \(m+2\tau m\) is correct. The prefix-excess constraints contribute \(\tau m^2\) inequalities with two nonzero coefficients each. The remaining constraints contribute \(O(\tau m)\) nonzero coefficients.
All coefficients are rational; the integer coefficients have magnitude at most \(m\). Repetition of input masses increases encoding length only polynomially. Sparse or dense encoding therefore yields a polynomial-size LP.
The exact rational LP theorem is stated sufficiently for its use: an explicitly encoded rational LP can be solved exactly in polynomial time in its binary encoding length. The required feasibility and boundedness are established. The determinant-bound observation supports the availability of an optimal rational basic feasible solution with polynomial coordinate bit length.
Summation and division for the recovered lottery preserve polynomial bit complexity. The proof never expands a mass into a denominator-sized population.
The argument covers \(m=1\): strict ranking conditions are vacuous, and the objective bounds force distortion \(1\). It also covers a single supported type, zero lottery coordinates, arbitrarily small positive rational masses, and lotteries of infinite distortion.
Required clarification or repair: none.
⟨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.