Simulace.info - User contributions [en]

Prisoner's dilemma

2012-06-18T14:43:42Z

Maja: /* Reference */

=Introduction=

In this chapter we will try to explain the essence of such problem as ''“prisoner’s dilemma”''. For a start, let’s have a look at the definition of this concept that classical science presents.

'''PRISONER’S DILEMMA''' is a fundamental problem in [http://plato.stanford.edu/entries/game-theory/ game theory], under which [http://plato.stanford.edu/entries/game-theory/#Games players] will not always cooperate with each other, even if it is in their interest. The theoretical idea which is reflected in this model sounds like this – ''self-interest may interfere with the achievement of the collective goal''. This collective goal is considered to be of his own interests by each individual included into this game. This model is being widely used in many modern works on the theory of ethics and social theory, mainly in the consideration of situations with a contradiction between individual and common interests. But for the start we will consider this dilemma in terms of game theory. This model also assumes that the player ''(“prisoner”)'' maximizes his own gain, without caring about the benefit of others. We will also take a look at the variant with altruistic players later in this chapter. [http://dic.academic.ru/dic.nsf/econ_dict/20858]

[[File:Iothers.png‎]]

Let’s see who the players are and what the game itself in this case is. The game refers to the process, which involves two or more parties fighting for the their interests. Each party has its own goal and uses some strategy that can lead to a gain or loss - depending on the behavior of other players. Accordingly, players are some [http://plato.stanford.edu/entries/game-theory/#Util rational individuals] who have an interest in the outcome of the game and opportunities to influence it. Simply put, players can play. Rationality of a player in this definition means that he has a coherent system of preferences in the outcome of the game and it is constant during the whole game. He chooses his actions in order to achieve the best outrome from the standpoint of the system, and for that he is using all the information at his disposal. Simply put, '''a player wants to win'''. Or, if it is not possible to win, to '''at least minimize his loss''' ''(which also means winning in some way)''.

=Prisoner’s dilemma – who is who?=

Now that we understand the basic concepts, let us return to the prisoner’s dilemma itself. A quick historical note, just for your information. The essence of the problem was formulated by two american mathematicians, not prosecutors and investigators – [http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Merrill-M.-Flood Merrill Flood] and [http://www.rand.org/pubs/authors/d/dresher_melvin.html Melvin Dresher] in 1950. They formulated this dilemma and it was used by [http://www.rand.org/about.html RAND Corporation] in the development strategies of nuclear confrontation. The name of the dilemma was given by american mathematician [http://www.nytimes.com/1995/01/27/obituaries/albert-w-tucker-89-pioneering-mathematician.html Albert Tucker].

[[File:Betrayal-cooperation.png‎|400px]]

Betrayal strictly dominates cooperation in the prisoner’s dilemma, so the only possible equilibrium is a betrayal of both players. Simply put, '''no matter what the other player will do, everyone will benefit more of betrayal'''. Because in any situation betraying is more profitable than cooperation, all [http://en.wikipedia.org/wiki/Perfect_rationality rational players] will choose first variant.

Behaving rationally individually, together participants will come to a waste solution: ''if both betray each other, in total they will receive a smaller gain than if they had cooperated''. Here lies the dilemma. In other words, this concept shows us how it is more profitable to achieve the mutually obligatory agreement.

==Formal definition of the prisoner’s dilemma==

'''PRISONER’S DILEMMA''' is best known example of a [http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html nonzero-sum game] where the «best» decision remains ambivalent. The theory of a nonzero-sum games distinguishes between [http://en.wikipedia.org/wiki/Cooperative_game cooperative] and [http://en.wikipedia.org/wiki/Non-cooperative_game noncooperative games]. In a cooperative game, players can make agreements to choose strategies jointly. In noncooperative games they cannot do so.

'''PRISONER’S DILEMMA''' is, by definition, a noncooperative game. If it were a cooperative game, the dilemma, it is argued, would disappear, because then the prisoners could make a pact not to confess, a pack from which each would derive a benefit.

It is clear, however, that if the pact is not enforceable, a new dilemma arises. For now each of the prisoners faces a decision of keeping the pact or breaking it. This choice induces another game exactly like prisoner’s dilemma, because it is in the interest of each to break the pact regardless of whether the other keeps it.

In this game the rational choice of strategy by both players leads to an outcome which is worse for both players than if they had chosen their strategies ''"irrationally"''. The paradox remains unresolved as long as we insist on adhering to the concept of rationaloty which makes perfect sense in zero-sum games but which makes questionable sense in nonzero-sum games. Thus the paradox forces a reexamination of our concept of rational decision. Herein lies a potential contribution by game theory to psychology and to behavioral science in general. [http://www.press.umich.edu/titleDetailLookInside.do?id=20269]

==Basic concept==

Let us now take a look at the classical concept of the prisoner’s dilemma. The legend says that once upon a time there were two criminals, Alfred '''(A)''' and Benjamin '''(B)''', who were caught for stealing two cars. They stole it separately from each other, but police suspected that our A and B acted together, as a band. This was only a speculation, sadly police had no evidence.

Police offered a deal to each one of the criminals: tell the truth about his companion and buy himself a freedom, while his companion will be sentenced to 10 years of prison. If the criminal refuses to testify, he gets 6 months in jail for refusing to cooperate with the investigation. If both testify against each other, both get 2 years in prison.

Criminals are isolated from each other and can not communicate. Their main interest is to reduce their own stay in jail as much as possible. What decision should take each of them: to make a deal with the investigation or to remain silent? Before you look for a solution in this chapter, try to imagine yourself in situation like this and decide what you would do and why? And then try to compare your answer with what science think of it:)

Unable to communicate with each other, criminals have to give each other away. After all, in fact, there are only four possible options:

[[File:Scheme.png|500px‎]]

If suspects are not allowed to talk, they do not know what the other one will do. In this situation, if A remains silent, he is dependent on B’s desicion and will ether sentenced for 10 years or 6 months. If A will testify against B, then as a result A will get 2 years in prison or will be released [http://www.apn.ru/publications/article19740.htm].

Thus, it would be better for each of the suspects to testify against each other, so that they will not to be condemned for 10 years. But if A and B have had the opportunity to communicate, then, of course, the best solution for each of them would be not make a deal with the investigation and get only 6 months in prison. This little problem illustrates that sometimes, acting solely in your personal interests will not always lead to the best results for others and for yourself. By acting for themselves, both prisoners went to jail for 2 years, when in fact they could do with only a half-year of imprisonment.

==Game balance==

Each prisoner can accurately predict his win in each of the four situations. As you know, the balance of the game in game theory is '''[http://en.wikipedia.org/wiki/Nash_equilibrium Nash equilibrium]'''. The prisoner’s dilemma is a game with a special kind of Nash equilibrium – '''[http://tuvalu.santafe.edu/~jkchoi/game4.pdf dominant strategy equilibrium]'''. But before we get to the dominant strategy equilibrium, let’s briefly review what is a normal Nash equilibrium.

'''NASH EQUILIBRIUM''' is the type of game solution of 2 or more players, in which neither party can increase their gain by changing his decision unilaterally while other members do not change their decisions. Accordingly, such a set of strategies chosen by participants and their winnings is called a Nash equilibrium. In other words, everything depends not only on you. [http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html]

But let us return to our problem. So, we still have 2 prisoners, sitting in 2 different cells without the possibility to agree on what to do next. And there are 4 possible variants of the outcome.
Remember, you had put yourself in the shoes of one of them? Let us repeat the experience, and thinking only rationally, try to make a decision. If we are afraid, we are more likely to think only about ourselves. Fear switches on instinct of self-preservation which is often stronger than moral standards and obligations.

Here is an estimated stream of thoughts in this case: ''“If I, Alfred, will remain silent, but Benjamin will tell them everything, then I am going to jail for 10 years. This simply can not happen. If I will tell them everything and he will do so as well, then we both stuck in here for 2 years. Too bad, but still it is better then 10 years. If Benji will remain silent, and I will tell the truth to the police, then he will stay here for 10 years, but I will be free (although I will probably suffer from insomnia caused by my dishonesty). Of course, there is a chance that he will not speak, and if I will do the same, then we both will get only half a year in jail. But again, the risk of getting 10 years in prison is to high. So, I will not keep my mouth shut and will give testimonies on him. It does not matter if he will or will not speak, I will avoid the worst – ten years in prison, and maybe I will even go home tomorrow, if he will be quiet.“''

Acting rationally in their own interest, the participants of this game come to an irrational result: in any case, both will get in jail, the only question is – for how long; but they could get a relatively short imprisonment if they were convinced that the other one will not say anything. The dilemma of ''“keeping silence – testifying”'' is resolved in favor of testimony, although in terms of the collective interest this decision, to put it mildly, is not optimal.

Now let us mentally put ourselves in the policeman shoes. His goal is to knock out the testimony. He can not change human characteristics of suspects, but he can put them in a context in which they will behave in a predictable manner. There are only two leverages in the hands of the police: fear and isolation. And they are more than enough to force the prisoners to act in police interests, rather than their own.

=Extensions of normal model=

==Iterated prisoner’s dilemma==

[[File:Iterated-pd.png|thumb|Iterated prisoner’s dilemma]]

Scenario goes like this: you and your colleague, Lucifer, are in jail and suspected of committing a crime. You are isolated from each other and do not know how the other will respond to questioning. The police invite both of you to implicate the other in the crime ''(defect)''. What happens depends on what both of you do, but neither of you know how the other will respond. If Lucifer betrays you ''(yields to the temptation to defect)'' while you remain silent, then you receive the longest jail term while Lucifer gets off free ''(and visa versa)''. If you both choose to cooperate with each other ''(not the police)'' by remaining silent, there is insufficient evidence to convict both of you, so you are both given a light sentence for a lesser crime. If both of you decide to defect, then you have condemned each other to slightly reduced but still heavy sentences.

The payoff in this game is a reduction in prison sentencing of very good, fairly good, fairly bad or very bad, which is translated into a point score system as is shown at the scheme. [http://www.iterated-prisoners-dilemma.net/]

==Finite Iteration==

[[File:Finite-iteration.png‎‎|thumb|Finite Iteration]]

Many of the situations that are alleged to have the structure of the PD, like defense appropriations of military rivals or price setting for duopolistic firms are better modeled by an iterated version of the game in which players play the PD repeatedly, retaining access at each round to the results of all previous rounds. In these iterated PDs players who defect in one round can be “punished” by defections in subsequent rounds and those who cooperate can be rewarded by cooperation. Thus the appropriate strategy for rationally self-interested players is no longer obvious. The theoretical answer to this question, it turns out, depends strongly on the definition of IPD employed and the knowledge attributed to rational players.

An IPD can be represented in extensive form by a tree diagram like one you can see at the scheme.

There is a significant theoretical difference on this matter between IPDs of fixed, finite length, like the one pictured above, and those of infinite or indefinitely finite length. In practice, there is not a great difference between how people behave in long fixed-length IPDs ''(except in the final few rounds)'' and those of indeterminate length. [http://plato.stanford.edu/entries/prisoner-dilemma/]

==The Centipede and the Finite IPD==

[[File:Centipede-pd.png‎‎|thumb|The Centipede PD with N=4]]

Many of the issues raised by the fixed-length IPD can be raised in even starker form by a somewhat simpler game. Consider a PD in which they punishment payoff is zero. Now iterate the asynchronous version of this game a fixed number times. Imagine that both players are restricted to highly “punitive” strategies according to which, they must always defect against a player who has ever defected. The result is a centipede game.

A stack of N one-dollar bills lies on a table. Players take turns taking money from the stack, one or two bills per turn. The game ends when the stack runs out or one of the players takes two bills ''(whichever comes first)''. Both players keep what they have taken to that point. The extensive form of the game with N=4 can be seen at the picture.

The centipede mainly raises the questions about cooperation and socially desirable altruism as does the PD and it is a favorite tool in empirical investigations of game playing [http://plato.stanford.edu/entries/prisoner-dilemma/]

==Infinite Iteration==

One way to avoid the dubious conclusion of the backward induction argument without delving too deeply into conditions of knowledge and rationality is to consider infinitely repeated PDs. No human agents can actually play an infinitely repeated game, of course, but the infinite IPD has been considered an appropriate way to model a series of interactions in which the participants never have reason to think the current interaction is their last. In this setting a pair of strategies determines an infinite path through of the game tree. If the payoffs of the one-shot game are positive, their total along any such path is infinite. This makes it somewhat awkward to compare strategies. If we confine ourselves to those strategies that can be implemented by mechanical devices ''(with finite memories and speeds of computation)'', however, it turns out that the sequence of payoffs to each player will always, after a finite number of rounds, cycle repeatedly through a particular finite sequence of payoffs. The relative value of such infinite sequences of payoffs can then be identified with the average value of the payoffs in one cycle. This value reflects the limit of average payoff per round as the number of rounds increases. Since there is no last round, it is obvious that backward induction does not apply to the infinite IPD. [http://plato.stanford.edu/entries/prisoner-dilemma/]

==N-player Prisoner’s Dilemma==

In the N-player prisoner’s dilemma multiple agents ''(N ≥ 2)'' interact within their designated group and must choose to cooperate or defect. Any benefit or payoff is received by all participants; any cost is borne by the cooperators only. Hardin describes the N-player prisoner’s dilemma as a «tragedy of the commons» game in which the players are worse off acting according to their self interests than if they were cooperating and coordinating their actions. [http://jp.poerf.de/papers/Rezaei09evolvingcooperation.pdf]

=Other conditions=

Not let us draw out attention to the boundary condition of the prisoner’s dilemma, namely the prison walls, the bars on the windows and a doors with a peepholes. All this indicates, that a person is in trouble already and even if he stands before the choice, the only thing he can do is to continue to lose. The only thing that remains to him is to minimize the inevitable losses.

The strategy of '''“testifying” '''strictly dominates over the strategy of '''“silence”'''. Similarly, another prisoner will come to the same conclusion. It is evident, that common interest of both prisoners is to work together, to keep silent and get only half of the year in jail. But prisoners are not able to cooperate in taking decisions. In other words, they do not have the opportunity to jointly implement their common interest. So each one of them begins to assert his personal interest, which does not lead to the best result.

But imagine that prisoners have the opportunity to discuss this situation. About what would they want to negotiate? Of course about common silence; as we see from the scheme above – it is the most painless variant for both of them as a group. However, each prisoner, after making sure that the other is convinced of the necessity and reasonableness of making a confession, will not confess himself, because he wants to be released. The fact that each of the prisoners, realizing how coordination of their tactics is mutually beneficial, will be in a better position while playing for himself. In that case he will be released.

As the analysis of options shows, the prisoners can not cooperate, because each of them has a personal interest. It is assumed that in this dilemma each of the prisoners acts according to the number of years he will be held in prison. But let’s imagine that our criminals are not selfish but altruistic, and each one also takes others’ interests into consideration. Then confession of the crime is the neccesary dominant strategy.

This dilemma represents a certain type of situations in which:
* there is a need to make an individual decision on the strategy of behavior in the context of common activity
* a separate participant of this situation is interested in the pursuit of general interest only when this general interest is being pursued by all participants
* because individual interests of participants in this situation as objectively separated individuals are different, in case of ignorance about the intentions of the other participant, each of them is forced to trying to achieve his private interest.

=Real life examples=

Now that we had more or less figured out what exactly the prisoner’s dilemma is, let’s see where in real life it is being used and how it helps to solve real-life conflict situations. Among the reasons of enormous popularity of prisoner’s dilemma let’s allocate one: it describes the choice that confronts us every day throughout our lives. It’s a choice between solidarity with other people and ou personal interests.

Many situations in the society are characterized by similar divergence between the decisions dictated by the individual and collective rationality. Famous examples are price wars and the arms race. In the context of the “prisoner’s dilemma” rejection should be considered as a cooperative strategy'' (of course with a partner and not with the authorities)'', and confession – non-cooperative or “cheating.”

==Prisoner’s dilemma in Eurozone==

Current situation with investors who run away from Greece illustrates the dilemma very well. In economic theory this is called a “coordination trap” or [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.176.6993 inefficient stable equilibrium]. It is the same balance as in our dilemma the silence and cooperation among the prisoners.

Exactly the same happenes in the eurozone. The tragedy of the situation in which Greece has a huge burden of debt in the absence of adequate tax revenues due to economic crisis, makes the market ''“pledge to each other”''. Noone believes in a ''“happy-end”'' and if you are too slow to react and lay someone down, then you will be layed down yourself. Default seems imminent, and investors want to get rid of the Greek bonds, while their price has not dropped completely, or, even worse, they all turned out to be worthless. Naturally, the new loan that Greece needs so desperately, can be forgetten.

The darkest result of all this might be the country default and rapid erosion of capital in European banks. This will lead to ceasing of lending and the subsequent closing of credit lines in U.S. banks. It will all be accompanied by a collapse in energy prices and the actual stopping of the world economy, as it happened in 2008.

There is an exit out of this situation – only a consistent and aggressive actions of central banks and governments of all countries that could convince investors on the market that the ''“laying each other down”'' is not necessary: there will be no default. In fact, this is our situation with the silent prisoners.

==Prisoner’s dilemma in price formation proces==

There are also many situations in pricing, when in process of creating price a certain group of companies face the prisoner’s dilemma. Often, one company may perceive the possibility of increasing their profits by reducing price for their goods or services. It does price lowering without paying attention to the pricing of its competitors. Simultaneously, its competitors can come to the same conclusioncan. Which means they really could make more money by cutting prices, not minding the actions of the first company. However, if the company and its competitors cut prices – that is, if all parties act in accordance with their own interests unilaterally – in many cases they all may come to a disadvantage in the end. The task of the industry in such situations is to keep prices high, despite the fact that each company would get some benefits from price reduction [http://bizkiev.com/content/view/822/205/].

==Authority and prisoner’s dilemma==

Finally, let’s take a look at an example of prisoner’s dilemma within the confines of an authoritarian society. It is enough to imagine any community under the rule of the authoritarian regime. It can be an Arab Spring or post-Soviet society. Since the Arab Spring happened recently, we can not analyze these events properly yet.That is why let’s try to understand what exactly happened after the collapse of the Soviet Union. Fear of approaching poverty and hunger, multiplied by the isolation caused by the destruction of the usual rules of social life and lack of time, immediately gave the results. Multi-million society, which lived in the Soviet solidarity just yesterday, made fast transition to the state of hyper-individualism – unfortunately, such is the power of fear.

In a society, which is built on fear of losing what you have, solidarity in most cases is impossible. The very formulation of the problem as minimizing the loss shapes events in a very certain way. The condition of minimization of losses and the role of a police officer are not discussed in the theoretical model of the prisoner’s dilemma. However, they are the most important feature of the prisoner’s dilemma in its application to real life. So, this game describes the condition of any human cooperation and solidarity. We call this condition: co-operation and solidarity should bring benefits to every member of the group, in which it occurs.

Probably it is not even worth writing about how effectively the model drives society into primitivism and regression. Finally, a few words about how choices in life expand, once you start to look at other people not only in the framework of prisoner’s dilemma, but also considering the option of group redistribution. A person, who sees the world in the light of group redistribution conquers fear. Hypothetical policeman no longer has control over him, because a prisoner is not alone – whole group covers his back. His power increases in proportion to the size and cohesion of this group. In addition, he starts to feel the taste of life, because now he can not only lose, but also win.

=Conclusion=

==Game theory in games==

Finally, more interactive example of prisoner’s dilemma in real life is a British game show '''[http://www.goldenballstvshow.com/ “Golden Balls”]'''. You can can check it out on YouTube, but let us take a look at the rules. There are two players, who play a game very similar to out prisoner’s dilemma and the prize is 100,000 pounds. Each of the players can choose either to split or steal. If both players split, then each one gets 50,000 pounds. If one player splits and the other steals, the person who split gets 100,000 and the other person gets 0. And finally, if both of them steal, then they both get 0. But the main difference is that before they start making their decisions, playes can talk for a few minutes and presumably convince the other person that they plan to split. Try to watch couple of episodes of this game and understand, what will be the best strategy to win. Then imagine that you play with a total stranger and then with someone you know. And then that you play one time or there are more games in one set [http://gametheoryinpractice.blogspot.com/2009/08/split-or-steal.html].

You can also try out an online version of this model to better understand the whole concept '''[http://serendip.brynmawr.edu/bb/pd.html Serendip’s Exchange: You Have Found The Prisoners’ Dilemma]'''.

Hopefully, the problematic of this model is now more clear to you and you can use it not only in theory, but also to solve real problems and tasks. Good luck!

=Exercises=

To be sure that you understood this chapter, try to figure out solutions for following examples.

==1. “Perestroika anecdote”==

There used to be a so-called story during Perestroika years. Two businessmen agreed, that one will sell another a truck full of tomatoes. They sign a contract. And only after that the first one goes to look for tomatoes, and the second one – for money.

As you can see, it is a classic example of the prisoner’s dilemma. The agreement was signed, but what if the first will find the tomatoes and the other one will not find the money or vice versa? Try to answer following questions:
* ''Should you trust your business partner in situation like this?''
* ''How far should your trust go?''
* ''Would it be better for non-tomato businessman to stop looking for money, let that simpleton be with his tomatoes. But what reputation will it bring, will there be anyone willing to deal with him in the future?''

==2. “TV Arms Race“==

Two large competiting companies need to determine their budgets on TV advertising for next year. As you can imagine, TV advertising is a very expensive toy. Therefore: more advertising –> lower the income –> lower the quality of goods'' (for ex., they will save money on the product formula)''. But if a competitor will give a lot more advertising than they are, they will lose bigger share of their business. Therefore, both companies have the exact same fear – another one will spend hundreds of millions of dollars per year on advertising.

'''TIP''': As a result, advertising race leads to the fact, that no washing powder washes anymore, soda is impossible to drink and at the end of the year companies are hardly above zero.

=Sources=

1. PRISONER’S DILEMMA. Kafedra jetiki filosofskogo fakul’teta MGU [online]. [cit. 2012-01-19].
Available from: http://www.ethicscenter.ru/en/content/16.htm

2. RAPOPORT, Anatol and Albert M. CHAMMAH. Prisoner’s Dilemma. Michigan: The University of Michigan , Ann Arbor Paperbacks, 2008. ISBN 0-472-06165-8.
Available from: http://www.press.umich.edu/titleDetailLookInside.do?id=20269

3. KRYLOV, Dmitrij. Katalazhka i restoran: kak vyrvat’sja iz dilemmy zakljuchjonnogo: Kak perestat’ byt’ pyl’ju.APN – Agenstvo politicheskih novostej [online]. [cit. 2012-01-19].
Available from: http://www.apn.ru/publications/article19740.htm

4. D. REIBSTEIN, David. Cenoobrazovanie: dilemma zakljuchennogo. BIZKIEV – biznes zhurnal [online]. [cit. 2012-01-19].
Available from: http://bizkiev.com/content/view/822/205/

5. «Dilemma zakljuchennogo»: Matrica vyigrysha. Ravnovesie Njesha. Dominirujuwaja strategija. [online]. [cit. 2012-01-19].
Available from: http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html

6. T., Sam. Split Or Steal. GAME THEORY IN PRACTICE [online]. 21.08.2009 [cit. 2012-01-22].
Available from: http://gametheoryinpractice.blogspot.com/2009/08/split-or-steal.html

7. http://dic.academic.ru/dic.nsf/econ_dict/20858. Jekonomika. Tolkovyj slovar’. — M.: “INFRA-M”, Izdatel’stvo “Ves’ Mir”. Dzh. Bljek. Obwaja redakcija: d.je.n. Osadchaja I.M.. 2000.

8. Serendip’s Exchange: You Have Found The Prisoners’ Dilemma. Serendip’s Exchange [online]. Wednesday, 08-Jun-2005 12:47:31 EDT [cit. 2012-04-07].
Available from: http://serendip.brynmawr.edu/bb/pd.html

9. REZAEI, Golriz, Michael KIRLEY a Jens PFAU. Evolving Cooperation in the N-player Prisoner’s Dilemma: A Social Network Model. Department of Computer Science and Software Engineering The University of Melbourne, Australia, 2010.
Available from: http://jp.poerf.de/papers/Rezaei09evolvingcooperation.pdf. Annual paper.
The University of Melbourne, Australia.

10. KUHN, Steven. Stanford Encyclopedia of Philosophy: Prisoner’s Dilemma. Stanford Encyclopedia of Philosophy [online]. Sep 4, 1997, Mon Oct 22, 2007 [cit. 2012-04-07].
Available from: http://plato.stanford.edu/entries/prisoner-dilemma/

11. WAYNE, Davis. PRISONER’S DILEMMA [online]. March 22nd, 2007 [cit. 2012-04-10].
Available from: http://www.iterated-prisoners-dilemma.net/

=References=

1. http://plato.stanford.edu/entries/game-theory/

2. http://plato.stanford.edu/entries/game-theory/#Games

3. http://plato.stanford.edu/entries/game-theory/#Util

4. http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Merrill-M.-Flood

5. http://www.rand.org/pubs/authors/d/dresher_melvin.html

6. http://www.rand.org/about.html

7. http://www.nytimes.com/1995/01/27/obituaries/albert-w-tucker-89-pioneering-mathematician.html

8. http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html

9. http://www.press.umich.edu/titleDetailLookInside.do?id=20269

10. http://www.apn.ru/publications/article19740.htm

11. http://tuvalu.santafe.edu/~jkchoi/game4.pdf

12. http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html

13. http://www.iterated-prisoners-dilemma.net/

14. http://plato.stanford.edu/entries/prisoner-dilemma/

15. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.176.6993

16. http://bizkiev.com/content/view/822/205/

17. http://www.goldenballstvshow.com/

18. http://serendip.brynmawr.edu/bb/pd.html

=Additional files=

[[media:Prisoner_dilemma_eng.pdf‎|Prisoner's Dilemma chapter]]

Prisoner's dilemma

2012-06-18T14:43:32Z

Maja: /* Reference */

=Introduction=

In this chapter we will try to explain the essence of such problem as ''“prisoner’s dilemma”''. For a start, let’s have a look at the definition of this concept that classical science presents.

'''PRISONER’S DILEMMA''' is a fundamental problem in [http://plato.stanford.edu/entries/game-theory/ game theory], under which [http://plato.stanford.edu/entries/game-theory/#Games players] will not always cooperate with each other, even if it is in their interest. The theoretical idea which is reflected in this model sounds like this – ''self-interest may interfere with the achievement of the collective goal''. This collective goal is considered to be of his own interests by each individual included into this game. This model is being widely used in many modern works on the theory of ethics and social theory, mainly in the consideration of situations with a contradiction between individual and common interests. But for the start we will consider this dilemma in terms of game theory. This model also assumes that the player ''(“prisoner”)'' maximizes his own gain, without caring about the benefit of others. We will also take a look at the variant with altruistic players later in this chapter. [http://dic.academic.ru/dic.nsf/econ_dict/20858]

[[File:Iothers.png‎]]

Let’s see who the players are and what the game itself in this case is. The game refers to the process, which involves two or more parties fighting for the their interests. Each party has its own goal and uses some strategy that can lead to a gain or loss - depending on the behavior of other players. Accordingly, players are some [http://plato.stanford.edu/entries/game-theory/#Util rational individuals] who have an interest in the outcome of the game and opportunities to influence it. Simply put, players can play. Rationality of a player in this definition means that he has a coherent system of preferences in the outcome of the game and it is constant during the whole game. He chooses his actions in order to achieve the best outrome from the standpoint of the system, and for that he is using all the information at his disposal. Simply put, '''a player wants to win'''. Or, if it is not possible to win, to '''at least minimize his loss''' ''(which also means winning in some way)''.

=Prisoner’s dilemma – who is who?=

Now that we understand the basic concepts, let us return to the prisoner’s dilemma itself. A quick historical note, just for your information. The essence of the problem was formulated by two american mathematicians, not prosecutors and investigators – [http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Merrill-M.-Flood Merrill Flood] and [http://www.rand.org/pubs/authors/d/dresher_melvin.html Melvin Dresher] in 1950. They formulated this dilemma and it was used by [http://www.rand.org/about.html RAND Corporation] in the development strategies of nuclear confrontation. The name of the dilemma was given by american mathematician [http://www.nytimes.com/1995/01/27/obituaries/albert-w-tucker-89-pioneering-mathematician.html Albert Tucker].

[[File:Betrayal-cooperation.png‎|400px]]

Betrayal strictly dominates cooperation in the prisoner’s dilemma, so the only possible equilibrium is a betrayal of both players. Simply put, '''no matter what the other player will do, everyone will benefit more of betrayal'''. Because in any situation betraying is more profitable than cooperation, all [http://en.wikipedia.org/wiki/Perfect_rationality rational players] will choose first variant.

Behaving rationally individually, together participants will come to a waste solution: ''if both betray each other, in total they will receive a smaller gain than if they had cooperated''. Here lies the dilemma. In other words, this concept shows us how it is more profitable to achieve the mutually obligatory agreement.

==Formal definition of the prisoner’s dilemma==

'''PRISONER’S DILEMMA''' is best known example of a [http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html nonzero-sum game] where the «best» decision remains ambivalent. The theory of a nonzero-sum games distinguishes between [http://en.wikipedia.org/wiki/Cooperative_game cooperative] and [http://en.wikipedia.org/wiki/Non-cooperative_game noncooperative games]. In a cooperative game, players can make agreements to choose strategies jointly. In noncooperative games they cannot do so.

'''PRISONER’S DILEMMA''' is, by definition, a noncooperative game. If it were a cooperative game, the dilemma, it is argued, would disappear, because then the prisoners could make a pact not to confess, a pack from which each would derive a benefit.

It is clear, however, that if the pact is not enforceable, a new dilemma arises. For now each of the prisoners faces a decision of keeping the pact or breaking it. This choice induces another game exactly like prisoner’s dilemma, because it is in the interest of each to break the pact regardless of whether the other keeps it.

In this game the rational choice of strategy by both players leads to an outcome which is worse for both players than if they had chosen their strategies ''"irrationally"''. The paradox remains unresolved as long as we insist on adhering to the concept of rationaloty which makes perfect sense in zero-sum games but which makes questionable sense in nonzero-sum games. Thus the paradox forces a reexamination of our concept of rational decision. Herein lies a potential contribution by game theory to psychology and to behavioral science in general. [http://www.press.umich.edu/titleDetailLookInside.do?id=20269]

==Basic concept==

Let us now take a look at the classical concept of the prisoner’s dilemma. The legend says that once upon a time there were two criminals, Alfred '''(A)''' and Benjamin '''(B)''', who were caught for stealing two cars. They stole it separately from each other, but police suspected that our A and B acted together, as a band. This was only a speculation, sadly police had no evidence.

Police offered a deal to each one of the criminals: tell the truth about his companion and buy himself a freedom, while his companion will be sentenced to 10 years of prison. If the criminal refuses to testify, he gets 6 months in jail for refusing to cooperate with the investigation. If both testify against each other, both get 2 years in prison.

Criminals are isolated from each other and can not communicate. Their main interest is to reduce their own stay in jail as much as possible. What decision should take each of them: to make a deal with the investigation or to remain silent? Before you look for a solution in this chapter, try to imagine yourself in situation like this and decide what you would do and why? And then try to compare your answer with what science think of it:)

Unable to communicate with each other, criminals have to give each other away. After all, in fact, there are only four possible options:

[[File:Scheme.png|500px‎]]

If suspects are not allowed to talk, they do not know what the other one will do. In this situation, if A remains silent, he is dependent on B’s desicion and will ether sentenced for 10 years or 6 months. If A will testify against B, then as a result A will get 2 years in prison or will be released [http://www.apn.ru/publications/article19740.htm].

Thus, it would be better for each of the suspects to testify against each other, so that they will not to be condemned for 10 years. But if A and B have had the opportunity to communicate, then, of course, the best solution for each of them would be not make a deal with the investigation and get only 6 months in prison. This little problem illustrates that sometimes, acting solely in your personal interests will not always lead to the best results for others and for yourself. By acting for themselves, both prisoners went to jail for 2 years, when in fact they could do with only a half-year of imprisonment.

==Game balance==

Each prisoner can accurately predict his win in each of the four situations. As you know, the balance of the game in game theory is '''[http://en.wikipedia.org/wiki/Nash_equilibrium Nash equilibrium]'''. The prisoner’s dilemma is a game with a special kind of Nash equilibrium – '''[http://tuvalu.santafe.edu/~jkchoi/game4.pdf dominant strategy equilibrium]'''. But before we get to the dominant strategy equilibrium, let’s briefly review what is a normal Nash equilibrium.

'''NASH EQUILIBRIUM''' is the type of game solution of 2 or more players, in which neither party can increase their gain by changing his decision unilaterally while other members do not change their decisions. Accordingly, such a set of strategies chosen by participants and their winnings is called a Nash equilibrium. In other words, everything depends not only on you. [http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html]

But let us return to our problem. So, we still have 2 prisoners, sitting in 2 different cells without the possibility to agree on what to do next. And there are 4 possible variants of the outcome.
Remember, you had put yourself in the shoes of one of them? Let us repeat the experience, and thinking only rationally, try to make a decision. If we are afraid, we are more likely to think only about ourselves. Fear switches on instinct of self-preservation which is often stronger than moral standards and obligations.

Here is an estimated stream of thoughts in this case: ''“If I, Alfred, will remain silent, but Benjamin will tell them everything, then I am going to jail for 10 years. This simply can not happen. If I will tell them everything and he will do so as well, then we both stuck in here for 2 years. Too bad, but still it is better then 10 years. If Benji will remain silent, and I will tell the truth to the police, then he will stay here for 10 years, but I will be free (although I will probably suffer from insomnia caused by my dishonesty). Of course, there is a chance that he will not speak, and if I will do the same, then we both will get only half a year in jail. But again, the risk of getting 10 years in prison is to high. So, I will not keep my mouth shut and will give testimonies on him. It does not matter if he will or will not speak, I will avoid the worst – ten years in prison, and maybe I will even go home tomorrow, if he will be quiet.“''

Acting rationally in their own interest, the participants of this game come to an irrational result: in any case, both will get in jail, the only question is – for how long; but they could get a relatively short imprisonment if they were convinced that the other one will not say anything. The dilemma of ''“keeping silence – testifying”'' is resolved in favor of testimony, although in terms of the collective interest this decision, to put it mildly, is not optimal.

Now let us mentally put ourselves in the policeman shoes. His goal is to knock out the testimony. He can not change human characteristics of suspects, but he can put them in a context in which they will behave in a predictable manner. There are only two leverages in the hands of the police: fear and isolation. And they are more than enough to force the prisoners to act in police interests, rather than their own.

=Extensions of normal model=

==Iterated prisoner’s dilemma==

[[File:Iterated-pd.png|thumb|Iterated prisoner’s dilemma]]

Scenario goes like this: you and your colleague, Lucifer, are in jail and suspected of committing a crime. You are isolated from each other and do not know how the other will respond to questioning. The police invite both of you to implicate the other in the crime ''(defect)''. What happens depends on what both of you do, but neither of you know how the other will respond. If Lucifer betrays you ''(yields to the temptation to defect)'' while you remain silent, then you receive the longest jail term while Lucifer gets off free ''(and visa versa)''. If you both choose to cooperate with each other ''(not the police)'' by remaining silent, there is insufficient evidence to convict both of you, so you are both given a light sentence for a lesser crime. If both of you decide to defect, then you have condemned each other to slightly reduced but still heavy sentences.

The payoff in this game is a reduction in prison sentencing of very good, fairly good, fairly bad or very bad, which is translated into a point score system as is shown at the scheme. [http://www.iterated-prisoners-dilemma.net/]

==Finite Iteration==

[[File:Finite-iteration.png‎‎|thumb|Finite Iteration]]

Many of the situations that are alleged to have the structure of the PD, like defense appropriations of military rivals or price setting for duopolistic firms are better modeled by an iterated version of the game in which players play the PD repeatedly, retaining access at each round to the results of all previous rounds. In these iterated PDs players who defect in one round can be “punished” by defections in subsequent rounds and those who cooperate can be rewarded by cooperation. Thus the appropriate strategy for rationally self-interested players is no longer obvious. The theoretical answer to this question, it turns out, depends strongly on the definition of IPD employed and the knowledge attributed to rational players.

An IPD can be represented in extensive form by a tree diagram like one you can see at the scheme.

There is a significant theoretical difference on this matter between IPDs of fixed, finite length, like the one pictured above, and those of infinite or indefinitely finite length. In practice, there is not a great difference between how people behave in long fixed-length IPDs ''(except in the final few rounds)'' and those of indeterminate length. [http://plato.stanford.edu/entries/prisoner-dilemma/]

==The Centipede and the Finite IPD==

[[File:Centipede-pd.png‎‎|thumb|The Centipede PD with N=4]]

Many of the issues raised by the fixed-length IPD can be raised in even starker form by a somewhat simpler game. Consider a PD in which they punishment payoff is zero. Now iterate the asynchronous version of this game a fixed number times. Imagine that both players are restricted to highly “punitive” strategies according to which, they must always defect against a player who has ever defected. The result is a centipede game.

A stack of N one-dollar bills lies on a table. Players take turns taking money from the stack, one or two bills per turn. The game ends when the stack runs out or one of the players takes two bills ''(whichever comes first)''. Both players keep what they have taken to that point. The extensive form of the game with N=4 can be seen at the picture.

The centipede mainly raises the questions about cooperation and socially desirable altruism as does the PD and it is a favorite tool in empirical investigations of game playing [http://plato.stanford.edu/entries/prisoner-dilemma/]

==Infinite Iteration==

One way to avoid the dubious conclusion of the backward induction argument without delving too deeply into conditions of knowledge and rationality is to consider infinitely repeated PDs. No human agents can actually play an infinitely repeated game, of course, but the infinite IPD has been considered an appropriate way to model a series of interactions in which the participants never have reason to think the current interaction is their last. In this setting a pair of strategies determines an infinite path through of the game tree. If the payoffs of the one-shot game are positive, their total along any such path is infinite. This makes it somewhat awkward to compare strategies. If we confine ourselves to those strategies that can be implemented by mechanical devices ''(with finite memories and speeds of computation)'', however, it turns out that the sequence of payoffs to each player will always, after a finite number of rounds, cycle repeatedly through a particular finite sequence of payoffs. The relative value of such infinite sequences of payoffs can then be identified with the average value of the payoffs in one cycle. This value reflects the limit of average payoff per round as the number of rounds increases. Since there is no last round, it is obvious that backward induction does not apply to the infinite IPD. [http://plato.stanford.edu/entries/prisoner-dilemma/]

==N-player Prisoner’s Dilemma==

In the N-player prisoner’s dilemma multiple agents ''(N ≥ 2)'' interact within their designated group and must choose to cooperate or defect. Any benefit or payoff is received by all participants; any cost is borne by the cooperators only. Hardin describes the N-player prisoner’s dilemma as a «tragedy of the commons» game in which the players are worse off acting according to their self interests than if they were cooperating and coordinating their actions. [http://jp.poerf.de/papers/Rezaei09evolvingcooperation.pdf]

=Other conditions=

Not let us draw out attention to the boundary condition of the prisoner’s dilemma, namely the prison walls, the bars on the windows and a doors with a peepholes. All this indicates, that a person is in trouble already and even if he stands before the choice, the only thing he can do is to continue to lose. The only thing that remains to him is to minimize the inevitable losses.

The strategy of '''“testifying” '''strictly dominates over the strategy of '''“silence”'''. Similarly, another prisoner will come to the same conclusion. It is evident, that common interest of both prisoners is to work together, to keep silent and get only half of the year in jail. But prisoners are not able to cooperate in taking decisions. In other words, they do not have the opportunity to jointly implement their common interest. So each one of them begins to assert his personal interest, which does not lead to the best result.

But imagine that prisoners have the opportunity to discuss this situation. About what would they want to negotiate? Of course about common silence; as we see from the scheme above – it is the most painless variant for both of them as a group. However, each prisoner, after making sure that the other is convinced of the necessity and reasonableness of making a confession, will not confess himself, because he wants to be released. The fact that each of the prisoners, realizing how coordination of their tactics is mutually beneficial, will be in a better position while playing for himself. In that case he will be released.

As the analysis of options shows, the prisoners can not cooperate, because each of them has a personal interest. It is assumed that in this dilemma each of the prisoners acts according to the number of years he will be held in prison. But let’s imagine that our criminals are not selfish but altruistic, and each one also takes others’ interests into consideration. Then confession of the crime is the neccesary dominant strategy.

This dilemma represents a certain type of situations in which:
* there is a need to make an individual decision on the strategy of behavior in the context of common activity
* a separate participant of this situation is interested in the pursuit of general interest only when this general interest is being pursued by all participants
* because individual interests of participants in this situation as objectively separated individuals are different, in case of ignorance about the intentions of the other participant, each of them is forced to trying to achieve his private interest.

=Real life examples=

Now that we had more or less figured out what exactly the prisoner’s dilemma is, let’s see where in real life it is being used and how it helps to solve real-life conflict situations. Among the reasons of enormous popularity of prisoner’s dilemma let’s allocate one: it describes the choice that confronts us every day throughout our lives. It’s a choice between solidarity with other people and ou personal interests.

Many situations in the society are characterized by similar divergence between the decisions dictated by the individual and collective rationality. Famous examples are price wars and the arms race. In the context of the “prisoner’s dilemma” rejection should be considered as a cooperative strategy'' (of course with a partner and not with the authorities)'', and confession – non-cooperative or “cheating.”

==Prisoner’s dilemma in Eurozone==

Current situation with investors who run away from Greece illustrates the dilemma very well. In economic theory this is called a “coordination trap” or [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.176.6993 inefficient stable equilibrium]. It is the same balance as in our dilemma the silence and cooperation among the prisoners.

Exactly the same happenes in the eurozone. The tragedy of the situation in which Greece has a huge burden of debt in the absence of adequate tax revenues due to economic crisis, makes the market ''“pledge to each other”''. Noone believes in a ''“happy-end”'' and if you are too slow to react and lay someone down, then you will be layed down yourself. Default seems imminent, and investors want to get rid of the Greek bonds, while their price has not dropped completely, or, even worse, they all turned out to be worthless. Naturally, the new loan that Greece needs so desperately, can be forgetten.

The darkest result of all this might be the country default and rapid erosion of capital in European banks. This will lead to ceasing of lending and the subsequent closing of credit lines in U.S. banks. It will all be accompanied by a collapse in energy prices and the actual stopping of the world economy, as it happened in 2008.

There is an exit out of this situation – only a consistent and aggressive actions of central banks and governments of all countries that could convince investors on the market that the ''“laying each other down”'' is not necessary: there will be no default. In fact, this is our situation with the silent prisoners.

==Prisoner’s dilemma in price formation proces==

There are also many situations in pricing, when in process of creating price a certain group of companies face the prisoner’s dilemma. Often, one company may perceive the possibility of increasing their profits by reducing price for their goods or services. It does price lowering without paying attention to the pricing of its competitors. Simultaneously, its competitors can come to the same conclusioncan. Which means they really could make more money by cutting prices, not minding the actions of the first company. However, if the company and its competitors cut prices – that is, if all parties act in accordance with their own interests unilaterally – in many cases they all may come to a disadvantage in the end. The task of the industry in such situations is to keep prices high, despite the fact that each company would get some benefits from price reduction [http://bizkiev.com/content/view/822/205/].

==Authority and prisoner’s dilemma==

Finally, let’s take a look at an example of prisoner’s dilemma within the confines of an authoritarian society. It is enough to imagine any community under the rule of the authoritarian regime. It can be an Arab Spring or post-Soviet society. Since the Arab Spring happened recently, we can not analyze these events properly yet.That is why let’s try to understand what exactly happened after the collapse of the Soviet Union. Fear of approaching poverty and hunger, multiplied by the isolation caused by the destruction of the usual rules of social life and lack of time, immediately gave the results. Multi-million society, which lived in the Soviet solidarity just yesterday, made fast transition to the state of hyper-individualism – unfortunately, such is the power of fear.

In a society, which is built on fear of losing what you have, solidarity in most cases is impossible. The very formulation of the problem as minimizing the loss shapes events in a very certain way. The condition of minimization of losses and the role of a police officer are not discussed in the theoretical model of the prisoner’s dilemma. However, they are the most important feature of the prisoner’s dilemma in its application to real life. So, this game describes the condition of any human cooperation and solidarity. We call this condition: co-operation and solidarity should bring benefits to every member of the group, in which it occurs.

Probably it is not even worth writing about how effectively the model drives society into primitivism and regression. Finally, a few words about how choices in life expand, once you start to look at other people not only in the framework of prisoner’s dilemma, but also considering the option of group redistribution. A person, who sees the world in the light of group redistribution conquers fear. Hypothetical policeman no longer has control over him, because a prisoner is not alone – whole group covers his back. His power increases in proportion to the size and cohesion of this group. In addition, he starts to feel the taste of life, because now he can not only lose, but also win.

=Conclusion=

==Game theory in games==

Finally, more interactive example of prisoner’s dilemma in real life is a British game show '''[http://www.goldenballstvshow.com/ “Golden Balls”]'''. You can can check it out on YouTube, but let us take a look at the rules. There are two players, who play a game very similar to out prisoner’s dilemma and the prize is 100,000 pounds. Each of the players can choose either to split or steal. If both players split, then each one gets 50,000 pounds. If one player splits and the other steals, the person who split gets 100,000 and the other person gets 0. And finally, if both of them steal, then they both get 0. But the main difference is that before they start making their decisions, playes can talk for a few minutes and presumably convince the other person that they plan to split. Try to watch couple of episodes of this game and understand, what will be the best strategy to win. Then imagine that you play with a total stranger and then with someone you know. And then that you play one time or there are more games in one set [http://gametheoryinpractice.blogspot.com/2009/08/split-or-steal.html].

You can also try out an online version of this model to better understand the whole concept '''[http://serendip.brynmawr.edu/bb/pd.html Serendip’s Exchange: You Have Found The Prisoners’ Dilemma]'''.

Hopefully, the problematic of this model is now more clear to you and you can use it not only in theory, but also to solve real problems and tasks. Good luck!

=Exercises=

To be sure that you understood this chapter, try to figure out solutions for following examples.

==1. “Perestroika anecdote”==

There used to be a so-called story during Perestroika years. Two businessmen agreed, that one will sell another a truck full of tomatoes. They sign a contract. And only after that the first one goes to look for tomatoes, and the second one – for money.

As you can see, it is a classic example of the prisoner’s dilemma. The agreement was signed, but what if the first will find the tomatoes and the other one will not find the money or vice versa? Try to answer following questions:
* ''Should you trust your business partner in situation like this?''
* ''How far should your trust go?''
* ''Would it be better for non-tomato businessman to stop looking for money, let that simpleton be with his tomatoes. But what reputation will it bring, will there be anyone willing to deal with him in the future?''

==2. “TV Arms Race“==

Two large competiting companies need to determine their budgets on TV advertising for next year. As you can imagine, TV advertising is a very expensive toy. Therefore: more advertising –> lower the income –> lower the quality of goods'' (for ex., they will save money on the product formula)''. But if a competitor will give a lot more advertising than they are, they will lose bigger share of their business. Therefore, both companies have the exact same fear – another one will spend hundreds of millions of dollars per year on advertising.

'''TIP''': As a result, advertising race leads to the fact, that no washing powder washes anymore, soda is impossible to drink and at the end of the year companies are hardly above zero.

=Sources=

1. PRISONER’S DILEMMA. Kafedra jetiki filosofskogo fakul’teta MGU [online]. [cit. 2012-01-19].
Available from: http://www.ethicscenter.ru/en/content/16.htm

2. RAPOPORT, Anatol and Albert M. CHAMMAH. Prisoner’s Dilemma. Michigan: The University of Michigan , Ann Arbor Paperbacks, 2008. ISBN 0-472-06165-8.
Available from: http://www.press.umich.edu/titleDetailLookInside.do?id=20269

3. KRYLOV, Dmitrij. Katalazhka i restoran: kak vyrvat’sja iz dilemmy zakljuchjonnogo: Kak perestat’ byt’ pyl’ju.APN – Agenstvo politicheskih novostej [online]. [cit. 2012-01-19].
Available from: http://www.apn.ru/publications/article19740.htm

4. D. REIBSTEIN, David. Cenoobrazovanie: dilemma zakljuchennogo. BIZKIEV – biznes zhurnal [online]. [cit. 2012-01-19].
Available from: http://bizkiev.com/content/view/822/205/

5. «Dilemma zakljuchennogo»: Matrica vyigrysha. Ravnovesie Njesha. Dominirujuwaja strategija. [online]. [cit. 2012-01-19].
Available from: http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html

6. T., Sam. Split Or Steal. GAME THEORY IN PRACTICE [online]. 21.08.2009 [cit. 2012-01-22].
Available from: http://gametheoryinpractice.blogspot.com/2009/08/split-or-steal.html

7. http://dic.academic.ru/dic.nsf/econ_dict/20858. Jekonomika. Tolkovyj slovar’. — M.: “INFRA-M”, Izdatel’stvo “Ves’ Mir”. Dzh. Bljek. Obwaja redakcija: d.je.n. Osadchaja I.M.. 2000.

8. Serendip’s Exchange: You Have Found The Prisoners’ Dilemma. Serendip’s Exchange [online]. Wednesday, 08-Jun-2005 12:47:31 EDT [cit. 2012-04-07].
Available from: http://serendip.brynmawr.edu/bb/pd.html

9. REZAEI, Golriz, Michael KIRLEY a Jens PFAU. Evolving Cooperation in the N-player Prisoner’s Dilemma: A Social Network Model. Department of Computer Science and Software Engineering The University of Melbourne, Australia, 2010.
Available from: http://jp.poerf.de/papers/Rezaei09evolvingcooperation.pdf. Annual paper.
The University of Melbourne, Australia.

10. KUHN, Steven. Stanford Encyclopedia of Philosophy: Prisoner’s Dilemma. Stanford Encyclopedia of Philosophy [online]. Sep 4, 1997, Mon Oct 22, 2007 [cit. 2012-04-07].
Available from: http://plato.stanford.edu/entries/prisoner-dilemma/

11. WAYNE, Davis. PRISONER’S DILEMMA [online]. March 22nd, 2007 [cit. 2012-04-10].
Available from: http://www.iterated-prisoners-dilemma.net/

=Reference=

1. http://plato.stanford.edu/entries/game-theory/

2. http://plato.stanford.edu/entries/game-theory/#Games

3. http://plato.stanford.edu/entries/game-theory/#Util

4. http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Merrill-M.-Flood

5. http://www.rand.org/pubs/authors/d/dresher_melvin.html

6. http://www.rand.org/about.html

7. http://www.nytimes.com/1995/01/27/obituaries/albert-w-tucker-89-pioneering-mathematician.html

8. http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html

9. http://www.press.umich.edu/titleDetailLookInside.do?id=20269

10. http://www.apn.ru/publications/article19740.htm

11. http://tuvalu.santafe.edu/~jkchoi/game4.pdf

12. http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html

13. http://www.iterated-prisoners-dilemma.net/

14. http://plato.stanford.edu/entries/prisoner-dilemma/

15. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.176.6993

16. http://bizkiev.com/content/view/822/205/

17. http://www.goldenballstvshow.com/

18. http://serendip.brynmawr.edu/bb/pd.html

=Additional files=

[[media:Prisoner_dilemma_eng.pdf‎|Prisoner's Dilemma chapter]]

Prisoner's dilemma

2012-06-18T14:43:23Z

Maja: /* Reference */

=Introduction=

In this chapter we will try to explain the essence of such problem as ''“prisoner’s dilemma”''. For a start, let’s have a look at the definition of this concept that classical science presents.

'''PRISONER’S DILEMMA''' is a fundamental problem in [http://plato.stanford.edu/entries/game-theory/ game theory], under which [http://plato.stanford.edu/entries/game-theory/#Games players] will not always cooperate with each other, even if it is in their interest. The theoretical idea which is reflected in this model sounds like this – ''self-interest may interfere with the achievement of the collective goal''. This collective goal is considered to be of his own interests by each individual included into this game. This model is being widely used in many modern works on the theory of ethics and social theory, mainly in the consideration of situations with a contradiction between individual and common interests. But for the start we will consider this dilemma in terms of game theory. This model also assumes that the player ''(“prisoner”)'' maximizes his own gain, without caring about the benefit of others. We will also take a look at the variant with altruistic players later in this chapter. [http://dic.academic.ru/dic.nsf/econ_dict/20858]

[[File:Iothers.png‎]]

Let’s see who the players are and what the game itself in this case is. The game refers to the process, which involves two or more parties fighting for the their interests. Each party has its own goal and uses some strategy that can lead to a gain or loss - depending on the behavior of other players. Accordingly, players are some [http://plato.stanford.edu/entries/game-theory/#Util rational individuals] who have an interest in the outcome of the game and opportunities to influence it. Simply put, players can play. Rationality of a player in this definition means that he has a coherent system of preferences in the outcome of the game and it is constant during the whole game. He chooses his actions in order to achieve the best outrome from the standpoint of the system, and for that he is using all the information at his disposal. Simply put, '''a player wants to win'''. Or, if it is not possible to win, to '''at least minimize his loss''' ''(which also means winning in some way)''.

=Prisoner’s dilemma – who is who?=

Now that we understand the basic concepts, let us return to the prisoner’s dilemma itself. A quick historical note, just for your information. The essence of the problem was formulated by two american mathematicians, not prosecutors and investigators – [http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Merrill-M.-Flood Merrill Flood] and [http://www.rand.org/pubs/authors/d/dresher_melvin.html Melvin Dresher] in 1950. They formulated this dilemma and it was used by [http://www.rand.org/about.html RAND Corporation] in the development strategies of nuclear confrontation. The name of the dilemma was given by american mathematician [http://www.nytimes.com/1995/01/27/obituaries/albert-w-tucker-89-pioneering-mathematician.html Albert Tucker].

[[File:Betrayal-cooperation.png‎|400px]]

Betrayal strictly dominates cooperation in the prisoner’s dilemma, so the only possible equilibrium is a betrayal of both players. Simply put, '''no matter what the other player will do, everyone will benefit more of betrayal'''. Because in any situation betraying is more profitable than cooperation, all [http://en.wikipedia.org/wiki/Perfect_rationality rational players] will choose first variant.

Behaving rationally individually, together participants will come to a waste solution: ''if both betray each other, in total they will receive a smaller gain than if they had cooperated''. Here lies the dilemma. In other words, this concept shows us how it is more profitable to achieve the mutually obligatory agreement.

==Formal definition of the prisoner’s dilemma==

'''PRISONER’S DILEMMA''' is best known example of a [http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html nonzero-sum game] where the «best» decision remains ambivalent. The theory of a nonzero-sum games distinguishes between [http://en.wikipedia.org/wiki/Cooperative_game cooperative] and [http://en.wikipedia.org/wiki/Non-cooperative_game noncooperative games]. In a cooperative game, players can make agreements to choose strategies jointly. In noncooperative games they cannot do so.

'''PRISONER’S DILEMMA''' is, by definition, a noncooperative game. If it were a cooperative game, the dilemma, it is argued, would disappear, because then the prisoners could make a pact not to confess, a pack from which each would derive a benefit.

It is clear, however, that if the pact is not enforceable, a new dilemma arises. For now each of the prisoners faces a decision of keeping the pact or breaking it. This choice induces another game exactly like prisoner’s dilemma, because it is in the interest of each to break the pact regardless of whether the other keeps it.

In this game the rational choice of strategy by both players leads to an outcome which is worse for both players than if they had chosen their strategies ''"irrationally"''. The paradox remains unresolved as long as we insist on adhering to the concept of rationaloty which makes perfect sense in zero-sum games but which makes questionable sense in nonzero-sum games. Thus the paradox forces a reexamination of our concept of rational decision. Herein lies a potential contribution by game theory to psychology and to behavioral science in general. [http://www.press.umich.edu/titleDetailLookInside.do?id=20269]

==Basic concept==

Let us now take a look at the classical concept of the prisoner’s dilemma. The legend says that once upon a time there were two criminals, Alfred '''(A)''' and Benjamin '''(B)''', who were caught for stealing two cars. They stole it separately from each other, but police suspected that our A and B acted together, as a band. This was only a speculation, sadly police had no evidence.

Police offered a deal to each one of the criminals: tell the truth about his companion and buy himself a freedom, while his companion will be sentenced to 10 years of prison. If the criminal refuses to testify, he gets 6 months in jail for refusing to cooperate with the investigation. If both testify against each other, both get 2 years in prison.

Criminals are isolated from each other and can not communicate. Their main interest is to reduce their own stay in jail as much as possible. What decision should take each of them: to make a deal with the investigation or to remain silent? Before you look for a solution in this chapter, try to imagine yourself in situation like this and decide what you would do and why? And then try to compare your answer with what science think of it:)

Unable to communicate with each other, criminals have to give each other away. After all, in fact, there are only four possible options:

[[File:Scheme.png|500px‎]]

If suspects are not allowed to talk, they do not know what the other one will do. In this situation, if A remains silent, he is dependent on B’s desicion and will ether sentenced for 10 years or 6 months. If A will testify against B, then as a result A will get 2 years in prison or will be released [http://www.apn.ru/publications/article19740.htm].

Thus, it would be better for each of the suspects to testify against each other, so that they will not to be condemned for 10 years. But if A and B have had the opportunity to communicate, then, of course, the best solution for each of them would be not make a deal with the investigation and get only 6 months in prison. This little problem illustrates that sometimes, acting solely in your personal interests will not always lead to the best results for others and for yourself. By acting for themselves, both prisoners went to jail for 2 years, when in fact they could do with only a half-year of imprisonment.

==Game balance==

Each prisoner can accurately predict his win in each of the four situations. As you know, the balance of the game in game theory is '''[http://en.wikipedia.org/wiki/Nash_equilibrium Nash equilibrium]'''. The prisoner’s dilemma is a game with a special kind of Nash equilibrium – '''[http://tuvalu.santafe.edu/~jkchoi/game4.pdf dominant strategy equilibrium]'''. But before we get to the dominant strategy equilibrium, let’s briefly review what is a normal Nash equilibrium.

'''NASH EQUILIBRIUM''' is the type of game solution of 2 or more players, in which neither party can increase their gain by changing his decision unilaterally while other members do not change their decisions. Accordingly, such a set of strategies chosen by participants and their winnings is called a Nash equilibrium. In other words, everything depends not only on you. [http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html]

But let us return to our problem. So, we still have 2 prisoners, sitting in 2 different cells without the possibility to agree on what to do next. And there are 4 possible variants of the outcome.
Remember, you had put yourself in the shoes of one of them? Let us repeat the experience, and thinking only rationally, try to make a decision. If we are afraid, we are more likely to think only about ourselves. Fear switches on instinct of self-preservation which is often stronger than moral standards and obligations.

Here is an estimated stream of thoughts in this case: ''“If I, Alfred, will remain silent, but Benjamin will tell them everything, then I am going to jail for 10 years. This simply can not happen. If I will tell them everything and he will do so as well, then we both stuck in here for 2 years. Too bad, but still it is better then 10 years. If Benji will remain silent, and I will tell the truth to the police, then he will stay here for 10 years, but I will be free (although I will probably suffer from insomnia caused by my dishonesty). Of course, there is a chance that he will not speak, and if I will do the same, then we both will get only half a year in jail. But again, the risk of getting 10 years in prison is to high. So, I will not keep my mouth shut and will give testimonies on him. It does not matter if he will or will not speak, I will avoid the worst – ten years in prison, and maybe I will even go home tomorrow, if he will be quiet.“''

Acting rationally in their own interest, the participants of this game come to an irrational result: in any case, both will get in jail, the only question is – for how long; but they could get a relatively short imprisonment if they were convinced that the other one will not say anything. The dilemma of ''“keeping silence – testifying”'' is resolved in favor of testimony, although in terms of the collective interest this decision, to put it mildly, is not optimal.

Now let us mentally put ourselves in the policeman shoes. His goal is to knock out the testimony. He can not change human characteristics of suspects, but he can put them in a context in which they will behave in a predictable manner. There are only two leverages in the hands of the police: fear and isolation. And they are more than enough to force the prisoners to act in police interests, rather than their own.

=Extensions of normal model=

==Iterated prisoner’s dilemma==

[[File:Iterated-pd.png|thumb|Iterated prisoner’s dilemma]]

Scenario goes like this: you and your colleague, Lucifer, are in jail and suspected of committing a crime. You are isolated from each other and do not know how the other will respond to questioning. The police invite both of you to implicate the other in the crime ''(defect)''. What happens depends on what both of you do, but neither of you know how the other will respond. If Lucifer betrays you ''(yields to the temptation to defect)'' while you remain silent, then you receive the longest jail term while Lucifer gets off free ''(and visa versa)''. If you both choose to cooperate with each other ''(not the police)'' by remaining silent, there is insufficient evidence to convict both of you, so you are both given a light sentence for a lesser crime. If both of you decide to defect, then you have condemned each other to slightly reduced but still heavy sentences.

The payoff in this game is a reduction in prison sentencing of very good, fairly good, fairly bad or very bad, which is translated into a point score system as is shown at the scheme. [http://www.iterated-prisoners-dilemma.net/]

==Finite Iteration==

[[File:Finite-iteration.png‎‎|thumb|Finite Iteration]]

Many of the situations that are alleged to have the structure of the PD, like defense appropriations of military rivals or price setting for duopolistic firms are better modeled by an iterated version of the game in which players play the PD repeatedly, retaining access at each round to the results of all previous rounds. In these iterated PDs players who defect in one round can be “punished” by defections in subsequent rounds and those who cooperate can be rewarded by cooperation. Thus the appropriate strategy for rationally self-interested players is no longer obvious. The theoretical answer to this question, it turns out, depends strongly on the definition of IPD employed and the knowledge attributed to rational players.

An IPD can be represented in extensive form by a tree diagram like one you can see at the scheme.

There is a significant theoretical difference on this matter between IPDs of fixed, finite length, like the one pictured above, and those of infinite or indefinitely finite length. In practice, there is not a great difference between how people behave in long fixed-length IPDs ''(except in the final few rounds)'' and those of indeterminate length. [http://plato.stanford.edu/entries/prisoner-dilemma/]

==The Centipede and the Finite IPD==

[[File:Centipede-pd.png‎‎|thumb|The Centipede PD with N=4]]

Many of the issues raised by the fixed-length IPD can be raised in even starker form by a somewhat simpler game. Consider a PD in which they punishment payoff is zero. Now iterate the asynchronous version of this game a fixed number times. Imagine that both players are restricted to highly “punitive” strategies according to which, they must always defect against a player who has ever defected. The result is a centipede game.

A stack of N one-dollar bills lies on a table. Players take turns taking money from the stack, one or two bills per turn. The game ends when the stack runs out or one of the players takes two bills ''(whichever comes first)''. Both players keep what they have taken to that point. The extensive form of the game with N=4 can be seen at the picture.

The centipede mainly raises the questions about cooperation and socially desirable altruism as does the PD and it is a favorite tool in empirical investigations of game playing [http://plato.stanford.edu/entries/prisoner-dilemma/]

==Infinite Iteration==

One way to avoid the dubious conclusion of the backward induction argument without delving too deeply into conditions of knowledge and rationality is to consider infinitely repeated PDs. No human agents can actually play an infinitely repeated game, of course, but the infinite IPD has been considered an appropriate way to model a series of interactions in which the participants never have reason to think the current interaction is their last. In this setting a pair of strategies determines an infinite path through of the game tree. If the payoffs of the one-shot game are positive, their total along any such path is infinite. This makes it somewhat awkward to compare strategies. If we confine ourselves to those strategies that can be implemented by mechanical devices ''(with finite memories and speeds of computation)'', however, it turns out that the sequence of payoffs to each player will always, after a finite number of rounds, cycle repeatedly through a particular finite sequence of payoffs. The relative value of such infinite sequences of payoffs can then be identified with the average value of the payoffs in one cycle. This value reflects the limit of average payoff per round as the number of rounds increases. Since there is no last round, it is obvious that backward induction does not apply to the infinite IPD. [http://plato.stanford.edu/entries/prisoner-dilemma/]

==N-player Prisoner’s Dilemma==

In the N-player prisoner’s dilemma multiple agents ''(N ≥ 2)'' interact within their designated group and must choose to cooperate or defect. Any benefit or payoff is received by all participants; any cost is borne by the cooperators only. Hardin describes the N-player prisoner’s dilemma as a «tragedy of the commons» game in which the players are worse off acting according to their self interests than if they were cooperating and coordinating their actions. [http://jp.poerf.de/papers/Rezaei09evolvingcooperation.pdf]

=Other conditions=

Not let us draw out attention to the boundary condition of the prisoner’s dilemma, namely the prison walls, the bars on the windows and a doors with a peepholes. All this indicates, that a person is in trouble already and even if he stands before the choice, the only thing he can do is to continue to lose. The only thing that remains to him is to minimize the inevitable losses.

The strategy of '''“testifying” '''strictly dominates over the strategy of '''“silence”'''. Similarly, another prisoner will come to the same conclusion. It is evident, that common interest of both prisoners is to work together, to keep silent and get only half of the year in jail. But prisoners are not able to cooperate in taking decisions. In other words, they do not have the opportunity to jointly implement their common interest. So each one of them begins to assert his personal interest, which does not lead to the best result.

But imagine that prisoners have the opportunity to discuss this situation. About what would they want to negotiate? Of course about common silence; as we see from the scheme above – it is the most painless variant for both of them as a group. However, each prisoner, after making sure that the other is convinced of the necessity and reasonableness of making a confession, will not confess himself, because he wants to be released. The fact that each of the prisoners, realizing how coordination of their tactics is mutually beneficial, will be in a better position while playing for himself. In that case he will be released.

As the analysis of options shows, the prisoners can not cooperate, because each of them has a personal interest. It is assumed that in this dilemma each of the prisoners acts according to the number of years he will be held in prison. But let’s imagine that our criminals are not selfish but altruistic, and each one also takes others’ interests into consideration. Then confession of the crime is the neccesary dominant strategy.

This dilemma represents a certain type of situations in which:
* there is a need to make an individual decision on the strategy of behavior in the context of common activity
* a separate participant of this situation is interested in the pursuit of general interest only when this general interest is being pursued by all participants
* because individual interests of participants in this situation as objectively separated individuals are different, in case of ignorance about the intentions of the other participant, each of them is forced to trying to achieve his private interest.

=Real life examples=

Now that we had more or less figured out what exactly the prisoner’s dilemma is, let’s see where in real life it is being used and how it helps to solve real-life conflict situations. Among the reasons of enormous popularity of prisoner’s dilemma let’s allocate one: it describes the choice that confronts us every day throughout our lives. It’s a choice between solidarity with other people and ou personal interests.

Many situations in the society are characterized by similar divergence between the decisions dictated by the individual and collective rationality. Famous examples are price wars and the arms race. In the context of the “prisoner’s dilemma” rejection should be considered as a cooperative strategy'' (of course with a partner and not with the authorities)'', and confession – non-cooperative or “cheating.”

==Prisoner’s dilemma in Eurozone==

Current situation with investors who run away from Greece illustrates the dilemma very well. In economic theory this is called a “coordination trap” or [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.176.6993 inefficient stable equilibrium]. It is the same balance as in our dilemma the silence and cooperation among the prisoners.

Exactly the same happenes in the eurozone. The tragedy of the situation in which Greece has a huge burden of debt in the absence of adequate tax revenues due to economic crisis, makes the market ''“pledge to each other”''. Noone believes in a ''“happy-end”'' and if you are too slow to react and lay someone down, then you will be layed down yourself. Default seems imminent, and investors want to get rid of the Greek bonds, while their price has not dropped completely, or, even worse, they all turned out to be worthless. Naturally, the new loan that Greece needs so desperately, can be forgetten.

The darkest result of all this might be the country default and rapid erosion of capital in European banks. This will lead to ceasing of lending and the subsequent closing of credit lines in U.S. banks. It will all be accompanied by a collapse in energy prices and the actual stopping of the world economy, as it happened in 2008.

There is an exit out of this situation – only a consistent and aggressive actions of central banks and governments of all countries that could convince investors on the market that the ''“laying each other down”'' is not necessary: there will be no default. In fact, this is our situation with the silent prisoners.

==Prisoner’s dilemma in price formation proces==

There are also many situations in pricing, when in process of creating price a certain group of companies face the prisoner’s dilemma. Often, one company may perceive the possibility of increasing their profits by reducing price for their goods or services. It does price lowering without paying attention to the pricing of its competitors. Simultaneously, its competitors can come to the same conclusioncan. Which means they really could make more money by cutting prices, not minding the actions of the first company. However, if the company and its competitors cut prices – that is, if all parties act in accordance with their own interests unilaterally – in many cases they all may come to a disadvantage in the end. The task of the industry in such situations is to keep prices high, despite the fact that each company would get some benefits from price reduction [http://bizkiev.com/content/view/822/205/].

==Authority and prisoner’s dilemma==

Finally, let’s take a look at an example of prisoner’s dilemma within the confines of an authoritarian society. It is enough to imagine any community under the rule of the authoritarian regime. It can be an Arab Spring or post-Soviet society. Since the Arab Spring happened recently, we can not analyze these events properly yet.That is why let’s try to understand what exactly happened after the collapse of the Soviet Union. Fear of approaching poverty and hunger, multiplied by the isolation caused by the destruction of the usual rules of social life and lack of time, immediately gave the results. Multi-million society, which lived in the Soviet solidarity just yesterday, made fast transition to the state of hyper-individualism – unfortunately, such is the power of fear.

In a society, which is built on fear of losing what you have, solidarity in most cases is impossible. The very formulation of the problem as minimizing the loss shapes events in a very certain way. The condition of minimization of losses and the role of a police officer are not discussed in the theoretical model of the prisoner’s dilemma. However, they are the most important feature of the prisoner’s dilemma in its application to real life. So, this game describes the condition of any human cooperation and solidarity. We call this condition: co-operation and solidarity should bring benefits to every member of the group, in which it occurs.

Probably it is not even worth writing about how effectively the model drives society into primitivism and regression. Finally, a few words about how choices in life expand, once you start to look at other people not only in the framework of prisoner’s dilemma, but also considering the option of group redistribution. A person, who sees the world in the light of group redistribution conquers fear. Hypothetical policeman no longer has control over him, because a prisoner is not alone – whole group covers his back. His power increases in proportion to the size and cohesion of this group. In addition, he starts to feel the taste of life, because now he can not only lose, but also win.

=Conclusion=

==Game theory in games==

Finally, more interactive example of prisoner’s dilemma in real life is a British game show '''[http://www.goldenballstvshow.com/ “Golden Balls”]'''. You can can check it out on YouTube, but let us take a look at the rules. There are two players, who play a game very similar to out prisoner’s dilemma and the prize is 100,000 pounds. Each of the players can choose either to split or steal. If both players split, then each one gets 50,000 pounds. If one player splits and the other steals, the person who split gets 100,000 and the other person gets 0. And finally, if both of them steal, then they both get 0. But the main difference is that before they start making their decisions, playes can talk for a few minutes and presumably convince the other person that they plan to split. Try to watch couple of episodes of this game and understand, what will be the best strategy to win. Then imagine that you play with a total stranger and then with someone you know. And then that you play one time or there are more games in one set [http://gametheoryinpractice.blogspot.com/2009/08/split-or-steal.html].

You can also try out an online version of this model to better understand the whole concept '''[http://serendip.brynmawr.edu/bb/pd.html Serendip’s Exchange: You Have Found The Prisoners’ Dilemma]'''.

Hopefully, the problematic of this model is now more clear to you and you can use it not only in theory, but also to solve real problems and tasks. Good luck!

=Exercises=

To be sure that you understood this chapter, try to figure out solutions for following examples.

==1. “Perestroika anecdote”==

There used to be a so-called story during Perestroika years. Two businessmen agreed, that one will sell another a truck full of tomatoes. They sign a contract. And only after that the first one goes to look for tomatoes, and the second one – for money.

As you can see, it is a classic example of the prisoner’s dilemma. The agreement was signed, but what if the first will find the tomatoes and the other one will not find the money or vice versa? Try to answer following questions:
* ''Should you trust your business partner in situation like this?''
* ''How far should your trust go?''
* ''Would it be better for non-tomato businessman to stop looking for money, let that simpleton be with his tomatoes. But what reputation will it bring, will there be anyone willing to deal with him in the future?''

==2. “TV Arms Race“==

Two large competiting companies need to determine their budgets on TV advertising for next year. As you can imagine, TV advertising is a very expensive toy. Therefore: more advertising –> lower the income –> lower the quality of goods'' (for ex., they will save money on the product formula)''. But if a competitor will give a lot more advertising than they are, they will lose bigger share of their business. Therefore, both companies have the exact same fear – another one will spend hundreds of millions of dollars per year on advertising.

'''TIP''': As a result, advertising race leads to the fact, that no washing powder washes anymore, soda is impossible to drink and at the end of the year companies are hardly above zero.

=Sources=

1. PRISONER’S DILEMMA. Kafedra jetiki filosofskogo fakul’teta MGU [online]. [cit. 2012-01-19].
Available from: http://www.ethicscenter.ru/en/content/16.htm

2. RAPOPORT, Anatol and Albert M. CHAMMAH. Prisoner’s Dilemma. Michigan: The University of Michigan , Ann Arbor Paperbacks, 2008. ISBN 0-472-06165-8.
Available from: http://www.press.umich.edu/titleDetailLookInside.do?id=20269

3. KRYLOV, Dmitrij. Katalazhka i restoran: kak vyrvat’sja iz dilemmy zakljuchjonnogo: Kak perestat’ byt’ pyl’ju.APN – Agenstvo politicheskih novostej [online]. [cit. 2012-01-19].
Available from: http://www.apn.ru/publications/article19740.htm

4. D. REIBSTEIN, David. Cenoobrazovanie: dilemma zakljuchennogo. BIZKIEV – biznes zhurnal [online]. [cit. 2012-01-19].
Available from: http://bizkiev.com/content/view/822/205/

5. «Dilemma zakljuchennogo»: Matrica vyigrysha. Ravnovesie Njesha. Dominirujuwaja strategija. [online]. [cit. 2012-01-19].
Available from: http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html

6. T., Sam. Split Or Steal. GAME THEORY IN PRACTICE [online]. 21.08.2009 [cit. 2012-01-22].
Available from: http://gametheoryinpractice.blogspot.com/2009/08/split-or-steal.html

7. http://dic.academic.ru/dic.nsf/econ_dict/20858. Jekonomika. Tolkovyj slovar’. — M.: “INFRA-M”, Izdatel’stvo “Ves’ Mir”. Dzh. Bljek. Obwaja redakcija: d.je.n. Osadchaja I.M.. 2000.

8. Serendip’s Exchange: You Have Found The Prisoners’ Dilemma. Serendip’s Exchange [online]. Wednesday, 08-Jun-2005 12:47:31 EDT [cit. 2012-04-07].
Available from: http://serendip.brynmawr.edu/bb/pd.html

9. REZAEI, Golriz, Michael KIRLEY a Jens PFAU. Evolving Cooperation in the N-player Prisoner’s Dilemma: A Social Network Model. Department of Computer Science and Software Engineering The University of Melbourne, Australia, 2010.
Available from: http://jp.poerf.de/papers/Rezaei09evolvingcooperation.pdf. Annual paper.
The University of Melbourne, Australia.

10. KUHN, Steven. Stanford Encyclopedia of Philosophy: Prisoner’s Dilemma. Stanford Encyclopedia of Philosophy [online]. Sep 4, 1997, Mon Oct 22, 2007 [cit. 2012-04-07].
Available from: http://plato.stanford.edu/entries/prisoner-dilemma/

11. WAYNE, Davis. PRISONER’S DILEMMA [online]. March 22nd, 2007 [cit. 2012-04-10].
Available from: http://www.iterated-prisoners-dilemma.net/

=Reference=

1. http://plato.stanford.edu/entries/game-theory/

2. http://plato.stanford.edu/entries/game-theory/#Games

3. http://plato.stanford.edu/entries/game-theory/#Util

4. http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Merrill-M.-Flood

5. http://www.rand.org/pubs/authors/d/dresher_melvin.html

6. http://www.rand.org/about.html

7. http://www.nytimes.com/1995/01/27/obituaries/albert-w-tucker-89-pioneering-mathematician.html

8. http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html

9. http://www.press.umich.edu/titleDetailLookInside.do?id=20269

10. http://www.apn.ru/publications/article19740.htm

11. http://tuvalu.santafe.edu/~jkchoi/game4.pdf

12. http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html

13. http://www.iterated-prisoners-dilemma.net/

14. http://plato.stanford.edu/entries/prisoner-dilemma/

15. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.176.6993

16. http://bizkiev.com/content/view/822/205/

17. http://www.goldenballstvshow.com/

18. http://serendip.brynmawr.edu/bb/pd.html

=Additional files=

[[media:Prisoner_dilemma_eng.pdf‎|Prisoner's Dilemma chapter]]

Prisoner's dilemma

2012-06-18T14:43:01Z

Maja:

=Introduction=

In this chapter we will try to explain the essence of such problem as ''“prisoner’s dilemma”''. For a start, let’s have a look at the definition of this concept that classical science presents.

'''PRISONER’S DILEMMA''' is a fundamental problem in [http://plato.stanford.edu/entries/game-theory/ game theory], under which [http://plato.stanford.edu/entries/game-theory/#Games players] will not always cooperate with each other, even if it is in their interest. The theoretical idea which is reflected in this model sounds like this – ''self-interest may interfere with the achievement of the collective goal''. This collective goal is considered to be of his own interests by each individual included into this game. This model is being widely used in many modern works on the theory of ethics and social theory, mainly in the consideration of situations with a contradiction between individual and common interests. But for the start we will consider this dilemma in terms of game theory. This model also assumes that the player ''(“prisoner”)'' maximizes his own gain, without caring about the benefit of others. We will also take a look at the variant with altruistic players later in this chapter. [http://dic.academic.ru/dic.nsf/econ_dict/20858]

[[File:Iothers.png‎]]

Let’s see who the players are and what the game itself in this case is. The game refers to the process, which involves two or more parties fighting for the their interests. Each party has its own goal and uses some strategy that can lead to a gain or loss - depending on the behavior of other players. Accordingly, players are some [http://plato.stanford.edu/entries/game-theory/#Util rational individuals] who have an interest in the outcome of the game and opportunities to influence it. Simply put, players can play. Rationality of a player in this definition means that he has a coherent system of preferences in the outcome of the game and it is constant during the whole game. He chooses his actions in order to achieve the best outrome from the standpoint of the system, and for that he is using all the information at his disposal. Simply put, '''a player wants to win'''. Or, if it is not possible to win, to '''at least minimize his loss''' ''(which also means winning in some way)''.

=Prisoner’s dilemma – who is who?=

Now that we understand the basic concepts, let us return to the prisoner’s dilemma itself. A quick historical note, just for your information. The essence of the problem was formulated by two american mathematicians, not prosecutors and investigators – [http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Merrill-M.-Flood Merrill Flood] and [http://www.rand.org/pubs/authors/d/dresher_melvin.html Melvin Dresher] in 1950. They formulated this dilemma and it was used by [http://www.rand.org/about.html RAND Corporation] in the development strategies of nuclear confrontation. The name of the dilemma was given by american mathematician [http://www.nytimes.com/1995/01/27/obituaries/albert-w-tucker-89-pioneering-mathematician.html Albert Tucker].

[[File:Betrayal-cooperation.png‎|400px]]

Betrayal strictly dominates cooperation in the prisoner’s dilemma, so the only possible equilibrium is a betrayal of both players. Simply put, '''no matter what the other player will do, everyone will benefit more of betrayal'''. Because in any situation betraying is more profitable than cooperation, all [http://en.wikipedia.org/wiki/Perfect_rationality rational players] will choose first variant.

Behaving rationally individually, together participants will come to a waste solution: ''if both betray each other, in total they will receive a smaller gain than if they had cooperated''. Here lies the dilemma. In other words, this concept shows us how it is more profitable to achieve the mutually obligatory agreement.

==Formal definition of the prisoner’s dilemma==

'''PRISONER’S DILEMMA''' is best known example of a [http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html nonzero-sum game] where the «best» decision remains ambivalent. The theory of a nonzero-sum games distinguishes between [http://en.wikipedia.org/wiki/Cooperative_game cooperative] and [http://en.wikipedia.org/wiki/Non-cooperative_game noncooperative games]. In a cooperative game, players can make agreements to choose strategies jointly. In noncooperative games they cannot do so.

'''PRISONER’S DILEMMA''' is, by definition, a noncooperative game. If it were a cooperative game, the dilemma, it is argued, would disappear, because then the prisoners could make a pact not to confess, a pack from which each would derive a benefit.

It is clear, however, that if the pact is not enforceable, a new dilemma arises. For now each of the prisoners faces a decision of keeping the pact or breaking it. This choice induces another game exactly like prisoner’s dilemma, because it is in the interest of each to break the pact regardless of whether the other keeps it.

In this game the rational choice of strategy by both players leads to an outcome which is worse for both players than if they had chosen their strategies ''"irrationally"''. The paradox remains unresolved as long as we insist on adhering to the concept of rationaloty which makes perfect sense in zero-sum games but which makes questionable sense in nonzero-sum games. Thus the paradox forces a reexamination of our concept of rational decision. Herein lies a potential contribution by game theory to psychology and to behavioral science in general. [http://www.press.umich.edu/titleDetailLookInside.do?id=20269]

==Basic concept==

Let us now take a look at the classical concept of the prisoner’s dilemma. The legend says that once upon a time there were two criminals, Alfred '''(A)''' and Benjamin '''(B)''', who were caught for stealing two cars. They stole it separately from each other, but police suspected that our A and B acted together, as a band. This was only a speculation, sadly police had no evidence.

Police offered a deal to each one of the criminals: tell the truth about his companion and buy himself a freedom, while his companion will be sentenced to 10 years of prison. If the criminal refuses to testify, he gets 6 months in jail for refusing to cooperate with the investigation. If both testify against each other, both get 2 years in prison.

Criminals are isolated from each other and can not communicate. Their main interest is to reduce their own stay in jail as much as possible. What decision should take each of them: to make a deal with the investigation or to remain silent? Before you look for a solution in this chapter, try to imagine yourself in situation like this and decide what you would do and why? And then try to compare your answer with what science think of it:)

Unable to communicate with each other, criminals have to give each other away. After all, in fact, there are only four possible options:

[[File:Scheme.png|500px‎]]

If suspects are not allowed to talk, they do not know what the other one will do. In this situation, if A remains silent, he is dependent on B’s desicion and will ether sentenced for 10 years or 6 months. If A will testify against B, then as a result A will get 2 years in prison or will be released [http://www.apn.ru/publications/article19740.htm].

Thus, it would be better for each of the suspects to testify against each other, so that they will not to be condemned for 10 years. But if A and B have had the opportunity to communicate, then, of course, the best solution for each of them would be not make a deal with the investigation and get only 6 months in prison. This little problem illustrates that sometimes, acting solely in your personal interests will not always lead to the best results for others and for yourself. By acting for themselves, both prisoners went to jail for 2 years, when in fact they could do with only a half-year of imprisonment.

==Game balance==

Each prisoner can accurately predict his win in each of the four situations. As you know, the balance of the game in game theory is '''[http://en.wikipedia.org/wiki/Nash_equilibrium Nash equilibrium]'''. The prisoner’s dilemma is a game with a special kind of Nash equilibrium – '''[http://tuvalu.santafe.edu/~jkchoi/game4.pdf dominant strategy equilibrium]'''. But before we get to the dominant strategy equilibrium, let’s briefly review what is a normal Nash equilibrium.

'''NASH EQUILIBRIUM''' is the type of game solution of 2 or more players, in which neither party can increase their gain by changing his decision unilaterally while other members do not change their decisions. Accordingly, such a set of strategies chosen by participants and their winnings is called a Nash equilibrium. In other words, everything depends not only on you. [http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html]

But let us return to our problem. So, we still have 2 prisoners, sitting in 2 different cells without the possibility to agree on what to do next. And there are 4 possible variants of the outcome.
Remember, you had put yourself in the shoes of one of them? Let us repeat the experience, and thinking only rationally, try to make a decision. If we are afraid, we are more likely to think only about ourselves. Fear switches on instinct of self-preservation which is often stronger than moral standards and obligations.

Here is an estimated stream of thoughts in this case: ''“If I, Alfred, will remain silent, but Benjamin will tell them everything, then I am going to jail for 10 years. This simply can not happen. If I will tell them everything and he will do so as well, then we both stuck in here for 2 years. Too bad, but still it is better then 10 years. If Benji will remain silent, and I will tell the truth to the police, then he will stay here for 10 years, but I will be free (although I will probably suffer from insomnia caused by my dishonesty). Of course, there is a chance that he will not speak, and if I will do the same, then we both will get only half a year in jail. But again, the risk of getting 10 years in prison is to high. So, I will not keep my mouth shut and will give testimonies on him. It does not matter if he will or will not speak, I will avoid the worst – ten years in prison, and maybe I will even go home tomorrow, if he will be quiet.“''

Acting rationally in their own interest, the participants of this game come to an irrational result: in any case, both will get in jail, the only question is – for how long; but they could get a relatively short imprisonment if they were convinced that the other one will not say anything. The dilemma of ''“keeping silence – testifying”'' is resolved in favor of testimony, although in terms of the collective interest this decision, to put it mildly, is not optimal.

Now let us mentally put ourselves in the policeman shoes. His goal is to knock out the testimony. He can not change human characteristics of suspects, but he can put them in a context in which they will behave in a predictable manner. There are only two leverages in the hands of the police: fear and isolation. And they are more than enough to force the prisoners to act in police interests, rather than their own.

=Extensions of normal model=

==Iterated prisoner’s dilemma==

[[File:Iterated-pd.png|thumb|Iterated prisoner’s dilemma]]

Scenario goes like this: you and your colleague, Lucifer, are in jail and suspected of committing a crime. You are isolated from each other and do not know how the other will respond to questioning. The police invite both of you to implicate the other in the crime ''(defect)''. What happens depends on what both of you do, but neither of you know how the other will respond. If Lucifer betrays you ''(yields to the temptation to defect)'' while you remain silent, then you receive the longest jail term while Lucifer gets off free ''(and visa versa)''. If you both choose to cooperate with each other ''(not the police)'' by remaining silent, there is insufficient evidence to convict both of you, so you are both given a light sentence for a lesser crime. If both of you decide to defect, then you have condemned each other to slightly reduced but still heavy sentences.

The payoff in this game is a reduction in prison sentencing of very good, fairly good, fairly bad or very bad, which is translated into a point score system as is shown at the scheme. [http://www.iterated-prisoners-dilemma.net/]

==Finite Iteration==

[[File:Finite-iteration.png‎‎|thumb|Finite Iteration]]

Many of the situations that are alleged to have the structure of the PD, like defense appropriations of military rivals or price setting for duopolistic firms are better modeled by an iterated version of the game in which players play the PD repeatedly, retaining access at each round to the results of all previous rounds. In these iterated PDs players who defect in one round can be “punished” by defections in subsequent rounds and those who cooperate can be rewarded by cooperation. Thus the appropriate strategy for rationally self-interested players is no longer obvious. The theoretical answer to this question, it turns out, depends strongly on the definition of IPD employed and the knowledge attributed to rational players.

An IPD can be represented in extensive form by a tree diagram like one you can see at the scheme.

There is a significant theoretical difference on this matter between IPDs of fixed, finite length, like the one pictured above, and those of infinite or indefinitely finite length. In practice, there is not a great difference between how people behave in long fixed-length IPDs ''(except in the final few rounds)'' and those of indeterminate length. [http://plato.stanford.edu/entries/prisoner-dilemma/]

==The Centipede and the Finite IPD==

[[File:Centipede-pd.png‎‎|thumb|The Centipede PD with N=4]]

Many of the issues raised by the fixed-length IPD can be raised in even starker form by a somewhat simpler game. Consider a PD in which they punishment payoff is zero. Now iterate the asynchronous version of this game a fixed number times. Imagine that both players are restricted to highly “punitive” strategies according to which, they must always defect against a player who has ever defected. The result is a centipede game.

A stack of N one-dollar bills lies on a table. Players take turns taking money from the stack, one or two bills per turn. The game ends when the stack runs out or one of the players takes two bills ''(whichever comes first)''. Both players keep what they have taken to that point. The extensive form of the game with N=4 can be seen at the picture.

The centipede mainly raises the questions about cooperation and socially desirable altruism as does the PD and it is a favorite tool in empirical investigations of game playing [http://plato.stanford.edu/entries/prisoner-dilemma/]

==Infinite Iteration==

One way to avoid the dubious conclusion of the backward induction argument without delving too deeply into conditions of knowledge and rationality is to consider infinitely repeated PDs. No human agents can actually play an infinitely repeated game, of course, but the infinite IPD has been considered an appropriate way to model a series of interactions in which the participants never have reason to think the current interaction is their last. In this setting a pair of strategies determines an infinite path through of the game tree. If the payoffs of the one-shot game are positive, their total along any such path is infinite. This makes it somewhat awkward to compare strategies. If we confine ourselves to those strategies that can be implemented by mechanical devices ''(with finite memories and speeds of computation)'', however, it turns out that the sequence of payoffs to each player will always, after a finite number of rounds, cycle repeatedly through a particular finite sequence of payoffs. The relative value of such infinite sequences of payoffs can then be identified with the average value of the payoffs in one cycle. This value reflects the limit of average payoff per round as the number of rounds increases. Since there is no last round, it is obvious that backward induction does not apply to the infinite IPD. [http://plato.stanford.edu/entries/prisoner-dilemma/]

==N-player Prisoner’s Dilemma==

In the N-player prisoner’s dilemma multiple agents ''(N ≥ 2)'' interact within their designated group and must choose to cooperate or defect. Any benefit or payoff is received by all participants; any cost is borne by the cooperators only. Hardin describes the N-player prisoner’s dilemma as a «tragedy of the commons» game in which the players are worse off acting according to their self interests than if they were cooperating and coordinating their actions. [http://jp.poerf.de/papers/Rezaei09evolvingcooperation.pdf]

=Other conditions=

Not let us draw out attention to the boundary condition of the prisoner’s dilemma, namely the prison walls, the bars on the windows and a doors with a peepholes. All this indicates, that a person is in trouble already and even if he stands before the choice, the only thing he can do is to continue to lose. The only thing that remains to him is to minimize the inevitable losses.

The strategy of '''“testifying” '''strictly dominates over the strategy of '''“silence”'''. Similarly, another prisoner will come to the same conclusion. It is evident, that common interest of both prisoners is to work together, to keep silent and get only half of the year in jail. But prisoners are not able to cooperate in taking decisions. In other words, they do not have the opportunity to jointly implement their common interest. So each one of them begins to assert his personal interest, which does not lead to the best result.

But imagine that prisoners have the opportunity to discuss this situation. About what would they want to negotiate? Of course about common silence; as we see from the scheme above – it is the most painless variant for both of them as a group. However, each prisoner, after making sure that the other is convinced of the necessity and reasonableness of making a confession, will not confess himself, because he wants to be released. The fact that each of the prisoners, realizing how coordination of their tactics is mutually beneficial, will be in a better position while playing for himself. In that case he will be released.

As the analysis of options shows, the prisoners can not cooperate, because each of them has a personal interest. It is assumed that in this dilemma each of the prisoners acts according to the number of years he will be held in prison. But let’s imagine that our criminals are not selfish but altruistic, and each one also takes others’ interests into consideration. Then confession of the crime is the neccesary dominant strategy.

This dilemma represents a certain type of situations in which:
* there is a need to make an individual decision on the strategy of behavior in the context of common activity
* a separate participant of this situation is interested in the pursuit of general interest only when this general interest is being pursued by all participants
* because individual interests of participants in this situation as objectively separated individuals are different, in case of ignorance about the intentions of the other participant, each of them is forced to trying to achieve his private interest.

=Real life examples=

Now that we had more or less figured out what exactly the prisoner’s dilemma is, let’s see where in real life it is being used and how it helps to solve real-life conflict situations. Among the reasons of enormous popularity of prisoner’s dilemma let’s allocate one: it describes the choice that confronts us every day throughout our lives. It’s a choice between solidarity with other people and ou personal interests.

Many situations in the society are characterized by similar divergence between the decisions dictated by the individual and collective rationality. Famous examples are price wars and the arms race. In the context of the “prisoner’s dilemma” rejection should be considered as a cooperative strategy'' (of course with a partner and not with the authorities)'', and confession – non-cooperative or “cheating.”

==Prisoner’s dilemma in Eurozone==

Current situation with investors who run away from Greece illustrates the dilemma very well. In economic theory this is called a “coordination trap” or [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.176.6993 inefficient stable equilibrium]. It is the same balance as in our dilemma the silence and cooperation among the prisoners.

Exactly the same happenes in the eurozone. The tragedy of the situation in which Greece has a huge burden of debt in the absence of adequate tax revenues due to economic crisis, makes the market ''“pledge to each other”''. Noone believes in a ''“happy-end”'' and if you are too slow to react and lay someone down, then you will be layed down yourself. Default seems imminent, and investors want to get rid of the Greek bonds, while their price has not dropped completely, or, even worse, they all turned out to be worthless. Naturally, the new loan that Greece needs so desperately, can be forgetten.

The darkest result of all this might be the country default and rapid erosion of capital in European banks. This will lead to ceasing of lending and the subsequent closing of credit lines in U.S. banks. It will all be accompanied by a collapse in energy prices and the actual stopping of the world economy, as it happened in 2008.

There is an exit out of this situation – only a consistent and aggressive actions of central banks and governments of all countries that could convince investors on the market that the ''“laying each other down”'' is not necessary: there will be no default. In fact, this is our situation with the silent prisoners.

==Prisoner’s dilemma in price formation proces==

There are also many situations in pricing, when in process of creating price a certain group of companies face the prisoner’s dilemma. Often, one company may perceive the possibility of increasing their profits by reducing price for their goods or services. It does price lowering without paying attention to the pricing of its competitors. Simultaneously, its competitors can come to the same conclusioncan. Which means they really could make more money by cutting prices, not minding the actions of the first company. However, if the company and its competitors cut prices – that is, if all parties act in accordance with their own interests unilaterally – in many cases they all may come to a disadvantage in the end. The task of the industry in such situations is to keep prices high, despite the fact that each company would get some benefits from price reduction [http://bizkiev.com/content/view/822/205/].

==Authority and prisoner’s dilemma==

Finally, let’s take a look at an example of prisoner’s dilemma within the confines of an authoritarian society. It is enough to imagine any community under the rule of the authoritarian regime. It can be an Arab Spring or post-Soviet society. Since the Arab Spring happened recently, we can not analyze these events properly yet.That is why let’s try to understand what exactly happened after the collapse of the Soviet Union. Fear of approaching poverty and hunger, multiplied by the isolation caused by the destruction of the usual rules of social life and lack of time, immediately gave the results. Multi-million society, which lived in the Soviet solidarity just yesterday, made fast transition to the state of hyper-individualism – unfortunately, such is the power of fear.

In a society, which is built on fear of losing what you have, solidarity in most cases is impossible. The very formulation of the problem as minimizing the loss shapes events in a very certain way. The condition of minimization of losses and the role of a police officer are not discussed in the theoretical model of the prisoner’s dilemma. However, they are the most important feature of the prisoner’s dilemma in its application to real life. So, this game describes the condition of any human cooperation and solidarity. We call this condition: co-operation and solidarity should bring benefits to every member of the group, in which it occurs.

Probably it is not even worth writing about how effectively the model drives society into primitivism and regression. Finally, a few words about how choices in life expand, once you start to look at other people not only in the framework of prisoner’s dilemma, but also considering the option of group redistribution. A person, who sees the world in the light of group redistribution conquers fear. Hypothetical policeman no longer has control over him, because a prisoner is not alone – whole group covers his back. His power increases in proportion to the size and cohesion of this group. In addition, he starts to feel the taste of life, because now he can not only lose, but also win.

=Conclusion=

==Game theory in games==

Finally, more interactive example of prisoner’s dilemma in real life is a British game show '''[http://www.goldenballstvshow.com/ “Golden Balls”]'''. You can can check it out on YouTube, but let us take a look at the rules. There are two players, who play a game very similar to out prisoner’s dilemma and the prize is 100,000 pounds. Each of the players can choose either to split or steal. If both players split, then each one gets 50,000 pounds. If one player splits and the other steals, the person who split gets 100,000 and the other person gets 0. And finally, if both of them steal, then they both get 0. But the main difference is that before they start making their decisions, playes can talk for a few minutes and presumably convince the other person that they plan to split. Try to watch couple of episodes of this game and understand, what will be the best strategy to win. Then imagine that you play with a total stranger and then with someone you know. And then that you play one time or there are more games in one set [http://gametheoryinpractice.blogspot.com/2009/08/split-or-steal.html].

You can also try out an online version of this model to better understand the whole concept '''[http://serendip.brynmawr.edu/bb/pd.html Serendip’s Exchange: You Have Found The Prisoners’ Dilemma]'''.

Hopefully, the problematic of this model is now more clear to you and you can use it not only in theory, but also to solve real problems and tasks. Good luck!

=Exercises=

To be sure that you understood this chapter, try to figure out solutions for following examples.

==1. “Perestroika anecdote”==

There used to be a so-called story during Perestroika years. Two businessmen agreed, that one will sell another a truck full of tomatoes. They sign a contract. And only after that the first one goes to look for tomatoes, and the second one – for money.

As you can see, it is a classic example of the prisoner’s dilemma. The agreement was signed, but what if the first will find the tomatoes and the other one will not find the money or vice versa? Try to answer following questions:
* ''Should you trust your business partner in situation like this?''
* ''How far should your trust go?''
* ''Would it be better for non-tomato businessman to stop looking for money, let that simpleton be with his tomatoes. But what reputation will it bring, will there be anyone willing to deal with him in the future?''

==2. “TV Arms Race“==

Two large competiting companies need to determine their budgets on TV advertising for next year. As you can imagine, TV advertising is a very expensive toy. Therefore: more advertising –> lower the income –> lower the quality of goods'' (for ex., they will save money on the product formula)''. But if a competitor will give a lot more advertising than they are, they will lose bigger share of their business. Therefore, both companies have the exact same fear – another one will spend hundreds of millions of dollars per year on advertising.

'''TIP''': As a result, advertising race leads to the fact, that no washing powder washes anymore, soda is impossible to drink and at the end of the year companies are hardly above zero.

=Sources=

1. PRISONER’S DILEMMA. Kafedra jetiki filosofskogo fakul’teta MGU [online]. [cit. 2012-01-19].
Available from: http://www.ethicscenter.ru/en/content/16.htm

2. RAPOPORT, Anatol and Albert M. CHAMMAH. Prisoner’s Dilemma. Michigan: The University of Michigan , Ann Arbor Paperbacks, 2008. ISBN 0-472-06165-8.
Available from: http://www.press.umich.edu/titleDetailLookInside.do?id=20269

3. KRYLOV, Dmitrij. Katalazhka i restoran: kak vyrvat’sja iz dilemmy zakljuchjonnogo: Kak perestat’ byt’ pyl’ju.APN – Agenstvo politicheskih novostej [online]. [cit. 2012-01-19].
Available from: http://www.apn.ru/publications/article19740.htm

4. D. REIBSTEIN, David. Cenoobrazovanie: dilemma zakljuchennogo. BIZKIEV – biznes zhurnal [online]. [cit. 2012-01-19].
Available from: http://bizkiev.com/content/view/822/205/

5. «Dilemma zakljuchennogo»: Matrica vyigrysha. Ravnovesie Njesha. Dominirujuwaja strategija. [online]. [cit. 2012-01-19].
Available from: http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html

6. T., Sam. Split Or Steal. GAME THEORY IN PRACTICE [online]. 21.08.2009 [cit. 2012-01-22].
Available from: http://gametheoryinpractice.blogspot.com/2009/08/split-or-steal.html

7. http://dic.academic.ru/dic.nsf/econ_dict/20858. Jekonomika. Tolkovyj slovar’. — M.: “INFRA-M”, Izdatel’stvo “Ves’ Mir”. Dzh. Bljek. Obwaja redakcija: d.je.n. Osadchaja I.M.. 2000.

8. Serendip’s Exchange: You Have Found The Prisoners’ Dilemma. Serendip’s Exchange [online]. Wednesday, 08-Jun-2005 12:47:31 EDT [cit. 2012-04-07].
Available from: http://serendip.brynmawr.edu/bb/pd.html

9. REZAEI, Golriz, Michael KIRLEY a Jens PFAU. Evolving Cooperation in the N-player Prisoner’s Dilemma: A Social Network Model. Department of Computer Science and Software Engineering The University of Melbourne, Australia, 2010.
Available from: http://jp.poerf.de/papers/Rezaei09evolvingcooperation.pdf. Annual paper.
The University of Melbourne, Australia.

10. KUHN, Steven. Stanford Encyclopedia of Philosophy: Prisoner’s Dilemma. Stanford Encyclopedia of Philosophy [online]. Sep 4, 1997, Mon Oct 22, 2007 [cit. 2012-04-07].
Available from: http://plato.stanford.edu/entries/prisoner-dilemma/

11. WAYNE, Davis. PRISONER’S DILEMMA [online]. March 22nd, 2007 [cit. 2012-04-10].
Available from: http://www.iterated-prisoners-dilemma.net/

=Reference=

1. http://plato.stanford.edu/entries/game-theory/
2. http://plato.stanford.edu/entries/game-theory/#Games
3. http://plato.stanford.edu/entries/game-theory/#Util
4. http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Merrill-M.-Flood
5. http://www.rand.org/pubs/authors/d/dresher_melvin.html
6. http://www.rand.org/about.html
7. http://www.nytimes.com/1995/01/27/obituaries/albert-w-tucker-89-pioneering-mathematician.html
8. http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/1998-99/game-theory/nonzero.html
9. http://www.press.umich.edu/titleDetailLookInside.do?id=20269
10. http://www.apn.ru/publications/article19740.htm
11. http://tuvalu.santafe.edu/~jkchoi/game4.pdf
12. http://shporiforall.ru/shpory/ek-teorii/2-dilemma-zaklyuchennogo-matrica-vyigrysha-ravnovesie-nesha-dominiruyushhaya-strategiya.html
13. http://www.iterated-prisoners-dilemma.net/
14. http://plato.stanford.edu/entries/prisoner-dilemma/
15. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.176.6993
16. http://bizkiev.com/content/view/822/205/
17. http://www.goldenballstvshow.com/
18. http://serendip.brynmawr.edu/bb/pd.html

=Additional files=

[[media:Prisoner_dilemma_eng.pdf‎|Prisoner's Dilemma chapter]]

File:Prisoner dilemma eng.pdf

2012-06-18T14:42:23Z

Maja:

2012-06-17T16:01:49Z

Simulation of a parking lot in Saint-Petersburg Airport

2012-06-11T13:23:48Z

Maja:

{{DISPLAYTITLE:Simulation of a parking lot in Saint-Petersburg Airport}}
This page contains a research report representing semester project for 4IT495 Simulation of Systems class (SS 2011/2012).

*'''Project name''': Simulation of a parking lot in Saint-Petersburg Airport
*'''Project type''': Research report
*'''Class''': 4IT495 Simulation of Systems (SS 2011/2012)
*'''Author''': Khabirova Maja
*'''Model type''': [[Discrete-event simulation| Discrete-event simulation]]
*'''Software used:''' [http://simprocess.com// Business Process Management Software, SIMPROCESS]

=Problem definition=

==Introduction==
Anyone who has ever met or sent off their relatives or colleagues at the Pulkovo airport in Saint-Peterburg, met the need to obtain a parking pass and pay for parking on the exit of the parking lot, if their car has been in for more than 15 minutes. Typically, this system is reasonably robust: approaching drivers line up to the barrier and drive into the territory, getting a parking ticket. To pay for parking, two payment machines are installed; you can pay with cash (both bills and change). In addition, an employee who solves problems related to the entering, exiting and paying in the parking lot is always on duty.

But recently following situation has been repeating: in the busiest hours in just forty minutes the queue to exit the airport begin to grow alarmingly, the drivers are getting nervous, trying
to get in free 15-minute interval, they signals at the people who stays too long near payment automats, trying to pay for their ticket.

The situation is following: when a man comes in to the payment automate and tries to put money into the receiving device, the machine does not respond right away, which strongly lengthens the time of payment. The second machine does not accept the money at all, although the display indicates that it is enabled and working properly. From time to time “working” and “idle” machines are swapped.

All attempts to ask the worker responsible for the correct operation of the system for assistance recently lead to nothing. One gets the impression that the assistant is executing an order
not to help people with their problems with the payment.

[[File:Pulkovo-scheme.png|400px|thumb|left|Scheme of Pulkovo International Airport parking lot]]

==Definition of the task==

In this work, the main task is to try to understand what is happening – why does it take so long to pay for the parking ticket and is payment the core of all the problems in this situation at all.

For a start, it was determined that this system is a system with positive feedback: the more cars are in the queue at the exit, the longer time the service for each driver will take. While drivers wait in line, their 15-minutes-of-free-parking interval runs out and they are forced to leave their car, spending extra time to get to the paying machine and pay. It seems obvious that the situation would have been saved by the installation of payment terminals which will accept banking cards or by placing more payment automates, as well as moving them closer to exits barriers.

As was mentioned before, behavior of the assistant seems irrational, too. He was not even trying to indicate non-working payment machines for the drivers, increasing the time spent in unsuccessful attempts to pay.

At the very beginning of the modeling process, it became clear that in this particular logistics system, the term “irrational” was not an absolute. Of course for the drivers the situation was more than irrational: the longer they spent in the queue, the lower the level of service was, however at the same time the payment was getting higher. In this case the drivers had absolutely no opportunity to influence the situation somehow.

For a commercial structure, that is operating the parking lot, situation was more than rational: the inconvenience of the drivers was converted into a direct profit for this commercial structure. Which leads to the fact, that in following case, customers do not pay for the high service level, but for its absence. And payment is exceeding that which they would pay for the high service in properly working system.

=Methodology=

==Chosen methodology==

Building a simulation model of this small supply chain will help to analyze processes occurring in it in details. Discrete-event simulation is a convenient tool for simulation in cases like this. It is based on the fact that in the system of discrete-event simulation several simple concepts embodies:

* in accordance with the schedule of arrival and departure of aircrafts certrain “processes” are introduced into the space of this model (in this case: cars with drivers and passengers).

* These cars are the “clients” of the three types of shared, limited in their capacity “servers”: device that is issuing parking tickets at the entrance, the device that verifies parking tickets at the exit and payment machines. Later in this work, I introduced, yet another type of “server” – the employee that services for parking system.

* at the entrance, at the exit and during the process of payment, drivers form a queues, which are based on FIFO the principle – first-in, first out. Later in this paper, I decided to use the Poisson distribution to generate the number of cars, though I tried not to deviate far from the concept of FIFO in my mind.

==Parameters==

Model parameters are the following: arrival schedule of cars, the number of available “servers”, the operation time and time, spent for waiting for passengers at the airport.

According to these considerations, discrete-event model will look like a certain “landfill”, where in discrete moments of time, independent virtual machines are coming and they are operating in order with a given program:

* stand in line to enter the parking lot

* get a parking ticket

* wait for passengers

* stand in line to exit

* if nessesary, pay for services

They, in turn, react to events – the release or capture of the resource, the “server”. To make it more realistic, some processes will be described by random variables (the Poisson distribution – arrival time of cars), which means that this version of simulation is a Monte Carlo simulation. In this particular case, for the sake of avoiding complicating of the model, all parameters will have approximate values based on real data. Nevertheless, the figures are rounded, as this task requires not the precise numerical values but the overall trend. Based on this trend, solutions will be formulated later.

All that remains is to choose the platform for the implementation of the model. Nowadays there is a wide choice of modeling systems on the market. There are powerful commercial system with a good visualization support (for ex., a product worked by team of russian developers – AnyLogic, or foreign variants – Arena, SIMSCRIPT, SLAM, SIMAN, AweSim), open systems (for ex., GPSS), as well as application libraries. As far as I can tell, in any of the cases one must have at least minimal skills of development or programming.

My choice was a system of Modeling and Simulation Tools, SIMProcess. The system has a broad palette of graphic features, it contains everything that is needed to quick creation of a discrete-event model and obtaining numerical results. An important factor in the decision was existance of a good documentation on this system.

At first, the situation was modeled on the paper. After a little thought originally scheduled algorithm has been extended:

* stand in line to enter the parking lot

* get a parking ticket

* wait for passengers

* stand in line to exit

* if nessesary, pay for services

A branch with an assistant on the parking lot was added:

* After payment some of the drivers goes straight to the exit.

* If they had problems, they go to the assistant (for ex., there is a problem with payment or barrier).

* After that, if their problem is solved by the assistant, some of the drivers go to the exit (problem with a barrier is solved).

* If the problem is solved, but payment still needed, drivers return to the “Payment” process.

==2.3 Model description==

Model starts from the Arrival point. Here number of drivers are generated according to estimated information, based on number of arriving flights. “Shifts“ are divided into 4 sections:

[[File:Phases.png‎]]

* morning hours – 07:00-12:00, there is approximately 3 drivers/1 minute

[[File:1-morning-hours.png]]
[[File:2-morning-hours.png‎‎]]

* peak hours – 12:01-18:00, approx. 10 drivers/1 minute

[[File:1-peak-hours.png]]
[[File:2-peak-hours.png‎]]

* evening hours – 18:01-00:00, approx. 4 drivers/1 minute

[[File:1-evening-hours.png‎]]
[[File:2-evening-hours.png]]

* night hours – 00:01-06:59, approx. 1 driver/1 minute

[[File:1-night-hours.png‎]]
[[File:2-night-hours.png]]

After drivers are “created“, they need to enter the parking lot. Process of Entering the parking lot is responcible for that. This process is described by a delay – “Getting the ticket“, which takes approx. 15 seconds and needs 2 “Entry barrier“ resources. After drivers got through the barrier and entered the parking lot, they usually wait for people they came to pick up, get them and their baggage. This process includes a certain delay – approx. 25 minutes.

After they are finished with their business, they need to exit. If they are still inside 15 minutes interval, they go to the exit of the parking lot, where they check their ticket and can ride away usinf one of the 2 exit barriers. This cause a sertain delay, approx. 15 seconds., 1 exit barrier as recources.

If they are out of 15 minutes interval, they need to go to the paying automat to pay for extra time they spent on the parking lot. Branch divides these 2 groups of drivers and while some of them go to the exit, others need to get to automats and pay. Process of paying with cash cause a delay of about 1 minute and requires 2 paying automats as a recource. However, as was mentioned earlier, only one automat is working, that is why in this simulation it will be mentioned as 1.0 in resource field.

Depending on how succesfull the paying was, some drivers may exit right away through one of 2 exit barriers, others may need an assiatance of the parking lot worker to deal with problems like: not working automat, out of cach and credit card only, not working ticket, etc. Parking lot assistant and visit of him is another process. This includes a delay of about 5 minutes. After that drivers can go straight to the exit or go back to the paying process, if still needed.

=Results=

The first question that is needed to be answered: is it true, that while the level of service is getting lower, it increases revenue for the company, that provides services at the parking lot? To answer this question, a series of numerical experiments with different numbers of incoming cars during different periods of time were done (these can be called a stress test). The numbers were based on the data of arriving aircrafts. Cars were entering the system in a certain period of time by certain “groups”.

[[File:Report1.jpg|thumb|Simulation report, showing lines formation process]]

The level of service is the time spent “from gate to gate”, which means average time that cars spent on the territory of the parking lot, although it would be better to summarize the time spent in the queue for entry and exit barrier. It is clear that certain effect of sharp increase of time spent waiting in queue is real and is approximately equal to 15 minutes. After that time half of the drivers needs to get out of their cars to pay. Obviously, the intensity of this effect can get worse by reducing the number of working paying machines and increasing the waiting time.

What happens at this point with the profits from the parking lot? To answer this question it is worth paying attention to the number of cars that does not fall into the 15-minutes-free interval and compare this number to the total number of cars, which entered the parking lot. The theory that was expressed earlier, is confirmed – it is clear that low bandwidth is profitable for the firm, that provides services to parking lot.

[[File:Report2.jpg|thumb|Simulation report, showing optimalisation of the process.]]

How can throughput be improved with minimal cost? One of the obvious solution to the traffic-manager, responsible for the transport component of the terminal (in this case his salary should not be counted as a percentage from profit that parking lot will generate) may be a minimal increase of “free” interval (for ex., from 15 up to 20 minutes). It is clear that such an action will have a positive effect on throughput.

It is clear that the reverse side of this improvement can be the reduction of free space in the area of parking, which can lead to certain problems. At some point it may become a limiting factor (it is not simulated in this scenario for the sake of simplifying the model). The solution to this problem though could be the next step: to encourage drivers spend a shorter time at the parking territory. How can this be achieved? Firstly, relevant information about the arrival of the aircrafts should be provided to the drivers; a board or display can be installed near the entry to the parking lot, or internal airport communications about arrivals and departures can be broadcasted at unallocated FM-band, so that drivers can get the information from the radio in their car.

The second solution could be the following: a selection of special waiting zones outside the airport. Now there are such areas at the entrances of the airport, but they are relatively small.

Here you can see results of testing and from this chart it is clear that main problem are (or more precisely – is, because only one is working) payment automats. Due to non-working problem delay for paying the parking fee is relatively long – 1 minute for each client. Enormous lines form because of that.

Let’s take a look at results of simulation, where number of payment terminals is increased to 4 machines and delay is 20 seconds per client only (because smaller lines form and one can pay without any stress).

It is clear that this fact changes lines formation process dramatically. Of course, due to the reason that I only used approximate data, numbers can seem a bit ridiculous at this stage, but overall trend is absolutely understandable – if we increase a number of payment terminals, it will absolutely have a positive influence on our model.

=Conclusion=

In conclusion, I would like to say a few words about the method that was used. In my work, simplest idealized model was used: a description of the algorithm of the coming cars, gates with barriers and payment automates. Despite its simplicity, this model allows us to give a qualitative answer to our questions. Clearly, more detailed models of complicated processses, such as job storage terminal, factory, supermarket, etc. would take much longer to develop, they require data collection and careful calibration. But eventually, the principles remain the same.

I will not deny that it is usually easier to understand more visualized processses. Visualization takes longer time to be created, but provides additional information about the situation. With the knowledge of how to interpret basic mathematical indicators that can be drawn from a discrete-event model, no less information can be extracted. For example:

• loading of individual resources

• overall system performance

• time that customers spend while waiting in the queues at each “server”

• total time needed for customers’ service

Simulation models can be used not only to analyze the current situation and scenario of possible development, but also to search for optimal parameters needed for normal work of the
logistic systems.

While doing this work, I realized that it is not appropriate to invest time and money to develop a simulation model from the very beginning. Even a simple processs can take a lot of time to be re-created. The best way to use a modeling system are the cases, where the overall dynamics of the logistic system is clear, when we know what are the constraints on resources, all the data are collected and characteristics of the simulated environment are estimated. Only in this situation, a simulation model can be a real tool to support management decision making. Perhaps in the future I will use this method to optimize certain processses and the ability to analyze the results, which I got in this course is the most important acquired skill.

=Sources=

1. Pulkovo Saint-Petersburg Airport. Pulkovo Saint-Petersburg Airport [online]. [cit. 2012-01-03].
Available from: http://www.pulkovoairport.ru/eng/

2. Pulkovo Parkovki. Pulkovo Aeroport Sankt-Peterburga [online]. [cit. 2012-01-06].
Available from: http://www.pulkovoairport.ru/transportation/parking/

3. Varianty parkovnki v Pulkovo-2. ZlataPraga.ru [online]. [cit. 2011-12-25].
Available from: http://www.zlatapraga.ru/tickets/Parking.php

4. ITone – prosto o slozhnom [online]. [cit. 2011-12-20].
Available from: http://www.itone.ru/bizness_processs/

5. Sistema biznes modelirovanija. Business Studio [online]. [cit. 2011-12-20].
Available from: http://www.businessstudio.ru/