Problem Set 4

CSE 112: Networked Life, Spring 2004

Due Thursday April 22, 9am

This problem set has five (5) problems for a total of 100 points, with 5 points of extra credit possible. Several of the problems have several parts.

  1. 25 points.

    For each of the following scenarios state whether or not it corresponds to a multiplayer prisoner's dilemma (MPD). (The MPD concept is discussed in detail in Schelling, pp. 217-237.) If the scenario does not describe a MPD, write the conditions for an MPD that are not satisfied and describe how these conditions are not satisfied. In all cases, sketch the payoff graphs that correspond to those shown in Schelling. If you make any assumptions, state them clearly!

    1. The EU countries are considering creating an EU Army. Each individual country has the option to denote a fixed number of troops to the communal project or to not donate any. All countries will benefit from the army, even those that didn't contribute to it.

    2. N fishermen want to build a lighthouse. The lighthouse has a fixed cost. Each fisherman has the option either to chip in or not.

    3. American politicians are discussing a potential high-speed magnetic levitation (mag-lev) train, connecting Boston-NYC-Philadelphia-Washington DC. As the track has to go mostly in a straight line, it is unavoidable that it passes through N smaller towns. Each of the towns' mayors can either tolerate the track or demand that the train can only pass if it also stops (which gives the town a great connection to the big cities and makes it very attractive to commuters). The fewer stops the train has, the faster and the more profitable it is. If it stops in every little town, it would be no faster than the already existing Amtrak and the politicians would not decide to build it.

    4. N teenagers all want to go to a house party. The location is very small. If too many people show up, it will be very crowded and not much fun. If not enough show up, it will be very empty and dead.

    5. In some class (a long long time ago in a universe far far away) students had the choice to go to recitations or not. Generally the recitations were regarded as a pain and the students didn't actually benefit from attending them. However, if very few students showed up, the TAs got the impression that the class must be too easy and increased the difficulty of the homework assignments.

  2. 20 points.

    Richy (row player) and Carol (column player) play a repeated two-action matrix game. Both follow a certain procedure:

    Let pn denote the probability that Richy plays row 1 in the n-th repetition of the game. And let qn be the probability that Carol plays column 1. Also let R( p , q ) and C( p , q ) be their respective payoffs under strategies p and q.

    Initially in the first game (n = 1), both play some random mixed strategy, which is not a Nash equilibrium.

    Now, let α be some small positive real number, close to zero.

    Afterwards, in the n-th game, Richy plays pn = pn-1 + α*(R(1, qn-1 ) - R( pn-1 , qn-1 ) )

    ... while Carol plays qn = qn-1 + α*(C( pn-1 , 1 ) - C( pn-1 , qn-1 ) )

    The repeated game ends if both player's strategies converge.

    1. What would happen if Richy and Carol's first strategy pair was a Nash equilibrium?
    2. Give a fairly brief argument (no more than 50 words) as to why someone might play like Richy and Carol.
    3. Select two games from those that have been discussed in class. For the first game, Richy's and Carol's way of playing should converge to a Nash equilibrium. For the second, both should keep playing forever. Write down what the two games are (give the matrices as well as the names of the games), stating which leads to convergence and which does not.
    4. What is the fundamental difference between the two games found in the previous question that leads to the different convergence behavior?

  3. 10 points.

    Write optimal strategies (ones that do the best they possibly can) for 100-turn repeated games. The strategies are to play against the following strategies:

    1. The opponent plays randomly, with both actions equally likely.
    2. The opponent plays left initially. The opponent plays left on future moves unless your previous move was to play bottom.

    This is the payoff matrix for the game. "You" are the row player, "the opponent" is the column player:

    3,3  0,5
5,0  1,1

    To get credit, you must specify your strategies exactly. You may write your strategies in STRANGE if you like, although this isn't required. You may also use the J-PRISON applet to run strategies against each other and see the result, but this isn't required. The applet does not seem to run under Windows, but should work on the Towne lab computers and on Macs. The applet is not supported, however.

  4. 15 points.

    Consider a network of 8 buyers (1-8) and 8 sellers (A-H) connected as follows:

    Trade can only occur along these connections. Let each buyer have $1 and have utility only for wheat; let each seller have 1 unit of wheat and have utility only for money. Exchanges have to be in increments of one cent and 1/100s of a unit of wheat. At equilibrium, how much wheat does each buyer get and how much does each seller make? (Answers that are correct to within 1/100 a unit of wheat / 1 cent will be accepted.)

  5. 30 points. (+5 points extra credit.)

    In an essay of between 300 and 500 words, explain how an understanding of network science (the overall topic of this class) can benefit (a) an individual person, (b) a corporation or other large-scale actor in an economy, and (c) a government. Give specific examples and scenarios for all three cases, explaining how each is related to the overall concepts of network science and showing what specific benefit would be obtained. Connect these specifics to more general principles that have been discussed in the lectures and in the readings. You should begin with a sentence that gives your definition of network science.

    Some of the things we've studied in class are preliminaries or components of a network science approach, but are not part of the new developments of network science. For instance, you shouldn't write about how an understanding of probability can help an individual.

    You may use one or more examples that have been discussed in lectures or in the readings, but you should explain them in your own words and connect them to the general concepts of networked science yourself. If you use an example that has been previously given, note where it came from. It is appropriate to refer to specific research and discussions by giving the name of the researcher or writer, but unless you're quoting directly (which you should do only for brief quotations) you are not required to give a detailed citation with page numbers.

    Your grade will be based on how complete your essay is, how clear and correct your discussion of the concepts is, whether you used appropriate citation, and how well you describe the individual examples and scenarios in the overall framework of network science.

    5 points extra credit will be awarded if all of your examples and scenarios are original (not discussed in lectures or readings.) Write "extra credit requested" at the top of your essay if you would like it to be considered for extra credit. The difference has to be more than superficial to earn you extra credit.