Connectivity and Equilibrium in Random Games
We study how the structure of the interaction graph of a game affects the existence of pure Nash equilibria. In particular, for a fixed interaction graph, we are interested in whether there are pure Nash equilibria arising when random utility tables are assigned to the players. We provide conditions...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Mathematical Statistics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72585 https://orcid.org/0000-0002-5451-0490 |
| _version_ | 1811083092214939648 |
|---|---|
| author | Daskalakis, Constantinos Dimakis, Alexandros G. Mossel, Elchanan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Daskalakis, Constantinos Dimakis, Alexandros G. Mossel, Elchanan |
| author_sort | Daskalakis, Constantinos |
| collection | MIT |
| description | We study how the structure of the interaction graph of a game affects the existence of pure Nash equilibria. In particular, for a fixed interaction graph, we are interested in whether there are pure Nash equilibria arising when random utility tables are assigned to the players. We provide conditions for the structure of the graph under which equilibria are likely to exist and complementary conditions which make the existence of equilibria highly unlikely. Our results have immediate implications for many deterministic graphs and generalize known results for random games on the complete graph. In particular, our results imply that the probability that bounded degree graphs have pure Nash equilibria is exponentially small in the size of the graph and yield a simple algorithm that finds small nonexistence certificates for a large family of graphs. Then we show that in any strongly connected graph of n vertices with expansion (1+Ω(1))log[subscript 2](n) the distribution of the number of equilibria approaches the Poisson distribution with parameter 1, asymptotically as n→+∞.
In order to obtain a refined characterization of the degree of connectivity associated with the existence of equilibria, we also study the model in the random graph setting. In particular, we look at the case where the interaction graph is drawn from the Erdős–Rényi, G(n, p), model where each edge is present independently with probability p. For this model we establish a double phase transition for the existence of pure Nash equilibria as a function of the average degree pn, consistent with the nonmonotone behavior of the model. We show that when the average degree satisfies np>(2+Ω(1))loge(n), the number of pure Nash equilibria follows a Poisson distribution with parameter 1, asymptotically as n→∞. When 1/n≪np<(0.5−Ω(1))log[subscript e](n), pure Nash equilibria fail to exist with high probability. Finally, when np=O(1/n) a pure Nash equilibrium exists with constant probability. |
| first_indexed | 2024-09-23T12:21:26Z |
| format | Article |
| id | mit-1721.1/72585 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:21:26Z |
| publishDate | 2012 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/725852022-09-28T01:05:18Z Connectivity and Equilibrium in Random Games Daskalakis, Constantinos Dimakis, Alexandros G. Mossel, Elchanan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Daskalakis, Constantinos Daskalakis, Constantinos We study how the structure of the interaction graph of a game affects the existence of pure Nash equilibria. In particular, for a fixed interaction graph, we are interested in whether there are pure Nash equilibria arising when random utility tables are assigned to the players. We provide conditions for the structure of the graph under which equilibria are likely to exist and complementary conditions which make the existence of equilibria highly unlikely. Our results have immediate implications for many deterministic graphs and generalize known results for random games on the complete graph. In particular, our results imply that the probability that bounded degree graphs have pure Nash equilibria is exponentially small in the size of the graph and yield a simple algorithm that finds small nonexistence certificates for a large family of graphs. Then we show that in any strongly connected graph of n vertices with expansion (1+Ω(1))log[subscript 2](n) the distribution of the number of equilibria approaches the Poisson distribution with parameter 1, asymptotically as n→+∞. In order to obtain a refined characterization of the degree of connectivity associated with the existence of equilibria, we also study the model in the random graph setting. In particular, we look at the case where the interaction graph is drawn from the Erdős–Rényi, G(n, p), model where each edge is present independently with probability p. For this model we establish a double phase transition for the existence of pure Nash equilibria as a function of the average degree pn, consistent with the nonmonotone behavior of the model. We show that when the average degree satisfies np>(2+Ω(1))loge(n), the number of pure Nash equilibria follows a Poisson distribution with parameter 1, asymptotically as n→∞. When 1/n≪np<(0.5−Ω(1))log[subscript e](n), pure Nash equilibria fail to exist with high probability. Finally, when np=O(1/n) a pure Nash equilibrium exists with constant probability. Alfred P. Sloan Foundation. Fellowship Microsoft Corporation. Research Fellowship National Science Foundation (U.S.). (Grant number CCF-0635319) National Science Foundation (U.S.). (Grant number DMS-05-28488) National Science Foundation (U.S.). (Grant number DMS-05-48249) (Career) National Science Foundation (U.S.). (Grant number CCF-0953960) (Career) 2012-09-10T13:31:37Z 2012-09-10T13:31:37Z 2011 Article http://purl.org/eprint/type/JournalArticle 1050-5164 http://hdl.handle.net/1721.1/72585 Daskalakis, Constantinos, Alexandros G. Dimakis, and Elchanan Mossel. “Connectivity and Equilibrium in Random Games.” The Annals of Applied Probability 21.3 (2011): 987–1016. https://orcid.org/0000-0002-5451-0490 en_US http://dx.doi.org/10.1214/10-aap715 Annals of Applied Probability Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Mathematical Statistics arXiv |
| spellingShingle | Daskalakis, Constantinos Dimakis, Alexandros G. Mossel, Elchanan Connectivity and Equilibrium in Random Games |
| title | Connectivity and Equilibrium in Random Games |
| title_full | Connectivity and Equilibrium in Random Games |
| title_fullStr | Connectivity and Equilibrium in Random Games |
| title_full_unstemmed | Connectivity and Equilibrium in Random Games |
| title_short | Connectivity and Equilibrium in Random Games |
| title_sort | connectivity and equilibrium in random games |
| url | http://hdl.handle.net/1721.1/72585 https://orcid.org/0000-0002-5451-0490 |
| work_keys_str_mv | AT daskalakisconstantinos connectivityandequilibriuminrandomgames AT dimakisalexandrosg connectivityandequilibriuminrandomgames AT mosselelchanan connectivityandequilibriuminrandomgames |