Game Theory 101: The Prisoner's Dilemma http://www.voutube.com/watch7v~IotsMu 1J 8 fA&feature~related 1. Pre-listening Try to explain the meaning of the following words, suspected trespass confess rat out sb defect from sb options be better off perplex cops be lenient cooperate testimony payoff 2. Listening. Decide whether the statements are T or F. 1. The police are not able to prove that the arrested are guilty. 2. Prisoners are able to talk to each other and negotiate a deal. 3. If both prisoners confess, the police will not believe them. 4. The first row in a matrix is the possible punishment of the first player. 5. Pronouns he and she are used to indicate the equality of the sexes. 6. It is better for the players to confess. 7. The first player will spend 5 years in jail is he remains silent. 8. The cooperate strategy is always dominated by the defect strategy. 9. Reasonable players always play a strictly dominated strategy. 10. Prisoners tend to defect from each other, that is why only defect-defect equilibrium is a stable solution. Prisoner's dilemma From Wikipedia, the free encyclopedia 1. Reading a) Read the first part of the text and find the underlined words which can be replaced by the following expressions. a) something making you work harder.................................................... b) formulated................. c)balance between various aspects........................ d)say what will happen in the future....................... e)prize........................ f) essential..................................g)not harmful........................................ The prisoner's dilemma is a fundamental problem in game theory that demonstrates why two people might not cooperate even if it is in both their best interests to do so. It was originally framed by Merrill Flood and Melvin Dresher working at RAND in 1950. Albert W. Tucker formalized the game with prison sentence payoffs and gave it the "prisoner's dilemma" name. 2. Fill in the missing parts of words in the description of PD. A classic example of the prisoner's dilemma (PD) is presented as follows: Two suspects are a......... by the police. The police have ins..........evidence for a conviction, and, having separated the prisoners, visit each of them to offer the same deal. If one testifies for the prosecution against the other (defects) and the other remains s......... (cooperates), the defector goes free and the silent accomplice receives the full one-year s...........If both remain silent, both prisoners are sentenced to only one month inj.........for a minor charge. If each betrays the other, each receives a three-month sentence. Each prisoner must choose to betray the other or to remain silent. Each one is assured that the other would not know about the b...........before the end of the investigation. How should thep............... act? If we assume that each player cares only about minimizing his or her own time in jail, then the prisoner's dilemma forms a non-zero-sum game in which two players may each either cooperate with or defect from (betray) the other player. In this game, as in most game theory, the only concern of each individual player (prisoner) is maximizing his or her own payoff, without any concern for the other player's payoff. The unique equilibrium for this game is a Pareto-suboptimal solution, that is, rational choice leads the two players to both play defect, even though each player's individual reward would be greater if they both played cooperatively. In the classic form of this game, cooperating is strictly dominated by defecting, so that the only possible equilibrium for the game is for all players to defect. No matter what the other player does, one player will always gain a greater payoff by playing defect. Since in any situation playing defect is more beneficial than cooperating, all rational players will play defect, all things being equal. In the iterated prisoner's dilemma, the game is played repeatedly. Thus each player has an opportunity to punish the other player for previous non-cooperative play. If the number of steps is known by both players in advance, economic theory says that the two players should defect again and again, no matter how many times the game is played. However, this analysis fails to predict the behavior of human players in a real iterated prisoners dilemma situation, and it also fails to predict the optimum algorithm when computer programs play in a tournament. Only when the players play an indefinite or random number of times can cooperation be an equilibrium, technically a subgame perfect equilibrium meaning that both players defecting always remains an equilibrium and there are many other equilibrium outcomes. In this case, the incentive to defect can be overcome by the threat of punishment. 3. Reading. In pairs discuss these questions. a) What do you know about John Nash? b) What does it mean when the method is stochastic? c) What is a cartel? d) What is the difference between a strict and weak Nash Equilibrium? e) What is a strategy profile? f) What does the payoff depend on? g) What was proven by Nash? Nash equilibrium From Wikipedia, the free encyclopedia 4. In this part of the text, try to fill in the missing connectives. Likewise In order to Stated simply However In game theory a)...........Nash equilibrium (named after John Forbes Nash, who proposed it) is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally. If each player has chosen a strategy and no player can benefit by changing his or her strategy while the other players keep theirs unchanged, then the current set of strategy choices and the corresponding payoffs constitute a Nash equilibrium. b)........., Amy and Phil are in Nash equilibrium if Amy is making the best decision she can, taking into account Phil's decision, and Phil is making the best decision he can, taking into account Amy's decision, c)........., a group of players is in Nash equilibrium if each one is making the best decision that he or she can, taking into account the decisions of the others. d)..........., Nash equilibrium does not necessarily mean the best payoff for all the players involved; in many cases all the players might improve their payoffs if they could somehow agree on strategies different from the Nash equilibrium (e.g., competing businesses forming a cartel e)..........increase their profits). 5) In pairs, try to read the notation given in the part Formal definition Formal definition Let (S, J) be a game with n players, where St is the strategy set for player i, S=Si XS2... XS„ is the set of strategy profiles and f=(fi(x), ...,f„(x)) is the payoff function for x €S. Let*/ be a strategy profile of player / and x.t be a strategy profile of all players except for player i. When each player i €{1,n} chooses strategy x, resulting in strategy profile x = (x;,Xr) then player i obtains payoff fi(x). Note that the payoff depends on the strategy profile chosen, i.e., on the strategy chosen by player i as well as the strategies chosen by all the other players. A strategy profile x* GS is a Nash equilibrium (NE) if no unilateral deviation in strategy by any single player is profitable for that player, that is A game can have either a pure-strategy or a mixed Nash Equilibrium, {in the latter a pure strategy is chosen stochastically with a fixed frequency). Nash proved that if we allow mixed strategies, then every game with a finite number of players in which each player can choose from finitely many pure strategies has at least one Nash equilibrium. When the inequality above holds strictly (with > instead of 5!) for all players and all feasible alternative strategies, then the equilibrium is classified as a strict Nash equilibrium. If instead, for some player, there is exact equality between ^tand some other strategy in the set S, then the equilibrium is classified as a weak Nash equilibrium. 6) Have a look at the part Formal definition and find these symbols. a) asterisk ........................... b) lower case letters................ c) parentheses....................... d) upper case letters................. e) subscript........................... f) italics............................... g) dots ................................. h) universal quantifier............... 7) Fill in the missing prepositions. a) All can agree.........strategies. b) It is profitable............the player, c) It can classified.............a weak Nash equilibrium. d) They can cooperate........or defect..............other players. e) It was named............John Forbes Nash. f) There is no concern............other player's payoff. g) What is it dominated..........? h) What do these players care............? i) It can be overcome............the threat.........punishment. j) No deviation.........strategy is profitable.