Abstract
While there have been a number of studies about the efficacy of methods to find exact Nash equilibria in bimatrix games, there has been little empirical work on finding approximate Nash equilibria. Here we provide such a study that compares a number of approximation methods and exact methods. In particular, we explore the trade-off between the quality of approximate equilibrium and the required running time to find one. We found that the existing library GAMUT, which has been the de facto standard that has been used to test exact methods, is insufficient as a test bed for approximation methods since many of its games have pure equilibria or other easy-to-find good approximate equilibria. We extend the breadth and depth of our study by including new interesting families of bimatrix games, and studying bimatrix games upto size \(2000 \times 2000\). Finally, we provide new close-to-worst-case examples for the best-performing algorithms for finding approximate Nash equilibria.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anbalagan, Y., Norin, S., Savani, R., Vetta, A.: Polylogarithmic Supports Are Required for Approximate Well-Supported Nash Equilibria below 2/3. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 15–23. Springer, Heidelberg (2013)
Bosse, H., Byrka, J., Markakis, E.: New algorithms for approximate Nash equilibria in bimatrix games. Theoretical Computer Science 411(1), 164–173 (2010)
Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56(3), 14:1–14:57 (2009)
Codenotti, B., Rossi, S.D., Pagan, M.: An experimental analysis of Lemke-Howson algorithm (2008). CoRR, abs/0811.3247
Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM Journal on Computing 39(1), 195–259 (2009)
Daskalakis, C., Mehta, A., Papadimitriou, C.H.: A note on approximate Nash equilibria. Theoretical Computer Science 410(17), 1581–1588 (2009)
Fearnley, J., Goldberg, P. W., Savani, R., Sørensen, T. B.: Approximate well-supported nash equilibria below two-thirds (2012). CoRR, abs/1204.0707
Gatti, N., Patrini, G., Rocco, M., Sandholm, T.: Combining local search techniques and path following for bimatrix games (2012). CoRR, abs/1210.4858
Goldberg, L.A., Goldberg, P.W., Krysta, P., Ventre, C.: Ranking games that have competitiveness-based strategies. Theor. Comput. Sci. 476, 24–37 (2013)
Goldberg, P.W., Papadimitriou, C.H., Savani, R.: The complexity of the homotopy method, equilibrium selection, and lemke-howson solutions. ACM Trans. Economics and Comput. 1(2), 9 (2013)
Kontogiannis, S.C., Spirakis, P.G.: Well supported approximate equilibria in bimatrix games. Algorithmica 57(4), 653–667 (2010)
Kontogiannis, S., Spirakis, P.: Approximability of symmetric bimatrix games and related experiments. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 1–20. Springer, Heidelberg (2011)
Lemke, C.E., Howson Jr, J.: Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics 12(2), 413–423 (1964)
Nudelman, E., Wortman, J., Shoham, Y., Leyton-Brown, K.: Run the gamut: a comprehensive approach to evaluating game-theoretic algorithms. In: AAMAS, pp. 880–887 (2004)
Porter, R., Nudelman, E., Shoham, Y.: Simple search methods for finding a nash equilibrium. Games and Economic Behavior, 642–662 (2008)
Sandholm, T., Gilpin, A., Conitzer, V.: Mixed-integer programming methods for finding nash equilibria. In: AAAI, pp. 495–501 (2005)
Savani, R., von Stengel, B.: Hard-to-solve bimatrix games. Econometrica 74(2), 397–429 (2006)
Savani, R., von Stengel, B.: Unit vector games (2015). CoRR, abs/1501.02243
Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate Nash equilibria. Internet Mathematics 5(4), 365–382 (2008)
Tsaknakis, H., Spirakis, P.G., Kanoulas, D.: Performance Evaluation of a Descent Algorithm for Bi-matrix Games. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 222–230. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Fearnley, J., Igwe, T.P., Savani, R. (2015). An Empirical Study of Finding Approximate Equilibria in Bimatrix Games. In: Bampis, E. (eds) Experimental Algorithms. SEA 2015. Lecture Notes in Computer Science(), vol 9125. Springer, Cham. https://doi.org/10.1007/978-3-319-20086-6_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-20086-6_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-20085-9
Online ISBN: 978-3-319-20086-6
eBook Packages: Computer ScienceComputer Science (R0)