Tight rates of approximation of mixed Nash equilibria by entropy regularization in continuous games

Khang Nguyen, Valentio Iverson, Sahan Wijetunga, William Chang, Guillaume Wang
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:4855-4872, 2026.

Abstract

We study how well the quantal response equilibrium ({QRE}) approximates the mixed {Nash} equilibrium ({MNE}) in two-player zero-sum games, as a function of the inverse temperature $\beta$. We introduce a reduction framework that decomposes the worst-case Nikaido–Isoda error of the {QRE} into a sum of two independent single-player {Gibbs} concentration problems, enabling tight matching bounds across a range of payoff classes. For finite games with $M \times N$ payoff matrices, we establish a tight rate of $\Theta(\beta^{-1}(\log M + \log N))$. For games with $\alpha$-Hölder-continuous payoffs on the torus, we prove a lower bound of $\Omega((d_x+d_y)/(\alpha\beta))$ and an upper bound of $O((d_x+d_y)\log(L\beta)/(\alpha\beta))$; whether the logarithmic gap is tight is left as an open problem. For smooth payoffs with sparse non-degenerate {MNE}, we prove that every individual game achieves a rate of $(d_x + d_y)/(2\beta) + O(1/\beta^2)$ via {Laplace} concentration, and that this rate is tight.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-nguyen26b, title = {Tight rates of approximation of mixed {Nash} equilibria by entropy regularization in continuous games}, author = {Nguyen, Khang and Iverson, Valentio and Wijetunga, Sahan and Chang, William and Wang, Guillaume}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {4855--4872}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/nguyen26b/nguyen26b.pdf}, url = {https://proceedings.mlr.press/v337/nguyen26b.html}, abstract = {We study how well the quantal response equilibrium ({QRE}) approximates the mixed {Nash} equilibrium ({MNE}) in two-player zero-sum games, as a function of the inverse temperature $\beta$. We introduce a reduction framework that decomposes the worst-case Nikaido–Isoda error of the {QRE} into a sum of two independent single-player {Gibbs} concentration problems, enabling tight matching bounds across a range of payoff classes. For finite games with $M \times N$ payoff matrices, we establish a tight rate of $\Theta(\beta^{-1}(\log M + \log N))$. For games with $\alpha$-Hölder-continuous payoffs on the torus, we prove a lower bound of $\Omega((d_x+d_y)/(\alpha\beta))$ and an upper bound of $O((d_x+d_y)\log(L\beta)/(\alpha\beta))$; whether the logarithmic gap is tight is left as an open problem. For smooth payoffs with sparse non-degenerate {MNE}, we prove that every individual game achieves a rate of $(d_x + d_y)/(2\beta) + O(1/\beta^2)$ via {Laplace} concentration, and that this rate is tight.} }
Endnote
%0 Conference Paper %T Tight rates of approximation of mixed Nash equilibria by entropy regularization in continuous games %A Khang Nguyen %A Valentio Iverson %A Sahan Wijetunga %A William Chang %A Guillaume Wang %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-nguyen26b %I PMLR %P 4855--4872 %U https://proceedings.mlr.press/v337/nguyen26b.html %V 337 %X We study how well the quantal response equilibrium ({QRE}) approximates the mixed {Nash} equilibrium ({MNE}) in two-player zero-sum games, as a function of the inverse temperature $\beta$. We introduce a reduction framework that decomposes the worst-case Nikaido–Isoda error of the {QRE} into a sum of two independent single-player {Gibbs} concentration problems, enabling tight matching bounds across a range of payoff classes. For finite games with $M \times N$ payoff matrices, we establish a tight rate of $\Theta(\beta^{-1}(\log M + \log N))$. For games with $\alpha$-Hölder-continuous payoffs on the torus, we prove a lower bound of $\Omega((d_x+d_y)/(\alpha\beta))$ and an upper bound of $O((d_x+d_y)\log(L\beta)/(\alpha\beta))$; whether the logarithmic gap is tight is left as an open problem. For smooth payoffs with sparse non-degenerate {MNE}, we prove that every individual game achieves a rate of $(d_x + d_y)/(2\beta) + O(1/\beta^2)$ via {Laplace} concentration, and that this rate is tight.
APA
Nguyen, K., Iverson, V., Wijetunga, S., Chang, W. & Wang, G.. (2026). Tight rates of approximation of mixed Nash equilibria by entropy regularization in continuous games. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:4855-4872 Available from https://proceedings.mlr.press/v337/nguyen26b.html.

Related Material