ABSTRACT
We present algorithmic applications of an approximate version of Caratheodory's theorem. The theorem states that given a set of vectors X in Rd, 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 nO(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 nO(log d/ε2).
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- S. Barman. Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem. arXiv:1406.2296, 2015.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- X. Chen, X. Deng, and S.-H. Teng. Sparse games are hard. In Internet and Network Economics, pages 262--273. Springer, 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- C. Daskalakis. On the complexity of approximating a Nash equilibrium. ACM Transactions on Algorithms (TALG), 9(3):23, 2013. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- C. Daskalakis, A. Mehta, and C. Papadimitriou. A note on approximate Nash equilibria. In Internet and Network Economics, pages 297--306. Springer, 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D. Garling. Inequalities: a journey into linear analysis, volume 19. Cambridge University Press Cambridge, 2007.Google ScholarCross Ref
- E. Hazan and R. Krauthgamer. How hard is it to approximate the best Nash equilibrium? SIAM Journal on Computing, 40(1):79--91, 2011. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarCross Ref
- J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. Springer Berlin-Heidelberg-New York, 1973.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic game theory. 2007. Google ScholarCross Ref
- 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.Google Scholar
- A. M.-C. So. Moment inequalities for sums of random matrices and their applications in optimization. Mathematical programming, 130(1):125--151, 2011. Google ScholarDigital Library
- H. Tsaknakis and P. G. Spirakis. An optimization approach for approximate Nash equilibria. In Internet and Network Economics, pages 42--56. Springer, 2007. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
Recommendations
Multi-player Approximate Nash Equilibria
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent SystemsIn this paper we study the complexity of finding approximate Nash equilibria in multi-player normal-form games. First, for any constant number m, we present a polynomial-time algorithm for computing a relative (1 - 1(1+(m-1)m))-Nash equilibrium in ...
Zero-Sum Game Techniques for Approximate Nash Equilibria
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent SystemsWe apply existing, and develop new, zero-sum game techniques for designing polynomial-time algorithms to compute additive approximate Nash equilibria in bimatrix games. In particular, we give a polynomial-time algorithm that given an arbitrary bimatrix ...
Finding approximate nash equilibria of bimatrix games via payoff queries
EC '14: Proceedings of the fifteenth ACM conference on Economics and computationWe study the deterministic and randomized query complexity of finding approximate equilibria in a k x k bimatrix game. We show that the deterministic query complexity of finding an ε-Nash equilibrium when ε < 1/2 is Ω(k2), even in zero-one constant-sum ...
Comments