ing game theory to practice as language pragmatics have been to analyzing human discourse or understanding language by computers.

The distinction between the syntax and semantics of games is, I think, quite important, as some of the disputes within game theory regarding the primacy of different game representations (for example, the strategic and extensive forms) suffer from the lack of this distinction. It might, however, be presumptuous for CS to intrude on this debate, except insofar as it lends logical insights. ³⁸ Indeed, perhaps this is more the role of mathematical logic than of CS per se.

But where CS can truly lead the way is in game theory’s pragmatics. Game theory as we know it embodies radical idealizations, which include the infinite capacity of agents to reason and the infinite mutually recursive modeling of agents. Backing off from these strong assumptions has proven challenging. A fairly thin strand of work under the heading of “bounded rationality” involves games played by automata. ³³ This is an important area of research that sometimes makes deep connections between the two fields. For example, early results showed that one of the well-known pesky facts in game theory—namely, that constant “defection” is the only subgame-perfect equilibrium in the finitely repeated prisoner’s dilemma game—ceases to hold true if the players are finite automata with sufficiently few states. ^{24, 28} A more recent result shows that when players in a game are computer programs, one obtains phenomena akin to the Folk Theorem for repeated games. ³⁶

This connection between theoretical models of computation and game theory is quite important and beautiful, but it constitutes a fairly narrow interpretation of the term “bounded rationality.” The term should perhaps be reserved for describing a much broader research agenda—one that may encourage more radical departures from the traditional view in game theory. Let me mention two directions that I think would be profitable (and difficult) to pursue under this broader umbrella.

When one takes seriously the notion of agents’ limited reasoning powers, it is not only some of the answers that begin to change; the questions themselves must be reconsidered. Consider

science operates
at many levels.
for some, it is
sufficient that
scientific theories
be clever, beautiful,
and inspirational.
others require
that any science
eventually
make contact
with compelling
applications
and be subjected
to empirical
evaluation.

the basic workhorses of game theory— the Nash equilibrium and its many variants—that have so far served as the very basic analysis tool of strategic interactions. Questioning the role of equilibrium analysis will be viewed by some in GT as act of heresy, but real life suggests that we may have no choice. For example, in the trading agent competition, Nash equilibrium of the game did not play a role in almost any participating program, ⁴² and this is certainly true as well of the more established chess and checkers competitions.

It is premature to write off the Nash equilibrium as irrelevant, however. For example, two programs competing in the TAC did in fact make use of what can be viewed as approximate empirical NE. ⁴² Another striking example is the computation of equilibria in a simplified game tree by a top-scoring program in a poker competition. ⁴³ It could be argued that maxmin strategies, which coincide with equilibrium strategies in zero-sum games, do play an important pragmatic role. But computation of either maxmin or equilibrium strategies in competitions has certainly been the exception to the rule. The more common experience is that one expends the vast majority of the effort on traditional AI problems such as designing a good heuristic function, searching, and planning. Only a little—albeit important—time is spent reasoning about the opponent.

The impact of such pragmatic considerations on game theory can be dramatic. Rather than start from very strong idealizing assumptions and awkwardly try to back off from them, it may prove more useful or accurate to start from assumptions of rather limited reasoning and mutual modeling, and then judiciously add what is appropriate for the situation being modeled. Which in-cremental-modeling approach will out has yet to be seen, but the payoff both for CS and GT can be substantial.

The second direction is radical in a different way. Game theory adopts a fairly terse vocabulary, inheriting it from decision theory and the found-aions of statistics.^e In particular, agents

e Parenthetically, it can be remarked that Savage’s setting, ³⁴ on which the modern Bayesian framework is based, does not have an obvious extension to the multi-agent case. However, this is not the focus of the point I am making here.