Networks, Crowds, and Markets Homework 2 Solution

Part 1: Best-Response Dynamics

    1. (a) Let G1 and G2 be games with the same set of players and action sets for each player, and assume that BRD converges to a PNE in both of these games. Consider a game G = (G1 + G2) where each player plays a single action for both G1 and G2 (i.e. plays the same action in both games at the same time) and receives utility equal to the sum of the utilities they would earn from G1 and G2. Will BRD converge in this game? If so, prove it; if not, nd a counterexample and argue why it doesn’t converge. (Hint: Start with a game that may not converge and try to split it into two separate games.)

        (b) Assume in a particular game G = G1 + G2 that BRD does converge. Will it necessarily converge to a state that is also a PNE in either G1 or G2? If so, prove it; if not, nd a counterexample.

    2. Consider the process of \better-response dynamics" rather than BRD, where instead of choos-ing a player’s best response (i.e. the response that maximizes their utility given others’ ac-tions), a player chooses any response that strictly increases their utility given other players’ actions.

        (a) Does the process of \better-response dynamics" still converge in games for which there is an ordinal potential function ? Prove it or show a counterexample. (Hint: This is in the notes now. It su ces to reference the correct theorem.)

        (b) Can you think of a game for which BRD converges but \better-response dynamics" might not? Show an example or justify that one doesn’t exist. (Hint: Remember that the better-response dynamics graph can have edges that the BRD graph might not. What if those edges formed a loop?)

    • Bonus Question 1. Recall the Traveler’s Dilemma that we studied in chapter 1. We have already illustrated why BRD converges in this game; nd a weakly ordinal potential function over states of this game and use it to de nitively prove the convergence of BRD. Make sure to justify that the potential function you nd is weakly ordinal (you can do this via computer if you wish).

    • Bonus Question 1.5. (This may be very di cult! ) Determine whether better-response dy-namics converge for the Traveler’s Dilemma. No formal proof is necessary, and you need not come up with a potential function. You are free to either use simulations, show (experimen-tally) that the graph contains no cycle, or nd an ordinal potential function and either prove it or experimentally verify.

Part 2: Networked Coordination Games

3. Consider the following simple coordination game between two players:


( ;X)
( ;Y)
(X; )
(x; x)
(0, 0)
(Y; )
(0, 0)
(y; y)


Show how we can pick x and y and then modify this payo matrix by adding an intrinsic utility for a single player and a single choice (e.g. give player 1 some intrinsic utility for choice Y ) such that the socially optimal state of the game is no longer an equilibrium.

    4. Consider a networked coordination game on a complete graph of ve nodes. Assume for simplicity that all edges represent the same coordination game (that is, Qe(X; X) = Qe0 (X; X)

for any pair of edges e; e0, and respectively for Y , but it is not necessarily the case that Qe(X; X) = Qe(Y; Y )), and that all nodes have the same intrinsic values for X and Y (that is, Ri(X) = Rj (X) for any nodes i; j, and respectively for Y ).

    (a) Show a possible assignment of intrinsic and coordination utilities such that every pure-strategy Nash equilibrium of the resulting game must be socially optimal. Justify that this holds for your construction.

    (b) Is there a possible assignment of intrinsic and coordination utilities such that there exists a pure-strategy Nash equilibrium with social welfare less than half of the maximum attainable social welfare? If not, prove it. If so, show such an assignment and explain why your construction does not violate Theorem 4.5 from the notes (the price of stability). (Hint: Theorem 4.5 only talks about the best equilibrium. Try to make a simple two-node game with one very good equilibrium and one bad equilibrium, and then extend what you nd there to the ve-node graph. It also won’t be necessary to use intrinsic values for this part.)

Part 3: Cascading Behavior in Networks

    5. Consider the network in Figure 1. Suppose that each node starts with the behavior Y , and has a q = 2=5 threshold for adopting behavior X. (That is, if at least 2/5 of a node’s neighbors have adopted X, that node will as well.)

        (a) Let e and f form a set S of initial adopters of X. Which nodes will eventually switch to X? (Assume that S will not participate in BRD.)

        (b) Find a cluster of density 1 q = 3=5 in the part of the graph outside S which blocks X from spreading to all nodes starting from S.

        (c) Add one node to S such that a complete cascade will occur at the threshold q = 2=5. Demonstrate how the complete cascade could occur (i.e. in what order nodes will switch).

    6. (a) Formulate a graph G, threshold q, and set S of initial adopters such that, assuming we start with S choosing X (and, importantly, able to participate in BRD) and other nodes choosing Y , we can either end up with every node in G playing X or with every node in G playing Y , depending on the order of switches in the BRD process.

        (b) What must be true of the set density of S for the above property to hold?

        (c) What must be true of the set density in any subset of V n S for the above property to hold?

Part 4: Tra  c Networks



3
















Figure 1: Question 5.


    7. There are two cities, A and B, joined by two routes which pass through towns C and D respectively. There are 120 travelers who begin in city A and must travel to city B, and may take the following roads:

a local street from A to C with travel time 15 + x, where x is the number of travelers using it,

a highway from C to B with travel time 90,

a highway from A to D with travel time 90, and

a local street from D to B with travel time 15 + y, where y is the number of travelers using it.

    (a) Draw the network described above and label the edges with their respective travel times. The network should be a directed graph (assume that all roads are one-way). Note: you may just describe the graph if you are typing the assignment up.

    (b) Find the Nash equilibrium values of x and y. (Show that this is the equilibrium.)

    (c) The government now adds a new two-way road connecting the nodes where local streets and highways meet. This new road is extremely e cient and requires no travel time. Find the new Nash equilibrium.

    (d) What happens to the total travel time as a result of the availability of the new road? (You don’t need to explain, a calculation is ne.)

    (e) Now suppose that the government, instead of closing the new road, decides to assign routes to travelers to shorten the total travel time. Find the assignment that minimizes the total travel time, and determine the total travel time using this assignment. (Hint: It is possible to achieve a total travel time less than the original equilibrium. Remember that, with the new road, there are now four possible routes that each traveler can take.)

Part 5: Experimental Evaluations




4

    8. This problem will make use of the data set available at: [http://snap.stanford.edu/data/egonets-Facebook.html].

In particular, please refer to the le \facebook combined.txt.gz"; it contains a text le listing all 88,234 edges (undirected edges representing Facebook friendship) in a sampled 4,039-node network (nodes are numbered 0 to 4038). It will be useful, for problem 8 to be able to input a graph presented in such a format into your code.

        (a) Consider the contagion examples that we observed in chapter 5 of the notes. Given an undirected graph, a set of early adopters S, and a threshold q (such that a certain choice X will spread to a node if more than q fraction of its neighbors are playing it), produce an algorithm that permanently infects the set S of early adopters with X and then runs BRD on the remaining nodes to determine whether, and to what extent, the choice will cascade through the network. (Note: \BRD" in this case is simply the process of iteratively deciding whether there is a node that will switch its choice and performing this switch.)

Once again, turn in your code and veri cation that your algorithm works on a few simple test cases. In particular, include the output on the two examples from Figure 4.1 in the notes; let S be the set of nodes choosing X in the gure, and, for each of the two graphs, include one example with a complete cascade and one without one (and specify what value of q you used for each).

        (b) Run your algorithm several (100) times on a fairly small random set of early adopters (k = 10) with a low threshold (q = 0:1) on the Facebook data set. What happens? Is there a complete cascade? If not, how many nodes end up being \infected" on average?

        (c) Run your algorithm several (10) times with di erent values of q (try increments of 0.05 from 0 to 0.5), and with di erent values of k (try increments of 10 from 0 to 250). Observe and record the rates of \infection" under various conditions. What conditions on k and q are likely to produce a complete cascade in this particular graph, given your observations?


        ◦ Bonus Question 2. (Optional, extra credit awarded depending on quality of solution.) Design an algorithm that, given a graph and a threshold q, nds (an approximation of) the smallest possible set of early adopters that will cause a complete cascade. Try running it on the Facebook data with di erent values of q and seeing how large a set we need.

    9. Consider the following problem: There are n Uber drivers and m potential riders. At a xed point in time, each driver has a list of compatible riders that she can pick up. Our goal will be to match drivers to riders such that the most riders at this time are picked up. We will use the maximum- ow algorithm, described in Chapter 6 of the notes to do this.

    (a) First, implement an algorithm that, given a directed graph, a source s, a sink t, and edge capacities over each edge in E, computes the maximum ow from s to t (you must implement this algorithm yourself). Turn in your code and verify that your algorithm works on a few simple test cases. In particular, test your algorithm on the graphs in Figures 6.1 and 6.3 from the lecture notes and submit the output.


5

    (b) Given a set of n drivers, m riders, and sets of possible riders that each driver can pick up,

        i. explain how we can use this maximum- ow algorithm to determine the the maximum number of matches, and

        ii. explain how we can additionally extend this to actually  nd the matchings.

(Hint: See the notes if you are confused about how to do this.)

    (c) Implement a maximal matching algorithm for Uber drivers and riders. Speci cally, given n drivers with constraints speci ed on m riders, computed the assignments of drivers to riders. Test your algorithm on at least 2 examples (with at least 5 riders and drivers each). Explain your examples and your results.

    (d) Now consider the case where there are n drivers and n riders, and the drivers each driver is connected to each rider with probability p. Fix n = 1000 (or maybe 100 if that’s too much), and estimate the probability that all n riders will get matched for varying values of p. Plot your results.

    • Bonus Question 3: In the above example, let p (n) be the smallest value of p where all n riders get matched with at least 99% probability. Prove bounds on what p (n) is as a function of n, e.g. is p (n) 1=n or p (n) 1=2. You will get partial credit for providing experimental evidence towards a proposed idea.





































6