CAREER: Equilibrium Computation and Other Total Search Problems

纳什均衡和市场均衡分别是计算博弈论和经济学中两个最基本的解概念。这些概念适用于密码学、拓扑学和验证等不同领域的许多长期未决问题。尽管我们现在已经对这些有了相当的理解，但在诸如有效的近似算法、超越最坏情况分析以及子类与其中问题之间的关系等领域中，许多基本问题仍然没有得到解决。本项目旨在通过汇集均衡计算、平方和分析、稳健分析和其他领域的工具来探索这些问题。预计该项目将为一大类此类问题提供高效和强大的算法，并开发工具，以获得来自不同领域的问题之间的联系，从而深入了解其复杂性。由于在社会网络分析和资源分配等领域的大量应用，前者将产生积极的实际影响。该项目将涉及和培训研究生和本科生在项目的各个层次，将研究结果与教学相结合，并使课堂讲稿和其他材料免费在线提供。该项目还将通过指导讲习班和伊利诺伊大学厄巴纳-香槟分校的倡议提供的机会，接触到代表性不足群体的学生。该项目的三个主要研究目标是：（i）通过常数近似纳什均衡的复杂性来理解PPAD类的最近指数时间假设，（ii）理解CLS类中来自拓扑、验证、密码学等的问题的相对复杂性，和（iii）发展超越最坏情况的分析，以解释存在的简单和经验快速算法计算均衡。这些问题将涉及开发新的近似和超越最坏情况的分析工具。此外，新的减少技术将需要开发相关的开放问题，从不同的领域和/或证明近似的硬度。该项目将通过建立在平衡计算和复杂性的最新工作，使用平方和方法，最近的平滑分析技术和证明下界的进展工具来接近这些。这个奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

Nash and market equilibria are two of the most fundamental solution concepts in computational game theory and economics, respectively. These concepts are applicable to many long-standing open questions in diverse fields such as cryptography, topology, and verification. Even though we have a fair understanding of these by now, many fundamental questions still remain unresolved in areas such as efficient approximation algorithms, beyond-worst-case analysis, and the relations between the sub-classes and the problems therein. This project aims to explore these questions by bringing together tools from equilibrium computation, sum-of-squares analysis, robust analysis, and other areas. The project is expected to provide efficient and robust algorithms for a large class of such problems, as well as to develop tools to obtain connections among problems from disparate fields and thereby bring insights into their complexity. The former will have a positive practical impact due to numerous applications in areas such as social network analysis and resource allocation. The project will involve and train graduate and undergraduate students at various levels of the project, integrate the findings with teaching, and make lecture notes and other material freely available online. The project will also reach students from underrepresented groups through mentoring workshops and the opportunities provided by initiatives at the University of Illinois at Urbana-Champaign.The three main research goals of this project are: (i) understand the recent exponential time hypothesis for the class PPAD through the complexity of constant-approximate Nash equilibria, (ii) understand the relative complexity of problems in the class CLS coming from topology, verification, cryptography, etc., and (iii) develop beyond-worst-case analysis to explain the existence of simple and empirically fast algorithms for computing equilibria. These problems will involve developing novel tools for approximation and for beyond-worst-case analysis. Furthermore, new reduction techniques will need to be developed to relate the open problems from diverse fields and/or to prove hardness of approximation. The project will approach these by building on recent work on equilibrium computation and complexity, using tools from the sum-of-squares method, recent smoothed analysis techniques, and advances in proving lower bounds. Tools developed in the process will contribute to the burgeoning literature in these domains and open up avenues for further exploration.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.