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.