Distributed Algorithms for α-Potential Functions in General-Sum Games
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.
Related
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Optimization Frameworks & Learning Algorithms for Discrete-Time Mean Field Games
- Distributed Attacker Assignment and Interception Control in Multi-Agent Target-Attacker-Defender Games
- Variational Contraction Conditions for Iterative Algorithms in Multi-Population Discrete-Time Regularized Mean-Field Games
- Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms
BibTeX
@misc{chen2026distributed,
title = {{Distributed Algorithms for $α$-Potential Functions in General-Sum Games}},
author = {Yifei Chen and Chinmay Maheshwari},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05516},
eprint = {2610.05516},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05516},
}
RIS
TY - UNPB
TI - Distributed Algorithms for α-Potential Functions in General-Sum Games
AU - Yifei Chen
AU - Chinmay Maheshwari
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05516
UR - https://arxiv.org/abs/2610.05516
AB - 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.
ER -