Answer: \(\text{Polynomial-time solvable}\), with exact rational probabilities encoded by binary numerators and denominators.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe ESR algorithm runs in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite alternative set \(A\) and a finite-support distribution \(\mu\) over complete weak rankings, with positive binary-rational masses summing to \(1\), compute an ESR lottery by running the ESR process on one representative for each type in \(\operatorname{supp}(\mu)\). What is the exact running time in \(m=|A|\), \(\tau=|\operatorname{supp}(\mu)|\), and the input bit length \(L\)?
Let \(A\) be a nonempty alternative set, with \(m=|A|\). A society is given by its support: the list of \(\tau\) distinct complete, transitive weak rankings with positive binary-rational masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
Write type \(i\)'s ranking as an ordered partition \(E_i^1,\ldots,E_i^{k_i}\) into nonempty indifference classes, best first, and let \(\mathcal E\) contain all distinct classes appearing in these partitions. For a lottery \(p\), write \(p(S)=\sum_{a\in S}p(a)\).
Define egalitarian simultaneous reservation (ESR) using one representative per supported type, each climbing at unit speed regardless of its mass. Identical subsets share one ceiling; their representatives' speeds do not add.
Initially set time \(t=0\), ceilings \(\ell(S)=0\) for \(S\in\mathcal E\), heights \(h_i=0\), and current classes \(C_i=E_i^1\).
At each stage, let \(\lambda^*\) be the largest \(\lambda\in[0,1-t]\) for which a lottery \(p\in\Delta(A)\) satisfies \(p(S)\ge\ell(S)\) for every \(S\in\mathcal E\) and \(p(C_i)\ge h_i+\lambda\) for every type \(i\).
A type bounces if \(p(C_i)=h_i+\lambda^*\) for every lottery feasible at \(\lambda=\lambda^*\). Advance time and all heights by \(\lambda^*\), then set \(\ell(S)\leftarrow\max(\{\ell(S)\}\cup\{h_i:C_i=S\})\).
If \(t<1\), simultaneously move every bouncing type to its next class and reset its height to \(0\); other types retain their class and height. Zero-duration stages are allowed. Stop at \(t=1\); an ESR lottery is any lottery satisfying all final ceiling bounds, returned with exact binary-rational probabilities.
Is exact computation of an ESR lottery for this distribution input solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite lists of agents with weak rankings, ESR is polynomial-time computable ([Aziz and Stursberg](https://ojs.aaai.org/index.php/AAAI/article/download/8796/8655)). No separate complexity result for the distribution formulation was verified.
Exact computation is polynomial-time solvable in \(m,\tau,L\). The masses do not enter the specified dynamics: the algorithm operates directly on the \(\tau\) supported rankings.
Here “exact binary-rational probabilities” means rational numbers represented by binary numerators and denominators. If it instead requires finite binary expansions, the output requirement can fail: three strict rankings with different top alternatives force the uniform lottery with probabilities \(1/3\). We use the usual exact rational encoding below.
The finite-agent LP approach appears in Algorithms 1–2 and Theorem 2 of [Aziz and Stursberg](https://ojs.aaai.org/index.php/AAAI/article/download/8796/8655). The following proof establishes the stage and bit-complexity bounds directly for the formulation in the question.
Let \(q=|\mathcal E|\). Since each ranking has at most \(m\) classes,
\(q\le \sum_{i=1}^{\tau}k_i\le \tau m.\)
At the beginning of a stage, define the ceiling-feasible polytope
\(P=\{p\in\mathbb R_{\ge 0}^{A}:\sum_{a\in A}p(a)=1,\ p(S)\ge\ell(S)\text{ for every }S\in\mathcal E\}.\)
We maintain the invariant that \(P\) is nonempty and every \(p\in P\) satisfies \(p(C_i)\ge h_i\) for every type \(i\). This holds initially.
Compute \(\lambda^*\) by the following LP, whose variables are the \(m\) probabilities and \(\lambda\):
\(\text{maximize }\lambda,\)
subject to
\(p\in P,\qquad 0\le\lambda\le 1-t,\qquad p(C_i)-\lambda\ge h_i\quad(1\le i\le\tau).\)
The invariant makes \(\lambda=0\) feasible. The feasible region is compact, so the maximum exists.
Let
\(F=\{p\in P:p(C_i)\ge h_i+\lambda^*\text{ for every }i\}.\)
For each type \(i\), solve another LP:
\(\beta_i=\max_{p\in F}p(C_i).\)
Because every member of \(F\) satisfies the corresponding lower bound, type \(i\) bounces exactly when
\(\beta_i=h_i+\lambda^*.\)
Thus one stage requires at most \(\tau+1\) exact LP solves. This tests the universal equality in the definition, rather than equality at a single optimal lottery.
Write \(h_i'=h_i+\lambda^*\), and update the ceilings as specified. The resulting ceiling-feasible polytope is exactly \(F\): its bounds combine the old ceilings with all inequalities \(p(C_i)\ge h_i'\).
Consequently, the updated ceilings are feasible. After moving bouncing types, retained types still satisfy their height bounds, while moved types have height zero and therefore satisfy theirs by nonnegativity. This proves the invariant inductively.
Suppose \(\lambda^*<1-t\), but no type bounces. For each \(i\), there is then a lottery \(p^{(i)}\in F\) satisfying
\(p^{(i)}(C_i)>h_i+\lambda^*.\)
Take their average,
\(\bar p=\frac1\tau\sum_{i=1}^{\tau}p^{(i)}.\)
Convexity gives \(\bar p\in F\). For every \(j\), all summands satisfy the lower bound for \(C_j\), and the \(j\)-th summand satisfies it strictly. Hence
\(\bar p(C_j)>h_j+\lambda^*\quad\text{for every }j.\)
Both the minimum of these finitely many positive slacks and \(1-t-\lambda^*\) are positive. Choose a positive \(\varepsilon\) smaller than both. Then \((\bar p,\lambda^*+\varepsilon)\) is feasible for the stage LP, contradicting maximality.
Therefore every stage ending before time \(1\) has at least one bouncing type. The argument also covers \(\lambda^*=0\).
Two invariants establish this.
First, when type \(i\) leaves class \(E_i^j\), let \(d_{ij}\) be its height immediately before resetting. By the definition of bouncing,
\(p(E_i^j)=d_{ij}\)
for every lottery satisfying the newly updated ceilings. Later ceiling-feasible polytopes are subsets of that polytope, because ceilings only increase. Thus this equality persists.
Second, if type \(i\) currently occupies its \(r\)-th class, then
\(\sum_{j<r}d_{ij}+h_i=t.\)
Indeed, its height increases by every stage duration, and each reset transfers its accumulated height into the departure value for the class it leaves. Zero-duration stages preserve the identity as well.
Now suppose \(C_i=E_i^{k_i}\), the last class. For every \(p\in P\), the classes partition \(A\), so the persistent equalities imply
\(p(C_i)=1-\sum_{j<k_i}d_{ij}=1-t+h_i.\)
If the current stage is nonterminal, then \(\lambda^*<1-t\). Consequently, every \(p\in F\) satisfies
\(p(C_i)=h_i+1-t>h_i+\lambda^*.\)
Such a type cannot bounce. Hence every move prescribed before time \(1\) has a next class available.
Each type can therefore move at most \(k_i-1\) times. Together with Section 2, this bounds the number of nonterminal stages by
\(\sum_{i=1}^{\tau}(k_i-1)\le\tau(m-1).\)
Including the terminal stage, the total number of stages is at most
\(K=\tau(m-1)+1.\)
This proves termination, including in the presence of zero-duration stages. The invariant proves that the final ceiling bounds admit a lottery.
A polynomial number of LP solves is insufficient by itself; their rational data must also remain polynomial in size.
Set \(n=m+1\), the number of variables in the stage LP. Suppose all current state values \(t,h_i,\ell(S)\) have a common positive integer denominator \(D\). Initially, \(D=1\).
The stage LP has coefficient entries in \(\{-1,0,1\}\), and every right-hand side is an integer divided by \(D\). Its nonempty compact feasible region has an optimal vertex. At that vertex, choose \(n\) linearly independent active constraints. They give a system
\(Bx=u/D,\)
where \(B\) is a nonsingular integer matrix with entries in \(\{-1,0,1\}\), and \(u\) is an integer vector.
Cramer’s rule implies that every coordinate of this vertex, in particular \(\lambda^*\), has denominator dividing \(D|\det B|\). Hadamard’s inequality gives
\(1\le|\det B|\le n^{n/2}.\)
Choose the next common denominator to be
\(D'=D|\det B|.\)
All updated state values have denominators dividing \(D'\): updates use additions, resets to zero, and maxima, each of which selects an existing value.
After at most \(K\) stages, therefore,
\(\log_2D\le \frac{Kn}{2}\log_2 n.\)
Every state value lies in \([0,1]\), so its numerator, when represented over this common denominator, is at most \(D\). Thus each state value has binary encoding length
\(B_{\mathrm{state}}=O\!\left(1+K(m+1)\log(m+1)\right)=O\!\left(1+\tau m^2\log(m+1)\right).\)
The bounce-test LPs use right-hand sides \(\ell(S)\) and \(h_i+\lambda^*\), which have the same polynomial bound. Their optimal values need not be stored as part of the state.
We use the standard exact rational linear-programming theorem: feasibility and finite optimization for explicitly given rational LPs can be solved in time polynomial in their binary descriptions, returning exact rational solutions and values. This includes lower-dimensional feasible regions. Exact recovery from polynomial-precision LP algorithms is discussed in [Vishnoi’s linear-programming notes, Section 1](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf).
All hypotheses hold here: the LPs have rational data, explicit polynomially many constraints, nonempty feasible regions, and bounded objectives. In particular, the bounce comparisons are exact.
Each stage LP has at most \(m+1\) variables and \(q+\tau+m+4\) inequalities, counting the probability-sum equality as two inequalities. Each bounce-test LP is no larger.
Let
\(R=\tau m+\tau+m+4,\qquad B=O\!\left(1+\tau m^2\log(m+1)\right).\)
A dense binary description of any LP used has length at most
\(H=O\!\left(R(m+1+B)\right).\)
There are at most
\(K(\tau+1)+1=O(\tau^2m)\)
LP solves, including one final feasibility LP that returns a lottery satisfying all final ceiling bounds. Constructing the class sets, updating the state, and performing rational comparisons also take polynomial time.
Consequently, a running-time bound in the requested parameters is
\(O(L)+O(\tau^2m)\,\operatorname{poly}\!\left((\tau m+\tau+m)\left(m+1+\tau m^2\log(m+1)\right)\right).\)
In particular, the running time is polynomial in \(m,\tau,L\), and the returned probabilities have polynomial binary encoding length.
No expansion of the masses into a population is needed. Under the specified unit-speed, shared-ceiling definition, changing the positive masses while preserving the support leaves the entire computation unchanged.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem: exact ESR computation is polynomial-time solvable in \(m,\tau,L\), with probabilities encoded as binary numerators and denominators. The argument is correct, including its termination and intermediate bit-length bounds. I found no major or minor mathematical issues.
The algorithm uses precisely the \(\tau\) supported rankings. Ignoring masses is justified by the task’s explicit dynamics: each supported type has one representative climbing at unit speed, independently of its mass.
The prover explicitly adopts rational encoding by binary numerators and denominators. This is the natural intended interpretation of the output requirement. Its warning about finite binary expansions is valid: probabilities such as \(1/3\) cannot have finite binary expansions. The convention is stated clearly and does not conceal a restriction on the intended problem.
The stage LP exactly represents the specified maximization. It includes the simplex constraints, every existing ceiling bound, each type’s current height constraint, and the time restriction \(0\leq\lambda\leq1-t\).
Initially, the ceiling-feasible polytope is the nonempty simplex, and all height bounds are zero. At subsequent stages, the asserted invariant makes \(\lambda=0\) feasible. Compactness follows from the simplex constraints and bounded \(\lambda\), so the optimum exists.
Updating each ceiling by the maximum of its previous value and all corresponding advanced heights imposes exactly the inequalities defining \(F\). This remains true when several types occupy the same subset: taking a maximum combines their lower bounds without adding their speeds.
Retained types satisfy their advanced height bounds throughout the updated polytope. Moved types have height zero, which follows from nonnegativity. Thus the induction is valid.
The set \(F\) is nonempty and compact. Consequently, each maximum \(\beta_i\) exists.
Every point of \(F\) already satisfies \(p(C_i)\geq h_i+\lambda^*\). Therefore \(\beta_i=h_i+\lambda^*\) is equivalent to equality for every feasible lottery, exactly as required by the definition. The prover correctly avoids inferring a bounce from equality at just one optimizer.
If no type bounces, the witnesses \(p^{(i)}\) exist by negating the universal equality and using the existing lower bounds.
Their average lies in \(F\). For each type \(j\), every summand satisfies its lower bound and the \(j\)-th summand satisfies it strictly. Since \(\tau\geq1\), the average has positive slack for every type.
There are finitely many types, and the remaining time slack is positive under \(\lambda^*<1-t\). Hence the stated positive \(\varepsilon\) exists and contradicts optimality. This argument also applies when \(\lambda^*=0\).
At departure, the bounce condition fixes the probability of the departed class throughout the updated ceiling-feasible polytope. Later ceiling-feasible polytopes are nested subsets because ceilings never decrease, so these equalities persist.
The identity
\[
\sum_{j<r}d_{ij}+h_i=t
\]
correctly accounts for every stage duration: heights accumulate elapsed time, and resetting transfers the accumulated height into the departure value. Zero-duration stages preserve the identity.
When a type occupies its last class, the partition of \(A\), normalization of the lottery, and persistent equalities give the stated identity
\[
p(C_i)=1-t+h_i.
\]
At a nonterminal stage, this is strictly greater than its advanced height. Such a type cannot bounce.
Every nonterminal stage therefore makes at least one valid forward move, and each type makes at most \(k_i-1\) moves. The bound
\[
K=\tau(m-1)+1
\]
follows, including the terminal stage. It excludes an infinite sequence of zero-duration stages. The case \(m=1\) is also covered: there are no possible moves and the stage is terminal.
The coefficient entries of the stage LP are indeed in \(\{-1,0,1\}\). If the state has common denominator \(D\), every right-hand side has denominator dividing \(D\), including \(1-t\).
A nonempty compact polytope has an optimal vertex. At a vertex, \(n=m+1\) linearly independent active constraints can be selected even when the feasible polytope is lower-dimensional. Thus the nonsingular integer system used by the prover is legitimate.
Cramer’s rule gives denominators dividing \(D|\det B|\). Hadamard’s bound is correctly applied: each row has Euclidean norm at most \(\sqrt n\), so
\[
1\leq|\det B|\leq n^{n/2}.
\]
Additions, resets, and ceiling maxima preserve divisibility by the chosen next denominator. Repeating the bound over at most \(K\) stages yields the stated polynomial bound on \(\log_2D\).
State values lie in \([0,1]\): time is capped at one, heights accumulate only elapsed time since their latest reset, and ceilings are maxima of such heights. Therefore the numerator bound is valid. The denominator argument concerns the optimal value and does not require the LP solver itself to return a vertex.
The prover states the needed standard theorem: explicitly represented rational LPs admit polynomial-time feasibility and finite optimization with exact rational outputs, including lower-dimensional feasible regions. Its hypotheses hold here: the descriptions are rational and polynomial in size, feasible regions are nonempty, and objectives are bounded.
The cited [Vishnoi notes, Section 1](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf) explicitly discuss conversion to exact rational optimization. The cited [Aziz–Stursberg paper](https://ojs.aaai.org/index.php/AAAI/article/download/8796/8655) contains the stated LP approach and polynomial-time theorem. The distribution-specific stage and bit bounds are established in the submitted argument itself.
The stage constraint count is correct: \(q\) ceiling inequalities, \(\tau\) height inequalities, \(m\) nonnegativity inequalities, two inequalities for normalization, and two bounds on \(\lambda\).
The description-length bound accounts for both the coefficient matrix and polynomial-sized rational right-hand sides. The number of LP solves is at most \(K(\tau+1)+1\), hence \(O(\tau^2m)\). Input processing, state updates, and exact comparisons have polynomial cost.
The final feasibility LP returns precisely a lottery satisfying all final ceilings, with polynomial-length exact rational coordinates. Thus the claimed running time and output guarantee follow.
No repair or additional clarification is needed under the explicitly stated rational encoding.
⟨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.