Networked Life (CIS 112), Spring 2010 Prof Michael Kearns Homework 2 Issued April 13, 2010. Due as hardcopy in class Tue April 27. Don’t forget to staple and write your name. 1. (20 points) Consider diagrams of the kind discussed in Schelling’s “Micromotives and Macrobehavior” (see Figure 1, page 104 for an example), for modeling activities in which the number of people participating at the current round (the y axis) is a function of the number participating at the last round (the x axis). a. Carefully draw such a diagram in which there are 3 stable equilibria and 2 unstable equilibria. b. Carefully draw such a diagram in which there are 3 stable equilibria and 4 unsta ble equilibria. c. What can you say in general about the relationship between the number of unstable and stable equilibria in such models? 2. (20 points) Consider the hypothetical spread of a disease on a network. Each vertex represents an individual person who may or may not decide to receive a vaccination. Each edge represents potential contact between a pair of people. A person can contract the disease from any of his neighbors on the graph who are infected, but cannot contract the disease if none of his neighbors are infected. If an individual chooses to receive the vaccination, he pays a fixed cost V and runs no risk of obtaining the disease. If a person chooses not to receive the vaccination, he pays a cost equal to N*X where N is the number of his neighbors who are not vaccinated and X is a fixed cost associated with the chance of contracting the disease. Assume that X is much larger than V. a. Suppose everyone chooses to receive the vaccination. Is this an equilibrium? Why or why not? b. Suppose the government decides to subsidize half of the population by providing them with the vaccination for free (i.e. this half of the population pays 0 and runs no risk of obtaining the disease). Will the other ha lf of the population be more likely to purchase the vaccination now? Briefly explai n why or why not. 3. (20 points) This problem considers networked models of trade economies as discussed recently in class. a. For the networks below, write the equilibrium wealths or prices in the space beside each vertex, assuming all vertices are initially endowed with one unit of milk or wheat and have preferences only for the other good. Wealth: Wealth: b. Draw a network with 4 Milk and 4 Wheat players in which all the equilibrium wealth values of the Milks are 0.5, 0.5, 1 and 2. Milks Wheats Milks Wheats Wealth: Wealth:4. (20 points) Consider a network formation game in which each of N players may purchase edges from their own vertex to other players for a fixed cost of c per edge. Let G denote the network formed by the collective edge purchases of all players. The overall payoff to a given player X is then equal to the number of players X is connected to in G, minus the total edge expenditures of player X. By “connected to”, we mean reachable by any finite‐length path. Note that we view this as a one‐shot game, in which all players simultaneously decide which edges to purchase. a. Consider a network that is a simple cycle over the N players. Are there values for the edge cost c such that this network is an equilibrium of the formation game? If not, why not? If so, which value(s) of c? b. Consider a network that is a line or chain over the N players: 1 ‐‐‐ 2 ‐‐‐ 3 ‐‐‐ 4 ‐‐‐ 5 ‐‐‐ … ‐‐‐ N‐1 ‐‐‐ N Suppose that c = N/4. Is it possible for this network to be an equilibrium? If not, why not? If so, describe who would purchase which edges at equilibrium. c. Repeat part (b) but for edge cost c = 3N/4. d. Suppose that c = 6 and that N is very large. Consider the “universal” structural properties of social networks we discussed in the first half of the course: small diameter, heavy‐tailed degree distributions and high clustering coefficient. For each of these properties, briefly discuss whether the equilibrium networks of the formation game must always have the property, may sometimes have the proper ty, or will never have the property. 5. (20 points) Pick one of the three assigned readings describing human‐subject experiments on strategic behavior in networks. Carefully propose and describe a variation of the experiments from your chosen paper. For instance, you could modify the nature of the game being played, the incentives, the information available to participants, the network structures examined, etc. You should then clearly describe the hypothesis your proposed experiments are designed to test. Proposals will be graded for their clarity, originality, and dem o nstration of understanding of the findings in the original experiments.