Algorithmic Game Theory

Game theory is a branch of mathematics devoted to studying interaction among rational and self-interested
agents. The field took on its modern form in the 1940s
and 1950s (von Neumann and Morgenstern 1947; Nash 1950,
Kuhn 1953), with even earlier antecedents (such as Zermelo
1913 and von Neumann 1928). Although it has had occasional
and significant overlap with computer science over the years,
game theory received most of its early study by economists.
Indeed, game theory now serves as perhaps the main analytical
framework in microeconomic theory, as evidenced by its prominent role in economics textbooks (for example, Mas-Colell,
Whinston, and Green 1995) and by the many Nobel prizes in
economic sciences awarded to prominent game theorists.
Artificial intelligence got its start shortly after game theory
(McCarthy et al. 1955), and indeed pioneers such as von Neumann and Simon made early contributions to both fields (see,
for example, Findler [1988], Simon [1981]). Both game theory
and AI draw (nonexclusively) on decision theory (von Neumann and Morgenstern 1947); for example, one prominent
view defines artificial intelligence as “the study and construction of rational agents” (Russell and Norvig 2003), and hence
takes a decision-theoretic approach when the world is stochastic. However, artificial intelligence spent most of its first 40 years
focused on the design and analysis of agents that act in isolation, and hence had little need for game-theoretic analysis.
Starting in the mid to late 1990s, game theory became a
major topic of study for computer scientists, for at least two
main reasons. First, economists began to be interested in systems whose computational properties posed serious barriers to
practical use, and hence reached out to computer scientists;
notably, this occurred around the study of combinatorial auctions (see, for example, Cramton, Shoham, and Steinberg 2006).
Second, the rise of distributed computing in general and the
Internet in particular made it increasingly necessary for computer scientists to study settings in which intelligent agents reason about and interact with other agents. Game theory generEditorial
Copyright © 2010, Association for the Advancement of Artificial Intelligence.