CAREER: Algorithmic Game Theory

算法博弈论是理论计算机科学与经济学交界的一个新兴研究领域。这个领域在很大程度上是由于传统算法技术在当今计算机科学中可以说是核心应用程序的不足-互联网和其他类似的大型、不同种类的网络。PI将在算法博弈论方面追求广泛的研究议程，这可以大致分为两个相关的类别。这项研究的第一个主要主旨将是分析在许多不同的应用中(主要是在网络中)自私行为固有的低效率。这里的双胞胎目标是开发通用的数学方法来确定自私行为何时导致接近最优的结果，并且对于不是这样的应用程序，了解恢复接近最优解决方案所需的集中干预的程度。该提案的第二个主要主题是对均衡的计算复杂性进行深入和系统的研究，例如纳什均衡。计算均衡的多项式时间算法，除了是一个重要的、基本的、尚未被理解的理论问题外，也是建立其可信度的关键一步。特别是，我们不能指望一个计算上难以处理的均衡概念成为现实生活中战略代理人行为的准确模型。与上述研究议程相辅相成的是一项教育计划，该计划包括广泛的研究生课程开发、本科教学和高年级和新生水平的课程开发，以及将本科生培养成研究的积极行动。该提议的智力价值源于其目标，即在算法博弈论的新兴、跨学科领域取得几项基础科学进展。该提议的更广泛影响包括通过研究生课程将研究与教学相结合，传播教育材料，将最先进的研究理念引入本科课程，以及招募本科生从事研究。

{\em Algorithmic game theory} is an emerging research area on the interface of theoretical computer science and economics. This field is largely motivated by the inadequacy of traditional algorithmic techniques for what is arguably the central application in computer science today---the Internet and other similarly large, heterogeneous networks. The PI will pursue a broad research agenda in algorithmic game theory,which can be loosely split into two related categories.The first main thrust of this research will be to analyze the inefficiency inherent in selfish behavior in numerous different applications (primarily in networks). The twins goals here are to develop general mathematical methods for determining when selfish behavior leads to a near-optimal outcome, and, for applications where this is not the case, to understand the degree of centralized intervention required to recover a near-optimal solution.The second main thrust of the proposal is a deep and systematic study of the computational complexity of equilibria, such as Nash equilibria. In addition to being an important, fundamental, and as yet poorlyunderstood theoretical issue, polynomial-time algorithms for computing equilibria are a crucial step toward establishing their credibility. In particular, we cannot expect a computationally intractable notion of equilibrium to be an accurate model of the behavior of real-life strategic agents. The above research agenda is complemented by an educational plan which includes extensive graduate course development, undergraduate teaching and course development at the senior and freshman levels, and activerecruitment of undergraduates into research.The {\bf intellectual merit} of the proposal stems from its goal of making several fundamental scientific advances across the emerging, interdisciplinary field of algorithmic game theory.{\bf Broader impacts} of the proposal include the integration of research and teaching through graduate courses, the dissemination of educational materials, the introduction of state-of-the-art research ideas into undergraduate courses, and the recruitment of undergraduates into research.