Learning in near-potential games
Except for special classes of games, there is no systematic framework for analyzing the dynamical properties of multi-agent strategic interactions. Potential games are one such special but restrictive class of games that allow for tractable dynamic analysis. Intuitively, games that are “close” to a...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72678 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1811082820621172736 |
|---|---|
| author | Candogan, Utku Ozan Ozdaglar, Asuman E. Parrilo, Pablo A. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Candogan, Utku Ozan Ozdaglar, Asuman E. Parrilo, Pablo A. |
| author_sort | Candogan, Utku Ozan |
| collection | MIT |
| description | Except for special classes of games, there is no systematic framework for analyzing the dynamical properties of multi-agent strategic interactions. Potential games are one such special but restrictive class of games that allow for tractable dynamic analysis. Intuitively, games that are “close” to a potential game should share similar properties. In this paper, we formalize and develop this idea by quantifying to what extent the dynamic features of potential games extend to “near-potential” games. We first show that in an arbitrary finite game, the limiting behavior of better-response and best-response dynamics can be characterized by the approximate equilibrium set of a close potential game. Moreover, the size of this set is proportional to a closeness measure between the original game and the potential game. We then focus on logit response dynamics, which induce a Markov process on the set of strategy profiles of the game, and show that the stationary distribution of logit response dynamics can be approximated using the potential function of a close potential game, and its stochastically stable strategy profiles can be identified as the approximate maximizers of this function. Our approach presents a systematic framework for studying convergence behavior of adaptive learning dynamics in finite strategic form games. |
| first_indexed | 2024-09-23T12:09:34Z |
| format | Article |
| id | mit-1721.1/72678 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:09:34Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/726782022-09-28T00:34:08Z Learning in near-potential games Candogan, Utku Ozan Ozdaglar, Asuman E. Parrilo, Pablo A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Ozdaglar, Asuman E. Candogan, Utku Ozan Ozdaglar, Asuman E. Parrilo, Pablo A. Except for special classes of games, there is no systematic framework for analyzing the dynamical properties of multi-agent strategic interactions. Potential games are one such special but restrictive class of games that allow for tractable dynamic analysis. Intuitively, games that are “close” to a potential game should share similar properties. In this paper, we formalize and develop this idea by quantifying to what extent the dynamic features of potential games extend to “near-potential” games. We first show that in an arbitrary finite game, the limiting behavior of better-response and best-response dynamics can be characterized by the approximate equilibrium set of a close potential game. Moreover, the size of this set is proportional to a closeness measure between the original game and the potential game. We then focus on logit response dynamics, which induce a Markov process on the set of strategy profiles of the game, and show that the stationary distribution of logit response dynamics can be approximated using the potential function of a close potential game, and its stochastically stable strategy profiles can be identified as the approximate maximizers of this function. Our approach presents a systematic framework for studying convergence behavior of adaptive learning dynamics in finite strategic form games. National Science Foundation (U.S.). (Grant number CMMI-0545910) United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (R6756-G2) 2012-09-13T13:20:09Z 2012-09-13T13:20:09Z 2011-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-61284-799-3 978-1-61284-800-6 0743-1546 http://hdl.handle.net/1721.1/72678 Candogan, Ozan, Asuman Ozdaglar, and Pablo A. Parrilo. “Learning in Near-potential Games.” 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), 2011. 2428–2433. https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1109/CDC.2011.6160867 Proceedings on the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), 2011 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Candogan, Utku Ozan Ozdaglar, Asuman E. Parrilo, Pablo A. Learning in near-potential games |
| title | Learning in near-potential games |
| title_full | Learning in near-potential games |
| title_fullStr | Learning in near-potential games |
| title_full_unstemmed | Learning in near-potential games |
| title_short | Learning in near-potential games |
| title_sort | learning in near potential games |
| url | http://hdl.handle.net/1721.1/72678 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT candoganutkuozan learninginnearpotentialgames AT ozdaglarasumane learninginnearpotentialgames AT parrilopabloa learninginnearpotentialgames |