Game Development Reference
In-Depth Information
factor (or, equivalently, taking δ = 1) if we assume that the cost of memory
increases unboundedly with N .)
Note that even if only one player is charged for memory, and memory is
free for the other player, then there is a Nash equilibrium where the bounded
player plays tit for tat, while the other player plays the best response of
cooperating up to (but not including) the last round of the game, and then
defecting in the last round.
Although with standard games there is always a Nash equilibrium, this
is not the case when we take computation into account, as the following
example shows.
Example 8.3 Consider roshambo (rock-paper-scissors). We model playing
rock, paper, and scissors as playing 0, 1, and 2, respectively. The payoff to
player 1 of the outcome ( i, j )is1if i = j ⊕ 1 (where denotes addition mod
3), 1if j = i⊕ 1, and 0 if i = j . Player 2's playoffs are the negative of those
of player 1; the game is a zero-sum game. As is well known, the unique Nash
equilibrium of this game has the players randomising uniformly between 0,
1, and 2.
Now consider a computational version of roshambo. Suppose that we take
the complexity of a deterministic strategy to be 1, and the complexity of a
strategy that uses randomisation to be 2, and take player i 's utility to be his
payoff in the underlying game minus the complexity of his strategy. Intuitively,
programs involving randomisation are more complicated than those that do
not randomise. With this utility function, it is easy to see that there is no
Nash equilibrium. For suppose that ( M 1 ,M 2 ) is an equilibrium. If M 1 uses
randomisation, then 1 can do better by playing the deterministic strategy j
1,
where j is the action that gets the highest probability according to M 2 (or
one of them in the case of ties). Similarly, M 2 cannot use randomisation. But,
as mentioned above, there is no equilibrium for roshambo with deterministic
strategies.
In practice, people do not play the (unique) Nash equilibrium (which
randomises uniformly among rock, paper, and scissors). It is well known that
people have di culty simulating randomisation; we can think of the cost for
randomising as capturing this di culty. Interestingly, there are roshambo
tournaments (indeed, even a Rock Paper Scissors World Championship -
see http://www.worldrps.com ), and topics written on roshambo strategies
[Walker and Walker, 2004]. Championship players are clearly not randomising
uniformly (they could not hope to get a higher payoff than an opponent
by randomising). The computational framework provides a psychologically
plausible account of this lack of randomisation.