By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

Deterministic quasipolynomial-time mean-payoff games

A uniform deterministic algorithm computes the exact zero-threshold winning set U={v∈V:∃ Max strategy σ ∀ Min strategies τ, MPw(πv,σ,τ)≥0}U = \{v \in V : \exists \text{ Max strategy } \sigma \ \forall \text{ Min strategies } \tau,\ \mathrm{MP}_w(\pi_{v,\sigma,\tau}) \ge 0\} for any finite mean-payoff game with arbitrary signed integer edge weights encoded in binary, using at most 2C(log⁡2(L+2))22^{C(\log_2(L+2))^2} bit operations for an absolute constant C>0C > 0, where LL is the complete explicit input length.

For the box solution hh in [0,D0]V[0, D_0]^V with D0=min⁡{2d:d∈Z≥0, 2d≥64(n+1)(W+1)}D_0 = \min\{2^d : d \in \mathbb{Z}_{\ge 0},\ 2^d \ge 64(n+1)(W+1)\}, the sets Vlo={i:hi≤nW}V_{\mathrm{lo}} = \{i : h_i \le nW\} and Vhi={i:hi≥D0−nW}V_{\mathrm{hi}} = \{i : h_i \ge D_0 - nW\} partition VV, and there exist positional strategies for Max on VhiV_{\mathrm{hi}} and Min on VloV_{\mathrm{lo}} guaranteeing original mean payoff at least 00 and upper limiting average at most −1/n-1/n, respectively, against arbitrary history-dependent opposition.

For every valid input (A,D,a,b)(A, D, a, b) with A∈ZVA \in \mathbb{Z}^V, dyadic D=2dD = 2^d, and a,b∈Q>0Va, b \in \mathbb{Q}_{>0}^V, the procedure Label(A,D,a,b)\mathrm{Label}(A, D, a, b) terminates and returns a vector in {+,−}V\{+, -\}^V assigning ++ to every index claimed by any Max witness and −- to every index claimed by any Min witness.

For any input (A,D,a,b)(A, D, a, b) with D≥4096D \ge 4096, integral pivot c−M≤k≤c+Mc - M \le k \le c + M, and r∈{q,D/2}r \in \{q, D/2\}, translating and clipping a relevant Max witness xx to [k−r/2,k+r/2][k - r/2, k + r/2] produces an integer subsolution x′x' with support Sx′={i:gix(k)<r}⊆SxS_{x'} = \{i : g_i^x(k) < r\} \subseteq S_x that claims every ii with gix(k)≤r/32g_i^x(k) \le r/32 whenever a′(Sx′)≤1a'(S_{x'}) \le 1 (and dually for Min witnesses).

The procedure Label(A,D,a,b)\mathrm{Label}(A, D, a, b) terminates on every valid input, and every child of a nonbase call has strictly smaller rank R=d+B(μ(a,b))R = d + B(\mu(a, b)), where the provisional child in Step 5 is the only child that preserves BB while every other child decreases BB by at least one.

The complete main computation makes at most ∑ℓ=0H∑j=0min⁡(ℓ,B0)(ℓj)sj≤(H+1)(B0+1)(1+Hs)B0\sum_{\ell=0}^{H} \sum_{j=0}^{\min(\ell, B_0)} \binom{\ell}{j} s^j \le (H+1)(B_0+1)(1+Hs)^{B_0} calls, which is 2O((log⁡2(L+2))2)2^{O((\log_2(L+2))^2)} calls, and the total bit-operation count including preprocessing, exact arithmetic, recursion, and output is 2C(log⁡2(L+2))22^{C(\log_2(L+2))^2}.

A uniform deterministic algorithm returns the exact value valw(v)\mathrm{val}_w(v) as a reduced rational for every v∈Vv \in V and globally optimal positional strategies σ⋆\sigma^\star for Max and τ⋆\tau^\star for Min against arbitrary history-dependent strategies in 2O((log⁡2(L+2))2)2^{O((\log_2(L+2))^2)} bit operations.

A uniform randomized algorithm returns all exact values and both globally optimal positional strategies specified in Corollary 7.1 with probability at least 7/87/8 for the entire output, running in 2O((log⁡2(L+2))2)2^{O((\log_2(L+2))^2)} bit operations on every random tape.

Uniform deterministic algorithms decide whether (v,c)(v, c) is energy-winning (and return a winning positional Max policy on a positive answer) in 2O((log⁡2(Lc+2))2)2^{O((\log_2(L_c+2))^2)} bit operations, and compute the exact minimum winning credit cmin⁡(v)∈Z≥0∪{∞}c_{\min}(v) \in \mathbb{Z}_{\ge 0} \cup \{\infty\} (and a winning positional Max policy when finite) in 2O((log⁡2(L+2))2)2^{O((\log_2(L+2))^2)} bit operations.

Feasibility of explicit rational tropical inequality systems (including all-finite feasibility, max-atom systems, and maximal finite-coordinate support for homogeneous systems) is decidable deterministically in 2O((log⁡(L+2))2)2^{O((\log(L+2))^2)} bit operations, and for each fixed integer k≥0k \ge 0, deciding whether an explicit m×nm \times n matrix (m≥n≥1m \ge n \ge 1) over Q∪{−∞}\mathbb{Q} \cup \{-\infty\} has tropical rank at least n−kn - k takes 2Ok((log⁡(L+2))2)2^{O_k((\log(L+2))^2)} bit operations.

Methods

Integer cycle perturbation w^(e)=(n+1)w(e)+1\widehat{w}(e) = (n+1)w(e) + 1 and finite-box clipped operator TA,u(z)=min⁡{u,max⁡{A,F(z)}}T_{A,u}(z) = \min\{u, \max\{A, F(z)\}\} to eliminate zero simple-cycle sums while separating negative original cycle sums from nonnegative ones.

Source excerpts

“Following the integer cycle perturbation of Björklund and Vorobyov [5, Section 9], put w^(e) = (n + 1)w(e) + 1, W = max_{e∈E} |w^(e)|.” · Show in paper

“There is a unique h ∈ [A, u] that is both a subsolution and a supersolution. It is precisely the unique fixed point of TA,u(z) = min{u, max{A, F(z)}}.” · Show in paper

Deterministic simultaneous labelling recursion `Label(A, D, a, b)` using downward and upward pivot passes with narrow width-qq calls, a provisional width-D/2D/2 call for mass reweighting, and a continuation call with overrides on I−I_- and I+∖I−I_+ \setminus I_-.

Source excerpts

“Procedure 4.1 (Label(A, D, a, b)). Set u = A + D and P = D/32. Execute the first applicable base case; if neither applies, proceed through Steps 3–6.” · Show in paper

“5. Provisional labels and new masses. Make one centered width-D/2 call at k^f with masses (a, b). ... 6. Continuation and overrides. Call Label(A, D, a¯, ¯b). In that child’s output put − on I− and + on I+ \ I−, leaving every other label unchanged.” · Show in paper

Exact rational value reconstruction via KK-step bisection on [−Win,Win][-W_{\mathrm{in}}, W_{\mathrm{in}}] using threshold queries wp/q(e)=qw(e)−pw_{p/q}(e) = qw(e) - p, followed by separate value-preserving strategy self-reductions for Max and Min.

Source excerpts

“For integers p and q > 0, replace each weight by wp/q(e) = qw(e) − p. ... Choose K = 1 + ⌈log2(2(Win + 1)n^2)⌉, computable from integer bit lengths. For each vertex, start with the closed interval [−Win, Win] and make K bisections.” · Show in paper

“At a vertex u, form a trial He for each outgoing edge e by keeping only e at u. Keep a trial for which Values(He) = v, and continue from that trial.” · Show in paper

Reset-game construction Rv,cR_{v,c} reducing fixed-credit energy-winning to zero-threshold mean-payoff winning, combined with binary search over [0,(n−1)Win][0, (n-1)W_{\mathrm{in}}] for minimum winning credits.

Source excerpts

“For the fixed pair (v, c) construct a mean-payoff game Rv,c. Replace every u ∈ V by an entry u_in owned by Min and an exit u_out owned by the original owner of u.” · Show in paper

“Binary search with a formal losing lower endpoint ℓ = −1 and the known winning upper endpoint h = H. While h − ℓ > 1, query ⌊(ℓ + h)/2⌋ by Equation (8.2) and replace the endpoint having the same answer.” · Show in paper

Denominator scaling, −∞-\infty preprocessing, and homogenization to reduce tropical inequality feasibility and fixed-corank tropical rank tests to zero-threshold mean-payoff games.

Source excerpts

“Let Q be the product of the positive denominators of the finite input coefficients, taking Q = 1 when there are none. ... To obtain a total game, apply the preprocessing of [1, Section 2.1].” · Show in paper

“After scaling, append c to A and d to B as a new column, and introduce one coordinate t.” · Show in paper