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
