Achieving Pareto Optimality Through Distributed Learning

H. Young and Jason R. Marden and Lucy Y. Pao

No 557, Economics Series Working Papers from University of Oxford, Department of Economics

Abstract: We 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.

Keywords: Learning; Optimisation; Distributed control (search for similar items in EconPapers)
JEL-codes: C72 C73 (search for similar items in EconPapers)
Date: 2011-07-01
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://ora.ox.ac.uk/objects/uuid:1236dae5-e861-416c-8f6c-61609d70350b (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:oxf:wpaper:557

Access Statistics for this paper

More papers in Economics Series Working Papers from University of Oxford, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Anne Pouliquen ( this e-mail address is bad, please contact ).