Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS 5854 : Networks, Crowds, and Markets
Homework 1
Submission: Your written homework solutions must be typed and submitted as a single .pdf file on Gradescope.
You must additionally submit all relevant files specified in the assignment for all coding problems, in the appropriate
format. The format is important because your code will be partially graded by an autograder. Template .tex and
.py files will be provided containing an outline for your submission.
Late Days: Each student may use four “late days” in total for the first three assignments in the semester, each
of which grants a 24-hour extension to an assignment’s due date. Late work beyond this limit will still be accepted
and graded until grades have been released for that assignment, but (unless discussed in advance with the TA and/or
instructor) will have a negative impact on final grades.
Collaborations: You may work in groups of up to 3 students. Every member of the group must list all other
collaborators at the top of their assignment. (Note: the maximum size of a connected component of groups must be
3. If A,B, and C work together, it must not be the case that A and D work together.)
Your submitted answers, explanations, and discussion for all written questions in the pdf must be your
own, individual, unique solutions. You will receive ZERO points for written explanations which are copied
verbatim or copied with minor changes (up to the discretion of the TAs)—either from another group member or from
a cited online source. You will also receive ZERO points for submitting code which is copied verbatim or with minor
changes (up to the discretion of the TAs) from an online source. You may share and even submit the same code,
examples, figures, and graphs with your collaborators, but ALL explanations must be your own. Additionally, you
may make use of published material (papers, Github, Wikipedia, etc.), provided that you acknowledge and specifically
cite all sources used. Still, this does not give you permission to copy code/ explanations from an online source. It is
considered a violation of academic integrity to submit a problem solution that you are unable to explain orally to a
member of the course staff.
How to receive credit: You must justify all answers to receive credit unless specified otherwise. We will
do our best to make clear the level of justification we expect for each problem. For coding questions, please turn in
complete, executable code for each part of the question that asks for an implementation. All coding questions will
also include a written component which you will include in the main .pdf file. Using Python is required. We will not
grade code based on style, but we may mark down code if we are unable to understand what it is doing. You may
use standard libraries to implement data structures such as graphs, but, unless otherwise specified, you may not use
pre-existing implementations of any algorithms without express permission from the TAs. (If a problem asks you to
implement X and you use a package that implements X for you, you will not get credit.)
Grading: There will be four homeworks throughout the semester. Each homework (and each problem within
each homework) will receive an associated weight specified by a number of points. Your raw score at the end of the
semester will be the sum of points earned divided by the total number of available points. If your raw score is greater
than 94%, you are guaranteed to get at least an A, 90% for A-, 87% for B+, 84% for B, and so on. We reserve the
right to lower the cutoffs (but we will not raise them).
There will additionally be optional bonus problems on some assignments. These will not be factored into your
raw point totals, but will be factored in after computing your raw score to determine your final grade (for getting an
A+, or possibly bumping up 1 or 2 letter grades).
1
Part 0: Logistics
Slack: Join the slack channel for the course, via the following link: SLACK
Collaborators: If you need help finding a group to collaborate on the assignments with, you can
use Slack and/ or fill out THIS GOOGLE FORM. Cody will periodically match people who fill out
this form before HW1 is due.
Policies: Read the full homework policies and guidelines above. If there are any questions, please
ask them on slack before this first homework is due.
Submitting on Gradescope: All homeworks will be released on Canvas, and submitted on
Gradescope. In the process of submitting on Gradescope, please be sure to match your submission
pages to problem numbers. (This makes grading much easier; otherwise we have to do it for you).
When submitting code on Gradescope, please make sure the preliminary autograder correctly eval-
uates your submission; otherwise you will receive an incorrect grade. Finally, when submitting code
on Gradescope, you have the option of submitting individually, or as a group; take your pick.
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.
2
(b) What are player 1’s and player 2’s best-response sets given the action profile (m,L)?
Explain in words why these are the best responses.
(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. (Your proof should be near the level of formality used in the
book. Part of the point of this problem is to get familiar with formally arguing about
the definitions provided.)
(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.
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: Try
modifying a game where BRD does not converge to give it a unique PNE.)
5. Consider the following two-person game between a kicker (row player) and a goalie (column
player). Before the penalty kick, the kicker can decide to either kick to the left, middle, or
right, and the goalie can decide to either guard left, middle, or right. Based on what each
player decides, they have the following payoffs:
GL GM GR
KL (-1, 1) (-0.5, 0.5) (1,-1)
KM (0.5, -0.5) (-1,1) (0.5, -0.5)
KR (1,-1) (-0.5, 0.5) (-1,1)
Intuitively, this says that the goalie blocks the kick if they both choose the same direction.
The kicker scores a goal if they choose opposite directions. The goalie has a slight advantage
to guard the middle (it can better react if the kicker chooses left or right). And the kicker
has a slight advantage if it kicks middle and the goalie commits to left or right.
(a) Prove that there is no pure-strategy Nash equilibrium in this game.
(b) Suppose each player chooses each action uniformly at random (so 1/3 probability for
each available choice). Compute the expected utility for each player.
(c) The kicker notices that kicking to the middle is not working out very well for her, so
she decides to randomly kick to the left or right instead (each with probability 1/2).
Compute the goalie’s strategy that maximizes its expected utility. Specifically, provide
3
probabilities xL, xM , xR (such that xL + xM + xR = 1) where xL is the probability the
goalie chooses GL, xM for GM, and xR for GR. Then compute the expected utility for
the goalie under those probabilities. Justify why the value you computed is maximal,
i.e. is a best response.
(d) Bonus (and a hint for the previous question): Prove there will always exist a “pure”
best response to any mixed strategy above, where the goalie plays one of the actions
with probability 1.
(e) Prove that the mixed action profile from part (c) is a Nash equilibria. Namely, neither
player has a (strictly) profitable deviation.
Part 2: Graph Theory
Note: Unless stated otherwise, please assume for any problem involving graphs that we refer to
undirected and unweighted graphs.
6. 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, your explanation
should tell me how to construct such a graph for that c. 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.
7. 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 average distance A and 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?
8. 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.
- 经济Economics
- 金融Finance
- 会计Accounting
- 工商管理Business Management
- 计算机computer science
- 商业分析business analysis
- 法律Law
- 管理Management
- 市场营销Marketing
- 哲学Philosophy
- 心理学Psychology
- 物理Physical
- 统计学statistics
- 电气工程electric engineering
- 化学chemistry
- 生物biology
- 数学mathematics
- 语言学linguistics
- 土木工程civil engineering
- 工程力学engineering mechanics
- 艺术art
PROFESSIONAL HELP!
在线咨询
立即下单
Wechat：THEend8_ 
Email：