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

The equilibrium solution of a zero-sum or a non-zero-sum game is said to be stable if, after any deviation from that equilibrium, an adjustment process that involves unilateral optimal responses by the players can bring it back to the starting point. One appealing feature of a stable equilibrium is that in the on-line adjustment process the players need to know only their own cost functions and the most recently computed (and broadcast) policies of the other players, and not the other players' cost functions. It is needless to say that not all equilibrium (saddle-point or Nash) solutions are stable, and hence the question arises whether there exists a different on-line (real-time implementable) computational algorithm which would converge to an equilibrium even if that equilibrium is not stable. In this paper, we address precisely this question, and introduce a relaxation technique which leads to on-line implementable algorithms that converge to equilibria, be they stable or unstable, and in some cases in a finite number of steps. We also obtain conditions for convergence of asynchronous algorithms which arise in the computation of equilibria in games where the order of responses in not fixed a priori. The discussion and the analyses are primarily confined to two-person deterministic games, with extensions to N-player games and stochastic games briefly mentioned and left as topics for future research.