Achieving Pareto Optimality Through Distributed Learning
AbstractWe propose a simple payoff-based learning rule that is completely decentralized, and that leads to an efficient configuaration of actions in any n-person finite strategic-form game with generic payoffs.� The algorithm follows the theme of exploration versus exploitation and is hence stochastic in nature.� We prove that if all agents adhere to this algorithm, then the agents will select the action profile that maximizes the sum of the agents' payoffs a high percentage of time.� The algorithm requires no communication.� Agents respond solely to changes in their own realized payoffs, which are affected by the actions of other agents in the system in ways that they do not necessarily understand.� The method can be applied to the optimization of complex systems with many distributed components, such as the routing of information in networks and the design and control of wind farms.� The proof of the proposed learning algorithm relies on the theory of large deviations for perturbed Markov chains.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by University of Oxford, Department of Economics in its series Economics Series Working Papers with number 557.
Date of creation: 01 Jul 2011
Date of revision:
Learning; Optimisation; Distributed control;
Find related papers by JEL classification:
- C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
- C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Fudenberg, Drew & Maskin, Eric, 1986. "The Folk Theorem in Repeated Games with Discounting or with Incomplete Information," Econometrica, Econometric Society, vol. 54(3), pages 533-54, May.
- Sergiu Hart & Andreu Mas-Colell, 2004.
"Stochastic Uncoupled Dynamics and Nash Equilibrium,"
Discussion Paper Series
dp371, The Center for the Study of Rationality, Hebrew University, Jerusalem.
- Hart, Sergiu & Mas-Colell, Andreu, 2006. "Stochastic uncoupled dynamics and Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 57(2), pages 286-303, November.
- Sergiu Hart & Andreu Mas-Colell, 2004. "Stochastic Uncoupled Dynamics and Nash Equilibrium," Working Papers 174, Barcelona Graduate School of Economics.
- Sergiu Hart & Andreu Mas-Colell, 2004. "Stochastic Uncoupled Dynamics and Nash Equilibrium," Levine's Bibliography 122247000000000466, UCLA Department of Economics.
- Sergiu Hart & Andreu Mas-Colell, 2004. "Stochastic uncoupled dynamics and Nash equilibrium," Economics Working Papers 783, Department of Economics and Business, Universitat Pompeu Fabra.
- Young, H Peyton, 1993. "The Evolution of Conventions," Econometrica, Econometric Society, vol. 61(1), pages 57-84, January.
- Young, H. Peyton, 2009. "Learning by trial and error," Games and Economic Behavior, Elsevier, vol. 65(2), pages 626-643, March.
- Foster, Dean P. & Young, H. Peyton, 2006. "Regret testing: learning to play Nash equilibrium without knowing you have an opponent," Theoretical Economics, Econometric Society, vol. 1(3), pages 341-367, September.
- Pradelski, Bary S.R. & Young, H. Peyton, 2012. "Learning efficient Nash equilibria in distributed systems," Games and Economic Behavior, Elsevier, vol. 75(2), pages 882-897.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Caroline Wise).
If references are entirely missing, you can add them using this form.