摘要 Abstract
我们评估了格点凸二次博弈的最佳响应(BR)算法,其中玩家具有非线性目标且可行集无界。我们给出了一个充分条件:如果某些交互矩阵(定义凸二次项的正定矩阵的逆与连接一个玩家问题到另一个玩家问题的矩阵的乘积)的所有奇异值均小于1,则无论初始点为何值,迭代都不会发散。我们证明了如果迭代被限制在有限多个策略(称为陷阱)之间,则通过识别玩家策略受限于该陷阱内有限博弈的混合策略纳什均衡,可以计算出松弛版本的纳什均衡。为了验证该充分条件的严密性,我们还展示了这样的例子:即使某个交互矩阵的一个奇异值超过1,仍存在无穷多个初始点使得迭代发散。最后,我们证明了如果所有交互矩阵的所有奇异值都大于1,则迭代会从除了可能有限个初始化点之外的所有初始点发散。
We evaluate the best-response (BR) algorithm for lattice convex-quadratic games, where the players have nonlinear objectives and unbounded feasible sets. We provide a sufficient condition that if certain interaction matrices (the product of the inverse of the positive definite matrix defining the convex-quadratic terms and the matrix that connects one player's problem to another's) have all their singular values less than 1, then the iterates do not diverge regardless of the initial point. We prove that if the iterates are trapped among finitely many strategies (called a trap), a relaxed version of the Nash equilibrium can be calculated by identifying a mixed-strategy Nash equilibrium of the finite game where the players' strategies are restricted to those in the trap. To establish the tightness of our sufficient condition, we also show examples where even if one singular value of one interaction matrix exceeds 1, there are infinitely many initial points from which the iterates diverge. Finally, we prove that if all the singular values of all the interaction matrices exceed 1, then the iterates diverge from every initial point except possibly a finite set of initializations.