tion, as both the matches and mismatches
are instructive. Looking at the interactions
between CS and GT taking place today,
one can identify the following foci:
a. Compact game representations;
b. Complexity of, and algorithms for,
computing solution concepts;
c. Algorithmic aspects of mecha-
nism design;
d. Game-theoretic analysis
inspired by specific applications;
e. Multiagent learning;
f. Logics of knowledge and belief,
and other logical aspects of
games.b
The crude mapping between this list
and Kalai’s is as follows:
1995 2008
1 •˲ a
2 •˲ b
3 •˲ c, d
4
5
e,
f
Here, I discuss the areas that match
up ( 1• ˲a, 2• ˲b, 3• ˲c, d), then turn to
the currently active areas that were not
discussed by Kalai (e, f), and finish with
the orphans on the other side ( 4, 5) that
were discussed by Kalai but not yet vigorously pursued.
There has been substantial work
on compact and otherwise specialized
game representations. Some of them
are indeed graph-based—graphical
games, 18 local-effect games, 21 MAIDS, 19
and Game networks, 20 for example. The
graph-based representations extend
also to coalition game theory. 7 But specialized representations exist that are
not graph based, such as those that are
multi-attribute based5 and logic based. 15
I believe this area is ripe for additional
work—regarding, for example, the strategy space of agents described using constructs of programming languages.
The complexity of computing a sample Nash equilibrium (as well as other
solution concepts) has been the focus
of much interest in CS, especially within the theory community. A new complexity class—PPAD—was proposed to
handle problems for which a solution
b This current survey originated in a presentation made at a December 2007 festschrift in
honor of E. Kalai.
is known to exist, 27 the computation of
a sample Nash equilibrium was shown
to be complete for this class, 2 and the
problem of computing Nash equilibria with specific properties was shown
to be NP-hard. 4, 10 At the same time,
algorithms—some quite sophisticated,
and all exponential in the worst case—
have been proposed to compute Nash
equilibria. 11, 41 Somewhat surprisingly,
recent experiments have shown that a
relatively simple search algorithm significantly outperforms more sophisticated algorithms. 31 This is an active area
that promises many additional results.
The third match is somewhat less tight
than the first two. There are at least two
kinds of optimization one could speak
about in a game-theoretic setting. The
first is computing a best response to a
fixed decision by the other agents; this is
of course the quintessential single-agent
optimization problem of operations research and AI, among other fields. The
second is the optimization by the designer of a mechanism aimed at inducing
games with desirable equilibria.
This so-called “mechanism design”
has been the focus of much work in
computer science. One reason is the
interesting interaction between traditional CS problems (such as optimization and approximation) and traditional mechanism-design issues (such
as incentive compatibility, individual
rationality, and social-welfare maximization). A good example is the interaction between the Vickrey-Clarke-Groves
mechanism and shortest-path computation; 26 another is the literature on combinatorial auctions, 6 which combine
a weighted-set-packing-like NP-hard
optimization problem with incentive
issues. The interplay between mechanism design and cryptography is worth
particular mention. Though both are in
the business of controlled dissemination of information, they are different in
significant ways. For one thing, they are
dual in the following sense: mechanism
design attempts to force the revelation
of information, while cryptography attempts to allow its hiding. For another,
they traditionally embody quite different models of paranoia. Game theory
assumes an even-keeled expected utility
maximization on the part of all agents,
while cryptography is more simple-minded: it assumes that “good” agents
act as instructed, while “bad” agents are
maximally harmful. Recent work, however, has begun to bridge these gaps.
This third category blends into the
fourth one, which is research motivated by specific applications that have
emerged in the past decade. For example, the domain of networking has given
rise to a literature on so-called “price
of anarchy” (which captures the inefficiency of equilibria in that domain),
games of routing, networking-forma-tion games, and peer-to-peer networks.
Other domains include sponsored
search auctions, information markets,
and reputation systems. This combination of the third and fourth categories
is arguably the most active area today
at the interface of CS and GT, and many
aspects of it are covered in Nisan et al., 25
which is an extensive edited collection
of surveys. The popularity of this area is
perhaps not surprising. The relevancies
of specific applications speak for themselves (although arguments remain
about whether the traditional game-theoretic analysis is an appropriate one).
More generally, it is not surprising that
mechanism design struck a chord in
CS, given that much of CS’s focus is on
the design of algorithms and protocols.
Mechanism design is the one area within GT that adopts such a design stance.
The fifth category active today is multiagent learning, also called “interactive
learning” in the game-theory literature.c
Multiagent learning, long a major focus
within game theory, has been rediscovered with something of a vengeance in
computer science and in particular AI;
witness special issues devoted to it in
the Journal of Artificial Intelligence39 and
the Machine Learning Journal. 12 For computer science, the move from single-agent learning to multiagent learning
is interesting not only because it calls
for new solutions but also because the
very questions change. When multiple
agents learn concurrently, one cannot distinguish between learning and
teaching, and the question of “optimal”
learning is no longer well defined (just
as the more general notion of an “
optimal policy” ceases to be meaningful
when one moves to the multiagent setting). For a discussion of this phenomenon, see the Journal of Artificial Intelligence special issue cited earlier. 39
c Kalai’s omission of this area is ironic, as he co-authored one of its seminal papers.
