A Stochastic Search Algorithm for the Computation of Perfect and Proper Equilibria

This paper shows that stochastic search algorithms can be used to compute the perfect and proper equilibria of finite games. These type of equilibria use perturbations as a means of escape from local equilibria. Intuitively, there is always a small probability that an agent will select alternative strategy, even if that strategy is sub-optimal. This allows agents to escape from local equilibria in much the same way that stochastic search algorithms (like genetic algorithms and simulated annealing, for example) escape from local equilibria. This paper constructs a possibility result showing that if this equilibrium exists, then it can be found by using a stochastic search algorithm. This paper also shows by example, using the three player extensive game "Selten's Horse", that stochastic search can be used to locate a perfect equilibrium in an extensive form game.