Using Simulated Annealing to Calculate the Trembles of Trembling Hand Perfection

Stuart, McDonald and Liam, Wagner (2003): Using Simulated Annealing to Calculate the Trembles of Trembling Hand Perfection.

Abstract

Within the literature on non-cooperative game theory, there have been a number of algorithms which will compute Nash equilibria. This paper shows that the family of algorithms known as Markov chain Monte Carlo (MCMC) can be used to calculate Nash equilibria. MCMC is a type of Monte Carlo simulation that relies on Markov chains to ensure its regularity conditions. MCMC has been widely used throughout the statistics and optimization literature, where variants of this algorithm are known as simulated annealing. This paper shows that there is interesting connection between the trembles that underlie the functioning of this algorithm and the type of Nash refinement known as trembling hand perfection. This paper shows that it is possible to use simulated annealing to compute this refinement.

• Item Type: MPRA Paper
• Language: English
• Keywords: Trembling Hand Perfection, Equilibrium Selection and Computation, Simulated Annealing, Markov Chain Monte Carlo
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C73 - Stochastic and Dynamic Games ; Evolutionary Games ; Repeated Games

References

[1] Besag, J. (1974) Spatial interaction and the statistical analysis of lattice systems (with discussion). Journal of the Royal Statistical Society Series B 36, 192–236.

[2] Friedman, J.W. (1991) Game Theory with Applications to Economics. Oxford University Press, Oxford.

[3] Georgobiani, D. A. and Torondzadze, A. F (1980) Solution of rectangular games by the Monte Carlo method. Trudy Vychisl. Tsentra Akad. Nauk Gruzin. SSR 20(2), 5-10.

[4] Gilks, W.R., Richardson, S. Spiegelhalter, D.J. (1996) Introducing Markov Chain Monte Carlo. In Gilks, W.R., Richardson, S. Spiegelhalter, D.J. (Eds..) Markov Chain Monte Carlo in Practice, 1–19. Chapman and Hall, London.

[5] Gilks, W.R. (1996) Full conditional distributions. In Gilks, W.R., Richardson, S. Spiegelhalter, D.J. (Eds.) Markov Chain Monte Carlo in Practice, 75–88. Chapman and Hall, London.

[6] Harsanyi, J.C., (1975) The tracing procedure: a Bayesian approach to defining a solution for n-person non-cooperative games. International Journal of Game Theory 4, 1-22.

[7] Harsanyi, J.C. and Selten, R. (1988) A General Theory of Equilibrium Selection in Games. MIT Press, Cambridge, MA.

[8] Hastings, W.K. (1970) Monte Carlo sampling methods using Markov chains and their application. Biometrika 57, 97–109.

[9] Kuhn, H.W. (1953) Extensive games and the problem of information. In Kuhn, H.W. and Tucker, A.W. Contributions to the Theory of Games Vol I, 193–216. Princeton University Press, Princeton N.J.

[10] Lempke, C.E. and Howson, J.T. (1964) Equilibrium points of bimatrix games. SIAM Journal on Applied Mathematics 12, 413–423.

[11] Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E., (1953) Equations of state calculations by fast computing machines. Journal of Chemistry Physics 21, 1087–1091.

[12] Myerson, R.B. (1978) Refinements of the concept of Nash equilibrium. International Journal of Game Theory 7, 73–80.

[13] Myerson, R.B. (1991) Game Theory: Analysis of Conflict. Harvard University Press, Cambridge, MA.

[14] Roberts, G.O. (1996) Markov chain concepts related to sampling algorithms. In Gilks, W.R., Richardson, S. Spiegelhalter, D.J. (Eds.) Markov Chain Monte Carlo in Practice, 45–57. Chapman and Hall, London.

[15] Scarf, H.E. (1973) Computation of Economic Equilibria. Yale University Press, New Haven, Conn.

[16] Selten, R. (1975) Reexamination of the Perfectness Concept for Equilibrium Concepts in Extensive Form Games. International Journal of Game Theory 4, 25–55.

[17] Selten, R. (1978) The Chain Store Paradox. Theory and Decision 9, 127–159.

[18] Ulam, S. (1954) Applications of Monte Carlo methods to tactical games. In Meyer, H.A. (Ed.) Symposium on Monte Carlo Methods, University of Florida 1954, p.63. John Wiley and Sons, New York.

[19] van Damme, E. (1991) Stability and Perfection of Nash Equilibria (2nd ed. rev. enl.). Springer-Verlag, Berlin.

[20] van Laarhoven, P.J.M. and Aarts, E.H.L. (1987) Simulated Annealing: Theory and Applications. D. Reidel Publishing, Dordrecht, Holland.

[21] Wilson, R. (1971) Computing Equilibria of N-Person Games. SIAM Journal on Applied Mathematics 21, 80–87.