Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

ABSTRACT

We present algorithmic applications of an approximate version of Caratheodory's theorem. The theorem states that given a set of vectors X in R^d, for every vector in the convex hull of X there exists an ε-close (under the p-norm distance, for 2 ≤ p < ∞) vector that can be expressed as a convex combination of at most b vectors of X, where the bound b depends on ε and the norm p and is independent of the dimension d. This theorem can be derived by instantiating Maurey's lemma, early references to which can be found in the work of Pisier (1981) and Carl (1985). However, in this paper we present a self-contained proof of this result.

Using this theorem we establish that in a bimatrix game with n x n payoff matrices A, B, if the number of non-zero entries in any column of A+B is at most s then an ε-Nash equilibrium of the game can be computed in time n^{O(log s/ε2})}. This, in particular, gives us a polynomial-time approximation scheme for Nash equilibrium in games with fixed column sparsity s. Moreover, for arbitrary bimatrix games---since s can be at most n---the running time of our algorithm matches the best-known upper bound, which was obtained by Lipton, Markakis, and Mehta (2003).

The approximate Carathéodory's theorem also leads to an additive approximation algorithm for the densest k-bipartite subgraph problem. Given a graph with n vertices and maximum degree d, the developed algorithm determines a k x k bipartite subgraph with density within ε (in the additive sense) of the optimal density in time n^O(log d/ε²).

References

1. N. Alon, S. Arora, R. Manokaran, D. Moshkovitz, and O. Weinstein. Inapproximability of densest κ-subgraph from average case hardness. http://www.tau.ac.il/ nogaa/PDFS/dks8.pdf, 2011.
2. N. Alon, T. Lee, and A. Shraibman. The cover number of a matrix and its algorithmic applications. Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM), 2014.
3. N. Alon, T. Lee, A. Shraibman, and S. Vempala. The approximate rank of a matrix and its algorithmic applications: approximate rank. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, pages 675--684. ACM, 2013.
4. S. Barman. Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem. arXiv:1406.2296, 2015.
5. A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan. Detecting high log-densities: an O (n1/4) approximation for densest k-subgraph. In Proceedings of the 42nd ACM symposium on Theory of computing, pages 201--210. ACM, 2010.
6. H. Bosse, J. Byrka, and E. Markakis. New algorithms for approximate Nash equilibria in bimatrix games. In Internet and Network Economics, pages 17--29. Springer, 2007.
7. J. Bourgain, A. Pajor, S. Szarek, and N. Tomczak-Jaegermann. On the duality problem for entropy numbers of operators. In Geometric aspects of functional analysis, pages 50--63. Springer, 1989.
8. M. Braverman, Y. K. Ko, and O. Weinstein. Approximating the best Nash equilibrium in n o(log n)-time breaks the exponential time hypothesis. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
9. B. Carl. Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces. In Annales de l'institut Fourier, volume 35, pages 79--118. Institut Fourier, 1985.
10. X. Chen, X. Deng, and S.-H. Teng. Sparse games are hard. In Internet and Network Economics, pages 262--273. Springer, 2006.
11. X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3):14, 2009.
12. C. Daskalakis. On the complexity of approximating a Nash equilibrium. ACM Transactions on Algorithms (TALG), 9(3):23, 2013.
13. C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195--259, 2009.
14. C. Daskalakis, A. Mehta, and C. Papadimitriou. A note on approximate Nash equilibria. In Internet and Network Economics, pages 297--306. Springer, 2006.
15. C. Daskalakis, A. Mehta, and C. Papadimitriou. Progress in approximate Nash equilibria. In Proceedings of the 8th ACM conference on Electronic commerce, pages 355--358. ACM, 2007.
16. C. Daskalakis and C. H. Papadimitriou. On oblivious ptas's for Nash equilibrium. In Proceedings of the 41st annual ACM symposium on Theory of computing, pages 75--84. ACM, 2009.
17. T. Feder, H. Nazerzadeh, and A. Saberi. Approximating Nash equilibria using small-support strategies. In Proceedings of the 8th ACM conference on Electronic commerce, pages 352--354. ACM, 2007.
18. D. Garling. Inequalities: a journey into linear analysis, volume 19. Cambridge University Press Cambridge, 2007.
19. E. Hazan and R. Krauthgamer. How hard is it to approximate the best Nash equilibrium? SIAM Journal on Computing, 40(1):79--91, 2011.
20. R. Kannan and T. Theobald. Games of fixed rank: A hierarchy of bimatrix games. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1124--1132. Society for Industrial and Applied Mathematics, 2007.
21. S. C. Kontogiannis, P. N. Panagopoulou, and P. G. Spirakis. Polynomial algorithms for approximating Nash equilibria of bimatrix games. In Internet and Network Economics, pages 286--296. Springer, 2006.
22. S. C. Kontogiannis and P. G. Spirakis. Efficient algorithms for constant well supported approximate equilibria in bimatrix games. In Automata, Languages and Programming, pages 595--606. Springer, 2007.
23. J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. Springer Berlin-Heidelberg-New York, 1973.
24. R. J. Lipton, E. Markakis, and A. Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM conference on Electronic commerce, pages 36--41. ACM, 2003.
25. O. L. Mangasarian and H. Stone. Two-person nonzero-sum games and quadratic programming. Journal of Mathematical Analysis and Applications, 9(3):348--355, 1964.
26. N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic game theory. 2007.
27. G. Pisier. Remarques sur un résultat non publié de B. Maurey (French) {Remarks on an unpublished result of B. Maurey}. Séminaire Analyse fonctionnelle (dit), pages 1--12, 1981.
28. A. M.-C. So. Moment inequalities for sums of random matrices and their applications in optimization. Mathematical programming, 130(1):125--151, 2011.
29. H. Tsaknakis and P. G. Spirakis. An optimization approach for approximate Nash equilibria. In Internet and Network Economics, pages 42--56. Springer, 2007.
30. H. Tsaknakis and P. G. Spirakis. Practical and efficient approximations of Nash equilibria for win-lose games based on graph spectra. In Internet and Network Economics, pages 378--390. Springer, 2010.

Index Terms

• Theory of computation

  • Design and analysis of algorithms