Asynchronous algorithms in non-cooperative games
type: Item
instance of: scholarly article
title: Asynchronous algorithms in non-cooperative games
zbMATH Open document ID: 0644.90101
DOI: 10.1016/0165-1889(88)90030-9
author: Tamer Başar
publication date: 1988-01-01T00:00:00Z
review text: The equilibrium solution of a zero-sum or a nonzero-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 (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, the author addresses precisely this question, and introduces 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. He also obtains conditions for convergence of asynchronous algorithms which arise in the computation of equilibria in games where the order of responses is 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.
reviewed by: Tamer Başar
Mathematics Subject Classification ID: 91A10
Mathematics Subject Classification ID: 90C90
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 91A05
Mathematics Subject Classification ID: 91A60
Mathematics Subject Classification ID: 91A15
zbMATH DE Number: 4051387
zbMATH Keywords: distributed algorithms
zbMATH Keywords: equilibrium solution
zbMATH Keywords: unilateral optimal responses
zbMATH Keywords: stable equilibrium
zbMATH Keywords: on-line adjustment process
zbMATH Keywords: computational algorithm
zbMATH Keywords: relaxation technique
MaRDI profile type: Publication
full work available at URL: 0165-1889(88)90030-9
OpenAlex ID: W1971270951
cites work: Dynamic noncooperative game theory
cites work: Q3713891
cites work: Asynchronous Iterative Methods for Multiprocessors
cites work: Distributed asynchronous computation of fixed points
cites work: Chaotic relaxation
cites work: Asymptotic agreement and convergence of asynchronous stochastic algorithms
cites work: Distributed algorithms for the computation of noncooperative equilibria
cites work: Distributed asynchronous deterministic and stochastic gradient optimization algorithms
published in: Journal of Economic Dynamics and Control
description: scientific article; zbMATH DE number 4051387