Sum-of-squares meets nash: lower bounds for finding any equilibrium
Sum-of-squares meets nash: lower bounds for finding any equilibrium
复制标题
平方和满足纳什：找到任何均衡的下界
DOI：
10.1145/3188745.3188892
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Mehta, Ruta
中科院分区：
文献类型：
--
作者：
Kothari, Pravesh K.;Mehta, Ruta
计算两人博弈中的纳什均衡（NE）是算法博弈论的核心问题。这项工作的主要动机是了解平方和方法在计算精确和近似平衡方面的强大功能。以前在这方面的工作主要集中在关于社会福利等平衡的一些自然质量衡量标准的近似“最佳”平衡的硬度上。然而，这样的结果并不直接与寻找任何平衡问题的复杂性相关。在这项工作中，我们提出了一个平方和算法（以及一般的凸松弛）的舍入框架，适用于在两个玩家双矩阵游戏中寻找近似/精确平衡。具体来说，我们用验证预言机（OV）定义了不经意舍入的概念。这些算法可以访问 DegreedSoS 松弛的解，以构建候选（部分）解决方案列表，并调用 averificationoracle 来检查列表中的候选是否给出（精确或近似）平衡。该框架捕获组合优化中最著名的近似算法，包括著名的基于半定规划的最大割、约束满足问题算法，以及最近针对独特游戏/小集扩展、最佳的 SoS 松弛的工作可分离状态，以及无监督机器学习中的许多问题。我们的主要结果是该框架中的强无条件下界。具体来说，我们表明，对于 є = θ(1/poly(n))，没有算法使用 ao(n) 度 SoS 松弛来构建 2o(n) 大小的候选列表并获得 є 近似 NE。对于某些常数 є，我们显示了 Degreeo(log(n)) SoS 松弛和列表 sizeno(log(n)) 的类似结果。在我们有限的算法框架中，我们的结果可以被视为对最近的 PPAD 指数时间假设的无条件确认。我们的证明策略包括构建一系列游戏，这些游戏都共享一个共同的平方和解，但任何游戏的每个（近似）均衡都远离该系列中任何其他游戏的每个均衡（在任一玩家的策略中）。在此过程中，我们加强了针对枚举算法的经典无条件下界，以找到 Daskalakis-Papadimitriou 的近似平衡点，以及 Gilbow-Zemel 的计算平衡点的经典难度。
Computing Nash equilibrium (NE) in two-player game is a central question in algorithmic game theory. The main motivation of this work is to understand the power of sum-of-squares method in computing equilibria, both exact and approximate. Previous works in this context have focused on hardness of approximating “best” equilibria with respect to some natural quality measure on equilibria such as social welfare. Such results, however, do not directly relate to the complexity of the problem of findinganyequilibrium.In this work, we propose a framework ofroundingsfor the sum-of-squares algorithm (and convex relaxations in general) applicable to finding approximate/exact equilbria in two player bimatrix games. Specifically, we define the notion ofoblivious roundings with verification oracle(OV). These are algorithms that can access a solution to the degreedSoS relaxation to construct a list of candidate (partial) solutions and invoke averificationoracle to check if a candidate in the list gives an (exact or approximate) equilibrium.This framework captures most known approximation algorithms in combinatorial optimization including the celebrated semi-definite programming based algorithms for Max-Cut, Constraint-Satisfaction Problems, and the recent works on SoS relaxations for Unique Games/Small-Set Expansion, Best Separable State, and many problems in unsupervised machine learning.Our main results are strong unconditional lower bounds in this framework. Specifically, we show that for є = Θ(1/poly(n)), there’s no algorithm that uses ao(n)-degree SoS relaxation to construct a 2o(n)-size list of candidates and obtain an є-approximate NE. For some constant є, we show a similar result for degreeo(log(n)) SoS relaxation and list sizeno(log(n)). Our results can be seen as an unconditional confirmation, in our restricted algorithmic framework, of the recent Exponential Time Hypothesis for PPAD.Our proof strategy involves constructing a family of games that all share a common sum-of-squares solution but every (approximate) equilibrium of any game is far from every equilibrium of any other game in the family (in either player’s strategy). Along the way, we strengthen the classical unconditional lower bound against enumerative algorithms for finding approximate equilibria due to Daskalakis-Papadimitriou and the classical hardness of computing equilibria due to Gilbow-Zemel.