Asynchronous algorithms in non-cooperative games
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.
- Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria
- Distributed algorithms for the computation of noncooperative equilibria
- scientific article; zbMATH DE number 18885
- Computation of equilibria in noncooperative games
- On relaxation algorithms in computation of noncooperative equilibria
- Asymptotic agreement and convergence of asynchronous stochastic algorithms
- Asynchronous Iterative Methods for Multiprocessors
- Chaotic relaxation
- Distributed algorithms for the computation of noncooperative equilibria
- Distributed asynchronous computation of fixed points
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- Dynamic noncooperative game theory
- scientific article; zbMATH DE number 3941302 (Why is no real title available?)
- Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria
- Asynchronous game of life
- Asynchronous games. II: The true concurrency of innocence
- On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games
- Asynchronous schemes for stochastic and misspecified potential games and nonconvex optimization
- Asynchronous algorithms for computing equilibrium prices in a capital asset pricing model
- Asynchronous Games over Tree Architectures
This page was built for publication: Asynchronous algorithms in non-cooperative games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102879)
