联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

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.