ݺߣ

ݺߣShare a Scribd company logo

Game theory through_examples gddsrt

•Download as DOC, PDF•
•
Bryan De Chavez
Bryan De Chavez

This document summarizes examples used to illustrate concepts from game theory and decision theory, including: 1) Games against nature involving a single agent making decisions under uncertainty. 2) Non-cooperative games involving two or more autonomous agents making decisions simultaneously without cooperation. Examples include friends trying to see each other and prisoners in a prisoner's dilemma. 3) Equilibrium concepts in game theory including dominant strategies, Nash equilibria, mixed strategies, and Pareto optimal outcomes.

1 of 4
Downloaded 16 times
SYMBOLIC SYSTEMS 202: The Rationality Debate (3 units) Winter Quarter 2003­2004, Stanford  University Instructor:  Todd Davies  Game Theory Through Examples (2/11/04) Games against nature ­ decision theory for a single agent Expected utility theory for a single agent is sometimes called the theory of "games against nature".   Consider this example.  Example 1: Planning a party  Our agent is planning a party, and is worried about whether it will rain or not.  The utilities and  probabilities for each state and action can be represented as follows:    Nature's states: Rain  (p=1/3) Party planner's possible actions: Outside 1 Inside 2 The expected utility of an action A given uncertainty about a state S = Probability(S|A)*Utility(S|A) +  Probability(not S|A)Utility(not S|A) Note that action A can be viewed as a compound gamble or outcome.  Also, note that the probability of a state can depend on the agent's choice of action, although, in the above  example, it does not.  For the party problem: EU(Outside) = (1/3)(1) + (2/3)(3) = 2.67; EU(Inside) = (1/3)(2) + (2/3)(2) = 2  Therefore, choose Outside, the action with the higher expected utility  (Noncooperative) game theory ­ decision theory for more than one agent, each acting autonomously (no  binding agreements)  In the examples below, we'll assume two self­utility maximizing agents (or players), each of whom has  complete information about the options available to themselves and the other player as well as their own  and the other's payoffs (utilities) under each option.  Example 2 ­ Friends hoping to see each other  Consider two people, Chris and Kim.  They both enjoy each other's company, but neither can  communicate with the other before deciding whether to stay at home (where they would not see each  other) or go to the beach this afternoon (where they could see each other).  Each prefers going to the  beach to being at home, and prefers being with the other person rather than being apart. This game can be  represented by the following normal (or matrix) form:   
Kim Home Chris  Home (0,0) Beach (1,0) Each player has a set of strategies (={Home,Beach} for both players in this example). Specifying one  strategy i for the row player (Chris) and one strategy j for the column player (Kim) yields an outcome,  which is represented as a pair of payoffs (Rij,Cij), where Rij is the utility the row player receives, and Cij  is the utility the column player receives.  In this example, going to the beach is a (strictly)  dominant strategy for each player, because it always  yields the best outcome, no matter what the other player does. Thus, if the players are both maximizing  their individual expected utilities, each will go to the beach.  So Beach­Beach is a dominant strategy  equilibrium  for this game.  Because of this, Kim and Chris, if they are rational, do not need to cooperate  (make an agreement) ahead of time.  Each can just pursue their own interest, and the best outcome will  occur for both.  Example 3 ­ "Friends" with asymmetric preferences  Now consider Betty and John.  John likes Betty, but Betty doesn't like John that much.  Each knows this,  and neither wants to call the other before deciding what to do this afternoon: stay at their respective  homes or go to the neighborhood swimming pool.  Here is the normal form:        John Home Betty Home (2,0) Pool (3,0) In this case, Betty's best strategy depends on what John does.  But if she assumes John is rational, she will  reason that he will not stay home, because going to the pool is a dominant strategy for him.  Knowing  this, she can decide to stay home (because 2>1).  This is called iterated dominance.   In this example,  Betty gets higher utility than John because of their relative preferences, and John gets less utility than he  would have if Betty wanted to be with him.  In this example, Pool­Home (3,0), Home­Pool (2,1), and Pool­Pool (1,2) are all Pareto optimal  outcomes.  An outcome is Pareto optimal (or efficient) if no agent can be made better off than that  outcome without making another agent  worse off.   The equilibrium outcomes in both this example and  the previous one are Pareto optimal.  Example  4 ­ Prisoners' dilemma  Consider Stan and Leland, two prisoners who have each been offered a deal to turn state's witness (defect)  against the other.  They can't communicate.   They had orginally agreed to remain in solidarity, i.e. not  testify against each other, but since the agreement cannot be enforced, each must choose whether to honor  it.  If both remain in solidarity, then they will each only be convicted of a minor chage.  If only one  defects, then the state will throw the book at the other and let the defector go.  If they both defect, each  will get convicted of a serious charge.  The payoff matrix (higher positive utility implies a better  outcome) is as follows:   
    Leland Solidarity Stan Solidarity (3,3) Defection (4,1) In this game, the strategy of defection is weakly dominant for each player, meaning that whatever the  other player does, defecting yields an outcome at least as good and possibly better than remaining in  solidarity would.  Note that if the bottom right cell payoffs were (2,2) instead of (1,1), then defecting  would be strictly dominant for each player.  Either way, Defection­Defection is a dominant strategy  equilibrium.   However, it is not Pareto optimal.  Both players could be made better off if neither defected  against the other.  This is an example of a social dilemma: a situation in which each agent's autonomous maximization of  self­utility leads to an inefficient outcome.  Such a situation can occur for any number of people, not just  two.  An agreement by two people to trade with each other (involving goods, services, and/or money)  set's up a prisoners' dilemma­type game whenever the agreement cannot be enforced.  Example 5 ­ Coordination  Let's go back to Chris and Kim.  They are going to the same conference, and each is expecting the other  to be there, but they haven't seen each other yet.  The conferees have their choice of two activities on the  first afternoon: swimming or hiking.  They both hope to see each other ­­ if they don't they will have no  fun, and each prefers swimming over hiking.  They must each decide what to do before knowing where  the other is going. Here is the normal form:        Kim Swim Chris Swim (2,2) Hike (0,0) The best outcome is obviously Swim­Swim, but going swimming is not dominant for either player.  Both  Swim­Swim and Hike­Hike have the property that each player's strategy  is the best (or tied for the best)  response to the other player's strategy in that pairing.  This defines a more general equilibrium notion  called the Nash equilibrium.  The dominance equilibria of examples 1­3 are all Nash equilibria as well.  A third equilibrium exists in this game involving what are called mixed strategies.  A mixed strategy is a  probability distribution over the pure strategies (which are Swim and Hike for each player in this  example).  (Note that the players do not have to have the same set of strategies available to them, even  though that has been the case in all our examples.) In this example, if each player individually throws a  die and goes swimming if the die comes up 1 or 2, and goes hiking if the die comes up 3, 4, 5, or 6, the  resulting expected utility (2/3 for each player) cannot be improved upon for either player given that the  other player uses this strategy.  In 1950, John Nash (depicted somewhat fictitiously in the film A Beautiful Mind ­­ the book is more  accurate!) proved that every finite game, involving any number of players, has at least one (Nash)  equilibrium, though there might not be any that involve only pure strategies for all players.  In this  example, there are three  equilibria: the mixed strategy equilibrium (Swim,1/3; Hike,2/3)­ (Swim,1/3;Hike,2/3), and two pure strategy equilibria ­­ Swim­Swim and Hike­Hike. 
When there is more than one equilibrium, and players cannot make binding agreements, they must try to  coordinate to arrive at an equilibrium outcome.  When only one equilibrium is also Pareto optimal, as  Swim­Swim is in this case, that fact should suggest to rational players that it will be the one around which  they coordinate.  Many other criteria for equilibrium selection have been studied (e.g. focal points,  subgame perfection, stability ­­ see the reading on game theory).  Example 6 ­ "Battle of the sexes"  Finally, let's consider Roy and Jen.  They are going to the same conference as Kim and Chris in example  5.  They each would prefer to be in the same place (the swim or the hike), but their preferences differ  about which it should be.  Roy would rather go swimming, and Jen would rather go hiking. Here is the  matrix form:        Jen Swim Roy Swim (3,2) Hike (1,1) This game has three Nash equilibria: Swim­Swim, Hike­Hike, and (Swim,2/3;Hike,1/3)­ (Swim,1/3;Hike,2/3).  Note that the mixed strategies differ for each player in the third equilibrium: each  goes to their preferred activity with 2/3 probability.  All of the equilibria are Pareto optimal this time, so that does not help for selection.  Only the mixed  strategy equilibrium results in equal expected utilities for the two players, so if both value equality or  symmetry, this might be the focal point. But of course it will be difficult for Roy and Jen to see that  unless they have studied game theory! 

More Related Content

Game theory through_examples gddsrt

  • 1. SYMBOLIC SYSTEMS 202: The Rationality Debate (3 units) Winter Quarter 2003­2004, Stanford  University Instructor:  Todd Davies  Game Theory Through Examples (2/11/04) Games against nature ­ decision theory for a single agent Expected utility theory for a single agent is sometimes called the theory of "games against nature".   Consider this example.  Example 1: Planning a party  Our agent is planning a party, and is worried about whether it will rain or not.  The utilities and  probabilities for each state and action can be represented as follows:    Nature's states: Rain  (p=1/3) Party planner's possible actions: Outside 1 Inside 2 The expected utility of an action A given uncertainty about a state S = Probability(S|A)*Utility(S|A) +  Probability(not S|A)Utility(not S|A) Note that action A can be viewed as a compound gamble or outcome.  Also, note that the probability of a state can depend on the agent's choice of action, although, in the above  example, it does not.  For the party problem: EU(Outside) = (1/3)(1) + (2/3)(3) = 2.67; EU(Inside) = (1/3)(2) + (2/3)(2) = 2  Therefore, choose Outside, the action with the higher expected utility  (Noncooperative) game theory ­ decision theory for more than one agent, each acting autonomously (no  binding agreements)  In the examples below, we'll assume two self­utility maximizing agents (or players), each of whom has  complete information about the options available to themselves and the other player as well as their own  and the other's payoffs (utilities) under each option.  Example 2 ­ Friends hoping to see each other  Consider two people, Chris and Kim.  They both enjoy each other's company, but neither can  communicate with the other before deciding whether to stay at home (where they would not see each  other) or go to the beach this afternoon (where they could see each other).  Each prefers going to the  beach to being at home, and prefers being with the other person rather than being apart. This game can be  represented by the following normal (or matrix) form:   
  • 2. Kim Home Chris  Home (0,0) Beach (1,0) Each player has a set of strategies (={Home,Beach} for both players in this example). Specifying one  strategy i for the row player (Chris) and one strategy j for the column player (Kim) yields an outcome,  which is represented as a pair of payoffs (Rij,Cij), where Rij is the utility the row player receives, and Cij  is the utility the column player receives.  In this example, going to the beach is a (strictly)  dominant strategy for each player, because it always  yields the best outcome, no matter what the other player does. Thus, if the players are both maximizing  their individual expected utilities, each will go to the beach.  So Beach­Beach is a dominant strategy  equilibrium  for this game.  Because of this, Kim and Chris, if they are rational, do not need to cooperate  (make an agreement) ahead of time.  Each can just pursue their own interest, and the best outcome will  occur for both.  Example 3 ­ "Friends" with asymmetric preferences  Now consider Betty and John.  John likes Betty, but Betty doesn't like John that much.  Each knows this,  and neither wants to call the other before deciding what to do this afternoon: stay at their respective  homes or go to the neighborhood swimming pool.  Here is the normal form:        John Home Betty Home (2,0) Pool (3,0) In this case, Betty's best strategy depends on what John does.  But if she assumes John is rational, she will  reason that he will not stay home, because going to the pool is a dominant strategy for him.  Knowing  this, she can decide to stay home (because 2>1).  This is called iterated dominance.   In this example,  Betty gets higher utility than John because of their relative preferences, and John gets less utility than he  would have if Betty wanted to be with him.  In this example, Pool­Home (3,0), Home­Pool (2,1), and Pool­Pool (1,2) are all Pareto optimal  outcomes.  An outcome is Pareto optimal (or efficient) if no agent can be made better off than that  outcome without making another agent  worse off.   The equilibrium outcomes in both this example and  the previous one are Pareto optimal.  Example  4 ­ Prisoners' dilemma  Consider Stan and Leland, two prisoners who have each been offered a deal to turn state's witness (defect)  against the other.  They can't communicate.   They had orginally agreed to remain in solidarity, i.e. not  testify against each other, but since the agreement cannot be enforced, each must choose whether to honor  it.  If both remain in solidarity, then they will each only be convicted of a minor chage.  If only one  defects, then the state will throw the book at the other and let the defector go.  If they both defect, each  will get convicted of a serious charge.  The payoff matrix (higher positive utility implies a better  outcome) is as follows:   
  • 3.     Leland Solidarity Stan Solidarity (3,3) Defection (4,1) In this game, the strategy of defection is weakly dominant for each player, meaning that whatever the  other player does, defecting yields an outcome at least as good and possibly better than remaining in  solidarity would.  Note that if the bottom right cell payoffs were (2,2) instead of (1,1), then defecting  would be strictly dominant for each player.  Either way, Defection­Defection is a dominant strategy  equilibrium.   However, it is not Pareto optimal.  Both players could be made better off if neither defected  against the other.  This is an example of a social dilemma: a situation in which each agent's autonomous maximization of  self­utility leads to an inefficient outcome.  Such a situation can occur for any number of people, not just  two.  An agreement by two people to trade with each other (involving goods, services, and/or money)  set's up a prisoners' dilemma­type game whenever the agreement cannot be enforced.  Example 5 ­ Coordination  Let's go back to Chris and Kim.  They are going to the same conference, and each is expecting the other  to be there, but they haven't seen each other yet.  The conferees have their choice of two activities on the  first afternoon: swimming or hiking.  They both hope to see each other ­­ if they don't they will have no  fun, and each prefers swimming over hiking.  They must each decide what to do before knowing where  the other is going. Here is the normal form:        Kim Swim Chris Swim (2,2) Hike (0,0) The best outcome is obviously Swim­Swim, but going swimming is not dominant for either player.  Both  Swim­Swim and Hike­Hike have the property that each player's strategy  is the best (or tied for the best)  response to the other player's strategy in that pairing.  This defines a more general equilibrium notion  called the Nash equilibrium.  The dominance equilibria of examples 1­3 are all Nash equilibria as well.  A third equilibrium exists in this game involving what are called mixed strategies.  A mixed strategy is a  probability distribution over the pure strategies (which are Swim and Hike for each player in this  example).  (Note that the players do not have to have the same set of strategies available to them, even  though that has been the case in all our examples.) In this example, if each player individually throws a  die and goes swimming if the die comes up 1 or 2, and goes hiking if the die comes up 3, 4, 5, or 6, the  resulting expected utility (2/3 for each player) cannot be improved upon for either player given that the  other player uses this strategy.  In 1950, John Nash (depicted somewhat fictitiously in the film A Beautiful Mind ­­ the book is more  accurate!) proved that every finite game, involving any number of players, has at least one (Nash)  equilibrium, though there might not be any that involve only pure strategies for all players.  In this  example, there are three  equilibria: the mixed strategy equilibrium (Swim,1/3; Hike,2/3)­ (Swim,1/3;Hike,2/3), and two pure strategy equilibria ­­ Swim­Swim and Hike­Hike. 
  • 4. When there is more than one equilibrium, and players cannot make binding agreements, they must try to  coordinate to arrive at an equilibrium outcome.  When only one equilibrium is also Pareto optimal, as  Swim­Swim is in this case, that fact should suggest to rational players that it will be the one around which  they coordinate.  Many other criteria for equilibrium selection have been studied (e.g. focal points,  subgame perfection, stability ­­ see the reading on game theory).  Example 6 ­ "Battle of the sexes"  Finally, let's consider Roy and Jen.  They are going to the same conference as Kim and Chris in example  5.  They each would prefer to be in the same place (the swim or the hike), but their preferences differ  about which it should be.  Roy would rather go swimming, and Jen would rather go hiking. Here is the  matrix form:        Jen Swim Roy Swim (3,2) Hike (1,1) This game has three Nash equilibria: Swim­Swim, Hike­Hike, and (Swim,2/3;Hike,1/3)­ (Swim,1/3;Hike,2/3).  Note that the mixed strategies differ for each player in the third equilibrium: each  goes to their preferred activity with 2/3 probability.  All of the equilibria are Pareto optimal this time, so that does not help for selection.  Only the mixed  strategy equilibrium results in equal expected utilities for the two players, so if both value equality or  symmetry, this might be the focal point. But of course it will be difficult for Roy and Jen to see that  unless they have studied game theory!