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.
