Affine Relaxations of the Best Response Algorithm: Global Convergence in Ratio-Bounded Games
研究两人非合作博弈中最佳响应算法的仿射松弛，定义了一类新的比率有界博弈，涵盖加权势博弈和零和博弈，分析了纳什均衡的存在唯一性、算法全局收敛性及收敛速度。
In a two-player noncooperative game framework, we deal with the affine relaxations of the best response algorithm (where a player’s strategy is a best response to the strategy of the other player that comes from the previous step), motivated by the first results obtained for convex relaxations in zero-sum games (J. Morgan, Int. J. Comput. Math., 4 (1974), pp. 143–175) and for nonconvex affine relaxations in non-zero-sum games (F. Caruso, M. C. Ceparano, and J. Morgan, SIAM J. Optim., 30 (2020), pp. 1638–1663). In order to be able to specify the convergence of any type of affine relaxation of the best response algorithm, we define a new class of games, called ratio-bounded games. This class contains games broadly used in literature (such as weighted potential and zero-sum games), both in finite and infinite dimensional settings. Its definition relies on a unifying property and on three associate key parameters explicitly related to the data. Depending on how the parameters are ordered, we provide a classification of the ratio-bounded games in four subclasses such that, for each of them, the following issues are answered when the strategy sets are real Hilbert spaces: existence and uniqueness of the Nash equilibria, global convergence of the affine relaxations of the best response algorithm, estimation of the related errors, determination of the algorithm with the highest speed of convergence, and comparison with the known results. Moreover, the investigation is supplemented by illustrating numerical examples and by describing a black-box model with a first-order oracle for an implementation of the algorithm.