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.

⊕

Search Nedrilad ::

Custom Search