Payoff-Based Dynamics for Multiplayer Weakly Acyclic Games
Authors:
- Jason R. MardenJMJason R. Marden
- H. Peyton YoungHYH. Peyton Young
- Gürdal ArslanGAGürdal Arslan
- Jeff S. ShammaJSJeff S. Shamma
Top Cited Papers
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 48 (1) , 373-396
Abstract
We consider repeated multiplayer games in which players repeatedly and simultaneously choose strategies from a finite set of available strategies according to some strategy adjustment process. We focus on the specific class of weakly acyclic games, which is particularly relevant for multiagent cooperative control problems. A strategy adjustment process determines how players select their strategies at any stage as a function of the information gathered over previous stages. Of particular interest are “payoff-based” processes in which, at any stage, players know only their own actions and (noise corrupted) payoffs from previous stages. In particular, players do not know the actions taken by other players and do not know the structural form of payoff functions. We introduce three different payoff-based processes for increasingly general scenarios and prove that, after a sufficiently large number of stages, player actions constitute a Nash equilibrium at any stage with arbitrarily high probability. We also show how to modify player utility functions through tolls and incentives in so-called congestion games, a special class of weakly acyclic games, to guarantee that a centralized objective can be realized as a Nash equilibrium. We illustrate the methods with a simulation of distributed routing over a network.Keywords
This publication has 18 references indexed in Scilit:
- Global Nash convergence of Foster and Young's regret testingGames and Economic Behavior, 2007
- Multi-agent learning for engineersArtificial Intelligence, 2007
- Autonomous Vehicle-Target Assignment: A Game-Theoretical FormulationJournal of Dynamic Systems, Measurement, and Control, 2007
- Cooperative Multi-Agent Learning: The State of the ArtAutonomous Agents and Multi-Agent Systems, 2005
- Adaptive HeuristicsEconometrica, 2005
- Dynamic Cesaro-Wardrop equilibration in networksIEEE Transactions on Automatic Control, 2003
- Evolutionary Implementation and Congestion PricingReview of Economic Studies, 2002
- Fictitious Play Property for Games with Identical InterestsJournal of Economic Theory, 1996
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973
- Über ein Paradoxon aus der VerkehrsplanungMathematical Methods of Operations Research, 1968