Problem Set 3

CSE 112: Networked Life, Spring 2004

Due: April 8 (NOTE CHANGE!!!)

  1. (20 Points)
    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 you described in the previous part.

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

  2. (25 Points)
    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.

  3. (OPTIONAL 5 Points Extra Credit)
    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.)

  4. (25 Points)
    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 you wrote above into a matrix game with the same payoffs.

    3. Write down a best strategies for each player.

  5. (30 Points)

    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" and briefly explain why it is 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).