The sixth and final major area of focus, also one not discussed in Kalai, ¹⁶ 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. ²² 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 survey²⁹ 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 theories³⁰ ( including the entire mini-industry of nonmonotonic logics⁹) play an equal if not greater role. Indeed, recent work at the interface of logic and game theory³⁷ extends the static treatment of Fagin et al. ⁸ 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 Halpern¹³ 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 survey¹⁴ 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. ³² 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. ³⁵ 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-