[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Prisoners dilemma/Axelrod experiments etc.




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.....