Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS 580: Algorithmic Game Theory
Instructions:
1. Please read all the instructions and questions carefully before you start answering the ques-
tions. Also, please ask for clarifications early on (on Slack or Piazza).
2. This exam has four questions, 25 points each. That is worth 100 points. However, it will be
graded out of 75 points to allow you to drop some questions.
3. You can work with at most one other person on this exam, but you need to write the solution
on your own and submit. Please mention the name of the student you discussed with on your
submission. Completely identical solutions will be considered plagiarism and a violation of
the university code of conduct.
4. Please type your solutions, if possible, in Latex or doc, whichever is suitable, and submit
them on Gradescope.
5. Even if you cannot solve a problem completely, submit whatever you have. Partial proofs,
high-level ideas, examples, and so on.
6. Except where otherwise noted, you may refer to lecture slides/notes. You cannot refer to
textbooks, handouts, or research papers that have not been listed. If you do use any approved
sources, make sure you cite them appropriately, and make sure to write in your own
words.
7. No late submissions will be accepted.
1. Potential and Smoothed games
(a) (10 points) This problem develops some theory about potential games; we talked about
these while discussing selfish routing. We consider an abstract finite game with n players,
each with finite strategy sets, say Si for agent i ≤ n. Each player has a payoff function
πi mapping outcomes (elements of S1×· · ·×Sn) to real numbers. Recall that a potential
function for such a game is defined by the following property: for every outcome s ∈
S1 × · · · × Sn, every player i, and every deviation s′i ∈ Si.
πi(s
′
i, s−i)− πi(si, s−i) = Φ(s′i, s−i)− Φ(si, s−i).
A team game is a game in which all players have the same payoff function: π1(s) = · · · =
πn(s) for every outcome s. In a dummy game, the payoff of every player i is independent
of its strategy: πi(si, s−i) = πi(s′i, s−i) for every s−i and every si, s
′
i ∈ Si.
1
Prove that a game with payoffs π1, . . . , πn is a potential game (i.e., admits a potential
function) if and only if it is the sum of a team game πt1, . . . , π
t
n and a dummy game
πd1 , . . . , π
d
n (i.e., πi(s) = π
t
i(s) + π
d
i (s) for every i and s.)
(b) (15 points) Consider n identical machines and m selfish jobs (the players). Each job j
has a processing time pj . Once jobs have chosen machines, the jobs on each machine are
processed serially from shortest to longest. (You can assume that the pj ’s are distinct.)
For example, if jobs with processing times 1, 3, and 5 are scheduled on a common ma-
chine, then they will complete at times 1, 4, and 9, respectively. The following questions
concern the game in which players choose machines in order to minimize their comple-
tion times. The objective function as a planner is to minimize the total completion time∑m
j=1Cj , where Cj is the completion time job j.
i. (4 points) Define the rank Rj of job j in a schedule as the number of jobs on j’s
machine with processing time at least pj (including j itself). For example, if jobs
with processing times 1, 3, and 5 are scheduled on a common machine, then they
have ranks 3, 2, and 1, respectively.
Prove that in these scheduling games, the objective function value of an outcome
can also be written as
∑m
j=1 pjRj .
ii. (4 points) Prove that the following algorithm produces an optimal outcome: (i) sort
the jobs from largest to smallest; (ii) for i = 1, 2, . . . ,m, assign the ith job in this
ordering to machine i mod n (where machine 0 means machine n).
iii. (7 points) Prove that for every such scheduling game, the expected objective function
value of every coarse correlated equilibrium is at most twice that of an optimal
outcome.
Hint: The (λ, µ)-smoothness condition (see notes provided) was required for all pairs
s∗, s of outcomes. Weaken the definition so that this condition only needs to hold for
some optimal outcome s∗ and all outcomes s. Observe that PoA of coarse correlated
equilibria remains at most λ1−µ assuming only this weaker condition (with the same
proof as before). Prove that this scheduling game satisfies this weaker condition for
λ = 2 and µ = 0.
2. Nash equilibrium and Cost Sharing Games (25 points)
(a) (10 points) Consider an n player game in which each player has 2 strategies. For this
problem, think of the strategies as ‘on’ or ‘off’. For example, the strategy can be either
to participate in an event or not. Further more, assume that the game is symmetric, in
that all players have the same payoff functions, and that the payoff for a player depends
only on the strategy of the player and the number of players playing strategy ‘on’. So the
game is defined by 2n values: uon(k) and uoff (k), which denote the payoff for playing
the ‘on’ and ‘off’ strategies, assuming that k of the other players chose to play ‘on’ for
k = 0, · · · , n− 1.
Give a polynomial time algorithm to find a correlated equilibrium for such a game. Note
that the input to this game consists of the 2n numbers above. As usual, polynomial
means polynomial in this input length. You may use the fact that linear programming
is solvable in polynomial time.
(b) (15 points) Let us extend the model of network cost-sharing games that we covered
in class by
2
allowing each edge e to have a cost γe(x) that depends on the number x of agents that
use it. The joint cost γe(x) is again split equally between the x users of the edge. Assume
that each function γe is concave, meaning that
γe(i+ 1)− γe(i) ≤ γe(i)− γe(i− 1)
for each i = 1, 2, . . . , k − 1.
Note that, at a strategy profile P = (P1, . . . , Pn), if f
P
e many agents are using edge
e ∈ E then the cost of each individual agent i is Ci(P ) =
∑
e∈P
γe(fPe )
fPe
, and the total
cost is C(P ) = ∑e∈E:fPe >0 γe(fPe ). The optimum outcome is P ∗ ∈ argminP C(P ). Let
Hk denote the k-th Harmonic number, i.e. Hk =
∑k
i=1
1
i .
i. (6 points) Prove that in every network cost-sharing game with k players, there exists
a pure Nash equilibrium with cost at most Hk times that of an optimal outcome.
ii. (9 points) Prove that in every network cost-sharing game with k players, every strong
Nash equilibrium has cost at most Hk times that of an optimal outcome.
3. Fair division (25 points)
(a) (10 points) Consider the problem of fairly allocating chores instead of goods. Let M
be the set of m chores that need to be allocated to a set N of n agents. Agent i
incurs pain/disutility dij from chore j, and has additive disutility over subsets, i.e.,
for set S ⊆ M , di(S) =
∑
j∈S dij . Note that, agents want to minimize their overall
disutility/pain. Accordingly, an allocation A = {A1, A2, . . . , An} of chores is said to be
envy-free up to any item (EFX) if and only if for every agents i, k
di(Ai \ {c}) ≤ di(Ak), for all chores c ∈ Ai.
i. (3 points) Suppose the instance is binary, i.e., for each i ∈ N, j ∈ M , dij ∈ {0, 1}.
Design a polynomial-time algorithm to find an EFX allocation.
ii. (3 points) Suppose the instance is identical, i.e., for each j ∈M , dij = dj > 0, ∀i ∈
N . Design a polynomial-time algorithm to find an EFX allocation.
iii. (4 points) Suppose the instance is identically ordered. That is, for all agents i,
di1 ≥ di2 ≥ · · · ≥ dim > 0. Show through an example that the following modification
of the envy-cycle algorithm fails: Consider chores from the most painful to least
painful (from 1 through m). Starting with an empty allocation, allocate the next
unallocated chore to a sink in the envy-graph, recompute the envy-edges, and remove
cycles.
(b) (15 points) In this fair allocation problem, we are given a graph G = (V,E) and a set
of n agents. Every item is associated with a unique edge in G, that is the items set
is M = E. The valuations of the agents for the items are identical and additive, that
is, valuation of any agent i ≤ n for a subset S ⊂ M is v(S) = ∑g∈S v(g). We need
to allocate items to agents in a fair manner, with the additional constraint that the set
of edges that corresponds to each bundle needs to be acyclic in G. In other words, an
allocation A = (A1, A2, . . . , An) is valid if and only if Ei = {e ∈ E | e ∈ Ai} forms a
forest in G for every 1 ≤ i ≤ n.
3
i. (2 points) Consider two spanning trees T1 and T2 of G. Prove that for every edge
e ∈ T1, there exists an edge e′ ∈ T2 such that T1 \ {e} ∪ {e′} is a spanning tree.
In general, a stronger theorem holds, which states that there exists a bijection ϕ
from the edges of T1 to the edges of T2 such that, for every edge e ∈ T1, we have
that T1 \ {e} ∪ {ϕ(e)} is a spanning tree. You can use this stronger fact in the
subproblems below, but you don’t need to prove it.
ii. (12 points) Show that, for this fair allocation setting, if a feasible allocation A is not
EF1, then there exists a feasible swap such that the valuation of Ah - the highest
valued bundle violating EF1 with respect to the least valued bundle - drops by at
least a multiplicative factor of (1− 1/m2), or its cardinality decreases by one, where
m is the number of items.
iii. (6 points) Using the above, design an algorithm to find an EF1 allocation in this
setting.
4. (Revenue and Welfare) (25 points)
(a) (10 points) Consider the following problem of designing a posted price mechanism, which
relates to prophet inequalities. There are n buyers for a single item and we want to sell
the item to one of them. Each buyer i arrives at our shop with probability pi, and they
don’t arrive at all with probability 1 − pi. If buyer i arrives, their value for the item is
vi. The buyers choose to arrive or not independently of each other, and we know that∑n
i=1 pi = 1 (on expectation, one buyer will arrive).
Consider the following mechanism: When buyer i arrives, if we haven’t sold the item
yet, we sell it to i with probability 1/2, else we pass with probability 1/2. Show that
the expected value of this mechanism is a 1/4-approximation to the expected maximum
value maxi pivi.
Hint: Recall the proof of the prophet inequality; notice that
E[ALG] =
n∑
i=1
Pr[Item is sold to buyer i] · vi.
Use this, along with Markov’s inequality, to upper bound the probability the item is not
sold at all. Markov’s inequality says that for a non-negative random variable X and
value a > 0, we have Pr[X ≥ a] ≤ E[X]a .
(b) (5 points) This problem considers a variation of the Bulow-Klemperer theorem. Consider
selling k ≥ 1 identical items (with at most one given to each bidder) to bidders with
valuations drawn iid from F , where F is a regular distribution (i.e., the corresponding
ϕ−1 is a monotonically increasing function). Prove that for every n ≥ k, the expected
revenue of the Vickrey auction (with no reserve) with n + k bidders is at least that of
the Myerson’s optimal auction for F with n bidders.
Hint: Myerson’s optimal auction will be Vickrey with reserve ϕ−1(0), i.e., discard bids
below ϕ−1(0), give the item to k highest bidders and charge them max{(k + 1)th highest
bid, ϕ−1(0)}
(c) (10 points) In a combinatorial auction there are n bidders and m items. Bidder i has a
monotone valuation vi(·) where vi(S) is their value for item set S (and vi(S∪T ) ≥ vi(S)
for all S, T ). A Walrasian Equilibrium is a price vector p⃗ such that:
4
• Each buyer i selects to purchase a set Bi ∈ argmaxS{vi(S)−
∑
j∈S pj}.
• The sets Bi are disjoint, and
⋃
iBi = [m].
i. (2 points) Find an example of 2 items and 2 bidders where there is no Walrasian
equilibrium.
ii. (8 points) Prove that a Walrasian equilibrium exists for v1, · · · , vn if and only if the
optimum of the LP relaxation below (called the configuration LP) is achieved at an
integral point (i.e. where each xi,S ∈ 0, 1).
max
∑
i
∑
S
vi(S) · xi,S
s.t.
∑
S
xi,S = 1 ∀i∑
S:j∈S
∑
i
xi,S ≤ 1 ∀j
xi,S ≥ 0 ∀i ∀S
Note that, here xi,S = 1 implies set S is assigned to agent i.
Hint: Use strong duality of linear programming.