Game Development Reference

In-Depth Information

the machine on that input. The complexity can also be used to capture the

complexity of the machine itself (e.g., the number of states, as in Rubinstein's

case) or to model the cost of searching for a new strategy to replace one that

the player has been given. (This makes sense if the game comes along with a

recommended strategy, as is typically the case in mechanism design. One of

the reasons that players follow a recommended strategy is that there may be

too much effort involved in trying to find a new one.)

We again consider Bayesian games, where each player has a type. In a

standard Bayesian game, an agent's utility depends on the type profile and

the action profile (that is, every player's type, and the action chosen by

each player). In a
computational Bayesian game
, each player
i
chooses

a Turing machine. Player
i
's type
t
i
is taken to be the input to player
i
's

Turing machine
M
i
. The output of
M
i
on input
t
i
is taken to be player
i
's

action. There is also a complexity associated with the pair (
M
i
,t
i
). Player
i
's

utility again depends on the type profile and the action profile, and also on

the complexity profile. The reason we consider the whole complexity profile

in determining player
i
's utility, as opposed to just
i
's complexity, is that,

for example,
i
might be happy as long as his machine takes fewer steps than

j
's. Given these definitions, we can define Nash equilibrium as usual. With

this definition, by defining the complexity appropriately, it will be the case

that playing safe for su
ciently large inputs will be an equilibrium.

Computational Nash equilibrium also gives a plausible explanation of

observed behaviour in finitely-repeated prisoner's dilemma.

Example 8.2
Recall that in the prisoner's dilemma, there are two prisoners,

who can choose to either cooperate or defect. As described in the table below,

if they both cooperate, they both get 3; if they both defect, then both get 1; if

one defects and the other cooperates, the defector gets 5 and the cooperator

gets
−
5. (Intuitively, the cooperator stays silent, while the defector 'rats out'

his partner. If they both rat each other out, they both go to jail.)

C

D

5
,
5

D
5
,−
5
−
3
,−
3

It is easy to see that defecting dominates cooperating: no matter what

the other player does, a player is better off defecting than cooperating.

Thus, 'rational' players should defect. And, indeed, (
D, D
) is the only Nash

equilibrium of this game. Although (
C, C
) gives both players a better payoff

than (
D, D
), this is not an equilibrium.

Now consider the finitely repeated prisoner's dilemma (FRPD), where

the prisoner's dilemma is played for some fixed number
N
of rounds. The

C

3
,
3

−

Search Nedrilad ::

Custom Search