Answer: Admits an FPTAS for computing a \((1+\varepsilon)\)-approximate equilibrium.
Theorem 8 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is a FPTAS to compute a (1 + ϵ)- approximate equilibrium in the Uniform-2-FLG.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite host graph, \(k\) facilities, rational masses \(d_t\) of customer types with reachability ranges \(R_t\), and \(\varepsilon > 0\), output a facility placement \(s\) such that every facility's uniformly captured mass is within factor \(1+\varepsilon\) of its best unilateral deviation.
Let \(H=(V,E)\) be a finite directed host graph with \(m=|V|\geq1\), and let \(k\geq1\) facilities each choose any vertex; co-location is allowed.
A society is given by its support: a list of \(\tau\geq1\) customer types, each with an explicitly listed nonempty reachability range \(R_t\subseteq V\) and positive binary rational mass \(d_t\). Here \(\tau\) is the support size, not the number of possible types; masses need not sum to \(1\).
For a placement \(s\in V^k\), set \(c_t(s)=|\{j:s_j\in R_t\}|\). Type \(t\) divides its mass equally among these facilities when \(c_t(s)>0\), and contributes nothing when \(c_t(s)=0\).
Facility \(j\) maximizes its captured mass \(u_j(s)=\sum_{t:s_j\in R_t}d_t/c_t(s)\). After a deviation, all shares are recomputed.
Given positive binary rational \(\varepsilon\), the required placement satisfies \(u_j(v,s_{-j})\leq(1+\varepsilon)u_j(s)\) for every facility \(j\) and every vertex \(v\in V\).
Does this mass problem admit an FPTAS with running time polynomial in \(m,\tau,k,L,1/\varepsilon\), where \(L\) is the total input bit length, or is computing such a placement NP-hard for some fixed rational \(\varepsilon>0\)?
For finite weighted clients whose ranges are closed outgoing neighborhoods, an FPTAS for the same approximation guarantee is known; computing an exact equilibrium is PLS-complete. [Source](https://arxiv.org/html/2211.14016#S5).
No separately stated result for the arbitrary-range mass formulation was verified; the known model already permits rational client weights.
The arbitrary-range mass problem admits an FPTAS. The algorithm below takes at most
\(\left\lceil k^2 h_k(1+1/\varepsilon)\right\rceil\)
best-response moves, where \(h_k=\sum_{\ell=1}^k1/\ell\), and uses exact rational arithmetic of polynomial bit length.
The cited paper establishes the neighborhood version in Theorem 8. Here is a self-contained proof for the explicitly listed arbitrary ranges. [Source, Section 5](https://arxiv.org/html/2211.14016#S5).
Set \(h_0=0\) and \(h_r=\sum_{\ell=1}^r1/\ell\) for \(r\geq1\). Define
\(\Phi(s)=\sum_{t=1}^{\tau}d_t h_{c_t(s)}\).
We claim that whenever facility \(j\) changes its location from \(a=s_j\) to \(b\), producing \(s'=(b,s_{-j})\),
\(\Phi(s')-\Phi(s)=u_j(s')-u_j(s)\).
To prove this, consider each type separately.
Summing proves the identity, including the cases where a type becomes covered or uncovered.
For each vertex, define its accessible mass by
\(W(v)=\sum_{t:v\in R_t}d_t\), and put \(M=\max_{v\in V}W(v)\).
Because at least one type exists, every range is nonempty, and every mass is positive, \(M>0\).
Let \(C(s)=\sum_{t:c_t(s)>0}d_t\) be the covered mass. Since every covered type has \(c_t(s)\geq1\),
\(\displaystyle C(s)\leq\sum_t d_t c_t(s)=\sum_{j=1}^kW(s_j)\leq kM.\)
Also, \(c_t(s)\leq k\), so
\(\displaystyle 0\leq\Phi(s)\leq h_k C(s)\leq kMh_k.\)
Next, fix any facility \(j\) and any placement of its opponents. Let
\(B_j(s)=\max_{v\in V}u_j(v,s_{-j})\)
be its best-response payoff.
Choose \(v^\star\) with \(W(v^\star)=M\). If facility \(j\) moves there, every type whose range contains \(v^\star\) shares its mass among at most \(k\) facilities. Thus
\(\displaystyle B_j(s)\geq u_j(v^\star,s_{-j})\geq\sum_{t:v^\star\in R_t}\frac{d_t}{k}=\frac{M}{k}.\)
This holds for every opponent placement. Co-location being allowed ensures that \(v^\star\) is always available.
Start from any placement. Repeatedly:
At termination, every facility and vertex satisfy
\(u_j(v,s_{-j})\leq B_j(s)\leq(1+\varepsilon)u_j(s)\),
which is exactly the required guarantee.
For any executed move, abbreviate \(B=B_j(s)\) and \(u=u_j(s)\). The strict improvement test implies
\(\displaystyle B-u>B-\frac{B}{1+\varepsilon}=\frac{\varepsilon}{1+\varepsilon}B\geq\frac{\varepsilon M}{(1+\varepsilon)k}.\)
By the exact-potential identity, this is also a lower bound on the potential increase.
Consequently, if \(N>0\) moves occur, then
\(\displaystyle N\frac{\varepsilon M}{(1+\varepsilon)k}<\Phi(s^{(N)})-\Phi(s^{(0)})\leq kMh_k.\)
Cancelling \(M>0\) gives
\(\displaystyle N<k^2h_k\frac{1+\varepsilon}{\varepsilon}=k^2h_k(1+1/\varepsilon).\)
An infinite execution is impossible, because a sufficiently long finite prefix would violate this bound. Since \(h_k\leq1+\ln k\), the move count is polynomial in \(k\) and \(1/\varepsilon\).
Using best responses is essential to this bound: the uniform lower bound applies to their payoffs, and need not hold for an arbitrary improving destination.
Precompute the membership indicators \(A_{t,v}\), equal to \(1\) when \(v\in R_t\) and \(0\) otherwise. For a candidate move of facility \(j\) to \(v\), the recomputed count is
\(\displaystyle c'_t=c_t(s)-A_{t,s_j}+A_{t,v}.\)
Its payoff is therefore
\(\displaystyle u_j(v,s_{-j})=\sum_{t:A_{t,v}=1}\frac{d_t}{c'_t}.\)
Every denominator appearing here lies between \(1\) and \(k\). A complete scan of all facilities and destinations uses \(O(km\tau)\) arithmetic operations.
Write \(d_t=p_t/q_t\), with positive integers \(p_t,q_t\), and use the common denominator
\(\displaystyle Q=k!\prod_{t=1}^{\tau}q_t.\)
For every possible positive count \(c\leq k\), \(q_tc\) divides \(Q\). Thus every payoff is represented exactly as an integer divided by \(Q\).
The bit length of \(Q\) is \(O(L+k\log(k+1))\). Every payoff is at most \(D=\sum_t d_t\), and \(D\leq\tau 2^L\); hence its numerator under denominator \(Q\) has bit length
\(O(L+k\log(k+1)+\log\tau)\).
If \(\varepsilon=a/b\), the improvement test between integer payoff numerators \(X\) and \(Y\) becomes \(bX>(a+b)Y\). It is therefore an exact integer comparison of polynomial bit complexity.
Combining the polynomial cost per scan with the move bound proves a running time polynomial in \(m,\tau,k,L,1/\varepsilon\). No normalization, expansion into unit-weight customers, or neighborhood restriction is required.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: the arbitrary-range mass formulation admits an FPTAS with the requested dependence on \(m,\tau,k,L,1/\varepsilon\). No major or minor mathematical issues were found.
The algorithm operates directly on the explicitly listed ranges \(R_t\) and rational masses \(d_t\). It does not assume that ranges are neighborhoods, that masses sum to one, or that customers can be expanded into unit-weight clients. Thus it addresses the formulation in USER_TASK.
The bibliographic statement is accurate: Theorem 8 states an FPTAS for computing a \((1+\varepsilon)\)-approximate equilibrium in the neighborhood-based Uniform-\(2\)-FLG. The paper defines rational client weights and the facility strategy space as \(V^k\). [Source, model and Section 5](https://arxiv.org/html/2211.14016#S5).
The prover does not apply that theorem to arbitrary ranges; it supplies an independent argument. Consequently, no unverified transfer of the theorem’s hypotheses is involved.
The proposed potential
\(\Phi(s)=\sum_t d_t h_{c_t(s)}\)
is well-defined because \(0\leq c_t(s)\leq k\) and \(h_0=0\).
The four membership cases are exhaustive and correct:
Summing these contributions establishes
\(\Phi(s')-\Phi(s)=u_j(s')-u_j(s)\).
The argument includes transitions between covered and uncovered types, and also permits a candidate destination equal to the current location.
The definition \(M=\max_v W(v)\) is valid because \(V\) is finite and nonempty. Positivity of the masses and nonemptiness of at least one range imply \(M>0\).
Each covered type has \(c_t(s)\geq1\), so
\(C(s)\leq\sum_t d_t c_t(s)\).
The identity
\(\sum_t d_t c_t(s)=\sum_j W(s_j)\)
correctly counts one contribution for each facility belonging to each type’s range. Co-located facilities are counted individually, as required.
Since every \(W(s_j)\leq M\), this gives \(C(s)\leq kM\). Monotonicity of the harmonic sums then gives
\(0\leq\Phi(s)\leq h_k C(s)\leq kMh_k\).
All constants and inequality directions are correct.
For every facility and every opponent placement, a vertex maximizing \(W(v)\) is an admissible destination. This uses the stated permission for co-location.
After moving there, every type containing that vertex has a positive count at most \(k\). Its contribution to the deviator is therefore at least \(d_t/k\). Summing proves
\(B_j(s)\geq M/k\).
The bound is uniform over facilities and opponent placements. It requires neither coverage of all types nor positivity of the facility’s current payoff.
For an executed move, \(B>(1+\varepsilon)u\) implies
\(B-u>\varepsilon B/(1+\varepsilon)\).
Combining this with \(B\geq M/k\) and the exact-potential identity gives the claimed strict lower bound
\(\varepsilon M/((1+\varepsilon)k)\)
on each potential increase.
Summing over any positive number \(N\) of moves and applying the global potential bound yields
\(N<k^2h_k(1+1/\varepsilon)\).
Cancellation of \(M\) is justified by \(M>0\). The finite-prefix argument rules out an infinite execution without assuming termination in advance.
The advertised ceiling bound is valid, though slightly weaker than the strict inequality. The estimate \(h_k\leq1+\ln k\) establishes polynomial dependence for every \(k\geq1\).
Upon termination, the absence of a strict threshold violation gives
\(B_j(s)\leq(1+\varepsilon)u_j(s)\)
for every facility. Since every candidate payoff is at most its best-response payoff, this is exactly the required guarantee. Equality at the threshold is correctly allowed.
The formula
\(c'_t=c_t(s)-A_{t,s_j}+A_{t,v}\)
correctly removes the deviator’s old membership and inserts its new membership.
Whenever \(A_{t,v}=1\), the resulting count satisfies \(1\leq c'_t\leq k\). Thus the payoff formula never divides by zero. Scanning all facility-destination pairs takes \(O(km\tau)\) arithmetic operations.
For \(Q=k!\prod_t q_t\), every \(q_tc\) with \(1\leq c\leq k\) divides \(Q\). Consequently, all candidate and current payoffs have exact integer representations over this fixed denominator.
The stated bound on the bit length of \(Q\) is correct. The payoff bound \(u_j\leq D\leq\tau2^L\) also correctly bounds numerator lengths. These bounds depend on input sizes, rather than on the number of preceding moves, so repeated updates cause no uncontrolled arithmetic growth.
With \(\varepsilon=a/b\), the comparison \(bX>(a+b)Y\) exactly implements the improvement test. Its operands have polynomial bit length. Together with the move bound and the final terminating scan, this establishes the requested polynomial running time.
The proof accommodates \(m=1\), \(k=1\), \(\tau=1\), duplicate ranges, vertices outside every range, uncovered types, zero current facility utility, and arbitrary positive rational \(\varepsilon\). No normalization assumption is used.
No additional lemma, hypothesis, computation, or clarification is needed to make the argument verifiable.
⟨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.