Connectivity and equilibrium in random games (Q549865)

The article analyzes the effect of connectivity in a random graph, captured by the edge probability, on existence or non-existence of pure Nash equilibria for games on the graph with random payoffs. This takes the form of a Poisson approximation for the number of such equilibria for the high connectivity case, and upper, resp. lower bounds for the existence of such equilibria for medium and low connectivity cases. Complementary results on probability bounds for non-existence of pure Nash equilibria are also given.