Paper deep dive
Distributed Algorithms for $α$-Potential Functions in General-Sum Games
Yifei Chen, Chinmay Maheshwari
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 10/6/2026, 9:56:08 AM
Summary
This paper addresses the distributed computation of the tightest alpha-potential approximation for general-sum games with continuous action spaces. The authors propose a two-level framework: a global outer search over finite deviation tuples and a distributed inner oracle for convex optimization over potential parameters. They develop a tailored primal-dual inner oracle that ensures uniform one-sided accuracy and combine it with global search methods like EXOTIC and projected zeroth-order ascent to balance accuracy and computational cost.
Entities (10)
Relation Signals (6)
Yifei Chen → affiliatedwith → Johns Hopkins University
confidence 99% · Yifei Chen is with the Department of Applied Mathematics and Statistics, Johns Hopkins University
Chinmay Maheshwari → affiliatedwith → Johns Hopkins University
confidence 99% · Chinmay Maheshwari is with the Department of Electrical and Computer Engineering, Johns Hopkins University
EXOTIC → combinedwith → primal-dual inner oracle
confidence 96% · This oracle can be combined with global outer search [EXOTIC] to obtain an end-to-end guarantee
primal-dual inner oracle → usedfor → finite-tuple reformulation
confidence 95% · We develop a primal--dual inner oracle tailored to this structure [finite-tuple reformulation]
projected zeroth-order ascent → alternativeto → EXOTIC
confidence 94% · We also develop a projected zeroth-order outer method as a computationally lighter alternative
finite-tuple reformulation → solves → general-sum games
confidence 93% · We study the problem of computing the tightest \(\alpha\)-potential approximation of a general-sum game... we use an exact finite-tuple reformulation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the problem of computing the tightest \(\alpha\)-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each player has access only to its own utility function. The difficulty is twofold: the approximation error involves a worst-case search over an infinite set of unilateral deviations, and the required utility information is distributed across players. For a linear-in-parameters potential class, we use an exact finite-tuple reformulation that separates the problem into a global outer search over deviation tuples and distributed convex inner problems. We develop a primal--dual inner oracle tailored to this structure and establish a uniform one-sided accuracy guarantee. This oracle can be combined with global outer search to obtain an end-to-end guarantee on the outer optimization error. We also develop a projected zeroth-order outer method as a computationally lighter alternative for higher-dimensional problems. Numerical experiments illustrate the accuracy--computation tradeoff between the two outer-search methods and show that the proposed optimization framework can improve upon analytical \(\alpha\)-potential constructions.
Tags
Links
- Source: https://arxiv.org/abs/2610.05516v1
- Canonical: https://arxiv.org/abs/2610.05516v1
Trouble viewing inline? Open PDF directly →
Full Text
89,378 characters extracted from source content.
Expand or collapse full text
Distributed Algorithms for α-Potential Functions in General-Sum Games Yifei Chen Affiliation: Yifei Chen is with the Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, Maryland, USA (email: ychen780@jhu.edu) Chinmay Maheshwari Affiliation: Chinmay Maheshwari is with the Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, Maryland, USA (email: chinmay_maheshwari@jhu.edu) Abstract We study the problem of computing the tightest α-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each player has access only to its own utility function. The difficulty is twofold: the approximation error involves a worst-case search over an infinite set of unilateral deviations, and the required utility information is distributed across players. For a linear-in-parameters potential class, we use an exact finite-tuple reformulation that separates the problem into a global outer search over deviation tuples and distributed convex inner problems. We develop a primal–dual inner oracle tailored to this structure and establish a uniform one-sided accuracy guarantee. This oracle can be combined with global outer search to obtain an end-to-end guarantee on the outer optimization error. We also develop a projected zeroth-order outer method as a computationally lighter alternative for higher-dimensional problems. Numerical experiments illustrate the accuracy–computation tradeoff between the two outer-search methods and show that the proposed optimization framework can improve upon analytical α-potential constructions. I Introduction Strategic interactions with heterogeneous and coupled objectives arise in networked control, resource allocation, and multi-agent learning [1, 2]. Potential games simplify the analysis of such systems by representing players’ unilateral utility changes through a common scalar function [3]. Exact potential functions, however, need not exist in general-sum games. Near-potential games instead quantify the mismatch through an approximation parameter α; smaller α yields tighter equilibrium and learning guarantees for the original game [4, 5, 6]. This motivates computing the smallest approximation error achievable within a prescribed class of potential functions. For finite-action games, unilateral deviations can be enumerated and the nearest potential can be computed by linear programming [7]. The continuous-action setting is substantially more difficult: the deviation space is infinite, and evaluating the uniform full-domain approximation error requires a generally nonconcave global maximization over deviations, even when the objective is convex in the potential parameters. Moreover, in many multi-agent systems utility information is naturally distributed: each player can evaluate its own utility but need not know the utility functions of other players. A centralized computation would therefore require collecting player-specific utility information. We instead seek a distributed procedure that keeps these utility evaluations local and coordinates the computation through communication among players. Existing continuous-action approaches typically exploit additional game structure rather than directly optimizing the full-domain error. For example, explicit or analytical α-potential constructions have been developed for asymmetric network games [6], dynamic congestion games [5], and dynamic N-player games [8], among others. Such constructions provide useful analytical bounds but need not yield the tightest approximation for a particular game instance. NePPO [9] instead optimizes an equilibrium-local proxy rather than the uniform full-domain criterion. Motivated by this gap, we study the distributed computation of the tightest full-domain approximation over continuous actions when each player has access only to its own utility function. We consider a potential class that is linear in its parameters, while allowing nonlinear dependence on the players’ actions through a prescribed feature map. Using the finite-tuple reformulation of [10], we express the original problem as a global outer maximization over finite collections of deviations, where evaluating each candidate tuple requires solving a convex optimization problem over the potential parameters. This yields a modular two-level architecture: the inner problem can be solved using distributed optimization with local utility evaluations, while different search procedures can be used for the outer problem. For the inner problem, general distributed constrained-optimization methods could in principle be applied [11, 12, 13]. We instead develop an oracle tailored to the finite-maximum structure of our problem. Each player maintains a single scalar constraint multiplier, evaluates only its local utility, and communicates its primal iterate with neighboring players. The resulting network-averaged output provides a one-sided estimate of the finite-tuple value with an error bound that is uniform over all queried tuples. This uniform oracle property allows us to combine the distributed inner solver with global tree search method EXOTIC [10] and obtain an end-to-end guarantee for the outer objective. We also consider projected zeroth-order ascent as a computationally lighter alternative when hierarchical global search becomes expensive. Our main contributions are as follows. (1) We formulate the distributed computation of the tightest near-potential approximation, within a prescribed linear-in-parameters potential class, for continuous-action general-sum games. Applying the finite-tuple reformulation of [10], we obtain an equivalent outer maximization over deviation tuples with convex inner problems. We also give sufficient conditions under which an optimizer of the finite-tuple problem recovers an optimizer of the original full-domain problem (Proposition 4). (2) We develop a distributed primal–dual oracle tailored to these inner problems. By retaining their finite-maximum structure, each player uses one scalar constraint multiplier, accesses only its local utility, and exchanges only its primal iterate with neighboring players. For an inner iteration budget K, we establish a uniform one-sided oracle error of order ~(K−1/4) O(K^-1/4) over all deviation tuples (Theorem 7). (3) We combine the distributed oracle with EXOTIC and derive an end-to-end convergence guarantee for the optimal near-potential value (Theorem 12). Together with the structural recovery conditions of Proposition 4, this further yields asymptotic recovery of an optimal potential parameter. We additionally develop a projected zeroth-order outer method as a scalable heuristic that avoids hierarchical tree search. Numerical experiments compare the resulting accuracy–computation tradeoff and show that the optimization-based approach can improve upon analytical near-potential constructions. Notation For a scalar λ, let [λ]+:=maxλ,0[λ]_+:= \λ,0\. Given a nonempty closed convex set Ω , let PΩ(x)P_ (x) denote the Euclidean projection of x onto Ω . For a convex function f, ∂f(x)∂ f(x) denotes its sub-differential at x, while ∇xf _xf denotes its gradient with respect to x whenever it exists. The communication network is represented by a connected undirected graph =(,ℰ)G=(V_G,E_G), where V_G is identical to the player set ℐI and ℰ⊆×E_G _G×V_G is the edge set. The neighbor set of player i is i:=j∈ℐ:(i,j)∈ℰ.N_i:=\j :(i,j) _G\. Let A_G be the adjacency matrix, with [A]ij=1[A_G]_ij=1 if (i,j)∈ℰ(i,j) _G and zero otherwise. Let D:=diag(d1,…,dN)D_G:=diag(d_1,…,d_N), where di:=∑j[A]ijd_i:= _j[A_G]_ij, and define the graph Laplacian as L:=D−AL_G:=D_G-A_G. I Problem Formulation Consider a strategic-form game Γ=(ℐ,ii∈ℐ,uii∈ℐ) =(I,\A_i\_i ,\u_i\_i ) with player set ℐ:=1,…,NI:=\1,…,N\, nonempty compact action sets i⊆ℝdiA_i ^d_i, and Lipschitz continuous utility functions ui:→ℝu_i:A , where :=∏i∈ℐiA:= _i A_i. For each i∈ℐi , write a=(ai,a−i)a=(a_i,a_-i), where a−ia_-i denotes the actions of all other players. Let :=2Y:=A^2. For y=(a,a′)∈y=(a,a ) and q:→ℝq:A , define the unilateral difference Δq(y,i):=q(ai′,a−i)−q(ai,a−i) _q(y;i):=q(a_i ,a_-i)-q(a_i,a_-i). Definition 1 (Exact potential function [3]) A function ϕ:→ℝφ:A is an exact potential function for Γ if Δϕ(y,i)=Δui(y,i) _φ(y;i)= _u_i(y;i) for all i∈ℐi and y∈y . A game admitting such a function is an exact potential game. General-sum games need not admit an exact potential function. We therefore consider approximate potentials that uniformly bound the discrepancy between unilateral potential and utility differences. Definition 2 (α-potential function) For α≥0α≥ 0, a function ϕ:→ℝφ:A is an α-potential function for Γ if |Δϕ(y,i)−Δui(y,i)|≤α| _φ(y;i)- _u_i(y;i)|≤α for all i∈ℐi and y∈y . The case α=0α=0 recovers an exact potential function. Our objective is to find the smallest α achievable within a prescribed class of candidate potentials. We consider ϕθ(a):=⟨θ,ψ(a)⟩,θ∈Θ⊆ℝd, _θ(a):= θ,ψ(a) , θ∈ ^d, (1) where ψ:→ℝdψ:A ^d is a prescribed Lipschitz continuous feature map and Θ is nonempty, compact, and convex11 1 Although we use linear parametrization of potential function in (1), the results in this paper extend to convex parameterization setting.. For each i∈ℐi and y∈y , define the signed approximation error ℓi(θ,y):=Δϕθ(y,i)−Δui(y,i), _i(θ,y):= _ _θ(y;i)- _u_i(y;i), and let f(θ,y):=maxi∈ℐℓi(θ,y),ℰ(θ):=maxy∈f(θ,y).f(θ,y):= _i _i(θ,y), (θ):= _y f(θ,y). (2) Since Y includes both directions of every unilateral deviation, ℰ(θ)=maxi∈ℐ,y∈|ℓi(θ,y)|E(θ)= _i ,\,y | _i(θ,y)|. Thus, ℰ(θ)E(θ) is the smallest α for which ϕθ _θ is an α-potential function. The resulting optimization problem is p⋆:=minθ∈Θℰ(θ)=minθ∈Θmaxy∈f(θ,y),p := _θ∈ E(θ)= _θ∈ _y f(θ,y), (3) with an optimal parameter denoted by θ⋆∈argminθ∈Θℰ(θ)θ ∈ _θ∈ E(θ). Computing the optimal approximation in (3) presents two main challenges. First, although the objective is convex in the potential parameters, its evaluation requires solving a generally nonconcave maximization over the continuous space of unilateral deviations. Second, evaluating the objective requires information about all players’ utilities, whereas each player has access only to its own utility function. We address these challenges in the next two sections. Section I derives an equivalent finite-tuple reformulation that separates the global nonconvex search from convex optimization over the potential parameters. Section IV develops a distributed algorithm for solving these convex subproblems using local utility information and combines it with outer optimization methods. Remark 3 (Choice of parameterization) Linearity in θ makes each ℓi(⋅,y) _i(·,y) affine and hence f(⋅,y)f(·,y) and ℰE convex, while expressiveness is determined by ψ. For a finite action space =a1,…,aMA=\a^1,…,a^M\, choosing d=Md=M and ψ(am)=emψ(a^m)=e_m recovers any tabular potential permitted by Θ . On compact continuous action spaces, expanding a polynomial basis yields uniform approximation of continuous potentials by the Stone–Weierstrass theorem [14]. The features may instead be fixed neural-network representations or discounted state-action occupancy measures, as in [8, Section 5]. Thus, linearity in the parameters still permits nonlinear dependence on actions or policies. Nevertheless, f remains generally nonconcave in y, making (3) convex–nonconcave minimax problem. I Finite-Tuple Reformulation We begin by reformulating the convex-nonconcave minimax optimization problem (3) to nonconcave convex maximin optimization problem using results in [10]. The key idea is to replace the maximization over the continuous deviation space with an outer search over finite collections of deviations. For each such collection, the corresponding optimization over the potential parameters is convex. Specifically, let :=d+1W:=Y^d+1 denote the set of tuples containing d+1d+1 deviations. For each w=(y1,…,yd+1)∈w=(y_1,…,y_d+1) , define F(θ,w):=max1≤j≤d+1f(θ,yj),G(w):=minθ∈ΘF(θ,w).F(θ,w):= _1≤ j≤ d+1f(θ,y_j), G(w):= _θ∈ F(θ,w). (4) For a fixed tuple w, the function F(⋅,w)F(·,w) measures the maximum approximation error over the deviations contained in w. Since F(⋅,w)F(·,w) is convex, computing G(w)G(w) amounts to solving a convex optimization problem over the potential parameters. Moreover, because F(θ,w)≤ℰ(θ)F(θ,w) (θ) for every θ∈Θθ∈ and w∈w , we have G(w)≤p⋆G(w)≤ p . Thus, every tuple provides a lower bound on the optimal approximation error. The following result establishes that maximizing these lower bounds over all tuples recovers the optimal value of the original problem. It also provides sufficient conditions under which an optimal parameter of the finite-tuple problem solves the original problem. Proposition 4 (Reformulation and optimizer recovery) Under the standing assumptions, p⋆=maxw∈G(w).p = _w G(w). (5) Moreover, let w⋆=(y1⋆,…,yd+1⋆)∈argmaxw∈G(w),w =(y_1 ,…,y_d+1 )∈ *arg\,max_w G(w), and θw⋆∈argminθ∈ΘF(θ,w⋆). _w ∈ *arg\,min_θ∈ F(θ,w ). Define the set of active player-deviation pairs S⋆:=(i,j)∈ℐ×[d+1]:ℓi(θw⋆,yj⋆)=F(θw⋆,w⋆).S := \(i,j) ×[d+1]: _i( _w ,y_j )=F( _w ,w ) \. Then θw⋆ _w is an optimal solution of (3) if either of the following conditions holds: (i) The finite-tuple objective is exact at θw⋆ _w , i.e., F(θw⋆,w⋆)=ℰ(θw⋆).F( _w ,w )=E( _w ). (i) The active feature-difference vectors positively span ℝdR^d, i.e., 0∈intconvΔψ(yj⋆,i):(i,j)∈S⋆.0 \ _ψ(y_j ;i):(i,j)∈ S \. Proof: The optimal-value identity (5) follows from [10, Proposition 2.1]. The required continuity and convexity conditions hold, while compactness of Θ ensures boundedness and attainment. For optimizer recovery, we use [10, Proposition 2.4]. Condition (i) directly implies that ℰ(θw⋆)=p⋆E( _w )=p ([10, Proposition 2.4-(i)]). Under condition (i), the active feature-difference vectors ensure that θw⋆ _w is the unique minimizer of F(⋅,w⋆)F(·,w ). Since every minimizer of ℰE also minimizes F(⋅,w⋆)F(·,w ), it follows that θw⋆ _w is also the unique minimizer of ℰE([10, Proposition 2.4-(i)]). The complete proof is provided in Appendix A. ∎Proposition 4 separates value recovery from parameter recovery. Equality (5) implies that solving the outer problem recovers the optimal approximation value p⋆p without additional assumptions. For an optimal tuple w⋆w , an inner minimizer solves the full-domain problem if it satisfies either condition (i) or condition (i) of Proposition 4. Section IV establishes convergence of the outer objective values to p⋆p . This value convergence alone does not guarantee recovery of a full-domain optimizer; the optimizer-recovery statement remains conditional on the conditions in Proposition 4. IV Distributed Oracle and Outer Optimization Proposition 4 motivates a modular two-level computational framework, illustrated in Figure 1. The framework separates the global maximization over deviation tuples from the convex optimization required to evaluate G(w)G(w). In this paper, we develop a distributed inner oracle tailored to the finite-tuple problem structure. At each outer query, a centralized coordinator broadcasts a candidate tuple w and an iteration budget K. Players then use local utility information and communication with their neighbors to compute an approximate evaluation G^K(w) G_K(w). We establish a uniform finite-time accuracy guarantee for the proposed oracle. For the outer optimization, we consider two methods that offer different computational trade-offs. First, we integrate our distributed oracle with EXOTIC [10], which provides a global optimization guarantee but can be computationally expensive in high-dimensional problems. Second, we develop a projected zeroth-order ascent method as a computationally scalable alternative, without a global optimality guarantee. We first present the distributed inner oracle and its convergence analysis, followed by the two outer optimization methods. Centralized outer coordinatorDistributed inner oracle (Algorithm 1)112233iijjNNtuple wwbudget KKoracle estimateG^K(w) G_K(w) Fig. 1: Centralized outer search coupled with the distributed inner oracle. For concision, we give only the main proof arguments in this section; complete proofs are provided in Appendix C. IV-A Inner Distributed Optimization Oracle Fix a candidate tuple w=(y1,…,yd+1)∈w=(y_1,…,y_d+1) . Using only its local utility information, each player i∈ℐi defines the finite-tuple objective hiw(θ):=max1≤j≤d+1ℓi(θ,yj).h_i^w(θ):= _1≤ j≤ d+1 _i(θ,y_j). (6) Then F(θ,w)=maxi∈ℐhiw(θ)F(θ,w)= _i h_i^w(θ) and G(w)=minθ∈Θmaxi∈ℐhiw(θ)G(w)= _θ∈ _i h_i^w(θ). Each hiwh_i^w is convex as a finite maximum of affine functions. Player i can compute its values and subgradients using its own utility uiu_i, the feature map ψ, and the tuple w. Introducing an epigraph variable replaces the maximum across players with one convex inequality per player. Choose common finite bounds tmint_ and tmaxt_ such that tmin≤hiw(θ)≤tmaxt_ ≤ h_i^w(θ)≤ t_ for all i∈ℐi , θ∈Θθ∈ , and w∈w , and let :=[tmin,tmax]T:=[t_ ,t_ ]. Such bounds exist because hiw(θ)h_i^w(θ) is uniformly bounded by continuity and compactness; the shared bounds used in implementation need not be tight. We obtain G(w)=minθ∈Θ,t∈ G(w)= _θ∈ ,\;t t t (7) s.t. .t. hiw(θ)≤t,∀i∈ℐ. h_i^w(θ)≤ t, ∀ i . Given (θ,t)(θ,t), player i can evaluate its own constraint hiw(θ)≤th_i^w(θ)≤ t. The optimization requires finding a common pair satisfying every player’s constraint. Suppose the players communicate over a connected undirected graph =(ℐ,ℰ)G=(I,E_G). Assign each player a local copy zi:=(θi⊤,ti)⊤∈:=Θ×.z_i:=( _i ,t_i) := ×T. Enforcing neighbor consensus yields minzi∈i∈ℐ _\z_i \_i 1N∑i=1Nti 1N _i=1^Nt_i (8) s.t. .t. hiw(θi)≤ti,∀i∈ℐ, h_i^w( _i)≤ t_i, ∀ i , zi=zj,∀(i,j)∈ℰ. z_i=z_j, ∀(i,j) _G. At consensus, its objective reduces to the common epigraph value t. Proposition 5 (Equivalence of the consensus formulation) If G is connected, the feasible sets of (7) and (8) correspond under replication zi=(θ,t)z_i=(θ,t) for every i∈ℐi , with identical objective values. Therefore, their optimal values equal G(w)G(w), and their optimal solutions correspond to this replication. IV-A1 Applying existing distributed optimization oracle Problem (8) can be solved using existing distributed optimization methods. For fixed w, each constraint hiw(θi)≤tih_i^w( _i)≤ t_i is equivalent to the d+1d+1 affine inequalities ⟨Δψ(yj;i),θi⟩−ti≤Δui(yj;i),j=1,…,d+1. _ψ(y_j;i), _i -t_i≤ _u_i(y_j;i), j=1,…,d+1. (9) These inequalities constitute an agent-specific affine conic constraint with cone ℝ−d+1R_-^d+1. Hence, the method of [12] applies directly to each finite-tuple subproblem. More recent methods such as D-APDB [13] accommodate more general private functional constraints. Remark 6 Our proposed method retains the finite-maximum representation of hiwh_i^w. Applying a general affine-conic method to the expanded formulation in (9) would associate a (d+1)(d+1)-dimensional constraint-dual variable with each player, while our method uses one scalar multiplier and obtains a subgradient from an active tuple element. Hence, the local dual state is (1)O(1) rather than (d)O(d), although evaluating the maximum may still require examining all d+1d+1 deviations. Our objective is not to obtain a faster general-purpose convergence rate, but to construct a simpler distributed oracle tailored to the finite-tuple subproblems. IV-A2 Proposed distributed oracle Inspired from [15, 16, 17], we propose a primal dual update based oracle on regularized Lagrangian function for (8). Let μi≥0 _i≥ 0 denote the multiplier associated with player i’s constraint hiw(θi)≤tih_i^w( _i)≤ t_i, and collect μ:=(μi)i∈ℐ∈ℝ+Nμ:=( _i)_i _+^N. For βk>0 _k>0, define ℒβk(Z,μ):=∑i∈ℐ[tiN+μi(hiw(θi)−ti)−βk2μi2].L_ _k(Z,μ):= _i [ t_iN+ _i (h_i^w( _i)-t_i )- _k2 _i^2 ]. (10) Algorithm 1 implements distributed projected descent–ascent on ℒβkL_ _k. At iteration k, let Z[k]Z[k] have rows zi[k]⊤z_i[k] and let μ[k]:=(μi[k])i∈ℐμ[k]:=( _i[k])_i . Specifically, lines 4–6 compute gi[k]∈∂ziℒβk(Z[k],μ[k]),g_i[k]∈ _z_iL_ _k(Z[k],μ[k]), and line 7 computes the dual ascent direction ri[k]=∇μiℒβk(Z[k],μ[k]).r_i[k]= _ _iL_ _k(Z[k],μ[k]). Accordingly, line 8 performs projected primal descent with a consensus correction, while line 9 performs projected dual ascent. After the primal–dual iterations, lines 12–15 compute the stepsize-weighted ergodic iterate of each player. Line 16 forms and broadcasts the network-averaged potential parameter, line 17 evaluates the corresponding oracle estimate, and line 18 returns the oracle outputs. Algorithm 1 DRPDM Inner Oracle 1: K≥1K≥ 1, c,β0>0c, _0>0, τ∈(0,1)τ∈(0,1), q∈(0,τ/2)q∈(0,τ/2), cβ0≤1c _0≤ 1, and σ∈(0,λmax−1(L)]σ∈ (0, _ ^-1(L_G) ]; set ηk=c(k+1)−τ _k=c(k+1)^-τ and βk=β0(k+1)−q _k= _0(k+1)^-q. 2: Initialize zi[0]∈z_i[0] and μi[0]=0 _i[0]=0 3: for k=0,…,K−1k=0,…,K-1 do 4: for all i∈ℐi in parallel do 5: ji⋆[k]∈argmax1≤j≤d+1ℓi(θi[k],yj)j_i [k]∈ _1≤ j≤ d+1 _i( _i[k],y_j) 6: si[k]←Δψ(yji⋆[k],i)s_i[k]← _ψ(y_j_i [k];i) 7: gi[k]←(μi[k]si[k], 1/N−μi[k])g_i[k]← ( _i[k]s_i[k],\,1/N- _i[k] ) 8: ri[k]←hiw(θi[k])−ti[k]−βkμi[k]r_i[k]← h_i^w( _i[k])-t_i[k]- _k _i[k] 9: zi[k+1]←P[zi[k]−ηkgi[k]z_i[k+1]← P_Z\! [z_i[k]- _kg_i[k] 10: +σ∑j∈i[A]ij(zj[k]−zi[k])] +σ _j _i[A_G]_ij (z_j[k]-z_i[k] ) ] 11: μi[k+1]←[μi[k]+ηkri[k]]+ _i[k+1]←[ _i[k]+ _kr_i[k]]_+ 12: end for 13: end for 14: SK←∑k=0K−1ηkS_K← _k=0^K-1 _k 15: for all i∈ℐi in parallel do 16: z¯i[K]←SK−1∑k=0K−1ηkzi[k]=:(θ¯i[K],t¯i[K]) z_i[K]← S_K^-1 _k=0^K-1 _kz_i[k]=:( θ_i[K], t_i[K]) 17: end for 18: θ¯w[K]←N−1∑iθ¯i[K] θ_w[K]← N^-1 _i θ_i[K]; broadcast θ¯w[K] θ_w[K] 19: Evaluate hiw(θ¯w[K])h_i^w( θ_w[K]) locally; aggregate G^K(w)←maxihiw(θ¯w[K]) G_K(w)← _ih_i^w( θ_w[K]) 20: return θ¯w[K] θ_w[K], G^K(w) G_K(w), and z¯i[K]i∈ℐ\ z_i[K]\_i IV-A3 Finite-time analysis The finite-budget output of Algorithm 1 is generally not the exact tuple value G(w)G(w). Since θ¯w[K]∈Θ θ_w[K]∈ , the definition of G(w)G(w) gives G^K(w):=F(θ¯w[K],w)≥G(w). G_K(w):=F( θ_w[K],w)≥ G(w). (11) Thus, G^K(w) G_K(w) is an upper estimate of G(w)G(w) generated by the finite-budget inner solver. The following result controls this overestimation uniformly over w∈w . Theorem 7 (Uniform inner-oracle accuracy) Under the standing assumptions, run Algorithm 1 with τ=3/4τ=3/4 and q=1/4q=1/4. Then, for every w∈w 0≤G^K(w)−G(w)=~(K−1/4).0≤ G_K(w)-G(w)= O\! (K^-1/4 ). (12) Proof: Define ℒ(Z,μ):=∑i∈ℐ[tiN+μi(hiw(θi)−ti)].L(Z,μ):= _i [ t_iN+ _i (h_i^w( _i)-t_i ) ]. Let Z¯[K] Z[K] have rows z¯i[K]⊤ z_i[K] , and define μ¯[K]:=(SK)−1∑k=0K−1ηkμ[k]. μ[K]:=(S_K)^-1 _k=0^K-1 _kμ[k]. Fix w∈w , and let θw⋆∈argminθ∈ΘF(θ,w),zw⋆:=(θw⋆,G(w)),Zc:=(zw⋆)⊤. _w ∈ _θ∈ F(θ,w),\,z_w :=( _w ,G(w)),Z_c:=1(z_w ) . Since zw⋆z_w is feasible and μ¯[K]∈ℝ+N μ[K] _+^N, ℒ(Zc,μ¯[K])≤G(w).L(Z_c, μ[K])≤ G(w). To control the disagreement among the local primal iterates, we first use the following bound on the dual iterates. Lemma 8 (Polynomial bound on dual iterates) Under the standing assumptions, there exists a constant Bμ>0B_μ>0, independent of w, i, and k, such that 0≤μi[k]≤Bμβk=Bμβ0(k+1)q,i∈ℐ,k≥0.0≤ _i[k]≤ B_μ _k= B_μ _0(k+1)^q, i , k≥ 0. (13) Since the primal update direction gi[k]g_i[k] depends linearly on μi[k] _i[k], this bound implies ‖gi[k]‖2=((k+1)q)\|g_i[k]\|_2=O((k+1)^q), which is the key input to the following consensus estimate. Define zav[k]:=1N∑i=1Nzi[k],ek:=1N∑i=1N‖zi[k]−zav[k]‖22.z_av[k]:= 1N _i=1^Nz_i[k], e_k:= 1N _i=1^N\|z_i[k]-z_av[k]\|_2^2. For the weighted ergodic iterates z¯i[K] z_i[K] in Algorithm 1, define z¯w[K]:=1N∑i∈ℐz¯i[K],DK:=NSK∑k=0K−1ηkek. z_w[K]:= 1N _i z_i[K], D_K:= NS_K _k=0^K-1 _ke_k. Lemma 9 (Consensus error) Under the standing assumptions, there exist constants Ce,CD>0C_e,C_D>0, independent of w, K, and the initial primal points, such that ek≤Ce(k+1)−1/2,k≥0,e_k≤ C_e(k+1)^-1/2, k≥ 0, (14) and for K≥1,K≥ 1, maxi∈ℐ∥z¯i[K]−z¯w[K]∥2≤DK≤CDK−1/4. _i \| z_i[K]- z_w[K]\|_2≤ D_K≤ C_DK^-1/4. (15) Let iKi_K attain F(θ¯w[K],w)=hiKw(θ¯w[K]),F( θ_w[K],w)=h_i_K^w( θ_w[K]), and let iKe_i_K be the corresponding coordinate unit vector. Then, by Lemma 9, F(θ¯w[K],w)≤ℒ(Z¯[K],iK)+(Gψ+1)DK.F( θ_w[K],w) ( Z[K],e_i_K)+(G_ψ+1)D_K. It remains to control the Lagrangian gap in the preceding bound. For this, we use the following ergodic primal–dual inequality. Lemma 10 (Ergodic primal–dual inequality) Under the conditions of Theorem 7, let Zc:=z⊤Z_c:=1z be any consensus comparator with z∈z . Then, for every μ∈ℝ+Nμ _+^N, ℒ(Z¯[K],μ)−ℒ(Zc,μ¯[K])≤RK+QK‖μ‖22,L( Z[K],μ)-L(Z_c, μ[K])≤ R_K+Q_K\|μ\|_2^2, (16) where, for some constant C0>0C_0>0 independent of w, K, and the initial primal points, RK:=C0SK[1+∑k=0K−1ηk2(k+1)1/2+∑k=0K−1ηk(k+1)1/4ek],R_K:= C_0S_K [1+ _k=0^K-1 _k^2(k+1)^1/2+ _k=0^K-1 _k(k+1)^1/4e_k ], and QK:=1SK[12+14∑k=0K−1ηkβk].Q_K:= 1S_K [ 12+ 14 _k=0^K-1 _k _k ]. Applying Lemma 10 with μ=iKμ=e_i_K, and using ‖iK‖2=1\|e_i_K\|_2=1, yields 0≤G^K(w)−G(w)≤RK+QK+(Gψ+1)DK.0≤ G_K(w)-G(w)≤ R_K+Q_K+(G_ψ+1)D_K. Finally, under τ=3/4τ=3/4 and q=1/4q=1/4, SK=Θ(K1/4)S_K= (K^1/4). The standard harmonic-sum bounds applied to the definitions above then give RK=~(K−1/4),QK=~(K−1/4).R_K= O(K^-1/4),Q_K= O(K^-1/4). Together with DK=(K−1/4)D_K=O(K^-1/4), this proves 0≤G^K(w)−G(w)=~(K−1/4)0≤ G_K(w)-G(w)= O(K^-1/4) uniformly over w∈w . ∎ IV-B Outer Optimization IV-B1 Global Search with EXOTIC We first consider EXOTIC [10] as a globally convergent method for solving the outer problem (5). EXOTIC adaptively explores a hierarchical partition of W. At a candidate tuple w, it invokes the distributed inner oracle with an iteration budget K and obtains an approximate value G^K(w) G_K(w). It progressively allocates computation between exploring new regions of W and refining the accuracy of promising oracle evaluations. Let n denote the total computational budget, measured as the cumulative number of synchronized inner iterations used across all oracle queries, including the final re-evaluations. Given n, EXOTIC determines a search horizon hmaxh_ and adaptively allocates inner iteration budgets across the nodes of the partition tree. After the tree-search phase, selected candidates are re-evaluated with a larger budget KfinalK_final, and the tuple with the largest refined estimate is returned. We defer the complete EXOTIC procedure and its budget allocation rule to the Appendix D. To invoke the convergence guarantee of EXOTIC from [10], we verify two properties of the outer problem. First, the objective G must vary regularly within cells of the hierarchical partition. Second, the number of cells that remain near-optimal at increasingly fine resolutions must be controlled. We establish these properties below. Equip W with the metric d(w,w~):=max1≤j≤d+1‖yj−y~j‖2,d_W(w, w):= _1≤ j≤ d+1\|y_j- y_j\|_2, and let LuL_u and LψL_ψ denote common Lipschitz constants of the utilities and the feature map, respectively. Lemma 11 (Regularity of the outer objective) Let Cθ:=maxθ∈Θ‖θ‖2.C_θ:= _θ∈ \|θ\|_2. Then, for all w,w~∈w, w , |G(w)−G(w~)|≤Lgamed(w,w~),|G(w)-G( w)|≤ L_gamed_W(w, w), (17) where Lgame:=2(CθLψ+Lu).L_game:=2(C_θL_ψ+L_u). EXOTIC uses a B-ary hierarchical partition h,rr=1Bh\W_h,r\_r=1^B^h of W, where h denotes the depth. Assume that the cell diameters decrease geometrically: diamd(h,r)≤αρh,α>0,0<ρ<1.diam_d_W(W_h,r)≤ _Wρ^h, _W>0, 0<ρ<1. (18) By Lemma 11, if h,rW_h,r contains an outer maximizer w⋆w , then G(w⋆)−G(w)≤νgameρh,w∈h,r,G(w )-G(w)≤ _gameρ^h, w _h,r, where νgame:=αLgame. _game:= _WL_game. Thus, the variation of G within an optimal cell decreases geometrically with the partition depth. It remains to characterize how many cells can remain near-optimal at a given depth. Define h(ε):=r:maxw∈h,rG(w)≥p⋆−ε.N_h( ):= \r: _w _h,rG(w)≥ p - \. Following [10, Definition 3.2], let dG≥0d_G≥ 0 be an admissible near-optimality exponent if, for some CG>1C_G>1, |h(2νgameρh)|≤CGρ−dGh,h≥0. |N_h(2 _gameρ^h) |≤ C_Gρ^-d_Gh, h≥ 0. (19) The exponent dGd_G captures the effective difficulty of the outer search: larger dGd_G allows more cells to remain competitive as the partition is refined. We can now combine these outer regularity properties with the uniform accuracy of the distributed inner oracle. Theorem 12 (Global outer-value guarantee) Suppose that the assumptions of Theorem 7 hold and that the hierarchical partition satisfies (18) and (19). Run EXOTIC with Algorithm 1 as its inner oracle and total inner-iteration budget n. Then, for the returned tuple w^n w_n, 0≤p⋆−G(w^n)=~(n−1/(dG+4)),0≤ p -G( w_n)= O (n^-1/(d_G+4) ), with all problem and algorithm constants fixed. Proof: Theorem 7 gives the uniform one-sided oracle bound 0≤G^K(w)−G(w)=~(K−1/4)0≤ G_K(w)-G(w)= O(K^-1/4), for every w∈.w . Lemma 11 together with (18) verifies the geometric variation condition required by EXOTIC, while (19) controls the number of near-optimal cells at each depth. Substituting the inner-oracle exponent 1/41/4 into [10, Theorem 3.3 and Corollary 3.5] gives the stated rate, with logarithmic factors absorbed into ~ O. ∎ Theorem 12 guarantees convergence of the outer value G(w^n)G( w_n) to p⋆p . The associated potential parameter is obtained from the final inner solve, θ^n:=θ¯w^n[Kfinal]. θ_n:= θ_ w_n[K_final]. The theorem does not, by itself, provide a finite-budget bound on the full-domain error ℰ(θ^n)E( θ_n). Exact optimizer recovery is characterized by Proposition 4; obtaining a quantitative finite-budget recovery guarantee would require additional stability or growth conditions. IV-B2 Projected Zeroth-Order Ascent Although EXOTIC provides a global outer-search guarantee, its hierarchical partition can become computationally expensive when W is high-dimensional. We therefore also consider a projected zeroth-order ascent method that uses only evaluations of the distributed oracle and avoids maintaining a partition tree. Assume that ⊆ℝDW ^D_W is convex with nonempty interior, and define the δ-interior δ:=w∈:w+δv∈ for all ‖v‖2≤1.W_δ:= \w :w+δ v for all \|v\|_2≤ 1 \. At iteration t, we sample vt∼Unif(D−1)v_t (S^D_W-1) and query the distributed oracle at wtw_t and wt+:=wt+δtvt.w_t^+:=w_t+ _tv_t. Let G^t0 G_t^0 and G^t+ G_t^+ denote the corresponding oracle estimates. We construct the zeroth-order ascent direction g^t:=Dδt(G^t+−G^t0)vt, g_t:= D_W _t ( G_t^+- G_t^0 )v_t, and update wt+1:=Pδt+1(wt+αtg^t),w_t+1:=P_W_ _t+1 (w_t+ _t g_t ), where δt _t is the perturbation radius and αt _t is the outer stepsize. Unlike EXOTIC, this procedure does not perform a global search over W and requires only two oracle evaluations per outer iteration. It therefore provides a more scalable alternative for high-dimensional problems. In this work, however, we use the method as a heuristic and do not establish global-optimality or stationarity guarantees for the resulting inexact projected updates. The complete procedure, including the decay schedules for δt _t and αt _t and the final re-evaluation step, is given in Appendix E. V Numerical Experiments We evaluate the framework in three complementary settings. A two-player benchmark with known optimum compares EXOTIC and zeroth-order (ZO) search and assesses parameter recovery; a three-player linear–quadratic game tests improvement over an analytical α-potential construction; and a 50-player game examines the scalability of ZO search in a high-dimensional potential class. V-A Experimental Protocol All experiments use Algorithm 1 as the distributed inner solver with c=1c=1, τ=12τ= 12, β0=0.125 _0=0.125, and q=16q= 16, unless stated otherwise; the consensus stepsize σ is chosen separately for each communication graph. Numerically, we use the uniform ergodic average z¯inum[K]:=K−1∑k=0K−1zi[k], z_i^num[K]:=K^-1 _k=0^K-1z_i[k], instead of the stepsize-weighted average used in the analysis. For EXOTIC, we use a deterministic binary midpoint partition with hmax∈500,1000,2000h_ ∈\500,1000,2000\ and s∈103,104s∈\10^3,10^4\, where a nominal inner budget K corresponds to sKsK DRPDM iterations. For ZO search, we set δt=δ0(t+1)−1/4 _t= _0(t+1)^-1/4 and αt=α0(t+1)−4/5 _t= _0(t+1)^-4/5, and cold-start each inner solve. Experiment-specific values of α0 _0, δ0 _0, and the iteration budgets are given below. V-B Two-Player Benchmark with Known Optimum Our first experiment considers a controlled benchmark for which the optimal full-domain approximation and corresponding potential parameter can be computed exactly. This allows us to evaluate both objective and parameter recovery and to compare the two outer-search methods. Consider a two-player, two-action game, where xi∈[0,1]x_i∈[0,1] denotes the probability that player i selects its first action. The mixed-strategy utilities are u1(x1,x2)=12−4x1−10x2+10x1x2u_1(x_1,x_2)=12-4x_1-10x_2+10x_1x_2 and u2(x1,x2)=10−2x1−8x2+2x1x2.u_2(x_1,x_2)=10-2x_1-8x_2+2x_1x_2. We use ψ(x1,x2)=(x1,x2,x1x2)⊤ψ(x_1,x_2)=(x_1,x_2,x_1x_2) and ϕθ(x1,x2)=⟨θ,ψ(x1,x2)⟩. _θ(x_1,x_2)= θ,ψ(x_1,x_2) . Because these utilities are multilinear extensions of a finite 2×22× 2 game, the optimal approximation can be computed exactly using the finite-game linear program of [4]. For the feature class above, this yields θ⋆=(−2,−10,6)⊤θ =(-2,-10,6) and p⋆=2.p =2. Consequently, we can evaluate both the full-domain optimality gap ℰ(θ^)−p⋆E( θ)-p and the parameter-recovery error ‖θ^−θ⋆‖2\| θ-θ \|_2. The players communicate over a single undirected edge. We set σ=0.45σ=0.45 and Θ=[−25,25]3 =[-25,25]^3. Since xi,xi′∈[0,1]x_i,x_i ∈[0,1], the resulting outer search space is =d+1=[0,1]16W=Y^d+1=[0,1]^16. For ZO search, we use T=2000T=2000, Kinner=104K_inner=10^4, and Kreeval=105K_reeval=10^5, and test α0∈0.01,0.03,0.1 _0∈\0.01,0.03,0.1\ and δ0∈0.0125,0.025,0.05. _0∈\0.0125,0.025,0.05\. For EXOTIC, we use the parameter grid specified in Section V-A. Fig. 2: Representative best-so-far finite-tuple values and exact full-domain errors for the two-player game: DRPDM-based EXOTIC (hmax=2000h_ =2000, s=104s=10^4; left) and ZO (α0=0.1 _0=0.1, δ0=0.025 _0=0.025; right). The dashed lines mark p⋆=2p =2. Table I compares the two methods. For EXOTIC, increasing hmaxh_ consistently reduces the recovered full-domain error. On this low-dimensional benchmark, EXOTIC achieves more accurate objective and parameter recovery, at the cost of greater computation at its highest-accuracy setting. Figure 2 shows representative trajectories for EXOTIC with (hmax,s)=(2000,104)(h_ ,s)=(2000,10^4) and ZO with (α0,δ0)=(0.1,0.025)( _0, _0)=(0.1,0.025); the latter is shown for illustration and is not the best-performing ZO configuration in Table I. TABLE I: Performance on the two-player continuous game. For ZO, the configuration denotes (α0,δ0)( _0, _0); for EXOTIC, it denotes (hmax,s)(h_ ,s). Method Configuration G G ℰ(θ^)E( θ) ℰ(θ^)−p⋆E( θ)-p ‖θ^−θ⋆‖2\| θ-θ \|_2 Time (s) ZO (10−2,0.0125)(10^-2,0.0125) 0.3063 2.3436 0.3436 0.4650 12.68 (3×10−2,0.0125)(3× 10^-2,0.0125) 0.4363 2.4676 0.4676 1.0612 12.43 (10−1,0.025)(10^-1,0.025) 0.6550 2.4251 0.4251 0.8502 12.30 EXOTIC (500,104)(500,10^4) 1.6265 2.4512 0.4512 0.5217 6.98 (1000,104)(1000,10^4) 1.9006 2.1555 0.1555 0.1166 16.39 (2000,104)(2000,10^4) 1.9214 2.0655 0.0655 0.1088 38.37 V-C Linear–Quadratic Network Games We next consider network games for which an analytical α-potential construction is available from [6]. Rather than recovering a known optimum, these experiments test whether our optimization-based approach can improve upon this analytical construction. We consider a small instance amenable to EXOTIC and a larger instance for which we use the ZO outer method. Consider the N-player linear–quadratic network game ui(a)=−12ai2+ζiai+γai∑j=1NVijaj,ai∈[−1,1],u_i(a)=- 12a_i^2+ _ia_i+γ a_i _j=1^NV_ija_j, a_i∈[-1,1], (20) where Vii=0V_i=0 and the off-diagonal entries are sampled independently as Vij∼Unif[1−εN,1+εN]V_ij [1- _N,1+ _N]. The players communicate over an undirected cycle. We optimize over the quadratic potential class ϕθ(a)=∑i=1Npiai2+∑i=1Nqiai+∑1≤i<j≤Nrijaiaj, _θ(a)= _i=1^Np_ia_i^2+ _i=1^Nq_ia_i+ _1≤ i<j≤ Nr_ija_ia_j, (21) where θ=(pii=1N,qii=1N,rij1≤i<j≤N)∈Θ⊆ℝdθ= (\p_i\_i=1^N,\,\q_i\_i=1^N,\,\r_ij\_1≤ i<j≤ N )∈ ^d and d=2N+N(N−1)2.d=2N+ N(N-1)2. As the analytical baseline, we use pi(0)=−12,qi(0)=ζi,rij(0)=γ2(Vij+Vji),i<j.p_i^(0)=- 12, q_i^(0)= _i, r_ij^(0)= γ2 (V_ij+V_ji ), i<j. (22) By [6], its full-domain approximation error is ℰ(θ0)=|γ|‖V−V⊤‖∞.E( _0)=|γ|\,\|V-V \|_∞. For this class of games, ℰ(θ)E(θ) can be evaluated exactly over the continuous action domain using a closed-form expression provided in Appendix F. We measure improvement by Imp(θ^):=ℰ(θ0)−ℰ(θ^),Imp%(θ^):=100Imp(θ^)ℰ(θ0).Imp( θ):=E( _0)-E( θ), _\%( θ):=100 Imp( θ)E( _0). (23) Positive values therefore indicate improvement over the analytical construction in the original full-domain objective. V-C1 Three-Player Game: Improving the Analytical Construction We first consider a low-dimensional instance for which EXOTIC can be used for global search over the finite-tuple space. The goal is to test whether optimizing the finite-tuple objective can improve upon the analytical baseline in (22). We consider a three-player instance with γ=ζi=1γ= _i=1, εN=0.5 _N=0.5, and communication over the three-node cycle. We consider the following parameterization of potential ϕθ(a)=−12∑i=13ai2+∑i=13ai+∑1≤i<j≤3θijaiaj,θ∈[−2,2]3. _θ(a)=- 12 _i=1^3a_i^2+ _i=1^3a_i+ _1≤ i<j≤ 3 _ija_ia_j, θ∈[-2,2]^3. Thus, dθ=3d_θ=3, dy=6d_y=6, and =4⊆ℝ24W=Y^4 ^24. The analytical baseline is θij(0)=(Vij+Vji)/2 _ij^(0)=(V_ij+V_ji)/2, for which ℰ(θ0)=‖V−V⊤‖∞=0.4480.E( _0)=\|V-V \|_∞=0.4480. We use the EXOTIC parameter grid from Section V-A and set σ=0.3σ=0.3. Across the tested configurations, the smallest observed exact full-domain error is 0.36930.3693, corresponding to a 17.58%17.58\% improvement over the analytical baseline. Figure 3 shows that the best finite-tuple value increases during the search, while the diagnostic full-domain error initially decreases and then stabilizes. Thus, in this instance, finite-tuple optimization identifies a potential that improves upon the analytical construction over the full action domain. Fig. 3: Representative EXOTIC search (hmax=2000h_ =2000, s=104s=10^4). The dashed line marks ℰ(θ0)=‖V−V⊤‖∞E( _0)=\|V-V \|_∞. V-C2 Fifty-Player Game: Scalable Zeroth-Order Search We finally consider a larger instance to examine the scalability of the ZO outer method. The full quadratic potential class has dθ=1325d_θ=1325, making hierarchical global search over =dθ+1W=Y^d_θ+1 computationally impractical. We therefore combine the ZO outer search with the distributed DRPDM oracle. We consider a 5050-player instance with γ=ζi=1γ= _i=1 and εN=0.8 _N=0.8. The interaction matrix V is generated with seed 4242 and held fixed throughout the experiment. The players communicate over a 5050-node cycle, with σ=0.225σ=0.225. We use the full quadratic potential class in (21), with dθ=1325d_θ=1325 and Θ=[−2,2]1325 =[-2,2]^1325. The analytical baseline in (22) has exact full-domain error ℰ(θ0)=‖V−V⊤‖∞=33.5072.E( _0)=\|V-V \|_∞=33.5072. We run Algorithm 3 for T=200T=200 iterations and test α0∈10−2,10−3,10−4 _0∈\10^-2,10^-3,10^-4\ and δ0∈0.00625,0.0125,0.025. _0∈\0.00625,0.0125,0.025\. Each base and perturbed query uses Kinner=10,000K_inner=10,000 DRPDM iterations, with the two queries evaluated in parallel from the same cold start θ0 _0. All nine configurations share the same interaction matrix, initial outer iterate, and zeroth-order directions. Because the outer method optimizes the finite-tuple objective rather than the full-domain error, we use the closed-form expression for ℰE available in this example only for diagnostic post-selection. Candidates whose initial full-domain error improves upon ℰ(θ0)E( _0) are independently re-solved using Kreeval=50,000K_reeval=50,000 DRPDM iterations, and we report the candidate with the smallest resulting exact error. If no candidate passes this screening step, we instead re-evaluate the candidate with the smallest initial error. Figure 4 shows the best-so-far trajectories, and Table I summarizes the post-selected outputs. Four of the nine configurations improve upon the analytical baseline. The best result is obtained with (α0,δ0)=(10−2,0.025)( _0, _0)=(10^-2,0.025), for which the iterate selected at t=163t=163 achieves ℰ(θ^out)=31.7768,E( θ_out)=31.7768, corresponding to a 5.16%5.16\% improvement. In contrast, all configurations with α0=10−4 _0=10^-4 perform worse than the baseline, suggesting that this outer stepsize is too small for the available iteration budget. The experiment also illustrates the distinction between outer-value recovery and parameter recovery. For an arbitrary nonoptimal tuple w, increasing G(w)G(w) need not monotonically reduce ℰ(θw)E( _w), since θw _w is optimized only against the deviations contained in w. Theorem 12 therefore controls the outer value, while recovery of the corresponding full-domain optimal potential is governed asymptotically by the structural conditions of Proposition 4. TABLE I: Post-selected outputs for the 50-player game with c=1c=1, after independent DRPDM re-evaluation with Kreeval=50,000K_reeval=50,000. α0 _0 δ0 _0 Selected t ℰ(θout)E( _out) Improvement 10−210^-2 0.01250.0125 140 32.730435 0.776793(2.32%) -0.776793\;(2.32\%) −10^-2 0.0250.025 163 31.776847 1.730381(5.16%)1.730381\;(5.16\%) 10−310^-3 0.01250.0125 67 33.584310 −0.077082(−0.23%)-0.077082\;(-0.23\%) 10−310^-3 0.0250.025 160 32.786437 0.720791(2.15%) -0.720791\;(2.15\%) Fig. 4: Best-so-far exact errors (top) and finite-tuple values (bottom) for the 5050-player ZO experiment. Columns correspond to δ0∈0.00625,0.0125,0.025 _0∈\0.00625,0.0125,0.025\, and curves to α0∈10−2,10−3,10−4 _0∈\10^-2,10^-3,10^-4\. The dashed lines mark ℰ(θ0)=33.5072E( _0)=33.5072. VI Conclusion We studied distributed computation of near-potential approximations for continuous-action general-sum games. An exact finite-tuple reformulation separates the problem into a global search over deviation tuples and distributed convex inner problem. For the inner problem, we developed a regularized primal–dual oracle with a uniform one-sided accuracy guarantee. Combined with EXOTIC, this yields an end-to-end global-search guarantee, while projected zeroth-order ascent provides a more scalable alternative. We also established sufficient conditions for recovering an optimizer of the original full-domain problem. Numerical experiments illustrate the tradeoff between global search accuracy and computational scalability. References [1] J. R. Marden, G. Arslan, and J. S. Shamma, “Cooperative control and potential games,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 39, no. 6, p. 1393–1407, 2009. [2] T. Li, G. Peng, Q. Zhu, and T. Başar, “The confluence of networks, games, and learning a game-theoretic framework for multiagent decision making over networks,” IEEE Control Systems Magazine, vol. 42, no. 4, p. 35–67, 2022. [3] D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, no. 1, p. 124–143, 1996. [4] O. Candogan, A. Ozdaglar, and P. A. Parrilo, “Learning in near-potential games,” in 2011 50th IEEE Conference on Decision and Control and European Control Conference, p. 2428–2433, 2011. [5] X. Guo, X. Li, C. Maheshwari, S. Sastry, and M. Wu, “Markov α-potential games,” IEEE Transactions on Automatic Control, vol. 71, no. 1, p. 275–290, 2026. [6] K. Rokade, A. Jain, F. Parise, V. Krishnamurthy, and E. Tardos, “Asymmetric network games: α-potential function and learning,” arXiv preprint arXiv:2508.06619, 2025. [7] O. Candogan, A. Ozdaglar, and P. A. Parrilo, “Dynamics in near-potential games,” Games and Economic Behavior, vol. 82, p. 66–90, 2013. [8] X. Guo, X. Li, and Y. Zhang, “An α-potential game framework for n-player dynamic games,” arXiv preprint arXiv:2403.16962, 2024. [9] A. Kalanther, S. Bharvirkar, S. Sastry, and C. Maheshwari, “Neppo: Near-potential policy optimization for general-sum multi-agent reinforcement learning,” 2026. [10] C. Maheshwari, C. Pimpalkhare, and D. Chatterjee, “EXOTIC: An exact, optimistic, tree-based algorithm for min-max optimization,” arXiv preprint arXiv:2508.12479, 2026. [11] K. Srivastava, A. Nedić, and D. Stipanović, Distributed Bregman-Distance Algorithms for Min-Max Optimization, p. 143–174. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. [12] N. S. Aybat and E. Y. Hamedani, “A primal–dual method for conic constrained distributed optimization problems,” in Advances in Neural Information Processing Systems, vol. 29, p. 5049–5057, 2016. [13] Q. Xu, N. S. Aybat, and M. Gürbüzbalaban, “An accelerated primal–dual algorithm with backtracking for decentralized constrained optimization,” Journal of Nonlinear and Variational Analysis, vol. 10, no. 3, p. 555–596, 2026. [14] M. H. Stone, “The generalized weierstrass approximation theorem,” Mathematics Magazine, vol. 21, no. 5, p. 237–254, 1948. [15] M. B. Khuzani and N. Li, “Distributed regularized primal-dual method: Convergence analysis and trade-offs,” 2017. [16] D. Mateos-Núñez and J. Cortés, “Distributed saddle-point subgradient algorithms with laplacian averaging,” IEEE Transactions on Automatic Control, vol. 62, no. 6, p. 2720–2735, 2017. [17] A. Nedić and A. Ozdaglar, “Subgradient methods for saddle-point problems,” Journal of Optimization Theory and Applications, vol. 142, no. 1, p. 205–228, 2009. Appendix A Proof of Proposition 4 The value identity follows from the reformulation argument of [10, Proposition 2.1]. Indeed, ℓi(θ,y) _i(θ,y) is continuous in (θ,y)(θ,y) and affine, hence convex, in θ, while Θ and Y are compact. Compactness of Θ replaces the coercivity assumption used in [10] to guarantee boundedness and attainment. Therefore, p⋆=maxw∈G(w).p = _w G(w). Let w⋆∈argmaxw∈G(w)w ∈ *arg\,max_w G(w) and θw⋆∈argminθ∈ΘF(θ,w⋆) _w ∈ *arg\,min_θ∈ F(θ,w ). Then F(θw⋆,w⋆)=G(w⋆)=p⋆.F( _w ,w )=G(w )=p . For optimizer recovery, we verify the two alternative conditions of [10, Proposition 2.4]. Under condition (i), ℰ(θw⋆)=F(θw⋆,w⋆)=p⋆,E( _w )=F( _w ,w )=p , so θw⋆ _w solves the full-domain problem. It remains to consider condition (i). For every (i,j)∈S⋆(i,j)∈ S , define the active loss gradient gij⋆:=Δψ(yj⋆,i).g_ij := _ψ(y_j ;i). Fix any θ∈Θθ∈ with θ≠θw⋆θ≠ _w , and let v:=θ−θw⋆≠0.v:=θ- _w ≠ 0. For every (i,j)∈⋆(i,j) , the affinity gives ℓi(θ,yj⋆)=ℓi(θw⋆,yj⋆)+⟨gij⋆,θ−θw⋆⟩. _i(θ,y_j )= _i( _w ,y_j )+ g_ij ,θ- _w . Since every (i,j)∈S⋆(i,j)∈ S is active at θw⋆ _w , F(θ,w⋆) F(θ,w ) ≥max(i,j)∈S⋆ℓi(θ,yj⋆) ≥ _(i,j)∈ S _i(θ,y_j ) =F(θw⋆,w⋆)+max(i,j)∈S⋆⟨gij⋆,v⟩. =F( _w ,w )+ _(i,j)∈ S g_ij ,v . We claim that max(i,j)∈S⋆⟨gij⋆,v⟩>0. _(i,j)∈ S g_ij ,v >0. Suppose instead that ⟨gij⋆,v⟩≤0 g_ij ,v ≤ 0 for every (i,j)∈S⋆(i,j)∈ S . Then the convex hull of the active gradients is contained in the closed halfspace g∈ℝd:⟨g,v⟩≤0.\g ^d: g,v ≤ 0\. This contradicts condition (i), because 0∈intconvgij⋆:(i,j)∈S⋆0 \g_ij :(i,j)∈ S \ implies that this convex hull contains a neighborhood of the origin, including a point in the direction v with strictly positive inner product with v. Hence, F(θ,w⋆)>F(θw⋆,w⋆)for every θ∈Θ∖θw⋆.F(θ,w )>F( _w ,w ) every θ∈ \ _w \. Thus, θw⋆ _w is the unique minimizer of F(⋅,w⋆)F(·,w ). Finally, let θ⋆∈argminθ∈Θℰ(θ)θ ∈ *arg\,min_θ∈ E(θ). Since w⋆w maximizes G, p⋆=G(w⋆)=minθ∈ΘF(θ,w⋆)≤F(θ⋆,w⋆).p =G(w )= _θ∈ F(θ,w )≤ F(θ ,w ). On the other hand, the tuple elements y1⋆,…,yd+1⋆y_1 ,…,y_d+1 belong to Y, so F(θ⋆,w⋆)=maxi,jℓi(θ⋆,yj⋆)≤maxi,y∈ℓi(θ⋆,y)=ℰ(θ⋆)=p⋆.F(θ ,w )= _i,j _i(θ ,y_j )≤ _i,\;y _i(θ ,y)=E(θ )=p . Hence F(θ⋆,w⋆)=G(w⋆)F(θ ,w )=G(w ), and therefore θ⋆θ also minimizes F(⋅,w⋆)F(·,w ). Its uniqueness gives θ⋆=θw⋆θ = _w , and hence θw⋆∈argminθ∈Θℰ(θ). _w ∈ *arg\,min_θ∈ E(θ). This proves optimizer recovery under condition (i). Appendix B Auxiliary Results Lemma 13 Let ρ∈(0,1)ρ∈(0,1) and ξ∈(0,1)ξ∈(0,1). Then, for every k≥1k≥ 1, ρk≤(ξe|logρ|)ξk−ξ,ρ^k≤ ( ξe| ρ| )^ξk^-ξ, (24) and ∑s=0k−1ρk−1−s(s+1)−ξ≤Cρ,ξk−ξ, _s=0^k-1ρ^k-1-s(s+1)^-ξ≤ C_ρ,ξk^-ξ, (25) where Cρ,ξ:=2ξ1−ρ+2e(1−ξ)|logρ|.C_ρ,ξ:= 2^ξ1-ρ+ 2e(1-ξ)| ρ|. Proof: Let b:=|logρ|>0b:=| ρ|>0 and define f(x):=xξe−bxf(x):=x^ξe^-bx for x>0x>0. Since f′(x)=xξ−1e−bx(ξ−bx),f (x)=x^ξ-1e^-bx(ξ-bx), f is increasing on (0,ξ/b)(0,ξ/b) and decreasing on (ξ/b,∞)(ξ/b,∞). Hence, supx>0xξρx=f(ξb)=(ξe|logρ|)ξ. _x>0x^ξρ^x=f ( ξb )= ( ξe| ρ| )^ξ. Taking x=kx=k proves (24). To prove (25), first rewrite the convolution as ∑s=0k−1ρk−1−s(s+1)−ξ=∑t=1kρk−tt−ξ. _s=0^k-1ρ^k-1-s(s+1)^-ξ= _t=1^kρ^k-tt^-ξ. We split the index set into ℐ1:=t∈[k]:t<k/2,ℐ2:=t∈[k]:t≥k/2.I_1:=\t∈[k]:t<k/2\, _2:=\t∈[k]:t≥ k/2\. For t∈ℐ2t _2, we have t−ξ≤2ξk−ξt^-ξ≤ 2^ξk^-ξ. Therefore, ∑t∈ℐ2ρk−tt−ξ _t _2ρ^k-tt^-ξ ≤2ξk−ξ∑t∈ℐ2ρk−t ≤ 2^ξk^-ξ _t _2ρ^k-t ≤2ξ1−ρk−ξ. ≤ 2^ξ1-ρk^-ξ. For t∈ℐ1t _1, we have k−t>k/2k-t>k/2 and hence ρk−t≤ρk/2ρ^k-t≤ρ^k/2. Since ξ∈(0,1)ξ∈(0,1), ∑t∈ℐ1t−ξ≤∑t=1kt−ξ≤∫0kx−ξx=k1−ξ1−ξ. _t _1t^-ξ≤ _t=1^kt^-ξ≤ _0^kx^-ξ\,dx= k^1-ξ1-ξ. It follows that ∑t∈ℐ1ρk−tt−ξ _t _1ρ^k-tt^-ξ ≤ρk/2k1−ξ1−ξ ≤ ρ^k/2k^1-ξ1-ξ =kρk/21−ξk−ξ. = kρ^k/21-ξk^-ξ. To bound the remaining factor, define g(x):=xρx/2g(x):=xρ^x/2 for x>0x>0. Since g′(x)=ρx/2(1−|logρ|2x),g (x)=ρ^x/2 (1- | ρ|2x ), the maximum of g is attained at x=2/|logρ|x=2/| ρ|. Consequently, kρk/2≤supx>0xρx/2=2e|logρ|.kρ^k/2≤ _x>0xρ^x/2= 2e| ρ|. Thus, ∑t∈ℐ1ρk−tt−ξ≤2e(1−ξ)|logρ|k−ξ. _t _1ρ^k-tt^-ξ≤ 2e(1-ξ)| ρ|k^-ξ. Combining the bounds over ℐ1I_1 and ℐ2I_2 gives ∑s=0k−1ρk−1−s(s+1)−ξ _s=0^k-1ρ^k-1-s(s+1)^-ξ ≤[2ξ1−ρ+2e(1−ξ)|logρ|]k−ξ ≤ [ 2^ξ1-ρ+ 2e(1-ξ)| ρ| ]k^-ξ =Cρ,ξk−ξ. =C_ρ,ξk^-ξ. This proves (25). ∎ Lemma 14 For r>0r>0 and K≥1K≥ 1, define Hr(K):=∑k=1Kk−r.H_r(K):= _k=1^Kk^-r. Then, Hr(K)≤1+K1−r−11−r,0<r<1,1+logK,r=1,1+1r−1,r>1.H_r(K)≤ cases1+ K^1-r-11-r,&0<r<1,\\[5.69054pt] 1+ K,&r=1,\\[2.84526pt] 1+ 1r-1,&r>1. cases Consequently, for every fixed r>0r>0, there exists a constant Cr>0C_r>0, independent of K, such that Hr(K)≤Cr(1+logK)K[1−r]+.H_r(K)≤ C_r(1+ K)K^[1-r]_+. More generally, for every b∈ℝb , K−bHr(K)≤Cr(1+logK)K−minb,b+r−1.K^-bH_r(K)≤ C_r(1+ K)K^- \b,b+r-1\. Proof: If 0<r<10<r<1, the integral comparison gives Hr(K)≤1+∫1Kx−rx=1+K1−r−11−r.H_r(K)≤ 1+ _1^Kx^-r\,dx=1+ K^1-r-11-r. If r=1r=1, then H1(K)≤1+∫1K1xx=1+logK.H_1(K)≤ 1+ _1^K 1x\,dx=1+ K. Finally, if r>1r>1, Hr(K)≤1+∫1∞x−rx=1+1r−1.H_r(K)≤ 1+ _1^∞x^-r\,dx=1+ 1r-1. These three estimates imply Hr(K)≤Cr(1+logK)K[1−r]+H_r(K)≤ C_r(1+ K)K^[1-r]_+ for some constant Cr>0C_r>0. Multiplying both sides by K−bK^-b gives K−bHr(K)≤Cr(1+logK)K−b+[1−r]+.K^-bH_r(K)≤ C_r(1+ K)K^-b+[1-r]_+. Since b−[1−r]+=b+r−1,0<r<1,b,r≥1,=minb,b+r−1,b-[1-r]_+= casesb+r-1,&0<r<1,\\ b,&r≥ 1, cases= \b,b+r-1\, we obtain K−bHr(K)≤Cr(1+logK)K−minb,b+r−1.K^-bH_r(K)≤ C_r(1+ K)K^- \b,b+r-1\. ∎ Appendix C Complete Proofs for Section IV This appendix supplies the complete proofs of the results used in the finite-time analysis of the distributed oracle and in the outer-search guarantee. Throughout, constants may depend on the fixed game, compact sets, communication graph, and algorithm parameters, but not on the queried tuple w, the iteration budget K, or the initial primal points in Z. C-A Proof of Proposition 5 Given any feasible point (θ,t)(θ,t) of (7), for i∈ℐ,i , set zi=(θ,t).z_i=(θ,t). The resulting collection satisfies all the local and consensus constraints of the consensus formulation, and its objective value is (N)−1∑i=1Nti=t.(N)^-1 _i=1^Nt_i=t. Conversely, consider any feasible collection zii∈ℐ\z_i\_i of the consensus formulation. Because G is connected, the consensus constraints imply that z1=⋯=zN=(θ,t)z_1=·s=z_N=(θ,t) for some (θ,t)(θ,t). The local constraints then imply hiw(θ)≤th_i^w(θ)≤ t for every i∈ℐi . Therefore, (θ,t)(θ,t) is feasible for (7), and the two corresponding points have the same objective value. C-B Proof of Lemma 8 Let Cθ:=maxθ∈Θ‖θ‖2,Ct:=max|tmin|,|tmax|,C_θ:= _θ∈ \|θ\|_2, C_t:= \|t_ |,|t_ |\, and recall the uniform bounds Gψ:=maxi∈ℐ,y∈‖Δψ(y,i)‖2,G_ψ:= _i ,\,y \| ψ(y;i)\|_2, and U:=maxi∈ℐ,y∈|Δui(y,i)|.U:= _i ,\,y | u_i(y;i)|. These constants are finite by compactness and continuity. Since |ℓi(θ,y)|≤CθGψ+U| _i(θ,y)|≤ C_θG_ψ+U, compactness of =[tmin,tmax]T=[t_ ,t_ ] gives |hiw(θi[k])−ti[k]|≤Bμ,Bμ:=CθGψ+U+Ct, |h_i^w( _i[k])-t_i[k] |≤ B_μ, B_μ:=C_θG_ψ+U+C_t, uniformly over w, i, and k. The dual update and ηkβk≤cβ0≤1 _k _k≤ c _0≤ 1 yield μi[k+1] _i[k+1] =[(1−ηkβk)μi[k]+ηk(hiw(θi[k])−ti[k])]+ = [(1- _k _k) _i[k]+ _k (h_i^w( _i[k])-t_i[k] ) ]_+ ≤(1−ηkβk)μi[k]+ηkBμ. ≤(1- _k _k) _i[k]+ _kB_μ. We prove by induction that μi[k]≤Bμ/βk _i[k]≤ B_μ/ _k. The claim holds at k=0k=0 because μi[0]=0 _i[0]=0. If it holds at iteration k, then μi[k+1] _i[k+1] ≤(1−ηkβk)Bμβk+ηkBμ ≤(1- _k _k) B_μ _k+ _kB_μ =Bμβk≤Bμβk+1, = B_μ _k≤ B_μ _k+1, where the last inequality follows from βk+1≤βk _k+1≤ _k. Therefore, 0≤μi[k]≤Bμβk=Bμβ0(k+1)q0≤ _i[k]≤ B_μ _k= B_μ _0(k+1)^q for all i, k, and w. For later use, Algorithm 1 and ‖si[k]‖2≤Gψ\|s_i[k]\|_2≤ G_ψ also give ‖gi[k]‖2 \|g_i[k]\|_2 ≤μi[k](Gψ+1)+1N≤Cg(k+1)q, ≤ _i[k](G_ψ+1)+ 1N≤ C_g(k+1)^q, (26) |ri[k]| |r_i[k]| ≤Bμ+βkμi[k]≤2Bμ, ≤ B_μ+ _k _i[k]≤ 2B_μ, (27) where Cg:=Bμβ0(Gψ+1)+1N.C_g:= B_μ _0(G_ψ+1)+ 1N. All these bounds are uniform over w. C-C Proof of Lemma 9 Let P:=IN−σL,J:=1N⊤.P:=I_N-σ L_G, J:= 1N11 . Because the graph is undirected, L=0L_G1=0 and ⊤L=0⊤1 L_G=0 , so P=,⊤P=⊤.P1=1, 1 P=1 . Moreover, di=ei⊤Lei≤λmax(L)d_i=e_i L_Ge_i≤ _ (L_G). The condition σ≤1/λmax(L)σ≤ 1/ _ (L_G) therefore implies Pii=1−σdi≥0,Pij=σ[A]ij≥0(i≠j).P_i=1-σ d_i≥ 0, P_ij=σ[A_G]_ij≥ 0 (i≠ j). Hence, P is nonnegative and doubly stochastic. Let the eigenvalues of L_G be ordered as 0=λ1(L)<λ2(L)≤⋯≤λN(L).0= _1(L_G)< _2(L_G)≤·s≤ _N(L_G). Connectivity gives λ2(L)>0 _2(L_G)>0. Since 0<σ≤1/λmax(L)0<σ≤ 1/ _ (L_G), spectral decomposition gives ρ:=‖P−J‖2=1−σλ2(L)<1. _G:=\|P-J\|_2=1-σ _2(L_G)<1. (28) Let Z[k]Z[k] and [k] G[k] have rows zi[k]⊤z_i[k] and gi[k]⊤g_i[k] , respectively. Since ∑j∈i[A]ij(zj[k]−zi[k])=−(LZ[k])i⊤, _j _i[A_G]_ij(z_j[k]-z_i[k])=-(L_GZ[k])_i , the stacked unprojected primal update is PZ[k]−ηk[k].PZ[k]- _k G[k]. Also, ek=1N‖(IN−J)Z[k]‖F.e_k= 1 N\|(I_N-J)Z[k]\|_F. The pairwise-variance identity and nonexpansiveness of the common row-wise projection onto Z give ek+1 e_k+1 ≤1N‖(IN−J)(PZ[k]−ηk[k])‖F ≤ 1 N \|(I_N-J)(PZ[k]- _k G[k]) \|_F ≤1N‖P−J‖2‖(IN−J)Z[k]‖F ≤ 1 N\|P-J\|_2\|(I_N-J)Z[k]\|_F +ηkN‖IN−J‖2‖[k]‖F + _k N\|I_N-J\|_2\| G[k]\|_F ≤ρek+ηkCg(k+1)q, ≤ _Ge_k+ _kC_g(k+1)^q, where the last inequality uses (26). Substituting ηk=c(k+1)−τ _k=c(k+1)^-τ yields ek+1≤ρek+cCg(k+1)−(τ−q).e_k+1≤ _Ge_k+cC_g(k+1)^-(τ-q). (29) Put ξ:=τ−q>0ξ:=τ-q>0. Iterating (29) gives, for every k≥1k≥ 1, ek≤ρke0+cCg∑s=0k−1ρk−1−s(s+1)−ξ.e_k≤ _G^ke_0+cC_g _s=0^k-1 _G^k-1-s(s+1)^-ξ. Let D:=maxz,z′∈‖z−z′‖2.D_Z:= _z,z \|z-z \|_2. Convexity of Z implies zav[0]∈z_ av[0] and hence e0≤De_0≤ D_Z. If 0<ρ<10< _G<1, Lemma 14 gives ρk≤Cρ,1k−ξ,∑s=0k−1ρk−1−s(s+1)−ξ≤Cρ,2k−ξ. _G^k≤ C_ρ,1k^-ξ, _s=0^k-1 _G^k-1-s(s+1)^-ξ≤ C_ρ,2k^-ξ. Thus, for a constant Ce>0C_e>0 independent of w and k, ek≤Cekq−τ.e_k≤ C_ek^q-τ. When ρ=0 _G=0, the same conclusion follows directly from (29). Enlarging CeC_e to cover k=0k=0 gives ek≤Ce(k+1)q−τ,k≥0.e_k≤ C_e(k+1)^q-τ, k≥ 0. (30) We next pass to the weighted ergodic averages. Since z¯w[K]=1SK∑k=0K−1ηkzav[k], z_w[K]= 1S_K _k=0^K-1 _kz_ av[k], for every player i, z¯i[K]−z¯w[K]=1SK∑k=0K−1ηk(zi[k]−zav[k]). z_i[K]- z_w[K]= 1S_K _k=0^K-1 _k (z_i[k]-z_ av[k] ). The definition of eke_k implies ‖zi[k]−zav[k]‖2≤Nek\|z_i[k]-z_ av[k]\|_2≤ Ne_k, and hence maxi‖z¯i[K]−z¯w[K]‖2≤NSK∑k=0K−1ηkek=DK. _i\| z_i[K]- z_w[K]\|_2≤ NS_K _k=0^K-1 _ke_k=D_K. (31) Furthermore, (30) gives ∑k=0K−1ηkek _k=0^K-1 _ke_k ≤cD+cCe∑k=1Kk−(2τ−q) ≤ cD_Z+cC_e _k=1^Kk^-(2τ-q) ≤c[D+CeH2τ−q(K)]. ≤ c [D_Z+C_eH_2τ-q(K) ]. Since SK=c∑k=1Kk−τ≥cK1−τS_K=c _k=1^Kk^-τ≥ cK^1-τ, DK≤NKτ−1[D+CeH2τ−q(K)].D_K≤ NK^τ-1 [D_Z+C_eH_2τ-q(K) ]. Applying Lemma 14 in Appendix B with b=1−τb=1-τ and r=2τ−qr=2τ-q yields DK≤CD(1+logK)K−minτ−q,1−τ,D_K≤ C_D(1+ K)K^- \τ-q,1-τ\, which proves both claims. C-D Proof of Lemma 10 For compactness, write ci[k]:=hiw(θi[k])−ti[k]c_i[k]:=h_i^w( _i[k])-t_i[k] and define the local unregularized Lagrangian ℒi(zi,μi):=tiN+μi(hiw(θi)−ti).L_i(z_i, _i):= t_iN+ _i (h_i^w( _i)-t_i ). Thus, ℒ(Z,μ):=∑i=1Nℒi(zi,μi).L(Z,μ):= _i=1^NL_i(z_i, _i). Fix a consensus comparator Zc=z⊤Z_c=1z , with z∈z , and any μ∈ℝ+Nμ _+^N. Let vi[k]:=∑j=1NPijzj[k].v_i[k]:= _j=1^NP_ijz_j[k]. Then the primal update is zi[k+1]=P(vi[k]−ηkgi[k]).z_i[k+1]=P_Z(v_i[k]- _kg_i[k]). Because z=P(z)z=P_Z(z), nonexpansiveness gives ‖zi[k+1]−z‖22≤‖vi[k]−ηkgi[k]−z‖22=‖vi[k]−z‖22−2ηk⟨gi[k],zi[k]−z⟩+2ηk⟨gi[k],zi[k]−vi[k]⟩+ηk2‖gi[k]‖22.\|z_i[k+1]-z\|_2^2≤\|v_i[k]- _kg_i[k]-z\|_2^2\\ =\|v_i[k]-z\|_2^2-2 _k g_i[k],z_i[k]-z \\ +2 _k g_i[k],z_i[k]-v_i[k] + _k^2\|g_i[k]\|_2^2. Since P is doubly stochastic, Jensen’s inequality yields ∑i‖vi[k]−z‖22≤∑i‖zi[k]−z‖22. _i\|v_i[k]-z\|_2^2≤ _i\|z_i[k]-z\|_2^2. Moreover, μi[k]≥0 _i[k]≥ 0 makes ℒi(⋅,μi[k])L_i(·, _i[k]) convex, and gi[k]∈∂zℒi(zi[k],μi[k])g_i[k]∈ _zL_i(z_i[k], _i[k]). Therefore, ⟨gi[k],zi[k]−z⟩≥ℒi(zi[k],μi[k])−ℒi(z,μi[k]). g_i[k],z_i[k]-z _i(z_i[k], _i[k])-L_i(z, _i[k]). Because P=IN−σLP=I_N-σ L_G, ∑i⟨gi[k],zi[k]−vi[k]⟩=σ⟨[k],LZ[k]⟩F. _i g_i[k],z_i[k]-v_i[k] =σ G[k],L_GZ[k] _F. Summing the preceding projection inequality over i gives ηk∑i[ℒi(zi[k],μi[k])−ℒi(z,μi[k])] _k _i [L_i(z_i[k], _i[k])-L_i(z, _i[k]) ] ≤12∑i(‖zi[k]−z‖22−‖zi[k+1]−z‖22) ≤ 12 _i (\|z_i[k]-z\|_2^2-\|z_i[k+1]-z\|_2^2 ) +ηkσ⟨[k],LZ[k]⟩F+ηk22∑i‖gi[k]‖22. + _kσ G[k],L_GZ[k] _F+ _k^22 _i\|g_i[k]\|_2^2. (32) For the dual update, projection onto ℝ+R_+ gives, for every comparator μi≥0 _i≥ 0, |μi[k+1]−μi|2 | _i[k+1]- _i|^2 ≤|μi[k]−μi+ηkri[k]|2 ≤ | _i[k]- _i+ _kr_i[k] |^2 =|μi[k]−μi|2+2ηk(μi[k]−μi)ci[k] =| _i[k]- _i|^2+2 _k( _i[k]- _i)c_i[k] −2ηkβkμi[k](μi[k]−μi) -2 _k _k _i[k]( _i[k]- _i) +ηk2|ri[k]|2. + _k^2|r_i[k]|^2. Completing the square gives (μi−μi[k])μi[k]=μi24−(μi[k]−μi2)2≤μi24.( _i- _i[k]) _i[k]= _i^24- ( _i[k]- _i2 )^2≤ _i^24. Since ℒi(zi[k],⋅)L_i(z_i[k],·) is affine, ℒi(zi[k],μi)−ℒi(zi[k],μi[k])=(μi−μi[k])ci[k].L_i(z_i[k], _i)-L_i(z_i[k], _i[k])=( _i- _i[k])c_i[k]. Rearranging the dual projection inequality therefore gives ηk[ℒi(zi[k],μi)−ℒi(zi[k],μi[k])] _k [L_i(z_i[k], _i)-L_i(z_i[k], _i[k]) ] ≤12(|μi[k]−μi|2−|μi[k+1]−μi|2) ≤ 12 (| _i[k]- _i|^2-| _i[k+1]- _i|^2 ) +ηk22|ri[k]|2+ηkβk4μi2. + _k^22|r_i[k]|^2+ _k _k4 _i^2. (33) Let Z¯[K] Z[K] have rows z¯i[K]⊤ z_i[K] and define μ¯[K]:=1SK∑k=0K−1ηkμ[k]. μ[K]:= 1S_K _k=0^K-1 _kμ[k]. Convexity of ℒ(⋅,μ)L(·,μ) and affinity of ℒ(Zc,⋅)L(Z_c,·) imply SK[ℒ(Z¯[K],μ)−ℒ(Zc,μ¯[K])]≤∑k=0K−1ηk[ℒ(Z[k],μ)−ℒ(Zc,μ[k])].S_K [L( Z[K],μ)-L(Z_c, μ[K]) ]\\ ≤ _k=0^K-1 _k [L(Z[k],μ)-L(Z_c,μ[k]) ]. Adding (33), summed over i, to (32), and then summing over k, makes all distance terms telescope. Since zi[0],z∈z_i[0],z , μi[0]=0 _i[0]=0, and the dropped terminal squared distances are nonnegative, we obtain SK[ℒ(Z¯[K],μ)−ℒ(Zc,μ¯[K])] S_K [L( Z[K],μ)-L(Z_c, μ[K]) ] ≤ND22+σ∑k=0K−1ηk|⟨[k],LZ[k]⟩F| ≤ ND_Z^22+σ _k=0^K-1 _k | G[k],L_GZ[k] _F | +12∑k=0K−1ηk2∑i(∥gi[k]∥22+|ri[k]|2) + 12 _k=0^K-1 _k^2 _i (\|g_i[k]\|_2^2+|r_i[k]|^2 ) +(12+14∑k=0K−1ηkβk)‖μ‖22. + ( 12+ 14 _k=0^K-1 _k _k )\|μ\|_2^2. (34) It remains to control the mixing and squared-direction terms. Since LJ=0L_GJ=0, Cauchy–Schwarz, (26), and the definition of eke_k yield |⟨[k],LZ[k]⟩F| | G[k],L_GZ[k] _F | ≤‖[k]‖F‖L‖2‖(IN−J)Z[k]‖F ≤\| G[k]\|_F\|L_G\|_2\|(I_N-J)Z[k]\|_F ≤N‖L‖2Cg(k+1)qek. ≤ N\|L_G\|_2C_g(k+1)^qe_k. Furthermore, (26)–(27) imply ∑i(‖gi[k]‖22+|ri[k]|2)≤C1(k+1)2q _i (\|g_i[k]\|_2^2+|r_i[k]|^2 )≤ C_1(k+1)^2q for a uniform constant C1>0C_1>0. Substituting these two bounds into (34), absorbing all fixed constants into C0>0C_0>0, and dividing by SKS_K gives ℒ(Z¯[K],μ)−ℒ(Zc,μ¯[K])≤RK+QK‖μ‖22,L( Z[K],μ)-L(Z_c, μ[K])≤ R_K+Q_K\|μ\|_2^2, where RKR_K and QKQ_K are exactly those defined in Lemma 10. The constant C0C_0 is independent of w, K, and the initial primal points because D_Z and all constants above are uniform. C-E Proof of Theorem 7 Fix w∈w and choose θw⋆ _w ∈argminθ∈ΘF(θ,w), ∈ _θ∈ F(θ,w), zw⋆ z_w :=(θw⋆,G(w)), :=( _w ,G(w)), Zc Z_c :=(zw⋆)⊤. :=1(z_w ) . The point zw⋆z_w is feasible for the epigraph problem, so ℒ(Zc,μ¯[K])≤G(w).L(Z_c, μ[K])≤ G(w). (35) Let iKi_K attain F(θ¯w[K],w)=hiKw(θ¯w[K]),F( θ_w[K],w)=h_i_K^w( θ_w[K]), let eiKe_i_K be the corresponding coordinate unit vector, and set t¯w[K]:=N−1∑it¯i[K] t_w[K]:=N^-1 _i t_i[K]. Then ℒ(Z¯[K],eiK)=t¯w[K]+hiKw(θ¯iK[K])−t¯iK[K].L( Z[K],e_i_K)= t_w[K]+h_i_K^w( θ_i_K[K])- t_i_K[K]. Since hiwh_i^w is GψG_ψ-Lipschitz and ‖z¯iK[K]−z¯w[K]‖2≤DK\| z_i_K[K]- z_w[K]\|_2≤ D_K, F(θ¯w[K],w) F( θ_w[K],w) ≤hiKw(θ¯iK[K])+GψDK ≤ h_i_K^w( θ_i_K[K])+G_ψD_K ≤ℒ(Z¯[K],eiK)+(Gψ+1)DK. ( Z[K],e_i_K)+(G_ψ+1)D_K. Applying Lemma 10 with μ=eiKμ=e_i_K, using ‖eiK‖2=1\|e_i_K\|_2=1, and invoking (35) gives 0≤G^K(w)−G(w)≤RK+QK+(Gψ+1)DK.0≤ G_K(w)-G(w)≤ R_K+Q_K+(G_ψ+1)D_K. (36) The lower bound follows directly from G(w)=minθ∈ΘF(θ,w)G(w)= _θ∈ F(θ,w). It remains to bound the three terms uniformly. Let Hr(K):=∑k=1Kk−rH_r(K):= _k=1^Kk^-r. From the definitions of RKR_K and QKQ_K, the pointwise consensus estimate (30), and SK≥cK1−τS_K≥ cK^1-τ, the right-hand side of (36) is bounded by a uniform constant multiple of Kτ−1[1+H2τ−2q(K)+Hτ+q(K)+H2τ−q(K)].K^τ-1 [1+H_2τ-2q(K)+H_τ+q(K)+H_2τ-q(K) ]. Indeed, ∑k=0K−1ηk2(k+1)2q _k=0^K-1 _k^2(k+1)^2q =c2H2τ−2q(K), =c^2H_2τ-2q(K), ∑k=0K−1ηk(k+1)qek _k=0^K-1 _k(k+1)^qe_k ≤cCeH2τ−2q(K), ≤ cC_eH_2τ-2q(K), ∑k=0K−1ηkβk _k=0^K-1 _k _k =cβ0Hτ+q(K), =c _0H_τ+q(K), while Lemma 9 supplies the H2τ−q(K)H_2τ-q(K) term through DKD_K. Applying Lemma 14 gives the respective decay exponents 1−τ, 1-τ, min1−τ,τ−2q, \1-τ,τ-2q\, min1−τ,q, \1-τ,q\, min1−τ,τ−q, \1-τ,τ-q\, up to a factor 1+logK1+ K. Their minimum is γc(τ,q)=minq,τ−2q,1−τ>0. _c(τ,q)= \q,τ-2q,1-τ\>0. Therefore, for a constant C>0C>0 independent of w, K, and the initial primal points, 0≤G^K(w)−G(w)≤C(1+logK)K−γc(τ,q).0≤ G_K(w)-G(w)≤ C(1+ K)K^- _c(τ,q). Setting τ=3/4τ=3/4 and q=1/4q=1/4 gives γc(τ,q)=minq,τ−2q,1−τ=14. _c(τ,q)= \q,τ-2q,1-τ\= 14. Therefore, 0≤G^K(w)−G(w)≤C(1+logK)K−1/4=~(K−1/4)0≤ G_K(w)-G(w)≤ C(1+ K)K^-1/4= O(K^-1/4) uniformly over w∈w , which proves Theorem 7. C-F Proof of Lemma 11 Let w=(y1,…,yd+1)w=(y_1,…,y_d+1) and w~=(y~1,…,y~d+1) w=( y_1,…, y_d+1). For any i, θ, and y,y~∈y, y , the definitions of ℓi _i, CθC_θ, LψL_ψ, and LuL_u give |ℓi(θ,y)−ℓi(θ,y~)| | _i(θ,y)- _i(θ, y)| ≤|⟨θ,Δψ(y,i)−Δψ(y~,i)⟩| ≤| θ, ψ(y;i)- ψ( y;i) | +|Δui(y,i)−Δui(y~,i)| +| u_i(y;i)- u_i( y;i)| ≤2(CθLψ+Lu)‖y−y~‖2 ≤ 2(C_θL_ψ+L_u)\|y- y\|_2 =Lgame‖y−y~‖2. =L_ game\|y- y\|_2. Taking finite maxima over players and tuple components preserves this common Lipschitz bound. Thus, for every θ∈Θθ∈ , |F(θ,w)−F(θ,w~)|≤Lgamed(w,w~).|F(θ,w)-F(θ, w)|≤ L_ gamed_W(w, w). Let θw~ _ w minimize F(⋅,w~)F(·, w). Then G(w)−G(w~) G(w)-G( w) ≤F(θw~,w)−F(θw~,w~) ≤ F( _ w,w)-F( _ w, w) ≤Lgamed(w,w~). ≤ L_ gamed_W(w, w). Interchanging w and w~ w proves |G(w)−G(w~)|≤Lgamed(w,w~).|G(w)-G( w)|≤ L_ gamed_W(w, w). If w⋆w and w lie in the same cell h,rW_h,r, the partition-diameter condition consequently gives G(w⋆)−G(w)≤Lgameαρh=νgameρh.G(w )-G(w)≤ L_ game _Wρ^h= _ gameρ^h. C-G Proof of Theorem 12 Theorem 7 gives the uniform one-sided oracle bound for all w∈,K≥1,w ,\,K≥ 1, 0≤G^K(w)−G(w)≤C(1+logK)K−1/4,0≤ G_K(w)-G(w)≤ C(1+ K)K^-1/4, (37) for some constant C>0C>0 independent of w and K. Lemma 11 and the geometric partition-diameter condition in (18) imply that every cell h,rW_h,r containing an optimizer w⋆w satisfies supw∈h,r(G(w⋆)−G(w))≤νgameρh. _w _h,r (G(w )-G(w) )≤ _gameρ^h. Moreover, (19) supplies the admissible near-optimality exponent dGd_G. To make the oracle error in (37) comparable to the depth-h resolution ρhρ^h, an inner budget of order Kh=~(ρ−4h)K_h= O(ρ^-4h) is sufficient. At the same depth, the number of near-optimal cells is at most of order ρ−dGhρ^-d_Gh. Consequently, the total inner work required by the EXOTIC search to resolve depth h is ~(ρ−(dG+4)h). O (ρ^-(d_G+4)h ). Equivalently, under total inner-iteration budget n, the finest achievable resolution satisfies ρh=~(n−1/(dG+4)).ρ^h= O (n^-1/(d_G+4) ). This is the budget argument in [10, Theorem 3.3 and Corollary 3.5], with the logarithmic oracle factor absorbed into ~ O. Hence, for the refined estimate returned by EXOTIC, p⋆−G^n=~(n−1/(dG+4)),p - G_n= O (n^-1/(d_G+4) ), (38) where G^n:=G^Kfinal(w^n). G_n:= G_K_final( w_n). Under the EXOTIC budget rule, hmax=⌊2n5B(1+logn)2⌋,Kfinal=⌊hmax/2⌋=Θ~(n).h_ = 2n5B(1+ n)^2 , K_final= h_ /2 = (n). Therefore, the final re-evaluation satisfies 0≤G^n−G(w^n)=~(n−1/4).0≤ G_n-G( w_n)= O(n^-1/4). Combining this bound with (38) gives p⋆−G(w^n) p -G( w_n) =p⋆−G^n+G^n−G(w^n) =p - G_n+ G_n-G( w_n) =~(n−1/(dG+4))+~(n−1/4). = O (n^-1/(d_G+4) )+ O(n^-1/4). Since dG≥0d_G≥ 0, 1dG+4≤14, 1d_G+4≤ 14, so the final re-evaluation error is no slower than the outer-search rate. Thus, 0≤p⋆−G(w^n)=~(n−1/(dG+4)).0≤ p -G( w_n)= O (n^-1/(d_G+4) ). Appendix D The EXOTIC Tree-Search Procedure For completeness, Algorithm 2 reproduces the EXOTIC procedure of [10], with minor notational changes and corrections of typographical errors. We use B for the branching factor, reserving K for the DRPDM iteration budget. For w∈w , z∈φ(w)z∈ (w), and H≥1H≥ 1, define H(w,z):=F(OPT(w,z,H),w). Eval_H(w,z):=F (OPT(w,z,H),w ). In our implementation, OPTOPT is instantiated by the distributed oracle in Algorithm 1. Algorithm 2 EXOTIC tree search [10] 1: Depth hmaxh_ , branching factor B, representatives (wh,r,zh,r)h,r\(w_h,r,z_h,r)\_h,r 2: Initialize (B)T^(B) with root (w0,1,G0,1=0,z0,1,#0,1=0)(w_0,1,G_0,1=0,z_0,1,\#_0,1=0) 3: for r=1,…,Br=1,…,B do 4: G1,r←hmax(w1,r,z1,r)G_1,r← Eval_h_ (w_1,r,z_1,r) 5: #1,r←hmax\#_1,r← h_ ; append (1,r)(1,r) to the root 6: end for 7: Tree-expansion phase 8: for h=1,…,hmaxh=1,…,h_ do 9: for m=1,…,⌊hmax/h⌋m=1,…, h_ /h do 10: H←⌊hmax/(hm)⌋H← h_ /(hm) 11: (h,r¯)←argmax(h,r)∈leaf(B)#h,r≥HGh,r(h, r)← _ subarrayc(h,r) _ leaf^(B)\\ \#_h,r≥ H subarrayG_h,r 12: Append the B children of (h,r¯)(h, r) 13: for r=1,…,Br=1,…,B do 14: Gh+1,r←H(wh+1,r,zh+1,r)G_h+1,r← Eval_H(w_h+1,r,z_h+1,r) 15: #h+1,r←H\#_h+1,r← H 16: end for 17: end for 18: end for 19: Re-evaluation phase 20: for p=0,…,⌊log2hmax⌋p=0,…, _2h_ do 21: (hp,rp)←argmax(h,r)∈(B)#h,r≥2pGh,r(h_p,r_p)← _ subarrayc(h,r) ^(B)\\ \#_h,r≥ 2^p subarrayG_h,r 22: Ghp,rp←⌊hmax/2⌋(whp,rp,zhp,rp)G_h_p,r_p← Eval_ h_ /2 (w_h_p,r_p,z_h_p,r_p) 23: end for 24: p^←argmax0≤p≤⌊log2hmax⌋Ghp,rp p← _0≤ p≤ _2h_ G_h_p,r_p 25: w^n←whp^,rp w_n← w_h_ p,r_ p 26: G^n←Ghp^,rp G_n← G_h_ p,r_ p 27: return G^n,w^n G_n, w_n Appendix E Projected Zeroth-Order Ascent Algorithm 3 gives the complete projected zeroth-order procedure. Each outer iteration uses two DRPDM evaluations, and the final tuple is re-evaluated using the larger budget KfinalK_ final. The exponents rδr_δ and rαr_α control the decay of the perturbation radius and outer stepsize, respectively; their numerical values are specified in Section V. Algorithm 3 Projected Zeroth-Order Ascent with DRPDM Evaluations 1: Outer budget T; inner budgets Ktt=0T−1\K_t\_t=0^T-1; final budget KfinalK_ final; δ0,α0>0 _0, _0>0 with δ0≠∅W_ _0≠ ; w0∈δ0w_0 _ _0; set δt=δ0(t+1)−rδ _t= _0(t+1)^-r_δ and αt=α0(t+1)−rα _t= _0(t+1)^-r_α. 2: for t=0,…,T−1t=0,…,T-1 do 3: Sample vt∼Unif(D−1)v_t (S^D_W-1) 4: wt+←wt+δtvtw_t^+← w_t+ _tv_t 5: Run Algorithm 1 on wtw_t and wt+w_t^+, each for KtK_t iterations with multipliers initialized to zero 6: Obtain G^t0 G_t^0 and G^t+ G_t^+ 7: g^t←(D/δt)(G^t+−G^t0)vt g_t←(D_W/ _t)( G_t^+- G_t^0)v_t 8: wt+1←Pδt+1(wt+αtg^t)w_t+1← P_W_ _t+1(w_t+ _t g_t) 9: end for 10: Run Algorithm 1 on wTw_T for KfinalK_final iterations 11: return wTw_T, θ^T:=θ¯wT[Kfinal] θ_T:= θ_w_T[K_final], and G^T:=F(θ^T,wT) G_T:=F( θ_T,w_T) Appendix F Exact Full-Domain Error for Linear–Quadratic Network Games This appendix derives the closed-form expression used to evaluate the full-domain error in the linear–quadratic network-game experiments. Recall the utility functions and quadratic potential parameterization introduced in Section V-C. For a unilateral deviation y=(a,ai′)y=(a,a_i ), the corresponding error is ℓi(θ,y)=(ai′−ai)[Ai(θ)(ai′+ai)+Bi(θ)+∑j≠iCij(θ)aj], _i(θ,y)=(a_i -a_i) [A_i(θ)(a_i +a_i)+B_i(θ)+ _j≠ iC_ij(θ)a_j ], (39) where Ai(θ):=pi+12,A_i(θ):=p_i+ 12, Bi(θ):=qi−ζi,B_i(θ):=q_i- _i, and for all j≠i,j≠ i, Cij(θ):=rmini,j,maxi,j−γVij.C_ij(θ):=r_ \i,j\, \i,j\-γ V_ij. Define Ki(θ):=|Bi(θ)|+∑j≠i|Cij(θ)|.K_i(θ):=|B_i(θ)|+ _j≠ i|C_ij(θ)|. (40) Maximizing (39) over the full action domain gives ℰ(θ)=maxi∈[N]Hi(θ),E(θ)= _i∈[N]H_i(θ), (41) where Hi(θ)=2Ki(θ),Ki(θ)≥2|Ai(θ)|,|Ai(θ)|+Ki(θ)+Ki(θ)24|Ai(θ)|,0≤Ki(θ)<2|Ai(θ)|.H_i(θ)= cases2K_i(θ),&K_i(θ)≥ 2|A_i(θ)|,\\[2.84526pt] |A_i(θ)|+K_i(θ)+ K_i(θ)^24|A_i(θ)|,&0≤ K_i(θ)<2|A_i(θ)|. cases (42) When Ai(θ)=0A_i(θ)=0, the first case applies. Hence, all reported full-domain errors are evaluated exactly, without discretizing or sampling the action space.