Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria (Q1104256)

Consider a two-person, nonzero-sum game in normal form, which is completely characterized by the strategy spaces U, V, for players 1 and 2, respectively, and the objective functions J 1 and J 2. A relaxation algorithm of Gauss-Seidel type (resp. Jacobi type) is of the form \[ u_{k+1}=\alpha u_ k+(1-\alpha)\arg \min J\quad 1(u,v_ k) \] \[ v_{k+1}=\beta v_ k+(1-\beta)\arg \min J^ 2(u_{k+1},v)\quad (resp.\quad replacing\quad u_{k+1}\quad by\quad u_ k), \] \(k=0,1,...\), \(u_ 0\in U\), \(v_ 0\in V\), and an asynchronous computation means that the players act at random points in time, regardless of the order of moves by the players. This paper discusses the conditions of convergence for various relaxation algorithms (synchronized or asynchronized), which may be on-line implementable. The extensions to N-player games and stochastic games are briefly mentioned and left as topics for future research.