CAREER: Bridging Game Theory, Economics and Computer Science: Equilibria, Fixed Points, and Beyond

互联网无疑是我们这个时代最重要的创新之一。除了作为沟通媒介，它还为新市场和新业务带来了巨大的机会。在过去的几十年里，对互联网和电子商务的研究一直是计算机科学中最令人兴奋和最具挑战性的研究领域之一。最近，博弈论和经济学的概念和方法在这一领域有许多成功的应用。这项提议的主要目标是弥合博弈论、经济学和计算机科学之间的算法差距。虽然计算效率一直是任何计算机系统设计中的关键问题，但博弈论和经济学中的研究几乎完全是非算法的。PI将致力于为一些基本模型和解决方案概念开发有效的算法，并了解其中固有的计算困难，旨在启发和实现下一代电子商务系统。为此，PI将对与纳什均衡和市场均衡相关的算法和复杂性理论问题进行系统研究。这包括两个玩家纳什均衡的多项式时间近似方案的搜索和新技术的发展，以了解各种效用函数和社会影响力的市场均衡的计算。PI还将致力于提高我们目前对PPAD和FIXP的理解，这两个复杂性类别（离散和连续）不动点计算，许多平衡计算的硬度结果依赖于此。作为两个最基本的解决方案的概念，纳什均衡和市场均衡的研究将有助于一个更坚实的算法和复杂性理论基础的交叉学科领域的博弈论。最后，PI将紧密结合教育与研究活动，例如，开发新的（入门和高级）课程，关于博弈论及其在分析社交网络中的应用;指导博士。学生;促进本科生研究。

The Internet is undoubtedly one of the most significant innovations of our era. Beyond serving as a medium of communication, it also enables huge opportunities for new markets and business. The study of the Internet and e-commerce has been one of the most exciting and challenging research areas in computer science during the past few decades. Recently, concepts and methodologies from game theory and economics have found numerous successful applications in this area. The main goal of this proposal is to bridge the algorithmic gap between game theory, economics and computer science. While computational efficiency has always been a critical issue in the design of any computer system, the study within game theory and economics has been almost entirely non-algorithmic. The PI will work to develop efficient algorithms for some of the fundamental models and solution concepts and to understand the computational difficulties inherent within them, with the aim to inspire and enable the next-generation e-commerce systems.For this purpose, the PI will perform a systematic study of both algorithmic and complexity-theoretic questions related to Nash equilibria and market equilibria. This includes the search of a polynomial-time approximation scheme for two-player Nash equilibria and the development of new techniques to understand the computation of market equilibria with various utility functions and with social influence. The PI will also work to improve our current understanding of PPAD and FIXP, two complexity classes for (discrete and continuous) fixed point computation, on which many of the hardness results of equilibrium computation rely. As two of the most fundamental solution concepts, the proposed research on Nash and market equilibria will contribute to a more solid algorithmic and complexity-theoretic foundation for the interdisciplinary field of Algorithmic Game Theory. Finally, the PI will tightly integrate education with the research activities by, e.g., developing new (introductory and advanced) courses on Algorithmic Game Theory and on its use in analyzing social networks; mentoring Ph.D. students; and promoting undergraduate research.