review articles

Doi: 10.1145/1785414.1785439

A new era of theoretical computer science
addresses fundamental problems about
auctions, networks, and human behavior.
BY tim RouGhGaRDen
algorithmic
Game theory

via concrete optimization problems and seeks optimal solutions, impossibility results, upper and lower bounds on feasible approximation guarantees, and so on. Finally, AGT usually adopts reasonable (for example, 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 AG T its distinct character and relevance.

Here, we touch on the current dominant research trends in AGT, loosely following the organization of the first book in the field. 30 We focus on contributions of the algorithms and complexity theory community; see two recent articles in Communications18, 40 and the references therein for alternative perspectives on computer science and game theory.

The widespread adop TioN of the Internet and the emergence of the Web changed society’s relationship 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 applications.

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 over the past 10 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 nontraditional auctions motivate much of the work in AGT. Secondly in its quantitative engineering approach: AGT research typically models applications

algorithmic mechanism Design Algorithmic mechanism design studies optimization problems where the underlying data—such as the values of goods and costs of performing a task— is initially unknown to the algorithm designer, and must be implicitly or ex-

 

key;insights

many modern computer science
applications involve autonomous
decision-makers with conflicting
objectives. current research in
algorithms and complexity theory
uses game theory as an important
tool for modeling and reasoning about
such applications.
one application domain is auctions,
including the single-item auctions
of eBay and amazon; the sponsored
search auctions of Google, Yahoo!,
and microsoft; and the combinatorial
auctions used by governments to
sell wireless spectrum. a second
application is large networks, where
the goal is to understand how such
networks form, how network users
behave, and what kind of design and
management strategies ensure good
network performance.
Recent results that determine the
computational complexity of computing
a nash equilibrium cast doubt on the
concept’s ability to predict the outcome
of rational behavior.