Decentralized learning of Nash equilibria in multi-person stochastic games with incomplete information
- 1 May 1994
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics
- Vol. 24 (5) , 769-777
- https://doi.org/10.1109/21.293490
Abstract
A multi-person discrete game where the payoff after each play is stochastic is considered. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A learning algorithm for the game based on a decentralized team of Learning Automata is presented. It is proved that all stable stationary points of the algorithm are Nash equilibria for the game. Two special cases of the game are also discussed, namely, game with common payoff and the relaxation labelling problem. The former has applications such as pattern recognition and the latter is a problem widely studied in computer vision. For the two special cases it is shown that the algorithm always converges to a desirable solution.This publication has 16 references indexed in Scilit:
- Stochastic networks for constraint satisfaction and optimizationSādhanā, 1990
- Associative learning of Boolean functionsIEEE Transactions on Systems, Man, and Cybernetics, 1989
- An SIMD machine for low-level visionInformation Sciences, 1988
- Relaxation techniques and asynchronous algorithms for on-line computation of noncooperative equilibriaPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Distributed algorithms for the computation of noncooperative equilibriaAutomatica, 1987
- Learning Optimal Discriminant Functions through a Cooperative Game of AutomataIEEE Transactions on Systems, Man, and Cybernetics, 1987
- Decentralized learning in finite Markov chainsIEEE Transactions on Automatic Control, 1986
- Relaxation Labeling with Learning AutomataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- A Learning Model for Routing in Telephone NetworksSIAM Journal on Control and Optimization, 1982
- Cooperating processes for low-level vision: A surveyArtificial Intelligence, 1981