EEE 598: Game Theory: Models, Algorithms and Applications
Assignment 4 (40 Points)
March 16, 2022
• Deadline: Friday, April 18 at 11:59 pm (Arizona time).
• Format: The only accepted format is PDF. Put your name and student number on your submission.
You can type your solutions (e.g., in LATEX), write your solutions using note-taking apps, or scan
your handwritten solutions. For the scanning option, you need to use a scanner or a scanner app to
have a pdf file of reasonable size. Also, make sure your handwriting is legible and well-organized.
• Questions about the assignment: If you have any question regarding a problem, consider using
Canvas Discussion so that you can benefit from and contribute to everyone’s learning and might
generate new insights/comments.
• Feel free to use any course material such as slides, notes, suggested books, and online resources. You
can also discuss the questions with your classmates. However, each student needs to submit their own
solutions. Also, please write the solutions based on your own understanding (i.e., no copy/paste).
• IMPORTANT NOTES: 1) For every question, you need to explain/elaborate how you obtain/derive
the solutions without using tools such as Matlab and Python. You can only use these tools/solvers
when I specifically ask you to do so. 2) Please try your best to answer every question, even if you don’t
know how to solve it. I can only give you some points for questions that you attempt to solve. Don’t
leave any blank.
• Cheating is strictly prohibited. The grader can easily detect cheating (i.e., find out if you copy solution
of someone else). All students, who are cheating, will get zero points.
1
1 Problem 1 (4 points)
Consider the extensive-form game in Figure 1.
Figure 1: Problem 1
1) How many pure strategies does each player have? List all pure strategies of P1 (1 point).
2) How many subgames does this game have (1 point)?
3) Find a SPE of this game (2 point). Hint: Backward induction, check which subgames are simultaneous.
2 Problem 2 (4 points)
Figure 2: Problem 2
1) Describe the game shown in Figure 2 (1 point). How many subgames do we have? (1 point)
2) Assume that the players are rational. Find the optimal value of x that P1 should choose to maximize
her payoff (2 points). Hint: backward induction, using similar analysis for the Cournot game between 2
firms to find y and z first. Specifically, δu1δy = 0 and
δu2
δz = 0. Then you can write y and z as a function of x.
Then, write u1 as a function of x. Then, which x will maximize u1.
2
3 Problem 3 (6 points)
Repeated game. Consider the Cournot duopoly games mentioned in the class. There are two firms. Each
needs to decide the production quantity (qi for firm i). The production cost is c per unit. The price
per unit depends on the total quantity, i.e., P = a − (q1 + q2). Assume a > c. The payoff of firm i is
ui(q1, q2) = qi(P − c) = qi(a− q1 − q2 − c).
1) What is the Nash equilibrium of this game if two firms make their decisions simultaneously? What
are the production level (i.e., quantity) and payoff (i.e., profit) of each firm in this case? (1 points) Hint: to
find optimal production of each firm, use the fact that derivative = 0 at optimality.
2) Now firm 1 decides q1 first. Firm 2 observes the amount chosen by Firm 1, and reacts and chooses q2.
What is the equilibrium in this case? (i.e., Stackelberg equilibrium, sequential equilibrium). What are the
production level (i.e., quantity) and payoff (i.e., profit) of each firm in this case? (2 points).
3) Can we achieve cooperation in a repeated version of this game? In other words, under which condition
of the discount factor α, the trigger strategy is a subgame perfect equilibrium (SPE)? (3 points) The trigger
strategy is as follows: play cooperation if both have been playing it. If either player deviates, switch to the
non-cooperative strategy (i.e., NE). Consider two cases: case 1 where no one has ever defected. case 2 where
one of the players had defected at time t. Verify under which condition of the discount factor α, no players
has incentive to deviate (i.e., no profitable deviation).
4 Problem 4 (7 points)
Recall the wireless transmission game of homework 1: two wireless transmitters, which can transmit at high
power (H) or low power (L). The transmission rate that they can achieve depends on both their transmission
power and on the other player’s decision, according to the following payoff matrix:
Table 1: Wireless Transmission
L H
L (2, 2) (0, 3)
H (3, 0) (1, 1)
They both want to maximize their transmission rate, and they have to transmit T packets. In contrast to
the case in HW1, now they can observe the other player’s strategy after they both transmit a packet (after
each stage of the game).
a) How many strategies does each player have? (1 point) Hint: use induction, check how many information
sets that each player has at stage t of the game. Then, check how many pure strategies for each of their
information sets.
b) Draw the game in extensive form for T = 2 packets. (1 point) Hint: check lectures to see how to
express a simultaneous game at each stage.
c) Determine the subgame perfect equilibrium for T = 2. (1 point)
d) How many information sets does each player have for T = 200? Determine the subgame perfect
equilibrium in this case. (1 point)
Consider now the case in which players have to transmit packets indefinitely T = ∞. To make the
problem well-posed we need the players’ costs to be finite. So, consider the following cost for each player i :
Ui = (1− α)
T∑
t=0
αtui(t), (1)
where 12 < α < 1 and ui(t) is the payoff of player i at stage (packet) t (as written in the payoff matrix
above).
e) Consider the strategy in which both players always play H. What is the outcome, when T = ∞? Is
this a Nash Equilibrium strategy? (1 point)
f) Consider the trigger strategy: a player i playing the trigger strategy starts by playing L, and keeps
playing L. However, if the other player plays H, then player i changes to H, and keeps playing H for the rest
3
of the game. What is the outcome, when T = ∞, if all players play the trigger strategy? Is this a Nash
Equilibrium strategy? (2 point) (Hint: Check the repeated game lectures).
5 Problem 5 (6 points)
Consider a cooperative game G(N, v), where N = {1, 2, 3, 4} (i.e., 5 players). The characteristic function is
v(∅) = 0;
v(1) = v(2) = 1; v(3) = v(4) = 2;
v(1,2) = 3; v(1,3) = v(2,3) = 4; v(1,4) = v(2,4) = 5; v(3,4) = 6;
v(1,2,3) = 6; v(1,2,4) = 6; v(1,3,4) = v(2,3,4) = 8;
v(1,2,3,4) = 11;
1) What is the optimal coalition for this game? (1point) Hint: check superadditive condition.
2) Is the payoff vector (2,2,3,4) in the core of this game? What is the core of this game (i.e., show the
core conditions in the explicit form)? What is the least-core of this game? (3 points)
3) What is the Shapley value payoff division of this game? Show the the Shapley value payoff division
satisfy the symmetry, dummy player, and additivity axioms. (2 points).
6 Problem 6 (6 points)
Consider an auction to sell frequency spectrum licenses for 10 and 20 MHz in the East and West directions.
The four possible options are shown below.
Table 2: Problem 6
Geographic direction
Bandwidth West-20 East-20
West-10 East-10
There are five bidders. In our problem, each bidder is interested for a particular combination of these
options. Let their bids be denoted by xi, i = 1, ..., 5 and be as follows:
x1(West-20, East-20) = 90,
x2(West-10, East-10) = 100,
x3(West-20, East-20) = 110,
x4(East-20, East-10) = 100,
x5(West-20, West-10) = 100.
The interpretation of the above is that bidder 1 desires the 20 MHz spectrum in both the West and East
directions and is willing to pay $90 for it. Determine the winners and the price each winner pays to the
auctioneer in
a) the pay-as-bid mechanism (first-price auction) (2 points)
b) the VCG mechanism (4 points)
Hint: here we have multiple items for sale. The seller wants to sell 4 spectrum licenses to 5 bidders.
Thus, we may have multiple winners, not just one. Let zj ∈ {0, 1} denote the binary indicator which is
equal to 1 if bidder j wins. The goal of the auctioneer is to maximize the social welfare
∑
i xizi (technically,
it should be the sum of bidders’ net utility (aka utility - payment) and the auctioneer’s (or seller’s) revenue.
But the revenue = total of payments from the bidders. Thus, the payment terms are cancelled out. Hence,
the social welfare =
∑
i xizi). Under the VCG mechanism, in step 2, you need to solve the social welfare
maximization problem, considering all bidders and taking into account the resource capacity constraint (i.e.,
you cannot more than what you have, here are 4 items). You can actually solve this problem analytically
and easily see which zi should be 1. In step 3, to compute the payment for every player j, you need to solve
the social welfare problem for all players, except player j (i.e., without the participation of j, who would
win?). Then, you obtain the payment of each player j following the formula in Step 3.
4
7 Problem 7 (7 points)
Collusion and Shill-bidding
Consider an auction for two items: A and B. Bidder 1 is willing to pay 2 million dollars for both items
together and is not interested in getting the items individually. Bidder 2 is only interested in item A, which
she values at 0.5 million dollar. Bidder 3 is only interested in item B, which he values at 0.5 million dollar.
Suppose the auctioneer is running the VCG mechanism.
a) Who is/are the winner(s) and what are the corresponding profit(s) (utilities) each winner makes? (1
point)
b) Show that by coordinating together, bidders 2 and 3 can collude. Namely, they can report a higher
value for each item than their true values to win the auction while making positive profit. What is the
maximum profit they can make by colluding? (2 points)
The reason for the possibility of profiting from collusion in the above example is that the utilities obtained
from the mechanism do not necessarily belong to the so-called Core, for every set of bids.
Let N denote a set of N bidders. Recall that the utility, also referred to as payoff, of a player j ∈ N is
0 if she is not a winner in the auction, and otherwise, is Jj = vj − pj , where vj is her total valuation for
the item(s) she submits bids for and pj is her payment to the auctioneer. Denote the auctioneer as player
0. The utility of the auctioneer is denoted by J0 ∈ R; this is the total payment collected by the auctioneer.
Let the bid profile of all bidders N be denoted by x = (x1, ..., xN ), where xj = (cj ,mj) is the price-item
pair. The Core is defined as
core(G) :=
{
(J0, . . . , JN )|
N∑
j=0
Jj = J(N),
∑
j∈S⋃{0} J
j ≥ J(S), ∀S ∈ N
}
(2)
c) Formulate the set of equalities and inequalities for the Core corresponding to the first set of bids in
the start of the problem (player 1 bidding $2 million and players 2 and 3 bidding $0.5 million for each item).
Verify that the VCG utilities are in the core. Show that for the case in b) where the collusion occurred,
VCG utilities were not in the core (2 points).
d) It can be shown that collusion by losers is not profitable if and only if for every set of bids x, the
utilities of the VCG outcome belong to the Core(G). Consider player 1 submitting a bid of $1 million for
each item and as before $2 million for both items {A,B}. Could we ensure that the VCG outcomes are in
Core(G) regardless of the bids of players 2,3? (2 points).
5