Connectivity and equilibrium in random games
From MaRDI portal
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 the distribution of the number of equilibria approaches the Poisson distribution with parameter 1, asymptotically as .
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
Cites work
- scientific article; zbMATH DE number 1754580 (Why is no real title available?)
- scientific article; zbMATH DE number 2119691 (Why is no real title available?)
- scientific article; zbMATH DE number 2243403 (Why is no real title available?)
- A note on the probability of \(k\) pure Nash equilibria in matrix games
- Bounding the inefficiency of equilibria in nonatomic congestion games
- Evolutionarily stable strategies of random games, and the vertices of random polygons
- How bad is selfish routing?
- Hypertree decompositions and tractable queries
- Limiting distributions of the number of pure strategy Nash equilibria in \(n\)-person games
- On the Desirability of Acyclic Database Schemes
- On the number of pure strategy Nash equilibria in random games
- On the probability of existence of pure equilibria in matrix games
- Probability of a pure equilibrium point in n-person games
- Selfish Routing in Capacitated Networks
- Selfish traffic allocation for server farms
- Sharp thresholds of graph properties, and the $k$-sat problem
- Stackelberg Scheduling Strategies
- The Price of Stability for Network Design with Fair Cost Allocation
- The price of anarchy is independent of the network topology
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The probability of an equilibrium point
- The threshold for random k-SAT is 2 k (ln 2 - O(k))
- Two moments suffice for Poisson approximations: The Chen-Stein method
- Worst-case equilibria
Cited in
(7)- Potts game on graphs: static equilibria
- Rock-scissors-paper game on regular small-world networks
- The probability of nontrivial common knowledge
- Hitting a path: a generalization of weighted connectivity via game theory
- The three kinds of degree distributions and Nash equilibrium on the limiting random network
- Pure Nash equilibria and best-response dynamics in random games
- Best-response dynamics, playing sequences, and convergence to equilibrium in random games
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)
