Approximating Carathéodory's Theorem and Nash Equilibria
Approximating Carathéodory's Theorem and Nash Equilibria
复制标题
近似卡拉西奥多里定理和纳什均衡
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Siddharth Barman
中科院分区：
文献类型：
--
作者：
Siddharth Barman
在本次演讲中至少2）可以表示为x的大多数b矢量的凸组合，其中结合b独立于caratheodory的定理的重要性。大约是很有趣的，它的算法也很明显。在收益矩阵之和稀少的游戏中，为NASH等效提供了多项式时间近似方案。该算法的运行时间与最著名的上限相匹配，该结合在（Lipton，Markakis和Mehta 2003）中获得
In this talk I will present an approximate version of Caratheodory’s theorem and its algorithmic applications. In particular, I will show that for every vector in the convex hull of a set of vectors X there exists a nearby (under p-norm distance, for p at least 2) vector that can be expressed as a convex combination of at most b vectors of X, where the bound b is independent of the dimension of the vectors. Given the significance of Caratheodory’s theorem, this approximate version is interesting in its own right. It also has notable algorithmic applications. Specifically, I will describe how this approximate version of Caratheodory’s theorem leads to a new algorithm for computing approximate Nash equilibria in two-player games. This algorithm, in particular, provides a polynomial-time approximation scheme for Nash equilibrium in games where the sum of the payoff matrices is sparse. Moreover, for arbitrary two-player games the running time of the algorithm matches the best-known upper bound, which is obtained in (Lipton, Markakis, and Mehta 2003). Arxiv preprint: http://arxiv.org/abs/1406.2296