AF: Medium: New Frontiers in Equilibrium Computation

经济学和社会科学的概念和方法在互联网和电子商务的研究中得到了许多应用。 许多此类应用的核心是均衡的概念，博弈论家和经济学家广泛研究了均衡，以建模和预测自私但理性的代理人的战略行为。 在过去的十年中，博弈和市场均衡的计算得到了深入的研究，许多令人兴奋的发展为更好地理解均衡带来了新的见解。 与此同时，它们为许多新的研究挑战打开了一扇窗户。 该项目的目标是探索一些重要的方向和问题，已经出现在新的平衡计算前沿。 研究沿着方向进行的项目将补充已经广泛的文献在经济学和社会科学的均衡，通过提供新的视角，通过透镜的算法，近似和计算的复杂性。 除了课程发展、指导博士生和让本科生参与无障碍项目外，研究所还将积极开展外展活动，广泛传播项目取得的成果。研究所计划探索的一些研究方向包括：1）加深我们对Rubinstein在他最近的突破中所采用的新的指数时间定点计算假设的理解，通过探索它与其他自然知识的联系，对基本平衡计算问题的精确复杂性进行了研究。 2)探索文献中深入研究的两个问题之间的联系，在匿名游戏中以多项式精度找到近似纳什均衡的问题，以及在两个玩家游戏中以恒定精度找到近似纳什均衡的问题。 3)研究具有唯一均衡的博弈和市场中均衡的计算。 当均衡存在唯一性时，均衡作为一种预测工具更有意义。 4)致力于阿罗-德布鲁市场均衡的二分法定理，旨在将每个效用族分为容易解决的和难以解决的两类。

Concepts and methodologies from economics and social sciences have found numerous applications in the study of the Internet and e-commerce. At the core of many such applications lies the notion of equilibria, which has been widely studied by game theorists and economists to model and predict the strategic behavior of selfish yet rational agents. During the past decade, the computation of equilibria in both games and markets has been studied intensively and many of the exciting developments have brought new insights towards a much better understanding of equilibria. At the same time, they opened up a window to many new research challenges. The goal of the project is to explore some of the important directions and problems that have emerged in the new frontiers of equilibrium computation. Research along directions pursued in the project will complement the already extensive literature in economics and social sciences on equilibria, by offering new perspectives through the lens of algorithms, approximation, and computational complexity. In addition to curriculum development, mentoring PhD students, and involving undergraduate students in accessible projects, the PIs will actively pursue outreach activities and broadly disseminate results obtained in the project.Some of the research directions that the PIs plan to explore include the following: 1) Deepen our understanding of the new exponential-time hypothesis for fixed-point computation employed by Rubinstein in his recent breakthrough, by exploring its connections with other natural conjectures on the exact complexity of fundamental equilibrium computation problems. 2) Explore connections between two problems that have been studied intensively in the literature, the problem of finding an approximate Nash equilibrium in an anonymous game with a polynomial precision and that in a two-player game with a constant precision. 3) Study the computation of equilibria in games and markets with a unique equilibrium. Equilibrium as a prediction tool is more meaningful when a unique equilibrium exists. 4) Work towards a dichotomy theorem for Arrow-Debreu market equilibria that aims to classify every family of utilities into those that are easy to solve and those that are intractable.