MAT109 · Erich Prisner · Franklin College · 2007-2009

Possible Final Questions

Chapter 1

  1. What is a zero-sum game?
    .........
  2. Explain why the game Blackjack could both be formulated as a game of perfect information, but also as a game of imperfect information.
    .........
  3. For each one of the following games, explain whether it is sequential, simultaneous, whether it has perfect information, and whether it contains randomness (random moves):
    .........
  4. What is rational behavior in the context of Game Theory
    .........
  5. What are outcomes, what are payoffs, what is the difference between both?
    The outcomes are the different possible end situations of a game. Each outcome has payoffs (which are numbers) for each player attached.
  6. What is a zero-sum game?
    A game where for every outcome the sum of all payoffs of all players equals 0.

Chapter 2

  1. If in a simultaneous 2-player game the first player has 4 possible moves and the other one 5 possible moves, how many different outcomes does the game have?
    4 · 5 = 20
  2. If in a simultaneous 3-player game the first player has 4 possible moves, the second one has 3 possible moves, and the third one has 5 possible moves, how many different outcomes does the game have?
    4 · 3 · 5 = 60.
  3. What is the difference between weak domination and strict domination?
    .........
  4. Consider the following two-player game.
      L    M    R  
    U  1,1    3,4    2,1  
    M  2,4    2,5    8,1  
    D  3,3    0,4    0,9  

    Maximin move is "M" for both Ann and Beth, guaranteeing a value of at least 2 for Ann and at least 4 for Beth.

    For Ann there is no domination, weak or strong. For Beth, move "M" dominates (strongly, and therefore also weakly) move "L".

    After removing option "L" for Beth, suddenly Ann's move "D" is strictly (and therefore also weakly) dominated by both "U" and "M". After eliminating this option as well, we arrive at the following bimatrix:
      M    R  
    U  3,4    2,1  
    M  2,5    8,1  
    Here again Beth has domination---move "M" stricty dominates move "R". After removing move "R", Ann's move "M" strictly dominates move "M". Therefore the IESD and IEWD matrix, the result after iterated eliminating strictly or weakly dominated moves, is
      M  
    U  3,4  

    The best responses are U-->M, M-->M, and D-->R for Beth, and L-->D, M-->U, and R-->M for Ann.

    Therefore the Nash equilibrium is "U" versus "M", since "M" is Beth's best response against Ann's "U", and "U" is Ann's best response against Beth's "M".

  5. Write down the payoff bimatrix of the following game. Find Maximin moves, domination, condensed best response digraph, and all pure Nash equilibria.
    SCHEDULING A DINNER PARTY: Ann and Beth are not on speaking terms, but have a lot of common friends. Both want to invite these friends to a dinner party this weekend. Possible are Friday or Saturday evening. Both slightly prefer Saturday. If both set the party at the same time, this will be considered a disaster with a payoff of -10 for both. If one plans the party on Friday and the other on Saturday, the one having the Saturday party gets a payoff of 5, and the other of 4.

    fridaysaturday
    friday-10,-104,5
    saturday5,4-10,-10
    Both moves are Maximin, there is no domination. Since this is a symmetric game, it suffices to show the condensed best response digraph, having only two vertices labeled "Friday" and "Saturday" and arcs from Friday to Saturday and from Saturday to Friday. These are two pure Nash equilibria: Friday versus Saturday and conversely.
  6. DEADLOCK: Two players play a symmetric game where each one can either cooperate or defect. If both cooperate, both get an payoff of 1. If both defect both get a payoff of 2. If one cooperate but the other defects, the one cooperating gets a payoff of 0, and the other defecting a payoff of 3.
    Draw the bimatrix of the game. Find the Maximin moves, possible domination, draw the best response digraph, and find all pure Nash equilibria.
    CooperateDefect
    Cooperate 1, 1  0, 3 
    Defect 3, 0  2, 2 
    Both games, PRISONER's DILEMMA and DEADLOCK have exactly one Nash equilibrium of both defecting. The difference is that in DEADLOCK both prefer the outcome over the "both cooperating" outcome, whereas in the PRISONER's DILEMMA they don't.

  7. STAG HUNT: Two players play a symmetric game where each one can either hunt stag or hare. If both hunt stag, both get an payoff of 3. If both hunt hare, both get a payoff of 1. If one hunts stag and the other hare, the stag hunter gets a payoff of 0, and the hare hunter a payoff of 2.
    Draw the bimatrix of the game. Find the Maximin moves, possible domination, draw the best response digraph, and find all pure Nash equilibria.

    Hunt stagChase hare
    Hunt stag 3, 3  0, 2 
    Chase hare 2, 0  1, 1 

    STAG HUNT has two Nash equilibria: Both hunting stag, which is Pareto-optimal, or both chasing hares.

  8. CHICKEN: Two players play a symmetric game where each one can either play Dove or Hawk. If both play Dove, both get an payoff of 2. If both play hawk, both get a payoff of 0. If one plays Dove and the other Hawk, the one playing Dove gets a payoff of 1, and the other one a payoff of 3.
    Draw the bimatrix of the game. Find the Maximin moves, possible domination, draw the best response digraph, and find all pure Nash equilibria.

    DoveHawk
    Dove 2, 2  1, 3 
    Hawk 3, 1  0, 0 

    As our previous example, CHICKEN also has two pure Nash equilibria, but this time they are the asymetric Dove/Hawk and Hawk/Dove combinations.

  9. What does it mean that a move in a simultaneous game strictly dominates another one? Would a player play a strictly dominated move?
    ...
  10. What is a Nash equilibrium? Why would the players play the moves forming a Nash equilibrium?
    ...

Chapter 3

  1. State Zermelo's Theorem
    Every finite perfect-information sequential game without random moves can be analyzed using backward induction.
  2. Find the backward induction solution of the following game:

  3. Find the backward induction solution of the following game:

  4. Find the backward induction solution of the following game:

Chapter 4

  1. You face 5 envelopes, containing $0, $1000, $2000, $3000, and $4000. You randomly choose one of them. What is the expected value?
    All five outcomes are equally likely, and have therefore a probability of 1/5. Therefore the expected values for the money is (1/5)·0 + (1/5)·1000 + (1/5)·2000 + (1/5)·3000 + (1/5)·4000 = it is (0+1000+2000+3000+4000)/5 = 10000/5 = 2000.
  2. You have five $1-bills, three $5-bills, and one $10 bills in your pocket. a) You randomly choose one of them to give the taxi driver a tip. What is the expected value?
    Each of the nine bills is equally likely, a probability of 1/9. Since five bills are one-dollar bills, the probability to draw one of them is 5/9. In the same way, the probability of drawing a $5 bill is 3/9, whereas the probability of drawing the $10 bill is 1/9. Therefore the expected values is (5/9)·1 + (3/9)·5 + (1/9)·10 = 30/9 = 3.33 dollars.
  3. Assume an experiment has three possible outcomes, and assume that the payoffs are 2, 3, and 5. Further assume that all these three outcomes are equally likely. What is the expected value for the payoff in this experiment?
    (1/3) · 2 + (1/3) · 3 + (1/3) · 5 = 10/3.
  4. Is it possible that the probability of an event is equal to -0.7? Is it possible that the probability of an event is equal to 0.7? Is it possible that the probability of an event is equal to 7?
    No, yes, and no. Probabilities must be between 0 and 1.
  5. Explain the concepts "theoretical probability" and "empirical probability".
    ....
  6. Explain the Law of Large Numbers.
    If an experiment is repeated more and more times, the empirical probability (relative frequency) of an event will converge, i.e. eventually come closer and closer, to its theoretical probability.

Chapter 5

  1. What are the expected payoffs in this game, if both players Ann and Beth would play optimally? At the beginning, will Ann choose "up" or "down"? When Ann would have to decide between "hot" and "cold", which one would she choose? When she would have to decide between "north" and "south", how would she decide? How would Beth decide between the options "left" and "right", between the options "west" and "east", and between the options "fast" and "slow" if she would have to?

    As we can be seen in the analysis, the expected payoff values for both are 4, and Ann will choose "down", "hot", and "north", and Beth will choose "left", "east", and "slow".
  2. What are the expected payoffs in this game, if both players Ann and Beth would play optimally? At the beginning, will Ann choose "up" or "down"? When Ann would have to decide between "hot" and "cold", which one would she choose? When she would have to decide between "north" and "south", how would she decide? How would Beth decide between the options "left" and "right", between the options "west" and "east", and between the options "fast" and "slow" if she would have to?

    As we can be seen in the analysis, the expected payoff value is 4 for Ann and 4.75 for Beth (with a neutral Ann). Ann will choose "up" or "down", "cold", and "north", and Beth will choose "right", "west", and "fast".
  3. The following sequential game with randomness but perfect information is given in extensive form. There are two players, Ann and Beth. Vertices are labeled by the player whose turn is it. Vertices without such a label are random moves, the probabilities for the two options are 50% and 50% in each case. The payoffs of the end vertices are given, always first Ann's payoff, then Beth's.
    Here is the solution done by using backwards induction for a "neutral" Beth:

    Note that there are a few variants here. The above solution is the case where a player would randomly chose among moves that yield identical payoffs for here (the neutral player). Note that in class we also discussed cases where a player, in such a case where two payoffs of two options for that player are identical, would look at the opponent's payoff as second (minor criterium). A friendly player would try to give the opponent the best possible (all under the condition that for her own payoff it doesn't matter), and a hostile player would try to minimize it. In the game above, Beth is in both situations indifferent about her moves. A friendly Beth would play "1" in both cases, a hostile Beth would play "2" in both cases, a neutral Beth alternates. Whether or not Ann is friendly or neutral or hostile doesn't matter. If Beth is friendly, then the values of the game are 2 for Ann and 1 for Beth. If Beth is neutral, then they are 1.5 for Ann and 1 for Beth, and they are 1 for both in case of a hostile Beth. In all these three cases, Ann would start the game by playing "1".

Chapter 6

  1. How many information sets do Ann and Beth have in this game? How many pure strategies does Ann have? How many pure strategies does Beth have? Select two pure strategies for Ann and two pure strategies for Beth, and give the expected payoffs for Ann and Beth in the four cases where Ann plays one of the two selected strategies and Beth plazs one of the two selected strategies.

    a) Ann has 3 information sets: The one where she walks or stays, the one where she decides between Lugano and Milano, and the one where she chooses between green, blue, or red. Since she has 2 options in the first, 2 option in the second, and 3 options in the third, she has 2·2·3=12 pure strategies. They are (walk,Lugano,green), (walk,Lugano,blue), (walk,Lugano,red), (walk,Milano,green), (walk,Milano,blue), (walk,Milano,red), (stay,Lugano,green), (stay,Lugano,blue), (stay,Lugano,red), (stay,Milano,green), (stay,Milano,blue), (stay,Milano,red).
    Beth has two information sets, the one where she calls or doesn't, and the one where she chooses between high, middle or low. Since she has 2 options in the first case and 3 options in the other, she has 2·3=6 pure strategies. They are (call,high), (call,middle), (call,low), (don't,high), (don't,middle), (don't,low).
    b) If Ann decides to stay, then she will not face the green/blue/red decision. therefore we have reduced pure strategies (stay,Lugano,.) and (stay,Milano,.). If Ann decides to walk, all other decisions may occur, so there are still the 5 reduced pure strategies (walk,Lugano,green), (walk,Lugano,blue), (walk,Lugano,red), (walk,Milano,green), (walk,Milano,blue), (walk,Milano,red). Thus Ann has 8 reduced pure strategies.
    I select (walk,Lugano,green) and (stay,Lugano,blue) for Ann, and (call,high) and (don't,middle) for Beth. There are also four cases how Nature could play: "snow" with probability 1/3, "warm" or "cold" "rain" with probability (1/3)·(1/2) = 1/6 each, and "sun" with probability 1/3.
    • If Ann plays (walk,Lugano,green) and Beth plays (call,high), then the payoffs for Ann and Beth are 4, 1 provided Nature plays "snow", 1, 2 provided Nature plays "warm rain", 3, 1 if Nature plays "cold rain", and 2, 3 if Nature plays "sun". Therefore the expected payoff for Ann equals (1/3)·4 + (1/6)·1 + (1/6)·3 + (1/3)·2 = 8/3. The expected payoff for Beth equals (1/3)·1 + (1/6)·2 + (1/6)·1 + (1/3)·3 = 11/6.
    • If Ann plays (walk,Lugano,green) and Beth plays (don't,middle), then the payoffs for Ann and Beth are 1, 4 provided Nature plays "snow", 1, 2 provided Nature plays "warm rain", 3, 1 if Nature plays "cold rain", and 3, 1 if Nature plays "sun". Therefore the expected payoff for Ann equals (1/3)·1 + (1/6)·1 + (1/6)·3 + (1/3)·3 = 2. The expected payoff for Beth equals (1/3)·4 + (1/6)·2 + (1/6)·1 + (1/3)·1 = 13/6.
    • If Ann plays (stay,Lugano,blue) and Beth plays (call,high), then the payoffs for Ann and Beth are 3, 1 provided Nature plays "snow", 2, 1 provided Nature plays "warm rain", 2, 1 if Nature plays "cold rain", and 2, 3 if Nature plays "sun". Therefore the expected payoff for Ann equals (1/3)·3 + (1/6)·2 + (1/6)·2 + (1/3)·2 = 7/3. The expected payoff for Beth equals (1/3)·1 + (1/6)·1 + (1/6)·1 + (1/3)·3 = 5/3.
    • If Ann plays (stay,Lugano,blue) and Beth plays (don't,middle), then the payoffs for Ann and Beth are 2, 1 provided Nature plays "snow", 2, 1 provided Nature plays "warm rain", 2, 1 if Nature plays "cold rain", and 3, 1 if Nature plays "sun". Therefore the expected payoff for Ann equals (1/3)·2 + (1/6)·2 + (1/6)·2 + (1/3)·3 = 7/3. The expected payoff for Beth equals (1/3)·1 + (1/6)·1 + (1/6)·1 + (1/3)·1 = 1.
  2. How many information sets do Ann and Beth have in this game? How many pure strategies does Ann have? How many pure strategies does Beth have?

    a) Ann has 3 information sets: The one where she chooses between high, middle, or low, the one where she decides between today or tomorrow, and the one where she chooses between green, blue, or red. Since she has 3 options in the first, 2 option in the second, and 3 options in the third, she has 3·2·3=18 pure strategies. They are (high,today,green), (high,today,blue), (high,today,red), (high,tomorrow,green), (high,tomorrow,blue), (high,tomorrow,red), (middle,today,green), (middle,today,blue), (middle,today,red), (middle,tomorrow,green), (middle,tomorrow,blue), (middle,tomorrow,red), (low,today,green), (low,today,blue), (low,today,red), (low,tomorrow,green), (low,tomorrow,blue), (low,tomorrow,red).
    Beth has two information sets, the one where chooses between hot and cold, and the one where she chooses between Lugano and Milano. Since she has 2 options in the first case and 2 options in the other, she has 2·2=4 pure strategies. They are (hot,Lugano), (hot,Milano), (cold,Lugano), (cold,Milano).
    b) If Ann decides to play middle when reaching this situation, then she will not face the green/blue/red decision. therefore we have reduced pure strategies (middle,today,.) and (middle,tomorrow,.). The other 12 pure strategies (high,today,green), (high,today,blue), (high,today,red), (high,tomorrow,green), (high,tomorrow,blue), (high,tomorrow,red), (low,today,green), (low,today,blue), (low,today,red), (low,tomorrow,green), (low,tomorrow,blue), (low,tomorrow,red) are also reduced. Thus Ann has 14 reduced pure strategies.
  3. For which of the following two classes of games can backward induction work and always create a "solution": "Sequential games with perfect information and randomness" or "Sequential games without perfect information and without randomness"?
    Backward induction works for sequential games with perfect information and randomness, but not for games without perfect information.
  4. What is an information set?
    A bunch of positions where a player is supposed to move, but which this player can not distinguish.

Chapter 7

  1. How many pure strategies does Ann have in this game? How many pure strategies does Beth have? Find the Normal Form of the game.

    Ann has one information set with two options. Therefore she has two pure strategies, choosing "K" or choosing "Q". Beth has two information sets with two options in each. therefore she has 4 pure strategies. One of them would be to choose "K" in her first information set and "K" in her second information set.
    The normal form looks as follows (with all expected payoffs just given for Ann, since we have a zero-sum game):
     KK  KQ  QK  QQ 
    K -1  1/7  -1/7  1 
    Q 1  1/7  -1/7  -1 
  2. How many pure strategies does Ann have in this game? How many pure strategies does Beth have? Find the Normal Form of the game.

    Ann has one information set with three choices, A1, A2, and A3. Therefore she has 3 pure strategies. One of them is to choose A1. Beth has two information sets with three moves in each. Therefore she has 3·3 pure strategies. One of them would be "B2B4", to choose B2 when facing the first information set and B4 when facing the second information set.
    The normal form looks as follows (with all expected payoffs just given for Ann, since we have a zero-sum game):
     B1B4  B1B5  B1B6  B2B4  B2B5  B2B6  B3B4  B3B5  B3B6 
    A1 -1  -1  -1  1  1  1  1  1  1 
    A2 1  0  1  0  -1  0  1  0  1 
    A3 1  1  -1  1  1  -1  1  1  -1 
  3. What is the difference between a move and between a strategy?
    Moves are the option a player has in a given information set. In a pure strategy, the player selects a move for every information set belonging to that player.
  4. Consider the following zero-sum game given by the extensive form as shown below:

    1. Is this a game of perfect or imperfect information? Why?
    2. Finish the Normal Form by filling out the four empty entries. Remember that we have a zero-sum game and therefore only Ann's payoffs are shown.
       B1B3  B1B4  B2B3  B2B4 
      A1A3 2  0  .....  -2 
      A1A4 -1  -1  -1  -1 
      A2A3 .....  0  1  0 
      A2A4 -2  .....  0  ...... 
    3. For the following three questions: If you were unable to fill in the four entries, just fill in any of the numbers -2, -1, 0, 1, 2 and then answer the next three questions with this completed matrix.
    4. Is there any weak domination? Which strategies weakly dominate which?
    5. Draw the Best Response Digraph
    6. Are there any Nash equilibria in pure strategies?

    1. It is a game of imperfect information since at least one information set contains more than one vertex.
    2. See here for Excel help.
       B1B3  B1B4  B2B3  B2B4 
      A1A3 2  0  0  -2 
      A1A4 -1  -1  -1  -1 
      A2A3 1  0  1  0 
      A2A4 -2  -1  0  1 
    3. ---
    4. Ann's second pure strategy A1A4 is weakly---even strictly---dominated by A2A3.
      Remember that for checking weak domination for Beth's pure strategies, we have to look at Beth's payoffs, which are the opposites of the numbers given. Beth's third pure strategy B2B3 is weakly dominated by B1B4.
    5. See the digraph to the right.
    6. Yes, A2A3 versus B1B4.
  5. Consider the following game given by the extensive form as shown below:

    1. Is this a game of perfect or imperfect information? Why?
    2. Can this game be analyzed using backward induction?
    3. How many information sets do Ann and Beth have in this game?
    4. How many pure strategies does Ann have? How many pure strategies does Beth have?
    5. Finish the Normal Form by filling out the four empty entries. Remember that we have a zero-sum game and therefore only Ann's payoffs are shown.
       B1B3  B1B4  B2B3  B2B4 
      A1A3 2/3  1/3  ...  0 
      A1A4 1  ...  2/3  ... 
      A2A3 -1/3  -1  0  -2/3 
      A2A4 0  -1/3  ...  0 
    6. Is there a Nash equilibrium in this game? What pure strategies would the two players play?

    It is a game of imperfect information, since there are information sets containing at least two vertices. For games of imperfect information, the Backward Induction method does not work.
    Ann has two information sets (note that the single vertex is also an information set) and Beth has also two information sets. The four pure strategies for Ann are "A1A3", A1A4", "A2A3", and "A2A4". The four pure strategies for Beth are "B1B3", B1B4", "B2B3", and "B2B4".
     B1B3  B1B4  B2B3  B2B4 
    A1A3 2/3  1/3  1/3  0 
    A1A4 1  1  2/3  2/3 
    A2A3 -1/3  -1  0  -2/3 
    A2A4 0  -1/3  1/3  0 
    Ann's pure strategy "A1A4 weakly dominates all others, therefore there are two pure Nash equilibria: "A1A4" versus "B2B3", and also "A1A4" versus "B2B4". In particular, a rational Beth will always play the move "B2" in her first information set.
  6. What is the normal form of a 2-player game?
    It is the payoff bimatrix obtained by viewing the game as a simultaneous game with all pure strategies of Ann as her moves, and all pure strategies of Beth as her moves.
  7. Do games with imperfect information have a Normal form? What about games with perfect information?
    Yes, all these games have a normal form.

Chapter 8

  1. What did von Neumann show in 1928?
    Every finite two-person zero-sum game has at least one Nash equilibrium in (pure or) mixed strategies.
  2. What is the difference between a pure and a mixed strategy?
    A mixed strategy assigns probabilities to pure strategies such that the sum of all these probabilities equals 1.
  3. What did Nash show in his 1950 thesis?
    Every game has at least one Nash equilibrium in mixed strategies.
  4. Does every game have a Nash equilibrium in pure strategies?
    No.
  5. Name one method to find a Nash equilibrium in mixed strategies for a general game.
    Brown's fictitious play process
  6. Does every game have a Nash equilibrium in mixed or pure strategies? What about if we look at games of perfect information? What about games of imperfect information?
    Yes, it has. That's Nash's Theorem. It's true both for perfect as well as for imperfect information.
  7. True or false: (All games considered are finite, with complete but not necessarily perfect information.)
    1. Every game has a Normal Form.
    2. Simultaneous games do not have an Extensive Form
    3. Every game has a pure Nash equilibrium
    4. Every sequential game with randomness and perfect information has a pure Nash equilibrium

    1. True.
    2. False, they do.
    3. False.
    4. True. It is the solution found by Backward Induction.
  8. ...........
    ........
  9. ...........
    ........
  10. ...........
    ........