## Description

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, find 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, find a

counterexample.

2. Consider the process of “better-response dynamics” rather than BRD, where instead of choosing a player’s best response (i.e. the response that maximizes their utility given others’ actions), 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 suffices 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; find a weakly ordinal potential function

Φ over states of this game and use it to definitively prove the convergence of BRD. Make sure

to justify that the potential function you find is weakly ordinal (you can do this via computer

if you wish).

* Bonus Question 1.5. (This may be very difficult!) Determine whether better-response dynamics 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 (experimentally) that the graph contains no cycle, or find 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)

2

Show how we can pick x and y and then modify this payoff 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 five nodes. Assume for

simplicity that all edges represent the same coordination game (that is, Qe(X, X) = Qe

0(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 purestrategy 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 twonode game with one very good equilibrium and one bad equilibrium, and then extend

what you find there to the five-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 S for the above property to

hold?

Part 4: Traffic 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 efficient 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 fine.)

(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 file “facebook combined.txt.gz”; it contains a text file 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 verification 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 figure, 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 different values of q (try increments of 0.05

from 0 to 0.5), and with different 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, finds (an approximation

of) the smallest possible set of early adopters that will cause a complete cascade. Try

running it on the Facebook data with different 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 fixed

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-flow 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 flow 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-flow algorithm to determine the the maximum

number of matches, and

ii. explain how we can additionally extend this to actually find 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. Specifically, given

n drivers with constraints specified 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