The sixth and final major area of focus, also one not discussed in Kalai, 16
is called “interactive epistemology” in
game theory and simply “reasoning
about knowledge and belief” in computer science. Starting in the mid-1980s,
this area was for a while the most active
focus of interaction between computer
science (including distributed systems,
AI, and theory) and game theory. Beside game theory, it established deep
ties with philosophy and mathematical
logic, culminating in the seminal book
by Fagin et al. 8, d It is interesting to speculate why this area was omitted from
Kalai’s list, even although it predates
his paper by a decade, and why today it
is not as broadly populated as the other
areas. I think the reason is that the subject matter is more foundational, primarily non-algorithmic, and appeals to
a smaller sliver of the two communities.
Be that as it may, it remains a key area of
interaction between the two fields.
These six areas are where most of
the action has been in past years, but by
listing only them and being brief about
each one, I have by necessity glossed
over some other important areas. The
references compensate for this omission to some extent. In addition, the
reader is referred to the following additional surveys, all by computer scientists
who each have a slightly different slant.
Most of these works go into considerably
more detail about some of the topics.
˲ The earliest relevant survey is probably by Linial. 22 Geared primarily toward
game theorists, this 58-page report has
deep coverage of game-theoretic aspects of distributed systems, fault-toler-ant computing, and cryptography, and
it also touches on computation of game
theoretic concepts, games and logic,
and other topics.
˲ Papadimitriou’s survey29 geared to-
d That book focused on static aspects of knowledge and belief, which, notwithstanding the
substantial computer-science credentials of
the authors, raise an interesting contrast between the computer-science and game-theory
literature in these areas. In game theory, static
theories are indeed the primary focus, whereas in computer science—in particular, in database theory and artificial intelligence—belief
revision and other dynamic theories30 (
including the entire mini-industry of nonmonotonic
logics9) play an equal if not greater role. Indeed, recent work at the interface of logic and
game theory37 extends the static treatment of
Fagin et al. 8 in a dynamic direction.
i expect game-
theory pragmatics
to be as critical
to reducing game
theory to practice
as language
pragmatics have
been to analyzing
human discourse
or understanding
language by
computers.
ward computer scientists, is a concise
five-page paper summarizing the main
complexity and algorithmic issues at
the interface of CS and GT circa 2001.
˲ The 21-page paper by Halpern13
is similar to Linial in that it is geared
toward game theorists and its main focus is distributed systems, but having
been published a decade later it is more
current. The work later evolved into a
17-page survey14 with an abbreviated
discussion of distributed computing
and additional material on complexity
considerations, price of anarchy, mediators, and other topics.
˲Roughgarden’s 30-page work is
a detailed survey of a specific topic—
namely, the complexity of computing
a sample Nash equilibrium. 32 Geared
mostly toward economists, it includes
ample background material on relevant
concepts from complexity theory.
The material discussed so far is not
only prominently featured in computer
science journals and conferences but
also is beginning to find its way into
textbooks. 35 These areas will undoubtedly continue to flourish. But now I
want to turn our attention to the two
closely-related areas— 4 and 5—listed
by Kalai that have not been looked at as
closely by the community at large, CS
in particular. I do this for two reasons: I
believe they are critical to the future success of game theory, and I believe that
CS can play an important role in them.
They both have to do with incorporating practical considerations into the
model of rationality that is inherent to
game theory. To repeat the caveat stated
earlier: unlike the material so far, the remaining discussion is future-directed,
speculative, and subjective.
Lessons from Linguistics
The field of linguistics distinguishes
among syntax, semantics, and pragmatics. Syntax defines the form of language, semantics defines its meaning,
and pragmatics defines its use. While
the three interact in important ways,
the distinctions have proved very useful. I believe that game theory may do
well to make similar distinctions, and
that CS can help in the process. Just as
in the case in linguistics, it is unlikely
that game-theory pragmatics will yield
to unified clean theories, as do syntax
and semantics. But I expect game-theory pragmatics to be as critical to reduc-