Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria (Q1104256)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria |
scientific article |
Statements
Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria (English)
0 references
1987
0 references
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.
0 references
stable equilibrium solution
0 references
relaxation algorithm
0 references
asynchronous computation
0 references
conditions of convergence
0 references