Evolutionarily Stable Strategies of Random Games and the Facets of Random Polytopes

Ohad Navon

An evolutionarily stable strategy (ESS) is an equilibrium strategy that is immune to invasions by rare alternative (mutant) strategies. Unlike Nash equilibria, ESS do not always exist in finite games. In this paper we address the question of what happens when the size of the game increases: does an ESS exist for almost every” large game? We let the entries of an n × n game matrix be independently randomly chosen according to a symmetrical subexponential distribution F, and study the expected number of ESS with support of size d as n → ∞. In a previous paper by Hart, Rinott and Weiss [6] it was shown that this limit is 1 2 for d = 2. This paper deals with the case of d ≥ 4, and proves the conjecture in [6] (Section 6,c), that the expected number of ESS with support of size d ≥ 4 is 0. Furthermore, it discusses the classic problem of the number of facets of a convex hull of n random points in Rd, and relates it to the above ESS problem. Given a collection of i.i.d. random points, our result implies that the expected number of facets of their convex hull converges to 2d as n → ∞.

September, 2016