Game Development Reference

In-Depth Information

For quite a few games, thinking in terms of Nash equilibrium gives insight

into what people do (there is a reason that game theory is taught in business

schools!). However, as is well known, Nash equilibrium suffers from numerous

problems. For example, the Nash equilibrium in games such as the repeated

prisoner's dilemma is to always defect (see Section 8.3 for more discussion

of the repeated prisoner's dilemma). It is hard to make a case that rational

players 'should' play the Nash equilibrium in this game when 'irrational'

players who cooperate for a while do much better! Moreover, in a game that

is only played once, why should a Nash equilibrium arise when there are

multiple Nash equilibria? Players have no way of knowing which one will be

played. And even in games where there is a unique Nash equilibrium (like

the repeated prisoner's dilemma), how do players obtain correct beliefs about

what other players are doing if the game is played only once? (See [Kreps,

1990] for a discussion of some of these problems.)

Not surprisingly, there has been a great deal of work in the economics

community on developing alternative solution concepts. Various alternatives

to and refinements of Nash equilibrium have been introduced, including,

among many others,
rationalizability
,
sequential equilibrium
,
(trembling hand)

perfect equilibrium
,
proper equilibrium
, and
iterated deletion of weakly domi-

nated strategies
. (These notions are discussed in standard game theory texts,

such as [Fudenberg and Tirole, 1991] and [Osborne and Rubinstein, 1994].)

Despite some successes, none of these alternative solution concepts address

the following three problems with Nash equilibrium, all inspired by computer

science concerns.

•

Although both computer science and distributed computing are concerned

with multiple agents interacting, the focus in the game theory literature

has been on the strategic concerns of agents - rational players choosing

strategies that are best responses to strategies chosen by the other player;

the focus in distributed computing has been on problems such as fault

tolerance and asynchrony, leading to, for example work on Byzantine

agreement [Fischer et al., 1985, Pease et al., 1980]. Nash equilibrium does

not deal with 'faulty' or 'unexpected' behaviour, nor does it deal with

colluding agents. In large games, we should expect both.

•

Nash equilibrium does not take computational concerns into account.

We need solution concepts that can deal with resource-bounded players,

concerns that are at the heart of cryptography.

•

Nash equilibrium presumes that players have common knowledge of the

structure of the game, including all the possible moves that can be made

Search Nedrilad ::

Custom Search