Games of fixed rank: a hierarchy of bimatrix games

ABSTRACT

We propose and investigate bimatrix games, whose (entry-wise) sum of the pay-off matrices of the two players is of rank k, where k is a constant. We will say the rank of such a game is k. For every fixed k, the class of rank k-games strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We show that even for k = 1 the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we can provide a deterministic polynomial time algorithm for finding an ε-approximation (whose running time is polynomial in 1\ε) as well as a randomized polynomial time approximation algorithm (whose running time is similar), but which offers the possibility of finding an exact solution in polynomial time if a conjecture is valid. The latter algorithm is based on a new application of random sampling methods to quadratic optimization problems of fixed rank.

REFERENCES

• 1: Imre Barany , Santosh Vempala , Adrian Vetta, Nash Equilibria in Random Games, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.123-131, October 23-25, 2005 [doi>10.1109/SFCS.2005.52]
• 2: J. Bulow and J. Levin. Matching and price competition. To appear in American Economic Review.
• 3: X. Chen and X. Deng. Settling the complexity of 2-player Nash equilibrium. Electronic Colloquium on Computational Complexity. Report TR05--140, 2005.
• 4: X. Chen and X. Deng. Computing Nash equilibria: Approximation and smoothed complexity. Electronic Colloquium on Computational Complexity. Report TR06-23, 2006.
• 5: Vincent Conitzer , Tuomas Sandholm, A technique for reducing normal-form games to compute a Nash equilibrium, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160731]
• 6: G. B. Dantzig. Linear Programming and Extensions. Princeton Univ. Press, Princeton, NJ, 1963.
• 7: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 8: K. Isaacson and C. B. Millham. On a class of Nash-solvable bimatrix games and some related Nash subsets. Naval. Res. Logist. Quarterly 23:311--319, 1980.
• 9: Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
• 10: H. Keiding. On the maximal number of Nash equilibria in an n x n bimatrix game. Games Econom. Behavior 21:148--160, 1997.
• 11: S. C. Kontogiannis, P. N. Panagopoulou, P. G. Spirakis. Polynomial algorithms for approximating Nash equilibria of bimatrix games. Electronic Colloquium on Computational Complexity. Report TR06-81, 2006.
• 12: C. E. Lemke and J. T. Howson. Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12:413--423, 1964.
• 13: Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779933]
• 14: O. L. Mangasarian. Equilibrium points of bimatrix games. J. Soc. Industr. Appl. Math. 12:778--780, 1964.
• 15: A. McLennan and I.-U. Park. Generic 4 x 4 two person games have at most 15 Nash equilibria. Games Econom. Behavior 26:111--130, 1997.
• 16: J. Nash. Equilibrium points in n-person games. Proc. Amer. Math. Soc. 36:48--49, 1950.
• 17: J. Nash. Non-cooperative games. Annals of Mathematics 54:286--295, 1951.
• 18: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ, 1944.
• 19: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 20: Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 21: T. Quint and M. Shubik. A bound on the number of Nash equilibria in a coordination game. Economic Letters 77:323--327, 2002.
• 22: Rahul Savani , Bernhard von Stengel, Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.258-267, October 17-19, 2004 [doi>10.1109/FOCS.2004.28]
• 23: B. von Stengel. New maximal numbers of equilibria in bimatrix games. Discrete Comput. Geom. 21:557--568, 1999.
• 24: B. von Stengel. Computing equilibria for two-person games. In R. J. Aumann, S. Hart (eds.), Handbook of Game Theory, North-Holland, Amsterdam, 2002.
• 25: S. Vavasis. Approximation algorithms for indefinite quadratic programming. Technical Report 91--1228, Dept. of Computer Science, Cornell University (Ithaca, NY), 1991.
• 26: Stephen A. Vavasis, Approximation algorithms for indefinite quadratic programming, Mathematical Programming: Series A and B, v.57 n.2, p.279-311, Nov. 2, 1992 [doi>10.1007/BF01581085]