review articles
Doi: 10.1145/1378704.1378721
The most dramatic interaction between CS
and GT may involve game-theory pragmatics.
By yoaV shoham
computer
science and
Game theory
ILLUS TRATION B Y JEAN FRANCOIS PODEVIN
GAME THEORy HAS influenced many fields,
including economics (its initial focus), political
science, biology, and many others. In recent years,
its presence in computer science has become
impossible to ignore. GT is an integral part of
artificial intelligence (AI), theory, e-commerce,
networking, and other areas of computer science,
and it is routinely featured in the field’s leading
journals and conferences. One reason is application
pull: the Internet calls for analysis and design of
systems that span multiple entities, each with its
own information and interests. Game theory, for all
its limitations, is by far the most developed theory
of such interactions. Another reason is technology
push: the mathematics and scientific mind-set of
game theory are similar to those that characterize
many computer scientists. Indeed, it is interesting
to note that modern computer science and modern
game theory originated in large measure at the same
place and time—namely at Princeton
University, under the leadership of John
von Neumann, in the 1950s.a
In this article I try to do two things:
identify the main areas of interaction
between computer science and game
theory so far; and point to where the
most interesting interaction yet may
lie—in an area that is still relatively un-derexplored.
The first part aims to be an unbiased
survey, but it is impossible to avoid
bias altogether. Ten researchers surveying the interactions between CS and
GT would probably write 10 different
types of reports. Indeed, several already
have (as I will discuss). Moreover, in
this brief discussion I cannot possibly
do justice to all the work taking place
in the area. So I try to compensate for
these limitations in two ways: I provide
a balanced set of initial pointers into
the different subareas, without regard
to the amount or nature of work that
has taken place in each; and I point the
reader to other relevant surveys of the
CS-GT interaction, each having its own
take on things.
The second part is decidedly subjective, but it is still meant to be broadly
relevant both to computer scientists
and game theorists interested in the interaction between the disciplines.
Lessons from Kalai (1995)
My departure point is a 13-year-old survey paper by E. Kalai, 16 a game theorist
with algorithmic sensibilities. Geared
primarily toward computer scientists,
the paper took stock of the interactions between game theory, operations
research, and computer science at the
time. It points to the following areas:
1. Graphs in games
2. The complexity of solving a game
3. Multiperson operations research
4. The complexity of playing a game
5. Modeling bounded rationality.
The reason I start with this paper, besides providing the interesting perspective of a non-computer scientist, is the
comparison with current CS-GT interac-
a I thank Moshe Tennenholtz for this observation, which is especially true of G T and AI.
