.png){kind=icon}
.png){kind=icon}
Return
Finite-Time Convergence to an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-Efficient Nash Equilibrium in Potential Games
.png){kind=icon}
PRE
AI
A
R
H
M
DOI：10.1109/tcns.2026.3673502.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This article investigates the convergence time of log-linear learning to an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-efficient Nash equilibrium in potential games, where an efficient Nash equilibrium is defined as the maximizer of the potential function. Previous literature provides asymptotic convergence rates to efficient Nash equilibria, and existing finite-time rates are limited to potential games with further assumptions such as the interchangeability of players. We prove the first finite-time convergence to an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-efficient Nash equilibrium in general potential games. Our bounds depend polynomially on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1/\epsilon$</tex-math></inline-formula>, which is an improvement over previous bounds for subclasses of potential games that are exponential in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1/\epsilon$</tex-math></inline-formula>. We then strengthen our convergence result in two directions: first, we show that a variant of log-linear learning requiring a constant factor less feedback on the utility per round enjoys a similar convergence time; second, we demonstrate the robustness of our convergence guarantee if log-linear learning is subject to small perturbations such as alterations in the learning rule or noise-corrupted utilities.
Keywords:
Game theory
log-linear learning
potential games
Journal
IF:
5
Papers:
1.6K
Citations:
5.8K
Organization
E
Cited Papers