Connectivity and equilibrium in random games

DOI10.1214/10-AAP715zbMATH Open1229.91079arXivmath/0703902OpenAlexW3103177970MaRDI QIDQ549865FDOQ549865

Alexandros G. Dimakis, Constantinos Daskalakis, Elchanan Mossel

Publication date: 19 July 2011

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: 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+Omega(1))lo{g}_2(n)$ the distribution of the number of equilibria approaches the Poisson distribution with parameter 1, asymptotically as $no+infty$.

Full work available at URL: https://arxiv.org/abs/math/0703902

zbMATH Keywords

random graphsgraphical gamesrandom gamespure Nash equilibria

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57) Phase transitions (general) in equilibrium statistical mechanics (82B26) Games involving graphs (91A43)

Cites Work

• Bounding the inefficiency of equilibria in nonatomic congestion games
• Title not available (Why is that?)
• Selfish Routing in Capacitated Networks
• Two moments suffice for Poisson approximations: The Chen-Stein method
• How bad is selfish routing?
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Price of Stability for Network Design with Fair Cost Allocation
• Title not available (Why is that?)
• Hypertree decompositions and tractable queries
• On the Desirability of Acyclic Database Schemes
• Stackelberg Scheduling Strategies
• Sharp thresholds of graph properties, and the $k$-sat problem
• On the number of pure strategy Nash equilibria in random games
• A note on the probability of \(k\) pure Nash equilibria in matrix games
• Limiting distributions of the number of pure strategy Nash equilibria in \(n\)-person games
• Evolutionarily stable strategies of random games, and the vertices of random polygons
• Probability of a pure equilibrium point in n-person games
• Selfish traffic allocation for server farms
• Title not available (Why is that?)
• The price of anarchy is independent of the network topology
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Title not available (Why is that?)
• The probability of an equilibrium point
• On the probability of existence of pure equilibria in matrix games

Cited In (5)

• Pure Nash Equilibria and Best-Response Dynamics in Random Games
• Rock-scissors-paper game on regular small-world networks
• The probability of nontrivial common knowledge
• Best-response dynamics, playing sequences, and convergence to equilibrium in random games
• Hitting a path: a generalization of weighted connectivity via game theory

   Recommendations

• Pure Nash Equilibria and Best-Response Dynamics in Random Games 👍 👎
• A note on the probability of \(k\) pure Nash equilibria in matrix games 👍 👎
• On the number of pure strategy Nash equilibria in random games 👍 👎
• On the prabability of existence of pure equilibria in matrix games 👍 👎
• The number of pure Nash equilibria in a random game with nondecreasing best responses 👍 👎

This page was built for publication: Connectivity and equilibrium in random games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q549865)