Approximate Nash Equilibria in Bimatrix Games
作者： Urszula Boryczka , Przemyslaw Juszczuk
DOI: 10.1007/978-3-642-23938-0_49
关键词: Symmetric equilibrium 、 Computer science 、 Equilibrium selection 、 Lemke–Howson algorithm 、 Trembling hand perfect equilibrium 、 Best response 、 Mathematical optimization 、 Epsilon-equilibrium 、 Nash equilibrium 、 Correlated equilibrium
摘要: Nash equilibrium is one of the main concepts in game theory. Recently it was shown, that problem finding and an approximate PPAD-complete. In this article we adapt Differential Evolution algorithm (DE) to above problem. It may be classified as continuous problem, where two probability distributions over set pure strategies both players should found. Every deviation from global optimum interpreted approximation called e-Nash equilibrium. We show, approach can determined iterative method, which successive iterations capable obtain e value close optimum. The contribution paper experimental analysis proposed indication it's strong features. try demonstrate, method very good alternative for existing mathematical mentioned
springer.com
springerlink.com参考文章(27)
Peter C. Ordeshook, Game theory and political theory : an introduction Cambridge University Press. ,(1986) , 10.1017/CBO9780511666742
Rainer Storn, Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces Journal of Global Optimization. ,vol. 11, pp. 341- 359 ,(1997) , 10.1023/A:1008202821328
Vincent Conitzer, Andrew Gilpin, Thomas Sandholm, Mixed-integer programming methods for finding Nash equilibria national conference on artificial intelligence. pp. 495- 501 ,(2005)
Peter Hammerstein, Reinhard Selten, Chapter 28 Game theory and evolutionary biology Handbook of Game Theory with Economic Applications. ,vol. 2, pp. 929- 993 ,(1994) , 10.1016/S1574-0005(05)80060-8
N.G. Pavlidis, K.E. Parsopoulos, M.N. Vrahatis, Computing Nash equilibria through computational intelligence methods Journal of Computational and Applied Mathematics. ,vol. 175, pp. 113- 136 ,(2005) , 10.1016/J.CAM.2004.06.005
Ryan Porter, Eugene Nudelman, Yoav Shoham, Simple search methods for finding a Nash equilibrium Games and Economic Behavior. ,vol. 63, pp. 642- 662 ,(2008) , 10.1016/J.GEB.2006.03.015
Xi Chen, Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium foundations of computer science. pp. 261- 272 ,(2006) , 10.1109/FOCS.2006.69
Andrew McLennan, The Expected Number of Nash Equilibria of a Normal Form Game Econometrica. ,vol. 73, pp. 141- 174 ,(2005) , 10.1111/J.1468-0262.2005.00567.X
Peter C. Ordeshook, Game Theory and Political Theory Cambridge Books. ,(1986)
Constantinos Daskalakis, Aranyak Mehta, Christos Papadimitriou, A note on approximate Nash equilibria Theoretical Computer Science. ,vol. 410, pp. 1581- 1588 ,(2009) , 10.1016/J.TCS.2008.12.031