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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)531-549
Number of pages19
JournalJournal of Economic Dynamics and Control
Issue number4
StatePublished - Dec 1987

ASJC Scopus subject areas

  • Economics and Econometrics
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria'. Together they form a unique fingerprint.

Cite this