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
    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
    0 references
    stable equilibrium solution
    0 references
    relaxation algorithm
    0 references
    asynchronous computation
    0 references
    conditions of convergence
    0 references
    0 references