CAREER: Algorithmic Game Theory

职业：算法博弈论

• 批准号: 0448664
• 负责人: Tim Roughgarden
• 金额: --
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0448664&HistoricalAwards=false
• 关键词: CAREER; Algorithmic; Game; Theory

{\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.

{\em算法博弈论}是理论计算机科学和经济学接口上的一个新兴研究领域。 这一领域的主要动机是传统的算法技术的不足，什么是可以说是在计算机科学的核心应用程序今天---互联网和其他类似的大型，异构网络。 PI将在算法博弈论方面进行广泛的研究，这可以大致分为两个相关的类别。这项研究的第一个主要目标是分析自私行为在许多不同应用中（主要是在网络中）固有的低效率。 这对孪生兄弟的目标是发展通用的数学方法来确定自私行为何时导致接近最优的结果，并在应用中，这不是情况下，了解需要集中干预的程度，以恢复一个接近最优的解决方案。该提案的第二个主要目标是深入和系统地研究均衡的计算复杂性，如纳什均衡。除了是一个重要的，基本的，但还不太了解的理论问题，多项式时间算法计算平衡是一个关键的一步，建立他们的可信度。 特别是，我们不能指望一个难以计算的均衡概念成为现实生活中战略代理人行为的准确模型。上述研究议程是由一个教育计划，其中包括广泛的研究生课程开发，本科教学和课程开发在高年级和新生的水平，并积极招募本科生进入research.The {\bf intellectual merit} of the proposal causes from its target of making some fundamental scientific advances across the emerging，intercultural field of algorithm game theory.该建议的更广泛影响包括通过研究生课程整合研究和教学，传播教育材料，将最先进的研究理念引入本科生课程，以及招募本科生参与研究。