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

摘要

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 β. 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 × N payoff matrices, we establish a tight rate of Θ(β^-1(log M + log N)). For games with α-Hölder-continuous payoffs on the torus, we prove a lower bound of Ω((d_x+d_y)/(αβ)) and an upper bound of O((d_x+d_y)log(Lβ)/(αβ)); 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β) + O(1/β^2) via Laplace concentration, and that this rate is tight.