Algorithmic Game Theory-英文文献.pdf

Algorithmic Game Theory∗ Tim Roughgarden† May 12, 2009 1 Introduction The widespread adoption of the Internet and the emergence of the Web changed society’s relation- ship with computers. The primary role of a computer evolved from a stand-alone, well-understood machine for executing software to a conduit for global communication, content-dissemination, and commerce. The algorithms and complexity theory community has responded to these changes by formulating novel problems, goals, and design and analysis techniques relevant for modern appli- cations. Game theory, which has studied deeply the interaction between competing or cooperating individuals, plays a central role in these new developments. Research on the interface of theoretical computer science and game theory, an area now known as algorithmic game theory (AGT), has exploded phenomenally over the past ten years. The primary research themes in AGT differ from those in classical microeconomics and game theory in important, albeit predictable, respects. Firstly in application areas: Internet-like networks and non-traditional auctions motivate much of the work in AGT. Secondly in its quantitative engi- neering approach: AGT research typically models applications via concrete optimization problems and seeks optimal solutions, impossibility results, upper and lower bounds on feasible approxi- mation guarantees, and so on. Finally, AGT usually adopts reasonable (e.g., polynomial-time) computational complexity as a binding constraint on the feasible behavior of system designers and participants. These themes, which have played only a peripheral role in traditional game theory, give AGT its distinct character and relevance. The next three sections touch on the current dominant r