Prisoners dilemma/Axelrod experiments etc.

[Subbarao Kambhampati <rao@asu.edu>]

Here is a popular book on game theory

http://www.amazon.com/exec/obidos/tg/detail/-/038541580X/002-8295522-5043245?v=glance


This book talks about the scene in Rand Corporation (Santa Monica;
CA) during cold war era, when much of the work 
got started (and of course, if you saw Beautiful Mind or read the book by
Sylvia Nassar, you know about Nash's own work,
that happened right after this).

Most of the interesting games for Rand Corporation of course were of
"imperfect information" variety (which we unfortunately
don't
much cover in this class). The classic example of
such games is prisoners dilemma--where two prisoners, who committed a
robbery together, are kept in two different cells and in-communicado, are
offered a deal to 
confess. If neither suspect confesses, they go free, and
split the proceeds of their crime say 5 units of utility for each
suspect. However, if one prisoner confesses and the other does not, the
prisoner who confesses testifies against the other in exchange for going
free and gets the entire 10 units of utility, while the prisoner who did
not confess goes to prison and gets nothing. If both prisoners confess,
then both are given a reduced term, but both are convicted, which we
represent by giving each 1 unit of utility: better than having the other
prisoner confess, but not so good as going free. The question is what is
the best strategy for each prisoner in such games?

If prisoners dilemma is played only once, the best strategy is for each
prisoner to confess (because if you don't and the other one does, you
have a big downside--you get stuck in the prison; while if you do, then
you have a potentially big upside). This despite the fact that globally,
the better optimum is for both players to cooperate and  not to
confess (but lack of communication disallows each player from trusting
the other).

This is interesting because many socially better policies--such as
building a bridge, making better schools etc, are globally better for all
agents. But for individual agents, it is better not to pay. This brings
up the issue as to how cooperatiive behavior among non-communicating
agents evolves at all. The point is that although prisoners dilemma
played once 
encourages each player to defect (i.e., confess), iterated prisoners
dilemma (i.e. those where the same game is played between the same set of
agents over and over) 
encourages cooperation. Iterated prisoners dilemmas have a very important
place in understanding how the so called "social virtues" such
as honesty and cooperation evolved. For a fascinating discussion on this,
see: 

http://www.amazon.com/exec/obidos/tg/detail/-/0140264450/002-8295522-5043245?v=glance

(An interesting issue regarding iterated prisoners dilemma game is what
should the strategy for a player be? 1. Should they always cooperate? 2.
Should they always defect? 3. Should they start by cooperating, and
defect when the other player defects? 4. Should they start by cooperating
and forgive a bit when the other player defects before defecting
themselves? 5. Should they use some fiendishly more complex strategy?

In late 70's a political scientist called Robert Axelrod conducted a
tournament 
(http://www.classes.cs.uchicago.edu/classes/archive/1998/fall/CS105/Project/node4.html)
among computer players using different strategies. A player using the
strategy is subjected to a variety of other players using different
strategies. 
He found that 3 (called tit-for-tat) and 4 (called forgiving tit-for-tat)
do the best (in terms of amassing utilities). None of the fiendishly
complicated strategies did
appreciably better than 3 and 4. 
The advantage of 4 over 3 is that the tit-for-tat strategy can lead to
endless recriminations (think the mideast situation). 

Matt Riddley talks about the evolutionary implications of this insight..


Rao


ps: Here is a story my grandmother used to tell us. Once a king decided
that he wants to make some large quantity of milk-based sweets. So,
he  puts out 
     a large container outside the castle and asks
all his humble subjects to come and pour a liter of fresh milk each into
the container (see the subjects have cows, and the
     king has subjects...)  He also tells people
not to 
     pour diluted milk because he needs high quality
milk for his sweets. After a couple of hours, when everyone has had a
chance to pour their share into the
     container, the king goes and brings the
container in, and finds it full of..... water.....