CAREER: Equilibrium Computation and Other Total Search Problems

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

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.