Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Carathéodory's Theorem
 Creators
 Barman, Siddharth
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 pnorm 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 selfcontained 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 nonzero 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 polynomialtime approximation scheme for Nash equilibrium in games with fixed column sparsity s. Moreover, for arbitrary bimatrix gamessince s can be at most nthe running time of our algorithm matches the bestknown 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 kbipartite 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/ε^2).
Additional Information
© 2015 ACM. The author thanks Federico Echenique, Katrina Ligett, Assaf Naor, Aviad Rubinstein, Anthony ManCho So, and Joel Tropp for helpful discussions and references. This research was supported by NSF grants CNS0846025 and CCF1101470, along with a Linde/SISL postdoctoral fellowship.
Attached Files
Submitted  1406.2296v3.pdf
Files
Name  Size  Download all 

md5:56bdec0212f0531767d6fdc5f249f634

316.1 kB  Preview Download 
Additional details
 Eprint ID
 58893
 DOI
 10.1145/2746539.2746566
 Resolver ID
 CaltechAUTHORS:20150715122540136
 arXiv
 arXiv:1406.2296
 CNS0846025
 NSF
 CCF1101470
 NSF
 Linde Institute of Economic and Management Science
 Caltech Social Science Experimental Laboratory
 Created

20150722Created from EPrint's datestamp field
 Updated

20211110Created from EPrint's last_modified field