Problem Set 3

CSE 112: Networked Life, Spring 2004

  1. Bob and Alice would like to go on a date tonight. Bob really wants to go to the movies and watch "The Pirates of the Caribbean". Alice would much rather go to the ballet instead. Bob hates ballet just as much as Alice hates movies. Unfortunately both cannot communicate with each other anymore before they head out. Hence both can go either to the movies or to the ballet and hope to find the other one there. (Keep in mind that both players would rather go to an unwanted event with the other one, instead of going to their favored event by themselves)

    1. Formulate the above problem as a matrix game. (Use: Only use the following payoffs: 10,5,-5,-10)

    2. Find all pure Nash Equilibria in the game found in (a)

    3. Compute the average payoff of the strategy pair (1/2,1/2) for both Bob and Alice. Is this a NE?

      Solution: a) Alice column, Bob row
      Alice: C B
      C: 10/5 -5/-5
      B: -10/-10 5/10

      b) Both go to the cinema or both go to the ballet c) No, if Bob plays (1,0) - i.e. always goes to the movies - his expected payoff jumps from 0 to 5.


  2. At some other University students have two options: Either they study for the final and get a good grade or they don't study and hope to be able to copy the solutions from one of the persons who sit next to them. Students at this University are very shortsighted and regard studying as a bad investment of their time. Failing the final would be regarded as very catastrophic. If a student hasn't studied enough, he/she has a certain probability of being able to copy the right results from one of the neighbors (You can denote this as a function S_i of the neighborhood).
    1. Give two aspects in which this problem is fundamentally different to the airline security problem.
    2. Formulate the payoff function similar to the interdependent security problems studied in class, depending on the individual probability for each student to study x_i and the neighborhood function S_i. (Make sure you state clearly the meaning of all variables you use)
    3. To make the model more realistic, we also have to consider that there is a probability q_i for each student to be caught cheating (and subsequently fail the exam). Assume a student always cheats if he/she hasn't studied enough. Update the function found in (b) to the more realistic model.

    [Solution: a)
    - The more other students "invest in studying", the LOWER is my incentive to study myself
    - If I study, I can totally rule out the danger of the "catastrophic" event of failing
    b) -[x_i*C+(1-x_i)*(1-S_i)*L]
    x_i : probability of studying
    C : "Cost" to study
    L : L>>>C, catastrophic cost of failing the final
    S_i : probability of being able to copy the right results from neighbors.

    c) -[x_i*C+(1-x_i)*[q_i+(1-q_i)(1-S_i)]*L ]


  3. Meanwhile Bob and Alice luckily both ended up at the cinema. In the movie, five pirates have stolen 100 gold coins. Now they are faced with the problem of how to divide their treasure. As all five pirates have different heights, they agreed to the following plan: The shortest pirate should suggest a way of how to split the coins (and he can suggest whatever he wants e.g. even giving everything to himself) and then ALL pirates should have a vote (including the one who just made the proposal). If he gets a MAJORITY voting for his split (half of the votes is not enough), then whatever he suggested will be done. If he doesn't get a majority, he will be thrown over board and the exact same procedure will be repeated with the remaining pirates.

    You can make the following assumptions:

    1. None of the pirates can swim. If they get thrown over board, they're shark bait (payoff -infinity)
    2. The pirates vote for letting another pirate be thrown over board if and only if this increases their expected payoff
    3. All five pirates are actually Penn Alumni and have taken at least one course on Game Theory. They will all act completely rationally and can also assume the others to act the same.

    Calculate the outcome of the treasure split. [There is only one correct solution.]
    (A full answer should include for each pirate - shortest to biggest - how much they get or if they will have to go over board and some reasoning why. Don't forget to clearly state the outcome of each vote that you mention.)

    Solution: Let the pirates be enumerated in ascending order according to their height. Let us look at the problem in reverse:
    - If only two pirates are left, P4 can only suggest a split of 0/100 as this is the only way that P5 is at least indifferent to killing P4.
    - If three pirates are left, P3 gets away with offering the split 100/0/0 as he knows that P4 will vote for his suggestion. P5 is not needed to win a majority.
    ...
    Pirate 1: 100 vote: YES
    Pirate 2: 0 vote: NO
    Pirate 3: 0 vote: YES
    Pirate 4: 0 vote: NO
    Pirate 5: 0 vote: YES

    Without the "pirates don't kill if they don't have to"-assumption, results are 97 0 2 1 0 or 97 0 2 0 1. All three outcomes are regarded correct.


  4. After the five pirates finished dividing up their treasure, the tallest pirate gets upset and challenges the shortest pirate to a duel. The shortest pirate makes the first move. The shortest pirate can either PUNCH or KICK. In return, the big pirate can DUCK or JUMP. Ducking makes him avoid a punch, and by jumping he can avoid a kick. The small pirate knows that whether he hits the big pirate or not, he has two options after that: He can STAY or FLEE. If he manages to hit, it would be very satisfying to stay in order to "teach the big pirate a lesson". Otherwise, however, it would be much healthier to flee.

    1. Write the above fight (only up to stay/flee) as a game in extended form (state your assumptions and use appropriate payoffs)

    2. Now translate the game from (a) into a Matrix game with the same payoffs.

      First big pirate, then small pirate:

      Punch - > Duck Punch - > Duck Punch - > Jump Punch - > Jump
      Kick -> Duck Kick -> Jump Kick -> Duck Kick -> Jump
      Punch;Duck->Stay, Jump->Stay -10 -10 10 10
      Punch;Duck->Stay, Jump->Flee -10 -10 5 5
      Punch;Duck->Flee, Jump->Stay -5 -5 10 10
      Punch;Duck->Flee, Jump->Flee -5 -5 5 5
      Kick; Duck->Stay, Jump->Stay 10 -10 10 -10
      Kick; Duck->Stay, Jump->Flee 10 -5 10 -5
      Kick; Duck->Flee, Jump->Stay 5 -10 5 -10
      Kick; Duck->Flee, Jump->Flee 5 -5 5 -5
      Punch - > Duck Punch - > Duck Punch - > Jump Punch - > Jump
      Kick -> Duck Kick -> Jump Kick -> Duck Kick -> Jump
      Punch;Duck->Stay, Jump->Stay 10 10 -10 -10
      Punch;Duck->Stay, Jump->Flee 10 10 -5 -5
      Punch;Duck->Flee, Jump->Stay 5 5 -10 -10
      Punch;Duck->Flee, Jump->Flee 5 5 -5 -5
      Kick; Duck->Stay, Jump->Stay -10 10 -10 10
      Kick; Duck->Stay, Jump->Flee -10 5 -10 5
      Kick; Duck->Flee, Jump->Stay -5 10 -5 10
      Kick; Duck->Flee, Jump->Flee -5 5 -5 5
      It is also correct to assume that kicking and punching give different payoffs.

    3. Write down a best strategies for each player.

      The best strategy for the short pirate is either:
      1) Punch; Duck -> Flee, Jump-> Stay
      2) Kick; Duck -> Stay, Jump -> Flee


    1. Write the four conditions which, if satisfied, qualify a 2-player, 2-action game as a prisoner's dilemma game.

    2. Consider this prisoner's dilemma game:

      C D
      C -1,-1 -10,0
      D 0,-10 -8,-8

      What are all the Nash equilibria of this game?

    3. Use the inequality aversion model with alpha=.5, beta =.2 (the same alpha and beta for both players.) Give the resulting matrix of *utilities* (not payoffs) for both players.

    4. What are all the Nash equilibria of this modified, behavioral game?

    5. Given the values alpha=.2 and beta=.1 for both players, can you write a game that is a prisoner's dilemma game (as defined in the Schelling book) but has an IA Nash equilibrium of (defect, defect)? If so, write one such game. If not, write "IMPOSSIBLE."

    6. Keeping the payoff as they are originally defined above, can you find values for alpha_row, beta_row, alpha_column, and beta_column that give a (cooperate, defect) equilibrium? (Note that the two players are now allowed to have different alpha and beta).

      Answers:
      1. Directly given in Shelling p. 216 (and given in recitation) 2. (D,D) is the only one. 3. -1, -1 -12, -2 -2, -12 -8, -8 4. (C,C) is the only one. 5. The original game given is such a game. 6. No. If the column player is to defect, alpha_col and beta_col must be close to zero, so that this player doesn't mind inequality. Then what settings of alpha_row and beta_row could prevent the row player from defecting? None. The "cooperate" option is not only lower payoff, it is also inqeuitable, whlie the "defect" option results in equal payoffs. No aversion to inequity can make a player prefer to cooperate. (Remember that alpha and beta cannot be negative in this model.)