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.