Further Results on Stability-Preserving Mechanisms for School Choice
Karthik Gajulapalli James A. Liu Vijay V. Vazirani























wbox

	colback  = white,














































@space@setup
	@preskip= 10pt
	@postskip=@preskip 






theoremTheorem
lemmaLemma
corollaryCorollary
definitionDefinition
problemProblem


exampleExample
observationObservation
propositionProposition
claimClaim
factFact
assumptionAssumption
warningWarning

definition
remark[theorem]Remark



fminipage

		

algbox[0]0.2in
	6.3in
	
	
	0.2in


≼
≽
≻
≺

#1≈_#1

#1Span(#1  )
#1


#1#2_#1[ #2 ]
#1#2^#1[ #2 ]
#1#2𝔼_#1[ #2 ]
#1[ #1 ]


def=
#1{#1  }
#1|#1  |




#1⌊#1 ⌋
#1⌈#1 ⌉

#1dim (#1)
#1sgn (#1)

∪
∩
⋃
⋂

#1|#1  |

#1[#1  ]
#1 #1 
#1 #1 


𝒞
ℰ
𝒢
ℒ
𝒮



















å𝑎
















𝑡
























































































                                                    






























←


















Department of Computer Science, University of California, Irvine





	Further Results on Stability-Preserving 

Mechanisms for School Choice

(Preliminary Version)
    Karthik Gajulapalli, James A. Liu, Vijay V. Vazirani
    
=============================================================================================


We build on the stability-preserving school choice model introduced and studied recently in <cit.>. We settle several of their open problems and we define and solve a couple of new ones.






    

	

    


§ INTRODUCTION


School choice is among the most consequential events in a child's upbringing, whether it is admission to elementary, middle or high school, and hence has been accorded its due importance not only in the education literature but also in game theory and economics. In order to deal with the flaws in the practices of the day, the seminal paper of Abdulkadiroglu and Sonmez <cit.> formulated this as a mechanism design problem. This approach has been enormously successful, especially in large cities involving the admission of tens of thousands of students into hundreds of schools, e.g., see <cit.>, and today occupies a key place in the area of market design in economics, e.g., see <cit.>. 

Once the basic game-theoretic issues in school choice were adequately addressed, researchers turned attention to the next level of questions. In this vein, in a very recent paper, Feigenbaum et. al. <cit.> remarked, “However, most models considered in this literature are essentially static. Incorporating dynamic considerations in designing assignment mechanisms ... is an important aspect that has only recently started to be addressed.” 

Our paper deals with precisely this. We study three natural settings in which students need to be assigned to schools in two temporally-separated rounds, denoted _1 and _2, for which we give mechanisms _1 and _2, respectively. _1 finds a stable matching M in round _1. In round _2, additional students need to be assigned to the schools. We want that _2 should also yield a stable matching, besides having other nice properties. Clearly, the task of _2 would be a lot simpler if it were allowed to reassign the schools of a small number of students who were matched in round _1. However, one of our central tenets is to disallow this altogether. Indeed, switching the school of a student midway, unsynchronized with her classmates, is well-known to cause traumatic effects, e.g., see <cit.>. Hence, _2 must extend M to a stable matching M'.

The use of Gale-Shapley student-proposing deferred acceptance algorithm, which finds a student-optimal stable matching of students to schools, has emerged as a method of choice in the literature. Two main advantages of this method are: 

	
  * As a consequence of stability, once the matching is done, no student and school, who are not matched to each other, will have the incentive to go outside the mechanism to strike a deal. Another advantage of stability is that it eliminates justified envy, i.e., the following situation cannot arise: there is a student s_i who prefers another student s_j's school assignment, say h_k, while being fully aware that h_k preferred her to s_j.
	
  * This mechanism is dominant strategy incentive compatible (DSIC), for students. This entails that regardless of the preferences reported by other students, a student can do no better than report her true preference list, i.e., truth-telling is a dominant strategy for all students. This immediately simplifies the task of students and their parents, since they don't need to waste any effort trying to game the system. 


In all three settings, we give a pair of mechanisms (_1, _2) which run in polynomial time and _2 extends, in a stable manner, the stable matching found by _1. Additionally, for the first two settings, (_1, _2) are DSIC for students w.r.t. reporting their preference lists. The additional requirements are much more stringent in Setting III due to which we were unable to find DSIC mechanisms; see the requirements below. Instead, we define the weaker notion of weak incentive compatible (WIC) mechanism, under which a student cannot gain by misreporting her choices, if all other students are truthful, and we provide such a pair of mechanisms.

The three settings involve the admission of students of a city, named City, into schools; the preference lists of both students and schools are provided to the mechanisms. In round _1, the capacity of each school is fixed but in round _2, the City is happy to allocate extra seats to specific schools per the recommendation of mechanism _2, which in turn has to meet specified requirements imposed by the City. In this round, in Settings I and II, _1 finds a student-optimal stable matching M. Let L be the set of left-over students, those who could not be admitted in this round. 

In round _2 of Setting I, the problem is to maximize the number of students admitted from L, by extending M in a stability-preserving, DSIC manner. In Setting II, a set N of new students also arrive from other cities and their preference lists are revealed to _2. The requirement now is to admit as few students as possible from N and subject to that, as many as possible from L, again in a stability-preserving, DSIC manner. Next, we consider a slightly different problem within Setting II, namely find the largest subset of (N ∪ L) that can be matched in a stability-preserving and DSIC manner. We give an efficient mechanism for this as well.

In Setting III, some students, who are residents of the City, try to game the system by not participating in round _1 but only showing up in round _2, thereby attempting to get admission to a better school. Therefore, _2 needs to be incentive compatible not only w.r.t. preference lists but also late participation. We note that the previous mechanisms were all oblivious in that they were given the preference lists of only those students who were being considered for admission, and not those who were not participating.

For Setting III, we need to define the notion of a non-oblivious mechanism, which needs to know the preference lists of all students who reside in the City, including the ones who don't participate in round _1.

We prove two impossibility results which clarify the strongest properties we can hope to expect from a pair (_1, _2) of mechanisms for Setting III. First, we prove that there is no pair of non-oblivious, stability-preserving, DSIC mechanisms. Second, we prove that there is no pair of oblivious, stability-preserving, WIC mechanisms. That leaves the possibility of obtaining a pair of non-oblivious, stability-preserving, WIC mechanisms for Setting III, and this is what we obtain. Additionally, both our mechanisms run in polynomial time. 

We finally give a procedure that outputs all possible stability-preserving extensions of a given stable matching (which may be exponentially many) with polynomial delay.




 

 §.§ Related work



Besides the references pointed out above on school choice, in this section, we will concentrate on 
recent work on dynamic matching markets, especially those pertaining to school choice. Feigenbaum et. al. <cit.> study the following issue that arises in NYC public high schools, which admits over 80,000 students annually: after the initial centralized allocation, about 10% of the students choose not attend the school allocated to them, instead going to private or charter schools. To deal with this, <cit.> give a two-round solution which maintains truthfulness and efficiency and minimizes the movement of students between schools. 


An interesting phenomena that has been observed in matching markets is unraveling, under which matches are made early to beat the competition, even though it leads to inefficiencies due to unavailability of full information. A classic case, indeed one that motivated the formation of centralized clearing houses, is that of the market for medical interns in which contracts for interns were signed two years before the future interns would even graduate <cit.>. A theoretical explanation of this phenomena was recently provided by <cit.>. 

We note that the phenomena we are studying in Setting III can be viewed as anti-unraveling: some students are able to game the system by making the match late. Clearly, this aspect deserves more work. We also note that this phenomenon is by no means rare, e.g., it occurred in the Pasadena School District and the authorities were made specific recommendations by economists from Caltech to counter it <cit.>. 

<cit.> point out that stable pairings may not necessarily last forever, e.g., a student may switch from private to public school or a married couple may divorce. They study  dynamic, multi-period, bilateral matching markets and they define and identify sufficient conditions for the existence of a dynamically stable matching.

<cit.> develops a notion of stability that applies in markets where matching opportunities arrive over time, much like the seats in our work. One of the things shown in this paper is that agents' incentive to wait for better matching opportunities can make achieving stability very difficult. Indeed, the notion of dynamic stability given in this paper is a necessary condition which a matching must satisfy in order that agents do not to find it profitable to game a mechanism by showing up in later rounds. 

A number of recent papers <cit.> consider the consequences of having a mechanism that repeats the Gale-Shapley Deferred Acceptance algorithm multiple times, similar to our work. Note that Deferred Acceptance is not consistent in that if one runs it, then removes some agents and their assignments, and runs it again on the remaining agents, one does not obtain the same assignment restricted to the left-over agents. In these papers, the authors show that there is room for manipulation by submitting empty lists in the first round. However, unlike our model in which changes are introduced in round _2, in all these papers, there is nothing that motivates running Deferred Acceptance twice, namely no arrivals of new students, no change in capacities, no changes in preferences, etc. 














	

	
	

§ PRELIMINARIES




 §.§ The stable matching problem for school choice



The stable matching problem for schools is defined as follows: We are given as input a set of m schools H = {h_1, h_2, … , h_m}, and a set of n students S ={s_1, s_2, … , s_n} who are seeking admissions to the schools. Each school h_j has some fixed  capacity c(j) of students who can be enrolled in the school. If the school is assigned c(j) students then we say that h_j is filled to capacity. If h_j is assigned less than c(j) students then we say h_j is under-filled.  




Every student s_i has a strict and totally ordered preference list l(s_i) over the schools H ∪{∅}. l(s_i) is ordered in decreasing order of preference, so if some student prefers a school h_j to h_k then h_j appears before h_k on the students preference list. We allow the inclusion of ∅ to allow partial preference lists. If a student prefers being unmatched than being matched to a school they dislike, then such a preference is modeled by letting ∅ precede the set of unwanted schools on the preference list of the student. We let ∅ have infinite capacity. Likewise each school h_j has a strict and totally ordered preference list l(h_j) over the students S ∪{∅}.


A matching M in this context is an assignment of students to schools that satisfy the capacity constraints of the schools, with the added condition that no student can be matched to more than one school. A matching is said to have a blocking pair (s_i,h_k) if there exists a student-school pair (s_i, h_j) and a school h_k such that s_i prefers h_k to h_j and either:


    
  * there is some student s_j currently matched to h_k such that h_k prefers s_i to h_j or
    
  * h_k is under-filled and h_k prefers s_i to ∅
.


In both the cases s_i would like to break her match with h_j and instead go to school h_k. We define a matching M to be stable if it does not contain any blocking pairs.






















§ PROBLEM DEFINITION



We study the assignment of students to schools in two rounds,  _1 and _2, which are temporally separated. In this section we state the two settings studied; for each, we will have two mechanisms, _1 and _2. In round _1, mechanism _1 finds a stable matching of students to schools, M. In round _2 a change is made to the sets of participants, which may cause M to no longer be a valid or stable matching. _2 then updates M to M' in order to ensure a stable matching. By allowing updates, we let some students in M get unmatched in M', or get matched to different schools. This differs from the settings discussed in <cit.> where  _2 is not allowed to break a match created by _1.



The students report their preference lists and the mechanisms operate on whatever is reported. We will assume that the schools' preference lists are truthfully reported. We will show that in Setting 1 there does not exist a mechanism that is dominant strategy incentive compatible (DSIC), and in Setting 2 our mechanism is DSIC for students, showing that students cannot do better by misreporting their preference lists.



We now state the common aspects of the first two settings before describing them completely. In both, in round _1, the setup defined in Section <ref> prevails and _1 simply computes any stable matching respecting the capacity of each school, namely c(j) for h_j. Let this matching be denoted by M.


In round _2, the City is allowed to re-allocate some students and update matching M to a new matching M' that is stable with respect to the round _2 participants. However, we want to minimize the number of students in S who are re-allocated. We refer to any stable matching M' that optimizes this objective as a minimum stable re-allocation.









 §.§ Setting I (Adding New Schools)



In this setting, the City has some new schools H' that have opened up in _2. The preference lists of students are updated to include schools in H', though their relative preferences between schools in H ∪{∅} are unchanged.
In particular the addition of new schools might result in some students wanting to leave their current schools to go to a new school. This could lead to vacant seats being created in the original schools, causing some other students to leave their current schools and move to schools they prefer more that now have vacant seats. The City wants to find a stable matching over students S and schools H∪ H' that minimizes the number of students who are re-allocated from their school in M.




	There is a polynomial time mechanism _2 that finds the minimum stable reallocation with respect to Round _1 matching M, students S, and schools H∪ H'.
 

 



 §.§ Setting II (Adding New Students)



In this setting, a set N of new students arrive from other cities in round _2. The preference lists of schools are also updated to include students in N, though their relative preferences between students in S∪{∅} are unchanged. The City wants to find a stable matching over students S ∪ N and schools H that minimizes the number of students who are re-allocated from their school in M.





There is a polynomial time mechanism _2 that is DSIC for students and finds the minimum stable reallocation with respect to Round _1 matching M, students S, and schools H∪ H'.
	
 








	
	
	
	

§ MECHANISM FOR ADDING NEW SCHOOLS



We first provide an example where running the Gale-Shapley algorithm over S,H∪ H' performs more re-allocations than required. This motivates the design of a mechanism that finds a minimum stable re-allocation by iteratively modifying the original matching M.



Assume there are 2 students A,B and 2 schools 1,2. The preferences for A,B are (2,1),(1,2), respectively. The preferences for 1,2 are (A,B),(B,A), respectively.
In round _1, school 1 has 1 seat, and school 2 has no seats. In round _2, school 2 adds 1 seat. (A,1) will be assigned in round _1; adding (B,2) in round _2 is the only stable matching with no re-allocations. However, running Gale-Shapley over all participants yields (A,2),(B,1), which requires a re-allocation.




Given a matching M, we define (s_i) to be the set of schools appearing before its matched school in M.  We also define (h_j) to be the set of students who prefer h_j to their matched school in M. Finally, we define (h_j) to be the student whom h_j prefers the best in the set (h_j). If (h_j) = ∅ then we define (h_j) = ∅.




 
 

When new schools are added each student is always matched to his original school, or better, in any minimum stable re-allocation of M.





Assume that M' is a minimum stable re-allocation of M, and some students are worse off in M'. Let M^* = M ∧ M', i.e. every student gets the match they prefer in M and M'.



We first show that M^* satisfies the capacity constraints of the schools. Let W be the students who did worse in M' (i.e. they are moved back to their original school in M^*). If some students in W leave a school going from M to M', then the students who replace them at that school must also be in W. To see this, observe that the school must prefer the replacing students to the leaving students. If there is a replacing student not in W, they would form a blocking pair with the school in M.



Next we show that M^* is stable. Let (s_i,h_i),(s_j,h_j)∈ M^*, and (s_i,h_j) be a blocking pair. Then s_i is matched to h_i or worse in both M and M', but (s_j,h_j) must be in one of these matchings, contradicting its stability.



M^* is  a stable re-allocation of M and has |W| fewer re-allocations than M', a contradiction.



 of Theorem <ref>:
The proof is by induction. We show that if a student is matched to a school at any step by the mechanism _2, then they must be matched to this school or better in any mechanism that computes a minimum stable re-allocation.



At step 0, this is true by Lemma 1.

Assume at step n, _2 moves student s_i to school h_j. This occurs when h_j has unmet capacity and s_i is (h_j). Any student that h_j prefers more than s_i and who is currently matched to a better school than h_j cannot be matched to h_j in any minimum stable reallocation, by the inductive hypothesis. So s_i must be matched to h_j or better.



We conclude that our algorithm moves students from their original schools only when they have to be moved, thus performing the minimum number of re-allocations.





All minimum stable re-allocations move the same set of students R.


The algorithm returns the school-optimal minimum stable re-allocation.
 

The algorithm runs in O(|R|*|H∪ H'|) time.
 





Since any minimum stable re-allocation moves the same set of students, it is easy to obtain the other minimum stable re-allocations. Let R be the set of students moved in M' and c_j(R) the number of students in R for school h_j. Let Barrier(h_j) be the (h_j) not in R, and M^† be a stable matching on R, and capacities c_j(R) for schools, where no school admits a student worse than its barrier. Then M^†∧ M^* is a minimum stable re-allocation.



Unfortunately, no mechanism that finds a minimum stable re-allocation can be incentive compatible as shown in Example <ref>.


Assume there are 2 students A,B and 3 schools 1,2,3. The preferences for A,B are (2,1,3),(1,2,3), respectively. The preferences for 1,2,3 are (A,B),(B,A),(A,B), respectively.
In R1, school 1 has 1 seat, and the other schools have no seats. In R2, schools 2 and 3 add 1 seat each. Under truthful reporting, (A,1) will be assigned in R1; assigning (B,2) in R2 is the only stable matching with no re-allocations. However, if A reports their preference as (2,3,1), the only stable matching in R2 is (A,2),(B,1).



Adding a new school, increasing capacities of some schools, and removing students from schools are all equivalent.



We first reduce adding a new school to increasing capacities of some schools. This can be achieved by fixing the capacity of the new school to be 0 in round _1, and then increasing its capacity in round _2.



To reduce increasing capacities of schools to removing students from schools, update the capacities of schools in round _1 and add dummy students who fill this extra capacity. In round _2 the dummy students are removed.



Removing students reduces to adding a new school by adding a school in round _2 who only likes the students to be removed, and whom all the students to be removed like more than their original schools.


	
	

§ MECHANISM FOR ADDING A NEW STUDENT



In the same vein as the previous section, we ask for a mechanism that finds a minimum stable re-allocation, under the addition of some new students N in round _2. Our mechanism finds a minimum stable re-allocation over any stable matching M. If M produced by _1 is a student-optimal matching we show that (_1, _2) is DSIC w.r.t reporting preference lists of students. We first show an example where running Gale-Shapley with the new students doesn't compute a minimum stable re-allocation over the underlying stable matching.  




Assume there are 3 students A,B,C and 2 schools 1,2,3. The preferences for A,B,C are (2,1,3),(1,2,3),(3,1,2), respectively. The preferences for 1,2 are (A,B,C),(B,A,C),(C,A,B), respectively. Each school has 1 seat.
In round _1, students A,B arrive. In round _2, student C arrives. Assume that (A,1),(B,2) is the stable matching computed in round _1. Leaving these pairings unchanged and adding (C,3) in round _2 is the only stable matching with no re-allocations. However, running Gale-Shapley from scratch yields (A,2),(B,1),(C,3), which requires a re-allocation.


For each school h_j we defined Worst-Student-Accepted(h_j) as the student who is currently matched to h_j and is preferred the least among all the other students matched to h_j.




When new students are added each student in M is matched to his original school, or worse, in any minimum stable re-allocation of M.



Assume that M' is a minimum stable re-allocation of M, and some students in M are matched to better schools in M'. Let M^* = M ∨ M', i.e. every student gets the worse school between M and M'.



We first show that M^* satisfies the capacity constraints of the schools. Let B be the students who did better in M', and who are not in N (i.e. they are moved back to their original school in M^*). If some students in B leave a school going from M to M', then the students who replace them at that school must also be in B. To see this, observe that the school must prefer the leaving students to the replacing students. If there is a replacing student not in B, they form a blocking pair with their original school in M.



Next we show that M^* is stable. Let (s_i,h_i),(s_j,h_j)∈ M^*, and (s_i,h_j) be a blocking pair. Then h_j is matched to s_j or worse in both M and M', but (s_i, h_i) must be in one of these matchings, contradicting stability. 



M^* is  a stable re-allocation of M and has |B| fewer re-allocations than M', a contradiction.




 of Theorem <ref>:
The proof is by induction. We show that if a student is matched to a school at any step by _2, then they must be matched to this school or worse in any minimum reallocation.



At step 0, this is true by Lemma 2.

Assume at step n _2 moves student s_i to school h_j. For any school h_k that s_i prefers to h_j, h_k must be full and s_i must be worse than the worst student currently accepted at h_k. Now, if s_i were to be admitted to h_k, then there must be some student currently admitted to h_k that must be removed. But by the inductive hypothesis, this student must be matched to a worse school, forming a blocking pair with h_k.




All minimum stable re-allocations move the same set of students R.


The algorithm returns the student-optimal minimum stable re-allocation.


The algorithm runs in O((|N∪ R|)*|H|) time.
 




As with the preceding setting, it is easy to find other minimum stable re-allocations by finding a stable matching M^† on R,c(R). For each student in R, we define Safety(s_i) to be the best school who prefers s_i to its worst admitted student not in R. We require that M^† does not match a student to a school worse than their safety.
Then M^†∨ M' is a minimum stable-reallocation.




Algorithm <ref> produces a stable minimum reallocation M' for any round _1 stable matching M. Under the special case that M is a student optimal matching, M' is the same as the matching produced by running Gale-Shapley on the entire set of students from both rounds. This follows as the algorithm can be seen as a continuation of Gale-Shapley on the round _2 participants, since each student proposes to schools in order of preference. The DSIC property of Gale-Shapley implies incentive compatibility of our algorithm when M is a student-optimal matching.



Removing a school, decreasing capacities of some schools, and adding new students are equivalent.


 
The reductions are symmetric to those in the preceding section.

	
	

§ NP-HARDNESS RESULTS




We show that many natural problems lying in the setting of two temporally-separated rounds are NP-complete. The first 3 problems involve stable extensions in round _2, where we are allowed to increase the capacities of schools but are not allowed to move students matched in round _1. Problem 4 asks if there is a way of moving some students in M to different schools in a way to accept more students and Problem 5 asks if there is a way of computing a single-round capacitated max weight stable matching. We define the problems formally below:

    

     A set of new students N arrive in round _2. Let L be the set of students in round _1 who are unmatched in M. The City wants to maximize the number of students in L with which the matching can be extended in a stability-preserving manner. Subject to this, the City wants to minimize the number of students N with which the matching can be extended in a stability-preserving manner. (MAX_L MIN_N)
    
    


    Same setting as Problem 1, but we want to first maximize the students in N, then, subject to this, minimize  the students in L. (MAX_N MIN_L)



    

    A set of new students N arrive in round _2. The City wants to extend the matching in a stability-preserving manner to include k students from N, such that we maximize the number of students matched from L.  It can be assumed without loss of generality that k is large enough to allow for a stable extension. (k-MAX_L)
    



     In round _2, we are allowed to increase the capacities of schools and re-allocate students. The City wants to maximize the number of students in L with which the matching can be updated in a stability-preserving manner. Subject to this, the City wants to minimize the number of re-allocations made to the original matching in round _1.

    

    Single-Round Capacitated Max-Weight Stable Matching: Given a set of students, and schools with strictly ordered preference lists l(s),l(h) respectively, and a weight function w(j) over the edges of students to schools, find a vector of capacities for the schools and a stable matching with respect to this vector that maximizes the total weight. 

    




Problems 1,2,3,4,5 are NP-complete.




For all the problems we reduce from an instance of cardinal set-cover problem. We denote an instance I of cardinal set-cover to have a sequence of sets S_i⊆ U and a universal set of elements U={e_1, .... e_m}

	
  * For every set S_i = { e_i1, e_i2, .., e_ik} we construct a corresponding school h_i. The preference list for each h_i is (n_i, e_i1,...., e_ik), where n_i ∈ N is a student who only wants to go to h_i. We set the capacities of the schools to 0 in round _1. In round _2 the n_i arrive. MAX_L MIN_N will match all e_j, and the fewest possible n_i. By our construction, when a student e_j is admitted to h_i, n_i must be admitted to h_i. Therefore the admitted n_i correspond to a optimal set cover.
	
	
  * The problem for MAX_N MIN_L is symmetric to MAX_L MIN_N. The only difference in the reduction is to have the gadget n_i be a student from L, and let the e_i be students in N.
	
	
  * For every set S_i = { e_i1, e_i2, .., e_ij} we construct a corresponding school h_i. The preference list for each h_i is (n_i, e_i1,...., e_ij), where n_i ∈ N is a student who only wants to go to h_i. We can then solve the decision version of set cover (i.e. is there a cover of size k?) by reducing to k-MAX_L and returning yes if all L are matched and no otherwise.
	
	
  * For every set S_i = { e_i1, e_i2, .., e_ik} we construct a corresponding school h_i. The preference list for each h_i is (w_i, e_i1,...., e_ik). We create another school h_0 whose preference list is (w_1, ... , w_n). Each w_i prefers h_i to h_0. We set the capacity of h_0 to n in round _1, and all other schools are set to capacity 0. In Round R2, all L will be admitted. To cover an element a school must re-allocate the corresponding w_i to that school, so minimizing the number of re-allocations corresponds to finding a minimum set cover.
	
	
  * For every set S_i = { e_i1, e_i2, .., e_ik} we construct a corresponding school h_i. The preference list for each h_i is (n_i, e_i1,...., e_ik), where n_i ∈ N is a student whose preference list is (h_i, h_0). 
    We add a school h_0 with preference list (n_1, n_2, .... ). We define weights on the edges in the following way:

    w(h_0, n_i) = 1,  w(h_j, n_i) = 0, w(h_j, e_ij) = 2.

    We note that any max-weight stable extension will match all e_ij. Therefore, we want to minimize the n_i's not matched to h_0. So the h_j who get matched to students correspond to the sets in an optimal set-cover.
	



	
	
	
	
	
	


	
	
	

§ ACKNOWLEDGEMENTS



We wish to thank Xi Chen for proposing Problem 3.
	
	alpha
	
	MV18

[MV18]MV.school
Tung Mai and Vijay V. Vazirani.
Stability-preserving, incentive-compatible, time-efficient mechanisms
  for increasing school capacity.
In arXiv, 2018.


	
