GU 4260 Spring 21 — Final (take-home exam)
Write your answers carefully. Be concise (don’t write a novel). 10% of the grade will be related to the quality of your writing (English, being clear, and concise).
All your answers have to be justified
Problem 1 (15 points) Consider the marriage problem with n women and n men. Sup- pose that for each man, all women are acceptable and, similalry, for each woman, all men are acceptable. Moreover, we suppose that all men have the same preferences over women. We do not make any assumption about women’s preferences.
This last assumption implies that the man-optimal matching and the women-optimal matching coincide. But it also implies that (for this case only) the Deferred Acceptance algorithm with men proposing is equivalent to another algorithm. Which one?
Don’t say it’s equivalent to the Deferred Acceptance algorithm with women proposing (that’s obvious given that the man-optimal and woman-optimal matchings coincide). We are referring to another algorithm.
Your answer should consist of:
• The name of that other algorithm
• A few lines to explain the intuition, i.e., why it is the case.
Problem 2 (22 points) We consider the marriage model a set M = {m1, m2, . . . , mn} of men and a set W = {w1,w2,…,wk} of women. Let Pm1,Pm2,…,Pmn and Pw1,Pw2,…,Pwk be the preferences of the men and women, respectively.
Assume that P is such that there are multiple stable matchings. This implies that the man-optimal matching, μM , and the women optimal matching, μW , differ. But there could be other stable matchings (that are neither the man-optimal or the woman-optimal matchings).
Below is the description of a procedure to find new stable matchings given two stable matchings (this procedure only works for stable matchings) Let μ and μ′ be any two stable matchings (not necessarily the woman-optimal or the man optimal matching).
With these two matchings we can construct two additional matchings, denoted λ and ν, as follows.
1
• The matching λ.
For each man, if μ(m) = μ′(m) then λ(m) = μ(m) = μ′(m). If μ(m) ̸= μ′(m), then λ(m) = μ(m) if man m prefers his partner under μ to his partner under μ′. Otherwise, let λ(m) = μ′(m). Formally, we write
μ(m) = μ′(m) if μ(m) = μ′(m) , ′
λ(m) = μ(m) if μ(m) Pm μ (m),
μ′(m) if μ′(m) Pm μ(m) .
For each woman, if μ(w) = μ′(w) then λ(w) = μ(w) = μ′(w). If μ(w) ̸= μ′(w), then λ(w) = μ(w) if woman w prefers her partner under μ′ to her partner under μ. Otherwise, let λ(w) = μ′(w). Formally, we write
μ(w) = μ′(w) if μ(w) = μ′(w) , ′
μ(w) if μ (w) Pw μ(w), μ′(w) if μ(w) Pw μ′(w) .
In other words, λ is constructed by matching each man to the woman he prefers between μ and μ′ and matching each woman to the man she prefers less between μ and μ′.
• The matching ν.
The matching ν is constructed like the matching λ, but this time by matching each man to the woman he prefers less between μ and μ′ and matching each woman to the man she prefers between μ and μ′.
It can be show that the matchings λ and ν are indeed matchings, i.e., for each man m and woman w, λ(m) = w if, and only if λ(w) = m and, similarly, ν(m) = w if, and only if ν(w) = m. The argument is a little bit technical. You are not asked to prove it. Take that result for granted.
1. Show that, for any two stable matchings μ and μ′, the matching λ as described above is stable.
Hint: Proceed by contradiction: start assuming that λ is not stable, and then use how λ is constructed. You need to consider two cases, whether the man prefers μ or μ′.
2
λ(w) =
Pm1 Pm2 Pm3 Pm4 w1w2w3w4 w2w1w4w3 w3w4w1w2 w4w3w2w1
Table 1: Marriage problem For the rest of the problem we consider
depicted in Table 1.
2. Consider the following matchings,
Pw1 Pw2 Pw3 Pw4 m4 m3 m2 m1 m3 m4 m1 m2 m2 m1 m4 m3 m1 m2 m3 m4
with four men and four women.
the preference profile with 4 men and 4 women
m m m m w2 w1 w3 w4 w1 w2 w4 w3
That is, in μ1 man m1 is matched to w2, m2 is matched to w1,… Construct the matchings λ and ν from μ1 and μ2.
3. Consider the following matchings,
m m m m m m m m μ3=1234 andμ4=1234.
w2 w4 w1 w3 w3 w1 w4 w2
Construct the matchings λ and ν from μ3 and μ4.
4. Consider the following matchings,
m m m m m m m m μ5=1234 andμ6=1234.
w3 w4 w2 w1 w4 w3 w1 w2 Construct the matchings λ and ν from μ3 and μ4.
Problem 3 (50 points) We consider the following career problem. Insider Trading, Inc. is a company that does not hire its traders from outside. All its traders are graduates from the in-company school. Students admitted to that school have their education fully financed by the Insider Trading, Inc. After graduation students must work for at least 3 years for
3
m m m m
μ1=1234 andμ2=1234.
the Insider Trading, Inc, in one of the several departments offered by the company (money laundering, dark e-commerce, tax evasion, etc.).
A major problem is that over the years students leave the company after 3 years, pre- ferring to work for other companies (they have skills that are highly appreciated by major banks, audit and accounting firms, governmental agencies, etc.). To prevent outflow of work- ers Insider Trading, Inc wants to offer a special contract after graduation: commit to work for 5 years and in exchange the student’s ranked higher for the department he/she wants.
Formally, the problem can be described as follows.
• There is a set of n students I = {i1,i2,…,in}.
• There is a set of departments D = {d1,d2,…,dm}.
• Each department d has a capacity qd, with mh=1 qdh ≥ n.
• Two different contracts, t0 and t+. The contract t0 corresponds to the 3 year commit- ment, and the contract t+ corresponds to the 5 year commitment.
• Each student i has a preference ordering Pi over department-contract pairs. For instance, Alice’s preferences could be
(d1, t0)PAlice(d1, t+)PAlice(d2, t0)PAlice(d2, t+)
which means that Alice’s top choice is department d1 with the contract t0, department d1 with the contract t+ is her second most preferred option, followed by department d2 with the contract t0, etc.
For simplicity, we will assume some structure about students’ preferences.
– If, for a contract t0 a student prefers department d to department d′, then the
student also prefers d to d′ with the contract t+ (and vice-versa), (d, t0)Pi(d′, t0) ⇔ (d, t+)Pi(d′, t+)
– Each student i = 1,…,n has a preference relation ≻i over departments alone, and a t0 contract is always preferred to a t+ contract,
d ≻i d′ ⇔ (d, t0)Pi(d′, t0) ⇔ (d, t+)Pi(d′, t+) 4
– There is a unique priority ranking π for all departments. We write π(j) > π(i) to denote that student j is ranked higher than student i (you can think π being constructed using students’ GPAs).
An assignment is a function μ that specifies, for each student, the department the student is assigned to and under which contract.
The main concept we will look at is that of a fair assignment. For any student i and assignment μ, let μd(i) and μ(i)t be the department and the contract assigned to i under μ, respectively.
An assignment μ is fair if for any student i,
(d∗, t∗) Pi μd(i), μt(i) ⇒ π(j) > π(i) for any j such that μd(j) = d∗ and μt(j) = t∗.
In other words, an assignment is fair if for any student, all the department-contract pairs he prefers (d∗ and t∗) to his assignment (μd(i) and μt(i)) have been assigned to students that have higher priority than i at that department d∗.
If this is not the case, then i would be better off with j’s contract and j’s department could replace j with i, who is ranked higher. We would say that i has justified envy.
The current way the Insider Trading, Inc is solving its problem is the following. Each students must submit two things:
• a ranking of departments
• the names of departments for which the student is willing to sign the t+ contract (i.e.,
commit to work for 5 years instead of 3 years).
For each department d, Insider Trading, Inc constructs students’ priority rankings as follows.
• For a fraction (1 − λ) of the seats at department d students are ranked according to the ordering π.
• For a fraction λ of the seats at department d students are ranked using the priority ranking πd+ that is constructed as follows:
– If i is willing to sign the contract t+ for department d and j is not, then πd+(i) > πd+(j). That is, i has a higher priority than j.
5
– If both i and j are willing to sign the contract t+ for department d, then πd+(i) > πd+(j) ⇔ π(i) > π(j).
– If neither i nor j are willing to sign the contract t+ for department d, then πd+(i) > πd+(j) ⇔ π(i) > π(j).
The assignemnt mechanism is as follows. It is a variation of the deferred acceptance algorithm.
Insider Trading, Inc Algorithm
Step 1
Each student applies to his most preferred department.
Each department accepts the top (1 − λ)qd students using the ranking π. For the remaining λqd seats, students are accepted using the ranking πd+.
Example: there are two seats, 3 candidates (i, j and k), and λ = 0.5. We have π(i) > π(j) > π(k). Suppose k signs the contract t+ but not i and j. So πd+(k) > πd+(i) > πd+(j). For the first seat we use π. So i is admitted. For the second seat we use πd+. So k is admitted.
(with k ≥ 2).
Each student who has been rejected at the previous step applies to his most preferred
department among the ones that haven’t rejected him yet.
Each department decision works the same way as in Step 1, considering the student it accepted at the previous step and the new applicants.
The algorithm ends when no student is rejected. At this point the assignment is finalized.
Any student who was assigned to a department d, at one of the top (1 − λ)qd seat is assigned with the contract t0 (even if he signed the contract t+ for that department at the beginning of the algorithm). Students assigned to one of the λqd seats are assigned with the contract t+ if they signed the contract t+ for that department. Otherwise they are assigned with the contract t0.
Consider the following case with 5 students and 4 departments. Departments d1, d2,
and d3 one have seat each, department d4 has two seats, and λ = 1 (if there is only 2
6
Step k
End
1.
one seat then we use λ = 1 for that seat). The preferences of the students are given in Table 2.
Pi1
(d1, t0)
(d2, t0)
(d1, t+)
(d3, t0) .
Pi2 (d1, t0) (d1, t+) (d2, t0) (d2, t+) (d4, t0) (d4, t+) (d3, t0) (d3, t+)
Pi3 (d1, t0) (d3, t0) (d1, t+) (d2, t0) (d3, t+) (d2, t+) (d4, t0) (d4, t+)
Pi4
(d4, t0)
(d2, t0)
(d4, t+)
(d2, t+) .
preferences
Pi5
(d4, t0)
(d4, t+)
(d1, t0)
(d1, t+) .
Table 2: Students’
The ranking π of the students is i1, i2, i3, i4, i5 (student i1 is the top student, i5 the lowest ranked student).
Suppose the students submit the preferences over departments given in table 3. Stu- dents i1, i2, i3, i4, and i5 also report that they are willing to sign the t+ contract for the departments d1, {d1,d4}, d1, d2, and d4, respectively (i.e., i2 is willing to sign the t+ contract for departments d1 and d4).
i1 i2 i3 i4 i5 d1 d1 d1 d4 d4 d2 d2 d3 d2 d3 d3 d4 d2 d1 d1 d4 d3 d4 d3 d2
Table 3: Submitted preferences over departments
and sets of departments for which they are willing to sign the t+ contract.
(a) Calculate the assignment using the Insider Trading, Inc Algorithm. (b) Is this assignment fair? If not, which student has justified envy?
(c) Is this assignment efficient? If not, give an assignement that Pareto dominates it. 7
2. We consider now an alternative algorithm. In this algorithm students submit their preferences over department-contract pairs (i.e., the preferences in Table 2).
Alternative algorithm
To describe the algorithm we first need to describe the departmente’s choice function.
Let d be a department (with capacity qd), and let X denote any set of student-contract pairs. For example, we could have X = {(i1, t+), (i2, t0), (i3, t+)} (we don’t need to specify the department because all those pairs are for department d). From the set X, we denote by Cd(X) the student-contract pairs that department d will choose (and thus reject the others). The function i contructed as follows.
(a) The first (1 − λ)qd seats are awarded, one at a time, to the student with the highest priority (from the ranking π). If X contains two pairs with the same student, chose the one with the contract t0.
We continue until (1−λ)qd student-contract pairs have be chosen or until all pairs in X have been considered (which ever happen first).
All the student-contract pair that have been chosen are included in Cd(X).
Example: If X = {(i1, t0), (i1, t0), (i2, t+), (i3, t0)}, π = i1, i2, i3, and (1−λ)qd = 2, then department d would first pick student i1 (the highest ranked) with contract t0. Then it would pick i2 (with contract t+) because i2 is ranked above i3.
(b) If there are still some student-contract pairs that have not been chosen yet (i.e., Cd(X) is a strict subset of X), we consider now only the pairs with the contract t+. The λqd seats are awarded, one at a time, to the student with the highest priority (from the ranking πd+).
(c)
Step 1
If there are still some open seats at the department, we consider all the student- contract pairs that haven’t been choosen yet (those are necessarily with the con- tract t0). Seats are awarded, one at a time, to the students with the highest priority (from the ranking π).
Start with the highest rank student according to the ranking π, say, i. Let (d, t) the department-contract pair that is ranked the highest in i’s preferences. We say that department d holds the pair (i, t).
8
Step k
Define A = {(i,t)} and A ′(1) = ∅ for all departments d′ ̸= d. The set A (1) d(1) d d
captures all the offers received by department d at then end of step 1.
(with k ≥ 2). Let i be the student with the highest rank (according to π) for whom no contract is currently held by a department. Let (d, t) the department-contract pair that is ranked the highest in i’s preferences that has not been rejected in a previous step. Department d holds this student-contract pair if (i, t) is chosen from the set Ad(k − 1) ∪ {(i, t)}. Otherwise (i, t) is rejected.
Let Ad(k) = Ad(k−1)∪{i,t)} and Ad′(k) = Ad′(k−1) for all departments d′ ̸= d. The set Ab(1) captures all the offers received by department b at then end of step k.
The algorithm terminates when all students have an offer that is on hold by a department.
In this case, the assignment of each department d is Cd(Ad(T)), where T denotes the last step of the algorithm.
End
Remark This algorithm differs from the Deferred Acceptance algorithm in an impor- tant way. In this algorithm each department keeps track of all the student-contract pairs it received (the set A). So even if a student-contract pair is rejected at some step, it is still added to the set A. It is therefore possible that, at the last step, a student a student-contract pair that was rejected at an earlier step ends up being accepted at the final step. It turns out that this algorithm is such that (thanks to the way the depart- ments form priority rankings) we have an assignment (no student is assigned to two different departments or to the same department but under two different contracts).
Calculate the assignment with the Alternative Algorithm and the preferences given in Table 2.
Your answer should, at each step of the algorithm, the sets Ad of each department.
There was a mistake in the grading of the students! It turns out that student i1’s grade was miscalculated and his final score is lower than that of i2 (but still higher than i3). So the real ranking of the students is π′ = i2, i1, i3, i4.
3. Calculate the assignment with the Insider Trading, Inc algorithm using the ranking π′. 9
4. Calculate the assignment with the Alternative algorithm using the ranking π′. (Again, your answer should provide all the details like in part 2).
5. Using all the previous answers, what is the property that the Alternative algorithm seems to satisfy that the Insider Trading, Inc algorithm does not? (No need to write a novel, a few lines should be enough.)
10