Econ 106D: Problem Set 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Econ 106D: Problem Set 1
Two-Sided Matching
January 18, 2023
Due date: Thursday, January 26 at 12:30pm (start of class).
Submission: Please submit an electronic copy to Carlos ([email protected]) in the form of a single PDF file. Please do not submit multiple and/or non-PDF files. Your name must be clearly printed at the top of the page. Submissions deemed difficult to read (e.g., blurry photo, illegible handwriting) or that do not meet the other parameters described here may be rejected.
Collaboration: You are permitted to work in groups of up to 4 people. You must clearly list the names of all people in your group (or indicate that you worked alone) at the top of your submission.
Resources: Aside from consulting with people in your group, you may consult any resources made available on the course website, including any references listed on the syllabus. If you invoke a fact from such a resource (e.g., reference a result stated in the lecture slides), clearly indicate where you have done so.
Other items: The purpose of the problem sets is to help you internalize the theoretical material discussed in lecture and to prepare for the exams. The problems on the midterm and final exams will look similar to those on the problem sets (appropriately calibrated to account for time constraints). To be concrete: Problem 1 is similar to what will appear on the exams, whereas Problem 2 is harder.
Credit and grading: Each question below (the 11 parts of Problem 1 and 3 main parts of Problem 2) is worth 10 points, for a total of 140 points. There is also a bonus question (part (d) of Problem 2) that is worth 10 points. 1
Problem 1
Consider an economy with 4 men and 4 women. The preferences of the men are:2
|
|
|
|
|
|
w1 w3 w2 w4 |
w2 w1 w4 w3 |
w4 w3 w2 w1 |
w2 w3 0 |
|
|
|
|
|
|
m4 m3 m2 m1 |
m1 m3 m2 m4 |
m2 m1 m3 m4 |
m4 m1 0 |
Questions:
(a) Is the matching {(m1 , w1 ), (m2 , w3 ), (m3 , w2 ), (m4 , w4 )} stable? Why or why not? Is this matching Pareto
efficient? Why or why not?
(b) Is the matching {(m1 , w1 ), (m2 , w3 ), (m3 , w2 ), m4 single, w4 single} stable? Why or why not? Is this matching
Pareto efficient? Why or why not?
(c) What is the outcome of the DA (deferred acceptance) with men proposing?
(d) What is the outcome of the DA with women proposing?
(e) Verify that the matching {(m1 , w3 ), (m2 , w1 ), (m3 , w2 ), m4 single, w4 single} is stable.
(f) Is the matching from the question above the unique stable matching? or are there other stable matchings?
(g) Is there a stable matching in which m4 and w1 are matched with one another? If yes, give an example of
such a matching; if no, provide an argument why not.
(h) Is there a stable matching in which w4 is matched? If yes, give an example of such a matching; if no, provide
an argument why not.
In the next three questions, agents report preference rankings and then the men-proposing DA is run to determine who matches with whom.
(i) Assume that all agents report their true preferences except possibly man m1 . Can man m1 improve his matching outcome by reporting a preference ranking different from his true ranking? If yes, please provide
(i) a preference ranking such that if m1 reports it then he gets a better match than he would by reporting his true ranking, and (ii) please provide the resulting matching. If no, please give an argument why not.
(j) Assume that all agents report their true preferences except possibly woman w1 . Can woman w1 improve her
matching outcome by reporting a preference ranking different from her true ranking? If yes, please provide (i) a preference ranking such that if w1 reports it then she gets a better match than she would by reporting her true ranking, and (ii) please provide the resulting matching. If no, please give an argument why not.
(k) Is truthful reporting a Nash equilibrium?
Problem 2
In class, we discussed the one-to- one two-sided matching problem, in which each participant can have at most one partner. We now consider the many-to- one two-sided matching problem, in which (i) one side of the market (“colleges”) can match with many partners on the other side (“students”), while (ii) each student can match with at most one college. The many-to-one model is important for most of the real-world matching markets (e.g., essentially all labor markets) discussed in class and in the readings.3
Formally, the model consists of the following pieces:
● A finite set of colleges c e C and a finite set of students s e S .
● Each student s has a strict preference over the colleges and remaining unmatched. For simplicity, we assume that all colleges are acceptable: each student strictly prefers going to college than not.
● Each college c has a preference 5C over sets of students S\ S S, constructed from the following objects:
– A capacity qC , meaning that it can admit at most qC students.4 Any set of students S\ for which lS\ l > qC is deemed unacceptable.5
– A “primitive” strict preference ordering BC over individual students (e.g., s BC s\ means that c strictly prefers student s to s\ ). For simplicity, we assume that all students are acceptable: absent capacity constraints, college c would strictly prefer to admit any given student than not.
The preference 5C is responsive: given any set of students S\ , student s\ in S\ , and student s\\ not in S\ , then we have S\ u {s\\ }/{s\ } ×C S\ if and only if such that s\\ BC s\ .6 In words: if two equally-sized sets of students S\ and S\\ differ only by the identify of one student, the college c’s preference between S\ and S\\ is
determined by its preference over the identify of that student.
In this setting, we define (stable) matchings as follows:
● A match is a list of pairs of the form (c, SC ), where c e C is a college and SC S S is a set of students, such that every college and student shows up exactly once.7
● Given a matching, a college-student blocking pair consists of a student s and college c such that (i) s and c are unmatched (s is not in SC ), (ii) s prefers c to whichever college they are currently matched to, and (iii) there is some student s\ that c is currently matched to (s\ is in SC ) such that s BC s\ .
● A match is stable if there do not exist any college-student blocking pairs.
Questions:
(a) Suppose there is just one college c and three students S = {s1 , s2 , s3 }. (i) Given an example of a preference
ordering 5C that is responsive. (ii) Give another example that is not responsive. (Hint: You can use a utility representation/assign numerical values to the (sets of) students.)
(b) Construct an example with two colleges C = {c1 , c2 } and three students S = {s1 , s2 , s3 } where each college
has responsive preferences. In your example: (i) exhibit a match that is stable, and (ii) exhibit another match that is unstable. In both cases, describe why the matching you exhibit is (un)stable.
(c) Consider the student-proposing Deferred Acceptance Algorithm:
1. Each student applies to their favorite college.
2. Each college c puts on its “wait list” its qC favorite students, among those who applied to it. (If fewer than qC students applied to college c, it can put all of them on the wait list.)
3. Each student s who is rejected from a college removes it from their list.
4. If any student s is rejected, return to Step 1.
5. If no student is rejected, terminate the process.
As rigorously as you can, argue that this algorithm (i) terminates in finite time, and (ii) results in a stable matching.
(d) Bonus (extra 10 points): Suppose we relax the assumption that colleges’ preferences are responsive, instead allowing each college c to have abritary preferences 5C over sets of students. Does the DAA from part (c) always terminate at a stable matching? Either give a proof (as formally as you can) or give a counterexample.
2023-01-28