[SOLVED] Cs 5854 : networks, crowds, and markets homework 1

Part 0: Slack
Join the slack channel for the course, via the following link: SLACK
Part 1: Game Theory
1. For each of the following three two-player games, find (i) all strictly dominant strategies, (ii)
the action profiles which survive iterative removal of strictly dominated strategies, and (iii)
all pure-strategy Nash equilibria. Give a brief justification for each part.
(a)
(∗, L) (∗, R)
(U, ∗) (5, 4) (4, 5)
(D, ∗) (4, 4) (0, 0)
(b)
(∗, L) (∗, R)
(U, ∗) (2, 2) (2, 1)
(D, ∗) (3, 2) (0, 3)
(c)
(∗, L) (∗, R)
(U, ∗) (6, 5) (4, 5)
(D, ∗) (5, 4) (2, 2)
2. Consider the two-player game given by the following payoff matrix:
(∗, L) (∗, M) (∗, R)
(t, ∗) (-1, 2) (5, 1) (0, 0)
(m, ∗) (1, 2) (-1, 0) (6, 2)
(b, ∗) (4, 1) (3, 1) (2, 0)
(a) Does either player have a strictly dominant strategy? If so, which player, what strategy,
and why? If not, what is the smallest number of entries in the payoff matrix which would
need to be changed so that some player did have a strictly dominant strategy? Justify
why this is the minimum, i.e. there is no smaller value that works.
(b) What are player 1’s and player 2’s best-response sets given the action profile (m, L)?
(c) Find all pure-strategy Nash equilibria for this game. (Argue why all that you wrote
are PNEs and why there are no others.) Describe how best-response dynamics might
converge to each pure-strategy Nash equilibria.
3. (a) Prove the following: If player 1 in a two-person game has a dominant strategy s1, then
there is a pure-strategy Nash equilibrium in which player 1 plays s1 and player 2 plays
a best response to s1.
(b) Is the equilibrium from part (a) necessarily a unique pure-strategy Nash equilibrium?
Justify your answer.
(c) In particular, can there also exist a pure-strategy Nash equilibrium where player 1 does
not play s1? Justify your answer.
(d) If s1 is instead a strictly dominant strategy for player 1, how do the answers to (a)-(c)
change? Provide proper justifications for each part.
2
4. Formulate a normal-form game (as a payoff matrix) that has a unique pure-strategy Nash
equilibrium, but for which best-response dynamics does not always converge (i.e. there are
possible starting states for which BRD will not converge). Justify your answer. (Hint: Rockpaper- scissors has no equilibrium, and thus BRD will not converge. Can you combine this
with a game that does have an equilibrium?)
Part 2: Graph Theory
Note: Unless stated otherwise, please assume for any problem involving graphs that we refer to
undirected and unweighted graphs.
5. Given a graph, we call a node x in this graph pivotal for some pair of nodes y and z if x (not
equal to y or z) lies on every shortest path between y and z.
(a) Give an example of a graph in which every node is pivotal for at least one pair of nodes.
Explain your answer.
(b) For any integer c ≥ 1, construct a graph where every node is pivotal for at least c
different pairs of nodes. That is, if I give you any value for c ≥ 1, you should be able to
give me such a graph. Explain your answer.
(c) Give an example of a graph having at least four nodes in which there is a single node x
which is pivotal for every pair of nodes not including x. Explain your answer.
6. Given some connected graph, let the diameter of a graph be the maximum distance (i.e.
shortest path length) between any two nodes. Let the average distance be the expected
shortest path length between a randomly selected pair of distinct nodes.
(a) Let G be a graph with average distance A. What is the smallest diameter possible for
such a graph? Provide a graph G that attains this minimum and prove that any smaller
is impossible.
(b) Give a graph G with diameter at least 3 · A.
(c) Repeat (b) for a diameter of at least 100 · A. (You don’t need to draw the graph, just
describe it and briefly justify why the diameter is at least 100 times larger than than
the average distance.) Describe how you could extend this to an arbitrarily large factor
C · A.
(d) Discuss what the diameter and average distance of a social network (given as a graph)
might represent. What might it mean if the diameter is very similar to the average
distance? What might it mean if the diameter is much greater?
7. Consider a graph G on n nodes.
(a) What is the fewest number of edges such that G is connected? Give an example with
that many edges, and argue why any fewer edges must result in a graph G which is
disconnected.
(b) What is the fewest number of edges such that any two nodes in G have a shortest path
length of 1? Again, prove that this is the minimum by arguing that no fewer is possible
and that the number you give is attainable.
3
(c) Repeat part (b) for a shortest path length of at most 2.
Part 3: Coding: Shortest Paths
8. Submit the following:
(a) In graph.py, implement (and turn in) a function create graph(n,p) that produces an
undirected graph with n nodes where each pair of nodes is connected by an edge with
probability p.
(b) Implement a general shortest-path algorithm for graphs, as described in lecture, that
works on your graph. In graph.py, include a function shortest path(G,i,j) that outputs
the length of the shortest path from node i to j in your graph G. Make sure to handle
the case where the graph is disconnected (i.e. no shortest path exists) by outputting
“infinity”.
(c) Construct a graph for n = 1000 and p = 0.1. Estimate the average shortest path between
a random pair of two (connected) nodes in the graph. For accuracy, repeat for 1000
random pairs of nodes in your graph. Output an execution trace in avg shortest path.txt
containing all path lengths written as (i, j, length).
(d) For n = 1000, run the shortest-path algorithm on data sets for many values of p (for
instance, 0.01 to 0.04 using .01 increments, and then 0.05 to 0.5 using .05 increments).
Turn in your numerical data as varying p.txt, and plot the average shortest path as a
function of p and submit as an image file varying p.(image extension) or include in your
main .pdf file.
Note: For p = 0.01 there is actually a small but reasonable chance (around 4%) to
produce a disconnected graph. If this occurs, resample and produce a connected graph
for the purposes of gathering data.
(e) Intuitively explain the behavior of the data you found; specifically, as p increases (in
particular, look at the larger values, e.g. 0.3 and above), what function does the average
shortest path length seem to asymptotically approach and why?
9. Now run your code on the Facebook social network data available at:
http://snap.stanford.edu/ data/egonets-Facebook.html
(In particular, please refer to the file “facebook combined.txt.gz”; the data is formatted as
a list of undirected edges between 4,039 nodes, numbered 0 through 4038. You will need to
parse this data as part of your code; knowing how to do this will be useful for subsequent
assignments!)
(a) Repeat the same analysis as in part 8(c) (i.e. run your algorithm on 1000 random pairs
of nodes and determine the average shortest path length). Include your code in graph.py
and include an execution trace in fb shortest path.txt
(b) For the Facebook data, estimate the probability p that two random nodes are connected
by an edge. Explain how you computed p.
(c) Is the average shortest path length of the Facebook data greater than, equal to, or less
than you would expect it to be if it were a random graph with the same number of nodes
and value of p? (To answer this, you may wish to run your code from question (8c) using
4
the p you determined in part (9b) and 4039 nodes.) Explain why you think this is the
case.
5