Game Development Reference
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.)
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
3 , 3