Answer: Polynomial-time solvable: an exact optimal equilibrium-stable pair, or a certificate that none exists, can be found in time polynomial in \(\tau\) and \(L\).
Theorem 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet µ be a probability measure and let ⃗q be the capacity vector. Given δ > 0, let ⃗yδ be the vector containing the positions returned by Algorithm 1. Then, W(⃗yδ) −min⃗y s.t. |Fµ(y2)−Fµ(y1)|≥q1+q2 W(⃗y) ≤δ. Numerical Experiments In this section, we run numerical experiments to validate our theoretical findings.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given tau\ locations \(x_t\in[0,1]\) with positive rational masses \(mu_t\) summing to \(1\), and rational capacities \(q_1ge q_2>0\) with \(Q=q_1+q_2<1\), choose percentile parameters \(p_1,p_2\in[0,1]\) satisfying \(p_2-p_1ge Q\), placing facilities at \(y_j=F_mu^{-1}(p_j)\). Define FCFS service and equilibrium stability when a cutoff divides a location’s mass, then determine the complexity, in \(tau\), input bit length, and approximation tolerance delta, of finding a stable pair with welfare at least \(mathrm{OPT}_mu-delta\), where \(mathrm{SW}_mu=Q-sum_{j=1}^2int_{B_{mu,q_j}(y_j)}|x-y_j|\,dmu(x)\) and boundary mass may be split fractionally.
A society is given by its support: \(\mu=\sum_{t=1}^{\tau}\mu_t\delta_{x_t}\), with distinct binary-rational locations \(x_t\in[0,1]\), positive binary-rational masses \(\mu_t\), and \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m=2\) facilities, with binary-rational capacities \(q_1\ge q_2>0\) and \(Q=q_1+q_2<1\); the tolerance \(\delta>0\) is binary rational, and \(L\) is the total input bit length.
Define \(F_\mu(z)=\mu([0,z])\) and \(F_\mu^{-1}(p)=\inf\{z\in[0,1]:F_\mu(z)\ge p\}\) for \(p>0\), with \(F_\mu^{-1}(0)=\min_t x_t\). Choose rational percentiles \(0\le p_1\le p_2\le1\) satisfying \(p_2-p_1\ge Q\), and place facility \(j\) at \(y_j=F_\mu^{-1}(p_j)\).
Represent the mass at each location by a continuum of individuals with distinct labels, using increasing location followed by increasing label as a fixed common priority order. In FCFS, each individual chooses one facility; each facility serves its closest applicants up to capacity, breaking distance ties by this priority. A cutoff may divide an atom, but each individual is served by at most one facility. Service gives utility \(1-|x-y_j|\); rejection gives zero.
An equilibrium is a measurable strategy profile in which almost every individual has no strictly profitable switch: admission after a switch occurs if capacity is unused or the individual precedes the admission cutoff in distance and priority. A pair is equilibrium stable if equilibria exist and all equilibria have the same integrated utility.
Let \(B_{\mu,q}(y)\) denote mass \(q\) selected in increasing distance from \(y\), taking all mass strictly inside the smallest sufficient radius and only the necessary boundary mass; equal-distance boundary choices have identical distance cost. Define \(\mathrm{SW}_\mu(p_1,p_2)=Q-\sum_{j=1}^{2}\int_{B_{\mu,q_j}(y_j)}|x-y_j|\,d\mu(x)\), with these integrals interpreted fractionally. Let \(\mathrm{OPT}_\mu\) be its supremum over equilibrium-stable pairs satisfying the percentile constraint.
Can one find an equilibrium-stable pair with \(\mathrm{SW}_\mu\ge\mathrm{OPT}_\mu-\delta\), or determine that no feasible pair exists, in time polynomial in \(m=2\), \(\tau\), \(L\), and \(\delta^{-1}\); or is achieving this additive guarantee NP-hard?
For finite agents, equilibrium stability means that all pure Nash equilibria have equal social welfare, and percentile mechanisms have a rank-separation characterization ([Auricchio–Clough–Zhang, 2024](https://proceedings.mlr.press/v244/auricchio24a.html)).
For absolutely continuous societies, a spatial search is claimed to achieve additive error \(\delta\) using \(O(\delta^{-2})\) comparisons; this is an asymptotic distributional result, not a finite-agent algorithm or a bit-complexity result for atomic rational societies ([Auricchio–Zhang, 2026](https://ojs.aaai.org/index.php/AAAI/article/view/38706/42668)).
The problem is polynomial-time solvable. In fact, one can find an exact maximizer of the stated objective over all feasible equilibrium-stable pairs, or certify that no such pair exists, in time polynomial in \(\tau\) and \(L\). Thus the running time need not depend on \(\delta^{-1}\).
The proof analyzes the atomic continuum game directly. It does not transfer the distributional search theorem to atoms: the cited [Auricchio–Zhang paper](https://ojs.aaai.org/index.php/AAAI/article/view/38706/42668) explicitly assumes absolute continuity.
Sort the support so that \(x_1<\cdots<x_\tau\), and define cumulative masses
\(C_0=0\) and \(C_i=\sum_{t=1}^{i}\mu_t\).
The percentiles placing a facility at \(x_i\) form the interval
Consequently, every admissible percentile pair produces a location pair \((x_i,x_k)\) with \(i\le k\). Both equilibrium stability and the stated objective depend only on these locations, not on the particular percentiles realizing them.
We can determine exactly which location pairs satisfy the percentile constraint.
Lemma 1. For \(i\le k\), there exist rational \(p_1\in I_i\) and \(p_2\in I_k\) satisfying \(p_2-p_1\ge Q\) precisely when
Proof. If \(i=1\), the largest possible separation is \(C_k\), attained by \(p_1=0\), \(p_2=C_k\).
If \(i>1\), every permitted pair satisfies
\(p_2-p_1<C_k-C_{i-1}\), proving necessity. Conversely, suppose \(D=C_k-C_{i-1}-Q>0\). Set
\(\varepsilon=\frac12\min\{\mu_i,D\}\),
\(p_1=C_{i-1}+\varepsilon\), and \(p_2=C_k\).
Then \(p_1\in I_i\), \(p_2\in I_k\), and
\(p_2-p_1=Q+D-\varepsilon\ge Q\).
These witnesses have polynomial bit length. ∎
Thus the remaining issue is deciding equilibrium stability for one fixed location pair. We next give an exact polynomial-time procedure for that decision.
Fix facility locations \(y_1,y_2\). Represent the individuals at \(x_t\) by labels \(\lambda\in[0,\mu_t)\), with Lebesgue measure. The population is the disjoint union
\(\Omega=\bigsqcup_{t=1}^{\tau}\bigl(\{t\}\times[0,\mu_t)\bigr)\).
An individual \((t,\lambda)\) has service utility
\(u_{tj}=1-|x_t-y_j|\ge0\)
at facility \(j\).
Facility \(j\)'s admission order is lexicographic in
\((|x_t-y_j|,x_t,\lambda)\).
Indeed, distance comes first, followed by the stipulated common priority order.
Let \(\rho_j(t)\) denote the position of support location \(t\) in the ordering by \((|x_t-y_j|,x_t)\).
For each facility we consider two kinds of descriptions.
Full mode. Choose a cutoff location \(c_j\) and a label threshold
\(a_j\in[0,\mu_{c_j}]\). Define the population prefix
\(E_j=\{(t,\lambda):\rho_j(t)<\rho_j(c_j)\}\cup \{(c_j,\lambda):\lambda<a_j\}\).
We require that facility \(j\) serve exactly \(q_j\) mass, that all its served applicants belong to \(E_j\), and that all its rejected applicants lie outside \(E_j\).
Open mode. Set \(E_j=\Omega\). Require that facility \(j\) reject no applicants and serve at most \(q_j\) mass.
The open mode deliberately permits equality with capacity. This makes its constraints closed; the equilibrium restrictions below remain sufficient even in that case.
All assertions about individuals and interval endpoints are understood almost everywhere.
Lemma 2.
Proof. If a facility has unused capacity, it serves every applicant, and a switching individual can be admitted. Open mode describes this situation.
If a facility is full, FCFS selects an initial segment of its applicants in the admission order. Its cutoff therefore specifies an initial segment of the entire population order. Because there are finitely many support locations, this population prefix consists of whole preceding locations and a label prefix at one cutoff location.
More explicitly, choose the last location in the facility’s order containing positive served mass, and take the essential supremum of the served labels there. FCFS implies that served applicants precede this cutoff and rejected applicants follow it, apart from null sets. This proves the first assertion.
For the second assertion, consider a full-mode description. All served applicants lie in the population prefix \(E_j\), and all rejected applicants lie after that prefix. Because the served mass is exactly \(q_j\), these served applicants are precisely the first \(q_j\) mass of applicants. The actual admission cutoff cannot lie after the nominated end of \(E_j\). Hence an individual preceding the actual cutoff belongs to \(E_j\).
For an open-mode description, the assertion holds because \(E_j=\Omega\). ∎
A nominated full-mode prefix may extend beyond the actual cutoff. This causes no difficulty: treating its whole prefix as available imposes stronger incentive restrictions, which will be sufficient for equilibrium. Conversely, an existing equilibrium is represented using its actual cutoff.
For each facility, choose open mode or full mode with a cutoff location. There are at most \((\tau+1)^2\) joint choices.
If both cutoff locations coincide, additionally choose one of the orders
\(a_1\le a_2\) or \(a_2\le a_1\).
Thus there are at most \(2(\tau+1)^2\) branches.
Within a branch, split each location’s label interval at every threshold occurring there. Call the resulting intervals cells. There are at most \(\tau+2\) cells: each of the at most two thresholds adds at most one cell.
For a cell \(h\), write \(t(h)\) for its support location and \(\ell_h\) for its length. Its length is an affine function of the threshold variables. For example, when both thresholds occur at one atom and \(a_1\le a_2\), the three lengths are
\(a_1\), \(a_2-a_1\), and \(\mu_t-a_2\).
On the interior of each cell, membership in each \(E_j\) is constant. Denote it by \(e_{hj}\in\{0,1\}\). These indicators are fixed by the branch. Zero-length cells and their endpoint conventions have no effect.
For each cell introduce four nonnegative variables:
Require the population identity
\(s_{h1}+s_{h2}+r_{h1}+r_{h2}=\ell_h\).
We now specify which categories are allowed.
For \(k\ne j\), allow \(s_{hj}\) only if
\(e_{hj}=1\),
and
\(e_{hk}=0\quad\text{or}\quad u_{t(h)j}\ge u_{t(h)k}\).
The first condition places served applicants inside their facility’s prefix. The second prevents a strictly profitable switch to the other facility whenever that facility is treated as available.
Allow \(r_{hj}\) only if
\(e_{hj}=0\),
and, for every \(k\in\{1,2\}\),
\(e_{hk}=1\ \Longrightarrow\ u_{t(h)k}=0\).
A rejected individual receives zero utility. These conditions ensure that every available facility offers zero utility, so there is no strictly profitable switch.
A forbidden category is enforced by setting its variable to zero. All category tests compare fixed rational numbers; none introduces a nonlinear constraint.
For a full-mode facility impose
\(\sum_h s_{hj}=q_j\).
For an open-mode facility impose
\(\sum_h s_{hj}\le q_j\).
Because an open-mode facility has \(e_{hj}=1\) on every cell, its rejected categories are automatically forbidden.
Finally, impose the threshold bounds and the branch’s threshold-order inequality. The resulting system is a rational linear program with \(O(\tau)\) variables and constraints.
Lemma 3. For the fixed locations, the equilibrium utility values are exactly the values of
\(U=\sum_h\sum_{j=1}^{2}u_{t(h)j}s_{hj}\)
over the feasible points of all the branch linear programs.
Proof: every feasible point produces an equilibrium.
Given a feasible point, partition each cell into measurable subintervals with the four prescribed category masses. Assign each individual the facility indicated by their category.
At a full-mode facility, all designated served applicants precede all designated rejected applicants, and their total mass is exactly its capacity. FCFS therefore produces the designated service outcome.
At an open-mode facility, there are no designated rejected applicants, and applicant mass does not exceed capacity. Again FCFS produces the designated outcome.
By Lemma 2, any switching individual who would be admitted at a facility belongs to its nominated set \(E_j\). The served-category restrictions therefore exclude every strictly profitable switch by a served individual. The rejected-category restrictions exclude every strictly profitable switch by a rejected individual, including cases of zero service utility.
The constructed profile is measurable and is an equilibrium almost everywhere. Its integrated utility is \(U\).
Proof: every equilibrium produces a feasible point.
Take an equilibrium. Use open mode at every facility with unused capacity and its actual cutoff at every full facility, as in Lemma 2. Choose the appropriate ordering branch if the two cutoffs occur at the same location.
Split the population into the resulting cells and record the masses of the four actual categories.
The population identities, nonnegativity conditions, and capacity constraints hold by construction. Served applicants belong to their own cutoff prefix; rejected applicants lie outside it.
For these actual cutoffs, membership in \(E_k\) means that a switch to facility \(k\) would gain admission, apart from null boundary sets. Thus equilibrium implies the stated utility inequality for every served category of positive mass. Likewise, a rejected category cannot have positive mass in a cell where an available facility offers positive utility.
Consequently, all forbidden categories have zero mass, giving a feasible point with the original equilibrium’s utility. ∎
This proof also handles a full facility with no rejected applicants. It belongs to a full-mode branch using its actual cutoff; completeness does not rely on the more restrictive open-mode description.
Each branch feasible region is closed and bounded. The thresholds lie in bounded intervals, and the category variables are nonnegative and sum to bounded cell lengths. Hence every nonempty branch is a compact rational polytope.
For every nonempty branch, minimize and maximize the linear objective \(U\). Define
\(U_{\min}=\min_{\text{nonempty branches}}\min U\),
\(U_{\max}=\max_{\text{nonempty branches}}\max U\).
By Lemma 3:
These are exact comparisons of rational values.
We use the standard rational linear-programming theorem: feasibility and linear optimization over an explicitly given rational polytope are solvable in polynomial bit complexity, with exact rational optimal solutions and values. Exact polynomial-time optimization for rational polyhedra is also stated in [Dadush–Végh–Zambelli](https://arxiv.org/abs/2606.11820).
Its hypotheses hold here: every branch is an explicitly described bounded polytope, its number of variables and constraints is \(O(\tau)\), and its coefficients have polynomial bit length in the original input. Therefore stability at fixed locations is decidable in polynomial time using \(O(\tau^2)\) linear programs.
The equilibrium utility \(U\) above is used to test stability. The optimization score is \(\mathrm{SW}_\mu\) exactly as defined in the question; the algorithm does not need to identify these two expressions.
For facility \(j\), sort the support locations by increasing distance \(d_{tj}=|x_t-y_j|\). Select mass greedily in that order until total selected mass is \(q_j\), dividing the final atom when necessary.
Writing the selected amounts as \(b_{tj}\), the cost is
\(\int_{B_{\mu,q_j}(y_j)}|x-y_j|\,d\mu(x)=\sum_t b_{tj}d_{tj}\).
This is exactly the required fractional integral. Equal-distance boundary choices have the same cost. Thus
\(\mathrm{SW}_\mu=Q-\sum_{j=1}^{2}\sum_t b_{tj}d_{tj}\)
is computable exactly by sorting and rational arithmetic in polynomial time.
The algorithm is:
There are \(O(\tau^2)\) location pairs and \(O(\tau^2)\) cutoff branches per pair, so the algorithm solves \(O(\tau^4)\) linear programs, each of polynomial encoding size. Its total bit complexity is polynomial in \(\tau\) and \(L\).
Finally, every allowed percentile pair produces one of the enumerated location pairs. Conversely, Lemma 1 supplies rational percentile witnesses for every retained pair. Since the objective and stability are constant for fixed locations, the possible feasible objective values form a finite set. Whenever this set is nonempty, its supremum is attained.
The returned pair therefore satisfies
\(\mathrm{SW}_\mu(p_1,p_2)=\mathrm{OPT}_\mu\),
and in particular
\(\mathrm{SW}_\mu(p_1,p_2)\ge\mathrm{OPT}_\mu-\delta\).
⟨structured verdict parsed — rendered above⟩
The claimed exact polynomial-time algorithm is verified. The cutoff representation and the linear programs correctly characterize equilibrium utility values under the admission rule in USER_TASK. No major or minor issues were found.
The inverse-CDF definition gives exactly the intervals \(I_1=[0,C_1]\) and \(I_i=(C_{i-1},C_i]\) for \(i>1\). In particular, the special definition at percentile zero is correctly incorporated.
For \(i=1\), the maximum separation is \(C_k\), and it is attained. For \(i>1\), every attainable separation is strictly smaller than \(C_k-C_{i-1}\), so the strict inequality in Lemma 1 is necessary.
The proposed witness also verifies sufficiency: its threshold satisfies \(0<\varepsilon\le\mu_i/2\) and \(\varepsilon\le D/2\). Therefore \(p_1\in I_i\) and \(p_2-p_1\ge Q\). This argument includes coincident facility locations, \(i=k\). All witness arithmetic has polynomial bit length.
Stability and the stated objective depend only on facility locations, so enumerating these location pairs loses no admissible solution.
The admission ordering \((|x_t-y_j|,x_t,\lambda)\) matches the specified distance ordering and common priority.
A full facility serves positive mass because \(q_j>0\). Consequently, the last support location containing positive served mass exists. Taking the essential supremum of its served labels supplies the stated cutoff, with endpoint discrepancies confined to null sets. FCFS ordering ensures that served applicants precede rejected applicants.
Lemma 2’s sufficiency direction also holds: when exactly \(q_j\) served mass lies inside a nominated prefix, the actual cutoff cannot lie beyond that prefix. Thus admitting a switching individual requires membership in the nominated prefix, almost everywhere.
The distinction between nominated and actual cutoffs is handled correctly. A larger nominated prefix can impose stronger incentive restrictions, but it cannot permit a profitable deviation omitted by the constraints.
Each facility has one open-mode choice or one of \(\tau\) cutoff-location choices. Two thresholds at the same location require the additional ordering branch described in the output. The branch count is therefore at most \(2(\tau+1)^2\).
Two thresholds create at most two additional cells, giving at most \(\tau+2\) cells. Within each branch, cell lengths are affine functions of the thresholds, and prefix membership is fixed on cell interiors.
Threshold endpoints, coincident thresholds, and zero-length cells introduce no missing population mass or incentive condition. The population identities force every category variable in a zero-length cell to vanish.
A served individual can profitably switch only to the other facility, only when admitted there, and only when its service utility is strictly larger. The served-category inequalities exclude precisely this possibility whenever the nominated prefix treats that facility as available. Equality of utilities correctly remains permissible.
A rejected individual has utility zero. Its permitted categories require every facility treated as available to offer zero service utility. Hence no strictly profitable switch is possible. The condition placing rejected applicants outside their own prefix also correctly enforces the designated service outcome.
The open-mode equality case is safe. Even if applicant mass equals capacity, treating the entire population as potentially available strengthens the incentive restrictions. Completeness does not depend on using open mode for such a facility.
For a feasible LP point, measurable partitions with the prescribed category masses exist within every cell. At a full facility, every designated served applicant precedes every designated rejected applicant, and served mass equals capacity. FCFS therefore realizes the designated categories. At an open facility, all applicants are served because their total mass does not exceed capacity.
Lemma 2 and the category restrictions then exclude strictly profitable switches almost everywhere. The integrated utility equals the LP objective.
Conversely, an equilibrium represented by its actual cutoffs satisfies all population and capacity constraints. For an individual switching from the other facility, membership before an actual full-facility cutoff gives admission under the task’s explicit rule; unused capacity gives admission in open mode. Equilibrium therefore forces the prescribed utility comparisons. Forbidden categories have zero mass.
The proof thus establishes equality of the sets of attainable utility values, rather than merely an LP relaxation.
Every branch region is closed and bounded: thresholds are bounded, and nonnegative category variables sum to bounded cell lengths. Nonempty regions therefore attain both utility extrema.
By Lemma 3, the global minimum and maximum equal the extrema over all equilibria. Existence plus equality of these extrema is exactly the task’s stability definition.
The invoked rational linear-programming theorem applies to explicitly encoded rational systems and rational linear objectives, allowing exact feasibility and optimization in polynomial bit complexity. Here the dimensions and constraint counts are \(O(\tau)\), and all coefficients have polynomial bit length. Lower-dimensional and degenerate branches pose no additional hypothesis requirement. The cited [Dadush–Végh–Zambelli paper](https://arxiv.org/abs/2606.11820) also supports exact polynomial-time optimization for rational data.
Multiplying the number of location pairs by the number of branches gives \(O(\tau^4)\) LPs. Exact comparisons of their rational optimal values remain polynomial-time operations.
Greedy selection by distance computes each prescribed fractional nearest-mass integral. Equal-distance choices have identical cost, and each capacity is smaller than total population mass.
The output correctly distinguishes equilibrium utility, used to test stability, from the separately defined optimization score. USER_TASK does not require these expressions to coincide.
Every feasible percentile pair corresponds to an enumerated location pair, and every retained location pair has rational percentile witnesses. Consequently, the feasible objective values form a finite set. If nonempty, that set has a maximum equal to the stated supremum. The returned pair therefore achieves the exact optimum and satisfies every positive additive tolerance.
The contextual assertion about absolute continuity is also supported by the cited paper’s explicit assumptions. No transfer of that result to atomic societies is used. See [Auricchio–Zhang, Basic Assumptions](https://ojs.aaai.org/index.php/AAAI/article/view/38706/42668).
No additional 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.