Distributed Algorithms for $α$-Potential Functions in General-Sum Games

Yifei Chen; Chinmay Maheshwari

cs.MAOct 4, 2026

Distributed Algorithms for $α$ -Potential Functions in General-Sum Games

Authors: Yifei Chen, Chinmay Maheshwari

Organizations: Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, Maryland, USA · Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, Maryland, USA

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.

Figures & tables

Panel of Figure 1 — Fig. 1 : Centralized outer search coupled with the distributed inner oracle.

Fig. 2 : Representative best-so-far finite-tuple values and exact full-domain errors for the two-player game: DRPDM-based EXOTIC (

h_{\max}=2000

s=10^{4}

; left) and ZO (

\alpha_{0}=0.1

\delta_{0}=0.025

; right). The dashed lines mark

p^{\star}=2

Method	Configuration	$\widehat{G}$	$\mathcal{E}(\widehat{\theta})$	$\mathcal{E}(\widehat{\theta})-p^{\star}$	$\\|\widehat{\theta}-\theta^{\star}\\|_{2}$	Time (s)
ZO	$(10^{-2},0.0125)$	0.3063	2.3436	0.3436	0.4650	12.68
	$(3\times 10^{-2},0.0125)$	0.4363	2.4676	0.4676	1.0612	12.43
	$(10^{-1},0.025)$	0.6550	2.4251	0.4251	0.8502	12.30
EXOTIC	$(500,10^{4})$	1.6265	2.4512	0.4512	0.5217	6.98
	$(1000,10^{4})$	1.9006	2.1555	0.1555	0.1166	16.39
	$(2000,10^{4})$	1.9214	2.0655	0.0655	0.1088	38.37

TABLE I : Performance on the two-player continuous game. For ZO, the configuration denotes

(\alpha_{0},\delta_{0})

; for EXOTIC, it denotes

(h_{\max},s)

Fig. 3 : Representative EXOTIC search ( $h_{\max}=2000$ , $s=10^{4}$ ). The dashed line marks $\mathcal{E}(\theta_{0})=\|V-V^{\top}\|_{\infty}$ .

$\alpha_{0}$	$\delta_{0}$	Selected $t$	$\mathcal{E}(\theta_{\mathrm{out}})$	Improvement
$10^{-2}$	$0.0125$	140	32.730435	$\phantom{-}0.776793\;(2.32\%)$
$\mathbf{10^{-2}}$	$\mathbf{0.025}$	163	31.776847	$\mathbf{1.730381\;(5.16\%)}$
$10^{-3}$	$0.0125$	67	33.584310	$-0.077082\;(-0.23\%)$
$10^{-3}$	$0.025$	160	32.786437	$\phantom{-}0.720791\;(2.15\%)$

TABLE II : Post-selected outputs for the 50-player game with

c=1

, after independent DRPDM re-evaluation with

K_{\mathrm{reeval}}=50{,}000

Fig. 4 : Best-so-far exact errors (top) and finite-tuple values (bottom) for the $50$ -player ZO experiment. Columns correspond to $\delta_{0}\in\{0.00625,0.0125,0.025\}$ , and curves to $\alpha_{0}\in\{10^{-2},10^{-3},10^{-4}\}$ . The dashed lines mark $\mathcal{E}(\theta_{0})=33.5072$ .

Explore similar work

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
Sep 14, 2026S. Rasoul EtesamiMean Field Games Observable Stochastic Game
Department of Industrial and Systems Engineering Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA
Minimax Last-Iterate Convergence in Matrix Games with Observed Actions
Sep 28, 2026Yuheng ZhangImperfect-Information Games Minimax
University of Illinois Urbana-Champaign
Efficient Gradient Methods for Distributed Saddle Problems
May 18, 2026Ruichen Luo, Anton Rodomanov, Sebastian U. StichDecentralized Optimization Primal-Dual Methods
Institute of Science and Technology Austria · CISPA Helmholtz Center

Sep 14, 2026, cs.LGJ/K move · Enter open · S save

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

S. Rasoul Etesami

Department of Industrial and Systems Engineering Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA

Mean Field Games Observable Stochastic Game Nash Equilibrium Decentralized Learning

Open paper AskPDF arXiv

We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov

α

-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order

\widetilde O(T^{-1/4})

and

\widetilde O(T^{-2/15})

for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error

α

. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov

α

-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.

Abstract

Explore similar work

High-Probability Nash Regret for Decentralized Learning in Markov ααα-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

Efficient Gradient Methods for Distributed Saddle Problems

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games