Two-Sided Matchings and Non-Cooperative Game
Theory
COMP 4418 – Assignment 2
Due 31st Oct. 2025, 17:00
Total Marks: 100
Late Penalty: 20 marks per day
Worth: 15% of the course
Note: For ALL the questions, a complete solution must be provided. Proofs or justifying
calculations are required to obtain full marks. Answers stated without adequate explanation
will receive at most half credit.
Question 1 (15 marks) Consider a Student Proposing Deferred Acceptance (SPDA) al-
gorithm on an one-one matching instance ⟨S,C ≺⟩ where |S| = |C| = n. For each of the
following statements, please decide whether it is true or false. Support your answer with
an example or a proof, as needed.
a) For any instance, at least one student always makes multiple proposals. (5 marks)
b) There is an instance where the number of proposals made is n(n+1)2 . (5 marks)
Hint. Recall that n(n+1)2 = ∑
n
i=1 i.
c) For any fixed college c ∈C, the optimal manipulation for c will always match c to its
optimal partner under any stable matching. (5 marks)
Note: For this and all other assignment questions, to show that a statement is true for
one instance, it is enough to give one such example. To show that a statement is true for all
one-one matching instances, a proof is required. To show that a statement is not true for all
instances, it is sufficient to give one instance where it does not hold.
Question 2 (10 marks) Consider the following one-one matching instance with n= 5.
s1 : c1 ≻ c2 ≻ c3 ≻ c4 ≻ c5 c1 : s5 ≻ s1 ≻ s3 ≻ s4 ≻ s2
s2 : c3 ≻ c4 ≻ c5 ≻ c1 ≻ c2 c2 : s1 ≻ s5 ≻ s2 ≻ s3 ≻ s4
s3 : c4 ≻ c5 ≻ c3 ≻ c2 ≻ c1 c3 : s3 ≻ s4 ≻ s5 ≻ s2 ≻ s1
s4 : c5 ≻ c3 ≻ c4 ≻ c1 ≻ c2 c4 : s4 ≻ s5 ≻ s3 ≻ s1 ≻ s2
s5 : c2 ≻ c1 ≻ c4 ≻ c5 ≻ c3 c5 : s1 ≻ s5 ≻ s2 ≻ s3 ≻ s4
Identify all colleges who can manipulate under the SPDA and explain why. Give an incon-
spicuous optimal manipulation for each, if any. Analogously, identify all students who can
1
Due Date: 31 Oct. 2025 COMP 4418 – Assignment 2
manipulate under the CPDA and give an inconspicuous optimal manipulation for each, if
any.
Question 3 (10 marks) Give a polynomial time algorithm to check if a given many-to-
one matching instance has multiple stable matchings. Prove its correctness and running
time.
Note. You can take any algorithm discussed in class/slides as a known subroutine that
you do not need to redefine.
Question 4 (20 marks) Consider the following normal-form game, which is parameter-
ized by a value α ∈ R.
x y
a −2 2 α −1
b 3
−3 −3 3
a) For which value of α is the game zero-sum? (3 marks)
b) For which values of α is the outcome (α,−1) Pareto-optimal? (3 marks)
c) For which values of α can the game be solved by iterated strict dominance? (4
marks)
d) For which value of α is it the maximin strategy of the row player to play a with
probability 12 ? (5 marks)
e) For which value of α will the column player play y with probability 34 in a Nash
equilibrium? (5 marks)
Question 5 (10 marks) Consider the following extensive-form game.
a
b
c
d e f g hi
j k l m n o p q
1
2
1 2
1 2
2 1
(4, 0) (2, 4) (1, 2) (0, 0)
(0, 5) (5, 1)
(4, 2) (1, 1) (1, 0) (3, 3)
a) Compute the subgame-perfect Nash equilibrium. Specify the strategy of each player
in each subtree of the game.(5 marks)
b) Is there a pure Nash equilibrium where player 2 has a utility of 4? Explain your
answer! (5 marks)
2
Due Date: 31 Oct. 2025 COMP 4418 – Assignment 2
Question 6 (20 marks) A picture is sold in an auction, which is attended by three po-
tential buyers: Aaron (A), Ben (B), and Charles (C). Each of the buyers has a personal
valuation for the picture: Aaron values the picture at vA = 90, Ben at vB = 60, and Charles
at vC = 40. The rules of the auction are simple: each agent simultaneously submits an in-
teger bid bx ∈ {0,1,2, . . . ,100}, the agent submitting the highest bid wins the picture and
pays his bid bx. The other agents leave empty-handed and do not pay anything. Ties are
broken lexicographically, so Aaron wins the picture if he submits the highest bid even if
another agent submits the same bid; further, if Ben and Charles tie for the highest bid, Ben
wins. We assume that the utility of each agent is quasi-linear: the utility of the agent who
wins the picture is his valuation vx minus his payment bx, and the utility of the other agents
is 0.
Example: Suppose Aaron bids 40, Ben 50, and Charles 30. Ben wins the picture and
pays his bid of 50. The utility of Ben is thus vB−bB = 60−50 = 10. The utility of Aaron
and Charles is 0.
a) Treat the above situation as a normal-form game, where the action space of each agent
is his bid bx ∈ {0, . . . ,100}. Identify a pure Nash equilibrium (NE) of this game and
justify why it is a NE, or explain why no pure NE exists. (10 marks)
b) We modify the rules of the auction by introducing a participation fee: each agent who
reports a non-zero bid has to pay a fee of c = 1. Hence, the utility of the agent who
gets the picture is his valuation vx minus his bid bx minus the participation cost c. The
utility of every other agent is −c if they report a non-zero bid, and 0 if they bid 0.
Example: Suppose Aaron bids 40, Ben 50, and Charles 0. Ben wins the picture, pays
his bid of 50 and a participation cost of 1. The utility of Ben is thus vB− bB− c =
60−50−1 = 9. The utility of Aaron is −1 since he reports a non-zero bid and thus
pays the participation fee, whereas the utility of Charles is 0.
Identify a pure Nash equilibrium (NE) of this modified normal-form game and justify
why it is a NE, or explain why no pure NE exists. (10 marks)
Question 7 (15 marks) Prove the following statements.
a) Let G1 = ({1,2},(A1i )i∈{1,2},(u1i )i∈{1,2}), G2 = ({1,2},(A2i )i∈{1,2},(u2i )i∈{1,2}), and
G3 =({1,2},(A3i )i∈{1,2},(u3i )i∈{1,2}) denote three two-player normal-form games such
that A1i = A
2
i = A
3
i for i ∈ {1,2} and u3i (a) = 12(u1i (a) + u2i (a)) for both players
i ∈ {1,2} and all action profiles a ∈ A. Show that, if a strategy profile s is a Nash
equilibrium for G1 and G2, then it is a Nash equilibrium for G3. (5 marks)
b) Let G= ({1,2},(Ai)i∈{1,2},(ui)i∈{1,2}) denote a two-player zero-sum game such that
A1 = A2 = {a1, . . . ,ak} for k > 1 and u1(ai,a j) = u2(a j,ai) for all ai,a j ∈ A. Show
that the value of G (i.e., the security level of player 1) is 0. (10 marks)
Hint: Consider any mixed strategy of player 2. Show that if player 1 uses the same
mixed strategy, his expected utility is 0. Conclude that player 1 can always secure 0.
SUBMISSION
• Submit your solution directly via Moodle in the assessment hub at the end of the
Moodle page. Please make sure that your manuscript contains your name and zID.
3
Due Date: 31 Oct. 2025 COMP 4418 – Assignment 2
• Your answers are to be submitted in a single PDF file. We will not accept any other
file formats. Please make sure that your solutions are clearly readable.
• The deadline for this submission is 31st October 2025, 17:00.
Academic Honesty and Plagiarism
All work submitted for assessment must be your own work. Assignments must be com-
pleted individually. We regard copying of assignments, in whole or part, as a very serious
offence. Be warned that:
• the submission of work derived from another person, or jointly written with someone
else will, at the very least, result in automatic failure for COMP4418 with a mark of
zero;
• allowing another student to copy from you will, at the very least, result in a mark of
zero for your own assignment; and
• severe or second offences will result in automatic failure, exclusion from the Univer-
sity, and possibly other academic discipline.
• students are not allowed to derive solutions together as a group during such discus-
sions. Students are also warned not to send solution fragments of the assignments to
each other in any form (e.g. as email or listings).
• In addition, copying/purchasing of solutions that is available on the web is also not
permitted. Students are strongly advised to protect their work. Do not leave your
terminal/computer unattended, or leave printouts at the printer for others to take.
Read the study guide carefully for the rules regarding plagiarism.
4

学霸联盟