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.