Evolutionarily Stable Strategies of Random Games, and the Vertices of Random
Polygons
Sergiu Hart, Yosef Rinott, and Benjamin Weiss
Abstract
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? Letting the
entries in the n x n
game matrix be randomly chosen according to an
underlying distribution F, we study the number of ESS with support of size
2. In particular, we show that, as
n goes to infinity,
the probability
of having such an ESS: (i) converges to 1 for distributions F with
"exponential and faster decreasing tails" (e.g., uniform, normal,
exponential); and (ii) it converges to 1 - 1/sqrt(e) for distributions
F
with "slower than exponential decreasing tails" (e.g., lognormal, Pareto,
Cauchy).
Our results
also imply that the expected
number of vertices of the convex hull of n random
points in the plane converges
to infinity for the
distributions in (i), and to 4 for the distributions in (ii).
- Annals of Applied Probability, 18 (2008), 1, 259-287
Last modified:
© Sergiu Hart