Game Development Reference
In-Depth Information
have already seen, in Example 8.2, one approach to explaining cooperation,
in terms of memory costs. Here is another in terms of regret.
Suppose that prisoner's dilemma is played for N rounds. There are 2 2 N 1
pure strategies for each player in N -round FRPD; computing the regret of
each one can be rather complicated. Thus, when using regret, it is reasonable
for the players to focus on a much more limited set of strategies. Suppose that
each player believes that the other player is using a strategy where he plays
tit for tat for some number k of rounds, and then defects from then on. Call
this strategy s k . (So, in particular, s 0 is the strategy of always defecting and
s N is tit for tat.) A straightforward argument shows that if a player believes
that the other player is playing a strategy of the form s k for some k with
0 ≤ k ≤ N , then the strategy that minimises player 1's regret is either s N− 1 ,
s 1 ,or s 0 ; see [Halpern and Pass, 2009] for details. Moreover, for su ciently
large N (it turns out that N> (( u 3 + u 2 − u 1 ) / ( u 2 − u 1 )) + 1 su ces), the
strategy that minimises regret is s N− 1 . Thus, if each player believes that
the other player is playing a strategy of the form s k - a reasonable set of
strategies to consider - then we get a strategy that looks much more like
what people do in practice.
8.6 Conclusions
As I mentioned earlier, economists have considered quite a few alternatives to
Nash equilibrium, including -Nash equilibrium, subgame perfect equilibrium,
sequential equilibrium, rationalizability, and many other notions [Osborne
and Rubinstein, 1994]. But none of these directly addresses the concerns that
I have addressed here: fault tolerance, computation, lack of awareness, and
lack of knowledge of other players' strategies. The results and approaches
of this chapter are are clearly only first steps. Here are some directions
for further research (some of which I am currently engaged in with my
collaborators):
While ( k, t )-robust equilibrium does seem to be a reasonable way of cap-
turing some aspects of robustness, for some applications, it does not go
far enough. I said earlier that in economics, all players were assumed to
be strategic, or 'rational'; in distributed computing, all players were either
'good' (and followed the recommended protocol) or 'bad' (in which case
they could be arbitrarily malicious). Immunity takes into account the
bad players. The definition of immunity requires that the rational players
are not hurt no matter what the 'bad' players do. But this may be too
strong. As Ayer et al. [2005] point out, it is reasonable to expect a certain
Search Nedrilad ::




Custom Search