Next Article in Journal
Acknowledgement to Reviewers of Algorithms in 2013
Next Article in Special Issue
Faster and Simpler Approximation of Stable Matchings
Previous Article in Journal
Bio-Inspired Meta-Heuristics for Emergency Transportation Problems
Previous Article in Special Issue
On Stable Matchings and Flows
Article

Choice Function-Based Two-Sided Markets: Stability, Lattice Property, Path Independence and Algorithms

1
Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar tudósok körútja 2., Budapest 1117, Hungary
2
MTA-ELTE Egerváry Reseach Group, Pázmány Péter sétány 1/C, Budapest 1117, Hungary
3
Department of Operations Research, Eötvös Loránd University, Pázmány Péter sétány 1/C, Budapest 1117, Hungary
*
Author to whom correspondence should be addressed.
Received: 23 June 2013 / Revised: 29 December 2013 / Accepted: 18 January 2014 / Published: 14 February 2014
(This article belongs to the Special Issue Special Issue on Matching under Preferences)

Abstract

We build an abstract model, closely related to the stable marriage problem and motivated by Hungarian college admissions. We study different stability notions and show that an extension of the lattice property of stable marriages holds in these more general settings, even if the choice function on one side is not path independent. We lean on Tarski’s fixed point theorem and the substitutability property of choice functions. The main virtue of the work is that it exhibits practical, interesting examples, where non-path independent choice functions play a role, and proves various stability-related results.
Keywords: stable matchings; college admission; choice function; lattice stable matchings; college admission; choice function; lattice

1. Introduction

In this paper, we study different generalizations of Gale and Shapley’s marriage and college admissions model. In the original model, there are n men and n women, and each of them has a preference order on the members of the other gender. Gale and Shapley proved [1] that there always exists a stable solution, and it can be found with the so-called deferred acceptance algorithm. The output of this algorithm is a man-optimal solution (or, if we change the role of the genders, a woman-optimal one). In these stable marriage schemes, one side of the marriage market receives the best and the other side the worst possible partners. An observation attributed to Conway generalizes man and woman optimality. It states that stable marriages form a complete lattice for the partial order defined by the men. That is, if S 1 and S 2 are two stable marriage schemes and each man chooses the better out of his partners, then these choices determine another stable marriage scheme, denoted by S 1 S 2 . If men choose their less preferred partners, we get the stable scheme S 1 S 2 .
This similarly applies to colleges and students. It is important for both the marriage and the college models that each agent on the market has strict preference orders. If we allow ties in the preference orders, then there are three well-known extensions of stability: we can talk about weakly stable, strongly stable and superstable solutions.
The motivation of this work is a fourth notion that we call “score-stability”. This is the objective of the centralized mechanism that constructs the college admissions scheme in Hungary. We use the following rough model for the Hungarian college admissions problem. Each student submits a set of applications to different colleges and declares a linear preference order over these applications. Each college has a strict quota on the number of admissible students. There is a score assigned to each application based on the entrance exams. After all this information is known, each college declares a score limit, and each student is accepted at the first college on her preference list, where her score is not below the appropriate limit. These score limits have to be stable; that is, no college receives more students than its quota. Moreover, each college would receive more students than its quota if it lowers its score limit, while the other ones keep theirs.
Our models can also be described with substitutable choice functions, as in the paper of Kelso-Crawford [2], but our choice functions are not necessarily path independent. A well-known result of Blair in [3] generalizes the case of strict preferences, by proving that if both sides of the matching market has path-independent substitutable choice functions, then stable solutions form a lattice under a natural partial order. It seems that in the literature, most of the practical, interesting stability notions involve a path independent choice function (because, if authors define a choice function with subset-ordering, that implies path independence). A counterexample to this is the Hungarian college entrance mechanism, which outputs a stable solution, even though the choice functions are certainly not path independent. We shall generalize Blair’s theorem for models involving non-path-independent choice functions. It turns out that if we drop the path-independent property, then it is not at all clear what exactly a stable solution is. For this reason, we study four kinds of stabilities: dominating stability, three-stability (which is defined by a three-partition of the contract set), four-stability (which comes from a four-partition of the contract set) and score-stability. This last notion is also generalized to so-called “loser-free” choice functions, allowing us to work with more flexible models describing diverse market situations, like company-worker admissions, with no strict preference ordering on the company’s side.
We compare the above four different stability notions. We shall examine the connections between the definitions in regard to the path-independent property. Aygün and Sönmez [4] showed that if F, G are substitutable and path-independent choice functions, then three-stable and dominating stable sets are equivalent, but if F and G are not path independent, then none of the directions is true. We extend this by considering the other two stabilities (four-stability and score-stability), as well.
Our model has features similar to that of Azevedo and Leshno [5] about stable cutoffs, but when they considered a continuum number of students, the probability of ties between students was zero. In their discrete model, colleges had a strict preference order over students (so the choice function is path independent); hence, a college refuses someone only if its quota is full. However, in our model, a college may refuse someone while it still has free seats.
In Section 2, we define some basic notations about stable matchings. Section 3 describes four different stability concepts, including the Hungarian college admissions model. In Section 4, we utilize Tarski’s fixed point theorem to give algorithms for finding the two extreme solutions, while we study the lattice property in Section 5, where it turns out that domination stability is not so useful; however, using four-stability, it is relatively easy to extend Blair’s theorem. We conclude in Section 6, and the Appendix contains the proofs of the theorems, statements and lemmas missing from the previous sections.

2. Preliminaries

In the stable marriage model, there are n men: M = m 1 , m n ; and women: W = w 1 , w n ; each of them having a strict preference order on the members of the other gender. Let G be a bipartite graph with color classes M and W, and let E—the set of edges in G —denote the possible marriages.
In this work, contract and edge are synonyms of one another. They both describe a possible marriage or admission. The notion of a contract was introduced in [6]. Our model originally does not include money transfer or wages; the set of contracts is the set of edges of some underlying bipartite graph, G . However, we may allow multiple edges between two vertices of G , and by this, we can model discrete prices on the contracts, since discrete monetary transfers are equivalent to the possibility of multiple contracts.
The notation w < m w means that man m prefers woman w to w. A subset, S, of contracts is a matching or marriage scheme in G if no vertex of G is adjacent to more than one edge in S. A matching S E can also be described as an involution μ : M W M W , such that if m and w are married (that is, ( m , w ) S ), then μ ( m ) = w and μ ( w ) = m , and for an unmatched agent, a, we define μ ( a ) = a . A marriage scheme S is called stable if, for any pair, ( m , w ) S , μ ( m ) > m w or μ ( w ) > w m holds. Men’s preferences define a partial order on stable marriage schemes: S M S , if μ ( m i ) m i μ ( m i ) , for all m i M and S > M S , if S M S and there exists a man m i such that μ ( m i ) > m i μ ( m i ) . Similarly, there is another partial ordering, W , defined by the women. It is well known that a marriage scheme is unanimously better for men, if and only if it is unanimously worse for women.
Definition 1. We call a stable matching S male-optimal (female-optimal) if it is better for the men (women) than any other stable matching: S M S ( S W S ) for every stable matching, S .
A stable matching, S, is male-pessimal (female-pessimal) if S M S ( S W S ) for every stable matching, S .
The Gale–Shapley (or deferred acceptance) algorithm consists of rounds. In each round, every unengaged man proposes to the most-preferred woman to whom he has not yet proposed. Each woman then considers all her suitors and keeps her most preferred one and refuses the others. In the next round, all rejected men continue proposing to their next choice. The algorithm terminates if no new proposal occurs. This happens after at most c o n s t · n 2 steps, since every man proposes to every women at most once. The outcome of the algorithm is always a stable marriage scheme.
Theorem 1. [1] The stable marriage scheme given by the deferred acceptance algorithm is male-optimal and female-pessimal.
Knuth in [7] attributes the observation to John Conway that stable marriages form a distributive lattice.
Theorem 2 (Conway) Assume that S 1 and S 2 are two stable marriage schemes. Let every men choose the better of his partners in S 1 and S 2 . This way, we get a stable matching that we denote by S 1 S 2 .
If the women choose their better partner, we get stable matching S 1 S 2 . It follows that stable marriages form a lattice. Our models are based on the choice functions that we describe next. We shall see that “traditional” models nicely fit this non-traditional framework.
Definition 2. Set function F : 2 E 2 E is called a choice function if F ( A ) A holds for any subset, A, of ground set E.
For convenience, for a choice function, F, let F ¯ ( A ) = A F ( A ) denote the set of unselected elements. We list some important properties of set functions.
Definition 3. A set function, F : 2 E 2 E , is monotone if F ( A ) F ( B ) whenever A B E holds.
A set function, F : 2 E 2 E , is antitone if F ( A ) F ( B ) whenever A B E holds.
A choice function, F : 2 E 2 E , is substitutable (sometimes called comonotone) if F ¯ ( A ) F ¯ ( B ) for any A B (that is, if F ¯ is a monotone function).
The substitutable property was originally defined by [2] with prices, differently from our definition. It was showed in, e.g., [6], that substitutability is equivalent with the property that if an agent chooses from an extended set of contracts, the set of rejected contracts expands.
Definition 4. A choice function, F : 2 E 2 E , is path independent, if F ( A ) B A implies F ( A ) = F ( B ) for any subsets, A and B, of E.
Path independence is called “irrelevance of rejected contracts (IRC)” in the paper of Aygün and Sönmez [4]:
Definition 5. [4] Contracts satisfy the irrelevance of rejected contracts (IRC) for choice function F if Y X , z X Y z F ( Y { z } ) F ( Y ) = F ( Y { z } )
Clearly, if the set of contracts is finite, this is equivalent to our path independence definition.
There is an alternative way to define path independence (see e.g., [8]):
Theorem 3. For a substitutable choice function, F, the path independence of F is equivalent, so that F ( A B ) = F ( F ( A ) F ( B ) ) hold for any sets, A and B, of choices.
Sometimes, the choice function is defined by a strict preference order over all subsets of E, such that F ( A ) is that subset of A that is the first in the order. In that case, the choice function will be automatically path independent, since if the best set in A is S and S B A , then the best set in B is S, as well. We will see, however, that typical scoring choice functions are not path independent. Therefore, we shall study path functions that are not necessarily independent more generally.
We can define the direct sum of two choice functions: if X Y = and F 1 : 2 X 2 X , F 2 : 2 Y 2 Y , F : 2 X Y 2 X Y ; then, F = F 1 + F 2 means that for every A X Y , F ( A ) = F 1 ( A X ) F 2 ( A Y ) . For example, on the graph of possible marriages, w 1 chooses from the contracts, w 1 m i , and w 2 chooses from the contracts, w 2 m i (so these two sets are disjoint). The sum of all women’s choice function will choose from all of the contracts.

2.1. Examples for Choice Functions

Here, we list some typical choice functions. Some of them are coming from practical applications, while some others are mostly theoretical, illustrating the flexibility of substitutable choice functions. Let v be an agent ( i.e., a vertex of G = ( V , E ) ), and let E ( v ) be the set of possible contracts involving v ( i.e., the edges from v).
  • Agent v’s preferences are strict and always choose the best one: F ( X ) = the best member of X.
  • Preferences are strict, and we allow polygamy ( i.e., a college can have more than one student). The choice function picks the best k contracts for some fixed k: F ( X ) = the best k members of X. If | X | k , then F ( X ) = X .
  • We allow ties in the preference list. Here, v chooses the best partner if it is unique and chooses the empty set if there is more than one best partner.
  • We allow ties in the preference list. Agent v chooses the best partner if it is unique, and it chooses the set of best partners if there are two or more.
  • Let Q k be the following choice function on E ( v ) : for A E ( v ) , if | A | k , then Q k ( A ) = A , and if | A | > k , then Q k ( A ) = .
  • Hungarian (H-scoring) choice function: Every contract has a certain integral score: in the college admissions model, this is the number of points that the corresponding student reached at the particular college’s entrance exam. There is also a quota, q. If X is a given set of contracts, then v picks score t, such that there are k contracts in X having a score of at least t and k q , and there are more than q contracts receiving a score of at least t - 1 . If no such t exists, then v picks t = 0 . The choice function selects the contracts from X having a score of at least t. For example, if v is offered four contracts with scores of three, two, two and one and the quota is q = 2 , then v chooses only the best contract with a score of three ( i.e., t = 3 ).
  • Permissive (L-scoring) choice function: Agent v has a quota, q, but it might choose more than q contracts. Namely, v chooses the best k 2 q contracts in a way that it chooses the best k q using the previous H-scoring method (with score limit t), and if k < q , then v adds the next group of applicants with score t - 1 . If the H-scoring function chooses exactly k = q applicants, then v keeps them and does not add new students. Score-stability defined with this choice function was called L-stable in [9]. In the previous example, v would set the score limit at two and pick three applicants with scores of three, two and two.
  • The weighted scoring choice function is similar to the H-scoring choice function, except every contract also has a cost. Agent v has a budget, k, instead of a quota, q. For a given X set of contracts, v determines t in such a way that the total cost of contracts having a score of at least t is not more than k, but the total cost of contracts having a score of at least t - 1 is more than k. If no such t exists, then t = 0 . Now, v chooses those contracts from X that have a score of at least t. For example, if v has four applicants according to the table below:
    a 1 a 2 a 3 a 4
    scores4321
    cost9551
    and the budget is 10, then v chooses only a 1 . (Agent v cannot skip some applicants and choose a cost of 9 + 1 .)
  • Strict hierarchical choice function: Agent v has a linear preference list over contracts, and there is a downward closed set system, I , of subsets of E ( v ) (that is, if A I , B A , then B I ). Let k be the greatest number, such that the set of k best contracts of set X belongs to I . Now, C ( X ) is the set of these k best applicants.
  • Weak hierarchical choice function: Agent v has a weak preference order (ties are allowed) over the contracts, and there is a downward closed set system, I , of subsets of E ( v ) . Let k be the greatest number, such that the set of k best contracts of set A is in I , and among equally good contracts, we choose all or none. Now, C ( A ) is the set of these k best applicants.
Statement 1. If the costs are increasing (a contract with a lower score is more expensive), then the weighted scoring choice function is path independent.
Proof. From set A, the college’s preference order is c 1 c 2 c n (contract c 1 has the best score; c n has the worst). If F ( A ) B A and F ( A ) = { c 1 , c 2 c k } , then by definition, the college cannot add the next best applicant, c k + 1 , to F ( A ) . Other contracts in B F ( A ) are more expensive than c k + 1 , so the college cannot choose any of them. Therefore, F ( B ) = F ( A ) . ☐
Definition 6. Assume that each contract, c, has some score, s ( c ) . A choice function, F, is loser-free if any rejected contract has a lower score than any accepted contract. That is, s ( c ) < s ( c ) holds whenever c F ( X ) and c X F ( X ) .
Note that the above Examples 1, 2, 4 and 7 are path independent. All of the above examples are substitutable and loser-free.
Remark 1. Any weighted scoring choice function is weak hierarchical, and any weak hierarchical is loser-free. However, not every loser-free choice function is weak hierarchical:
Example 1. If a > b > c and F ( A ) = A if | A | 2 and F ( { a , b , c } ) = { a } , then F is loser-free and substitutable. However: F ( { a , b } ) = { a , b } , so { a , b } is supposed to be a set in I ; however, F ( { a , b , c } ) { a , b } , so this function is not hierarchical.
Not every weak hierarchical function is a weighted scoring choice function:
Example 2. The set of contracts is E = { a , b , c , d } ; the preference order is a > b > c > d , and I = { , { a } , { b } , { c } , { d } , { a , b } { c , d } } . Therefore, for example, F ( { a , b , c } ) = { a , b } . However, if we want to describe it with weights: the weight limit is Q. Sets { a , b } and { c , d } are under Q, but { a , c } and { b , d } are “heavier” than Q. Therefore, { a , b , c , d } are under and above 2 Q at the same time. This is a contradiction.

3. Stability Concepts

In this section, we formulate different stability concepts, which we shall study later.

3.1. Dominating Stability

In the original stable marriage model, a matching is stable, if it dominates every other contract; so, for every e = ( m , w ) S , either μ ( m ) > m e or μ ( w ) > w e . A natural generalization of the notion is dominating stability. In the article of Hatfield and Milgrom [6], they defined stable allocations similar to our dominating stability definition. They said that a doctor-hospital allocation is stable if there is no blocking contract set.
Unfortunately, it turns out that for non-path-independent choice functions, a dominating stable solution might not exist. Although this is the direct generalization of the original stability notion of Gale and Shapley, it seems that in practical applications, this notion does not help too much.
Definition 7. We say that a contract set, X, is F-dominated by S if F ( S X ) X = .
This means if the agent can choose from the union of sets S and X, he will choose S or a subset of S. Based on this, we introduce the dominating function:
Definition 8. For choice function F : 2 X 2 X , let dominating function:
D F ( A ) : = { x X : x F ( A { x } ) }
denote the set of contracts F-dominated by A.
Note that D F ( A ) A = F ¯ ( A ) .
Statement 2. If F is a substitutable choice function, then D F is monotone.
Proof. Let A B . If x D F ( A ) then x F ( A { x } ) x F ¯ ( A { x } ) . Since F is substitutable, x F ¯ ( B { x } ) x F ( B { x } ) so x D F ( B ) . ☐
Examples for choice functions and corresponding dominating functions:
Example 3. F 1 = Q 1 : There are two students interested in the same college, with equal scores, but the quota is one. If someone applies alone, he is accepted, but if both of them apply, the college rejects both.
F 2 = Q 2 : There are two students applying for the same college, with equal scores. The quota is two, so everybody is accepted.
F 3 : There are two students applying for the same college. a is better then b, and the quota is one. Therefore, the college chooses a.
{ a } { b } { a , b }
F 1 { a } { b }
D F 1 { b } { a } { a , b }
F 2 { a } { b } { a , b }
D F 2
F 3 { a } { b } { a }
D F 2 { b } { b }
The dominating function has some properties that will be useful later.
Lemma 1. If F is substitutable and path independent, then F ( A ) = S D F ( S ) A = A S . This means the set, A S , is dominated by S if and only if each contract, c A S , is dominated by S.
Lemma 2. If F is substitutable, path independent and F ( A ) = S , then D F ( A ) = D F ( S ) .
Definition 9. Subset S of E is dominating stable, if D F ( S ) D G ( S ) = E S .
Therefore, every e S is either F-dominated or G-dominated by S.
Remark 2. If S is dominating stable, then F ( S ) = S = G ( S ) , so the set, S, is acceptable for both sides.
Proof. Suppose that s S F ( S ) . Then, by definition, s D F ( S ) , but D F ( S ) E S ; a contradiction. For G, a similar proof applies. ☐
Example 4. Men and women have strict preferences. F is the common choice function of men, and G is the common choice function of women, which choose the single best option for every player. If S is dominating stable, then from F ( S ) = S = G ( S ) , set S is a matching, and for every e = m w S , contract e F ( S { e } ) or e G ( S { e } ) , so that one of m or w does not want to choose m w instead of his/her current marriage. Therefore, in this case dominating stability is equivalent to the original stable marriage definition of Gale and Shapley.
Note that even for substitutable F and G, a dominating stable solution does not always exists.
Example 5. Let F and G be the following functions, defined on a set of three contracts: { a , b , c } . F chooses everything, and G prefers a to b, b to c and c to a.
Now, F is substitutable and path independent, and G is substitutable, but not path independent.
{ a } { b } { c } { a , b } { b , c } { a , c } { a , b , c }
F { a } { b } { c } { a , b } { b , c } { a , c } { a , b , c }
G { a } { b } { c } { a } { b } { c }
D F
D G { b } { c } { a } { b , c } { c , a } { a , b } { a , b , c }
Suppose that S is dominating stable. Since G ( S ) = S , the cardinality of S is at most one. However, then, D F ( S ) D G ( S ) = D G ( S ) E S , because every contract dominates only one other contract.
A similar example appeared in [4].

3.2. Three-Stability

Fleiner defined the following stability concept, for a two-sided market, where the choice functions of each side over the contracts are F and G:
Definition 10. [8] Subset S of E is three-stable, if there exists subsets A and B of E, such that F ( A ) = S = G ( B ) and A B = E , A B = S . Pair ( A , B ) with this property is called a three-stable pair, and S is a three-stable set.
The explanation of the name, three-stable, is that we partition the set E of contracts into three parts, as showed in the Figure 1, S, A S and B S , where S is stable, A S is F-dominated by S and B S is G-dominated by S.
In the original marriage model, F and G select the one best partner for the men and women. It is easy to see that every three-stable set, S, is a matching, and it is stable, since men prefer contracts in S to A S and women prefer S to B S .
On the other hand, if S is a stable matching, then it is also a three-stable set with the pair ( A , B ) , where we define A S as the set of contracts that the men prefer less than the contracts of S and B : = S ( E A ) .
Example 6. Figure 2 illustrates a small example for a possible market. There are two possible contracts, a and b, and F = Q 1 , G = Q 1 ; then, only S = is three-stable, and it can be achieved with two ( A , B ) three-stable pairs, where A = { a , b } , B = or A = , B = { a , b }
Figure 1. Three-partition of the edge-set.
Figure 1. Three-partition of the edge-set.
Algorithms 07 00032 g001
Figure 2. Example for three-stability.
Figure 2. Example for three-stability.
Algorithms 07 00032 g002

3.3. Four-Stability

We introduce the notion of four-stability: it is kind of similar to three-stability, but while a double dominated contract, e, can belong to both A and B in the three-stable sometimes, now, we put e in a fourth contract-set. Therefore, while three-stability is a more natural definition, four-stability has nicer properties and is more useful, because it is closely related to score-stability. Moreover, for path-independent choice functions, for any four-stable set, the corresponding ( A , B ) pair is unique.
Definition 11. The choice functions of the two sides of the market are F and G. Subset S of E is four-stable, if there exists subsets A and B of E, such that F ( A ) = S = G ( B ) and A B = S and D F ( A ) = E B , D G ( B ) = E A .
Figure 3. Four-partition of the edge-set.
Figure 3. Four-partition of the edge-set.
Algorithms 07 00032 g003
This concept is called four-stable because we partition the set E of contracts into four parts, as seen in Figure 3: S is stable; A S is F-dominated by S; B S is G-dominated by S; and the contracts in E ( A B ) are both F- and G-dominated.
Example 7. We consider the same example as for three-stability: There are two possible contracts, a and b, and F = Q 1 , G = Q 1 . Now, there are three four-stable solutions:
S = , where A = { a , b } , B = or A = , B = { a , b }
S = { a } , A = { a } , B = { a }
S = { b } , A = { b } , B = { b }
Remark 3. If F and G are substitutable choice functions and S is three-stable or four-stable, then F ( S ) = S = G ( S ) .
Proof. Since F ( A ) = S and F ¯ ( S ) F ¯ ( A ) = A S , F ( S ) = S . Similarly, G ( B ) = S implies G ( S ) = S . ☐
Statement 3. If F and G are substitutable and F is path independent, then for a four-stable set, S, there exists a unique ( A , B ) pair.

3.4. Score-Stability

In this part, we describe the stability notion used in the Hungarian college admission scheme. For this reason, we shall call the agents colleges and applicants, and application is a synonym for contract. The mathematical model of the Hungarian college admissions system is close to stable matchings. Our model is a simplified version of the one that is used in practice. Biró, Kiselgof [9], Azevedo and Leshno [5] also examined the math behind stable score limits.
We shall generalize the model for loser-free choice functions, in particular for weighed scoring choice functions that have possible practical applications.
Assume that we have n applicants A 1 , A 2 , , A n and m colleges C 1 , C 2 , C m . Let E be the set of all contracts. It is convenient to think that E is the set of edges of the bipartite graph with color classes { A 1 , , A n } and { C 1 , , C m } , where each edge, A i C j , of the graph corresponds to a contract between applicant A i and college C j . There, every applicant has a strict preference order over the colleges she applies to, and each college assigns some score s ( A i C j ) (an integer between one and M) to each of its applicants. Moreover, each college, C, has a quota, q ( C ) , on admissible applicants. According to the law, no college can accept more applicants than its quota; moreover if an applicant, A i , with a certain score, s ( A i C j ) , is not acceptable to some college, C j , then any applicant with the same or lower score has to be unacceptable for C j .
To determine the admissions after all information is known, each college has to declare a score limit. Let the score limits for colleges C 1 , C 2 , C m be t 1 , t 2 , t m , respectively. Each applicant will become a student at her most preferred college where she has a high enough score. More precisely, applicant A i is assigned to college C j if s ( A i C j ) t j ( i.e., score s ( A i C j ) of A i at C j is not less than threshold t j for C j ) and s ( A i C j n ) < t j for j > i j ( i.e., score s ( A i C j ) of A i at C j is less than the score limit, t j , if A i likes C j more than C j ). The vector of declared score limits ( t 1 , t 2 , , t m ) is called a score vector. The stability notion below is defined according to the requirements of Hungarian law.
Definition 12. Score vector ( t 1 , t 2 , t m ) is valid if no college exceeds its quota with these score limits.
Score vector ( t 1 , t 2 , t m ) is critical if for every college, C j , either t j = 0 or score vector ( t 1 , t 2 , , t j - 1 , t j - 1 , t j + 1 , , t m ) would assign more than q ( C j ) students to C j (that is, no single college can decrease its score limit without exceeding its quota).
A score vector, s ̲ , is score-stable if s ̲ is valid and critical.
The above college admissions model determines a natural choice function for applicants and another one for the colleges. Therefore, for subset X E of contracts, F i ( X ) denotes the most preferred contract from X of applicant A i , and F ( X ) is the common choice function of all applicants. Therefore, F = F 1 + F 2 + F n . Similarly, G j ( X ) denotes the set of contracts that college C j would choose if it can select freely. More precisely, let X j denote the set of contracts with C j in X, and let C j declare a score limit, t j , such that no more than q ( C j ) contracts from X j has score of at least t j , but either t j = 0 or more than q ( C j ) contracts has a score of at least t j - 1 . Let G j ( X ) be the set of all contracts in X j above the score limit, t j . Define choice function G : 2 E 2 E as the common choice function of all colleges, G = G 1 + G 2 + G m .
It is easy to see that choice function F of the applicants is path independent, but G for the colleges is not.
For example, G = Q 1 is a typical scoring choice function; there are two equally good contracts, a , b , and the quota is one. However, G ( { a , b } ) = { a } { a , b } and G ( { a } ) G ( { a , b } ) , so it is not path independent.

3.5. Generalized Score-Stability

We can generalize the above framework, keeping the main property needed to ensure the existence of a stable solution, namely the loser-free property that allows us to extend the model in a way that is fairly generalized and has economically interesting choice functions.
Let F be direct sum of substitutable choice functions of the applicants, and G is a direct sum of loser-free, substitutable choice functions of the colleges. Every college, C j , has a choice function, G j , over the contracts involving it, and G = G 1 + G m .
We say a set { A i 1 , A i 2 , A i k } of applicants is feasible for college C j if G j ( X ) = X for the contract set X = { A i 1 C j , A i 2 C j , A i k C j } ; otherwise, it is infeasible. Each contract, c, has a score, s ( c ) .
Lemma 3. A choice function G : 2 E 2 E is loser-free if and only if there exists a function P G : 2 E N E , such that for every set A E of contracts, P G gives the score-limit, for which the accepted contracts above the score limit are exactly the set accepted by G ( A ) .
Proof. If G is loser-free, the set of accepted contracts from A are all above a score limit; let the maximal score limit they reach be P G ( A ) . On the other hand, if we have a given score limit by P G , no one can be missed out, while others with the same score get in; so, G must be loser-free. ☐
Let P : N E 2 E be a function, that codes the scores of the applicants: P ( t ) is the set of contracts above the score limit given by score vector t ̲ . P ( t ̲ ) = { A C E : s ( A C ) t ( C ) } . Therefore, P ( 0 ̲ ) = E and P is antitone on the scores: if t ̲ 1 t ̲ 2 , then P ( t ̲ 1 ) P ( t ̲ 2 ) .
Note that P ( P G ( A ) ) A = G ( A ) for every A E .
There exists a score vector T ̲ (a highest possible score of +1 for every college), where P ( T ̲ ) = . From contracts above the score limit, the students choose F ( P ( t ̲ ) ) , and contract set G ( F ( P ( t ̲ ) ) ) is acceptable for the colleges. Therefore, score vector t ̲ is valid if and only if G ( F ( P ( t ̲ ) ) ) = F ( P ( t ̲ ) ) .
The score vector, t ̲ , is critical if for any 1 j m , the new score vector ( t 1 , t 2 , , t j - 1 , t j - 1 , t j + 1 , , t m ) is not valid for college C j , or t j = 0 . We call t ̲ stable if it is both valid and critical.
Lemma 4. If t ̲ is valid, but t ̲ = ( t 1 , t 2 , , t j - 1 , t j - 1 , t j + 1 , , t m ) is not, then the only college that can get an infeasible set of students at score vector t ̲ is college C j .
Proof. The set of offered places increases at college C j and stays unchanged at other colleges. For applicant A i , if she rejected a college, C k , earlier (where C k C j ), she will also reject C k when she has more choices, so colleges other than C j cannot have too many students.
With score limit t ̲ , the set of students going to college C k is F ( P ( t ̲ ) ) E ( C k ) ; denote it by Z. Additionally, with score limit t ̲ , it is Z . As we have seen, Z Z , and from the substitutability, G k ( Z ) = Z implies G k ( Z ) = Z . ☐
Definition 13. We call a score vector t ̲ C j -valid, if it is acceptable for college C j , i.e., G j ( F ( P ( t ̲ ) ) ) = F ( P ( t ̲ ) ) E ( C j ) ) .
The following two lemmas help to understand how the set of the valid score vectors look:
Lemma 5. Let t ̲ and t ̲ be two score vectors, and t ̲ is C j -valid. For college C j , score limit t j t j , but t i t i for every college C i C j . Then, t ̲ is also C j -valid.
Lemma 6. Let t ̲ 1 and t ̲ 2 be two valid score vectors, and t ̲ m i n is their pointwise minimum ( t j m i n = min ( t j 1 , t j 2 ) for every 1 j m ). Then, t ̲ m i n is also valid.

4. Algorithms

In this section, we show algorithms to find three-stable, four-stable and score-stable allocations. As we will see, these stable solutions always exist, if F and G are substitutable (and G is also loser-free in the case of score-stability). Moreover, these algorithms give us the men-optimal/women-optimal solutions. We show a close connection between Tarski’s fixed theorem and the Gale–Shapley algorithm.

4.1. Tarski’s Fixed Point Theorem

Recall that a lattice is a partially ordered set, L, with the property that any two elements, x , y , of L have a greatest lower bound x y and a least upper bound x y . A lattice, L, is complete if any subset, X, of L has a greatest lower bound X and a least upper bound X . Function f : L L from lattice L to lattice L is monotone if x y implies f ( x ) f ( y ) for any elements, x , y , of L.
Theorem 4 (Tarski’s fixed point theorem [10]). Let L be a complete lattice and f : L L be a monotone function on L. Then, set L f = { x L : f ( x ) = x ) } of fixed points of f is a nonempty, complete lattice on the restricted partial order.
If lattice L is finite in Theorem 4, there is a straightforward algorithm to find the least and greatest fixed points. Let zero be the smallest element in lattice L. Therefore, 0 f ( 0 ) and from monotonity 0 f ( 0 ) f ( f ( 0 ) ) f ( f ( f ( 0 ) ) ) . Since the lattice is finite, there exists an i, where f i ( 0 ) = f i + 1 ( 0 ) . Therefore, f i ( 0 ) is a fixed point.
Statement 4. The above fixed point a = f i ( 0 ) is the least of all fixed points of f.
Proof. Let x be an arbitrary fixed point of f. Since f is monotone, 0 x f ( 0 ) f ( x ) = x and f j ( 0 ) f j ( x ) = x for every j 1 . We get that a = f i ( 0 ) x . ☐
Similarly, we can start with the greatest element one. From 1 f ( 1 ) f ( f ( 1 ) ) f ( f ( f ( 1 ) ) ) , we see that there is a j, such that f j ( 1 ) = f j + 1 ( 1 ) .
This f j ( 1 ) is the greatest of all fixed points of f.

4.2. Generalized Gale–Shapley Algorithm for Three-Stable and Four-Stable Sets

For three-stable sets, we can generalize the Gale–Shapley algorithm to the case where both choice functions are substitutable, but they do not have to be path independent. It is a special case of the monotone function iteration that finds a fixed point of a monotone function. The following algorithm is the same as in [6]:
Let F be the choice function of men/students, and G is the choice function of women/colleges. In the male-proposing version, let X 1 = E ; men choose from all contracts and propose to Y 1 = F ( E ) = E F ¯ ( E ) . Women choose G ( F ( E ) ) and reject G ¯ ( F ( E ) ) . In the second step, men choose from all contracts, except for the rejected ones: X 2 = E G ¯ ( Y 1 ) = E G ¯ ( F ( X 1 ) ) . They choose F ( X 2 ) . The women take these contracts and the previously rejected contracts and choose from Y 2 = F ( X 2 ) G ¯ ( F ( X 1 ) = E F ¯ ( X 2 ) . Since G is substitutable, if a contract was rejected earlier, it will be rejected in this step, as well.
Here, this algorithm differs from the original Gale–Shapley, since there, women choose only from their current proposals. However, if G is path independent, then G ( Y 2 ) F ( X 2 ) Y 2 implies G ( Y 2 ) = G ( F ( X 2 ) ) ; so, putting back already refused proposals to the choice set does not change the outcome.
A general step of the algorithm: for a given X i , let Y i = E F ¯ ( X i ) , and let X i + 1 = E G ¯ ( Y i ) . Define the following function, f:
f ( X i , Y i ) = ( E G ¯ ( Y i ) , E F ¯ ( E G ¯ ( Y i ) ) )
We can define a partial order on pairs ( A , B ) ( A , B ) , if A A and B B .
Observe that f is monotone for this ordering. The iteration of this monotone function gives us a fixed pair ( X i , Y i ) , which corresponds to a three-stable pair ( A , B ) . If we start our iteration from pair ( X 1 , Y 1 ) = ( E , F ( E ) ) , we get the male-optimal matching; if we start from ( X 1 , Y 1 ) = ( , ) , we get the female-optimal one.
There is an alternative algorithm similar to the previous one:
Define function f : 2 E × 2 E 2 E × 2 E by:
f ( A , B ) : = ( E ( G ¯ ( B ) ) , E ( F ¯ ( A ) )
If F and G are substitutable, then f is monotone for order ≤, since, if B decreases, then G ¯ ( B ) decreases; so E G ¯ ( B ) increases. Similarly, if A increases, then E F ¯ ( A ) decreases.
As before, three-stable pairs are exactly the fixed points of f . We start the iteration from ( A 1 , B 1 ) = ( E , ) for the men-optimal or with ( A 1 , B 1 ) = ( , E ) for the women-optimal solution.
For four-stability, we define monotone function f as follows:
f ( A , B ) : = ( E ( D G ( B ) ) , E ( D F ( A ) ) )
If F , G are substitutable, then D F , D G are monotone; therefore, f is monotone for order ≤. Fixed points of f are four-stable pairs ( A , B ) , since A = E ( D G ( B ) ) , B = E ( D F ( A ) ) ) .
If we start the iteration of f from ( A 1 , B 1 ) = ( E , ) , we get a four-stable pair with the largest possible A and smallest possible B; so, it is men-optimal. Starting pair ( A 1 , B 1 ) = ( , E ) leads to the women-optimal solution.

4.3. Algorithms for Score-Stability

In this section, we describe algorithms for the generalized score-stability, hence also for score-stability.
1. The score-decreasing algorithm: colleges start from a valid score vector t 0 ̲ (e.g., t C ̲ : = ( M + 1 , , M + 1 ) ). First, if there is a college, C i , that can lower its score limit without getting too many students, then C i will decrease its score limit to the lowest score, such that C i still gets a feasible set of students. Here, C i chooses from free students and students who prefer C i to their college; so, it chooses score limit P G i ( E D F ( P ( t ̲ ) ) . Then, we find another college, and iterate this score-decreasing step. (It is convenient to check C 1 first, then C 2 , then all colleges one-by-one. After C m , we return to C 1 again.) The algorithm terminates if no college wants to lower its score limit any more. As soon as no college can decrease its score limit, the score vector is stable. Let s C ̲ denote the stable score vector that we get by running the score-decreasing algorithm on t C ̲ .
Theorem 5. If stable score vector t ̲ is the output of the score-decreasing algorithm with input t 0 ̲ , where t 0 ̲ is valid, then t ̲ is stable and is t ̲ , the maximum of all the stable score vectors that are not greater than t 0 ̲ . Consequently, s C ̲ is the maximum of all stable score vectors. Furthermore, s C ̲ is applicant-pessimal.
2. The score-increasing algorithm: colleges start with some critical score vector, t 0 ̲ (e.g., t A ̲ = ( 0 , , 0 ) ), and keep on raising their score limits. If there is a college, C i , that has an infeasible set of students, then it raises the score limit to the lowest score where it becomes feasible. Therefore, it chooses P G i ( F ( P ( t ̲ ) ) . Then, another college, C j , increases the score limit and all colleges one-by-one. The algorithm stops if no college wants to raise its score limit. Let s A ̲ be the stable score vector the score-increasing algorithm outputs from input t A ̲ .
Theorem 6. If score vector t ̲ is the output of the score-increasing algorithm with input t 0 ̲ , where t 0 ̲ is critical, then t ̲ is stable, and it is the minimum of all the stable score vectors that are not less than t 0 ̲ . Consequently, s A ̲ is the minimum of all stable score vectors. Moreover, s A ̲ is applicant-optimal.
Theorem 7. The score-decreasing and score-increasing algorithms run in polynomial time; the decreasing terminates in O ( m 2 n ) steps, and the increasing stops in O ( m n ) steps.

5. The Lattice Property

Tarski’s Theorem implies the following corollary for three-stability.
Theorem 8. [8] If F , G : 2 E 2 E are substitutable choice functions, then three-stable pairs form a nonempty complete lattice for partial order ≤.
Define function f : 2 E × 2 E 2 E × 2 E by:
f ( A , B ) : = ( E ( G ¯ ( B ) ) , E ( F ¯ ( A ) ) = ( E ( B G ( B ) ) , E ( A F ( A ) )
It is straightforward to see that three-stable pairs are exactly the fixed points of f. Therefore, since f is monotone, three-stable pairs form a lattice.
A similar theorem can be proven for the four-stable ( A , B ) pairs:
Theorem 9. If F , G : 2 E 2 E are substitutable choice functions, then the four-stable pairs form a nonempty complete lattice for partial order ≤.
Function
f ( A , B ) : = ( E ( D G ( B ) ) , E ( D F ( A ) ) )
is monotone, and its fixed points are exactly the four-stable pairs; so, we can use Tarski’s theorem again.

5.1. Generalization of Blair’s Theorem

In this subsection, we show a lattice property of stable sets (rather than stable pairs).
Definition 14. Define a new partial order: for choice function F, let S F S if F ( S S ) = S .
Observation 1. [3] If F is substitutable and path independent, then F is indeed a partial order; in particular, A F B F C implies A F C .
Blair proved the lattice property of dominating stable sets assuming the path-independent property of the choice functions [3]. As we will see in Theorem 15, if F and G are both path independent, the dominating stability, three-stability and four-stability are equivalent, so Blair’s theorem holds for each of these notions.
Theorem 10 (Blair). [3] If F , G : 2 E 2 E are substitutable, path-independent choice functions, then the dominating stable sets form a lattice for partial order F .
We generalize the above lattice property for four-stability, and there is a close connection between score-stability and four-stability. Now, we require path independency on only one side.
Theorem 11 (Generalization of Blair’s theorem). If F and G are substitutable choice functions and F is path independent, then: The four-stable sets form a lattice for partial order F ; If S is a four-stable set, then, there is a unique four-stable pair ( A , B ) that corresponds to S; furthermore, S F S if and only if ( A , B ) ( A , B ) .
If only one of F and G is path independent, dominating stable sets do not form a lattice. Moreover, dominating stable sets do not necessarily exist, as we have seen is SubSection 3.1.
Example 8. Given one college, C 1 , and two applicants, A 1 , A 1 , and two contracts, a = A 1 C 1 and b = A 2 C 1 . The college has a quota of one, and both applicants want to go to C 1 ; so, G = Q 1 , F = Q 2 . The dominating stable solutions are { a } and { b } ; however, a and b are uncomparable, since F ( { a , b } ) = { a , b } . Therefore, the dominating stable sets do not form a lattice.
Remark 4. If F and G are substitutable choice functions, but none of them is path independent, then the lattice property does not always hold for four-stability. It is also false that for stable set S there is only one corresponding ( A , B ) pair.
Example 9. We have two contracts, a and b. The choice function is Q 1 for both sides. In this situation, we have four four-stable pairs:
A = B = { a , b } S =
A = { a } B = { a } S = { a }
A = { b } B = { b } S = { b }
A = { a , b } B = S =
Now, F { a } and F { b } , but { a } and { b } are uncomparable. Therefore, these two sets do not have a supremum.

5.2. The Lattice of Stable Score Vectors

A graph, G, is simple if G has neither parallel edges nor loops. Therefore, between a given student and college, only one contract is permitted. In some applications, for example in the college enrollment system, the underlying graph is simple: one cannot apply to the same department, in the same year, twice. For the sake of generalizations that involve for example loser-free choice functions, the underlying graph in our model may not be simple.
Assume that F and G are substitutable choice functions and G is also loser-free. Define the following function f : N E N E :
f ( t ̲ ) = P G ( E D F ( P ( t ̲ ) ) )
Therefore, we take all contracts above score limit t ̲ (this is P ( t ̲ ) ) and add those contracts that are not dominated by P ( t ̲ ) . Then, f ( t ̲ ) is the score limit that the colleges choose for this set.
If t ̲ 1 t ̲ 2 , then P ( t ̲ 1 ) P ( t ̲ 2 ) . Since D F is monotone, E D F ( P ( t ̲ 1 ) ) ) E D F ( P ( t ̲ 2 ) ) ) . For a greater set, P G gives a higher score limit; so, P G ( E D F ( P ( t ̲ 1 ) ) ) P G ( E D F ( P ( t ̲ 2 ) ) ) . Therefore, f is a monotone function, indeed.
Statement 5. If the underlying graph, G , is simple, and choice functions F and G are substitutable, G is loser-free; then, score vector t ̲ is stable if and only if t ̲ = P G ( E D F ( P ( t ̲ ) ) ) .
Tarski’s fixed point theorem implies the following corollary:
Theorem 12. If graph G is simple, choice functions F and G are substitutable and G is loser-free, then the score-stable sets form a non-empty lattice.
Moreover, we can achieve a connection with four-stability for every bipartite graph.
Statement 6. If choice functions F and G are substitutable, G is loser-free and F is path independent, then the following two statements are equivalent: (i) S = F ( P ( t ̲ ) ) for some score vector t ̲ , such that f ( t ̲ ) = t ̲ . (ii) The contract set S is four-stable.
As a corollary of Statements 5 and 6, we get the following theorem:
Theorem 13. If choice functions F and G are substitutable, G is loser-free and the applicants’ choice function F is path independent, then every score-stable set is also four-stable. Furthermore, if we require that graph G is simple, then score-stability is equivalent with four-stability.
Example 10. Figure 4 illustrates a counterexample for Theorem 13 if the underlying graph is not simple.
Figure 4. A counterexample.
Figure 4. A counterexample.
Algorithms 07 00032 g004
There is one college and one student, and the student applies both for math and physics, but prefers math. She achieved a zero score on both. The college has a common quota of one for these two faculties. If the score limit is one, the college accepts nobody.
If the score limit is zero, the college accepts both contracts a and b, and the applicant prefers a, so only a realizes. This is valid and stable. Therefore, the only score-stable solution is t ̲ = 0 , S = F ( P ( t ̲ ) ) = { a } . There are two four-stable sets: S = with A = , B = { a , b }
Stable score vectors form a lattice, even if the graph is not simple; so, a stronger version of Theorem 12 is also true:
Theorem 14. If choice functions F and G are substitutable and G is loser-free, then the score-stable sets form a non-empty lattice.
In the Appendix, we prove Theorem 14 by taking a pointwise minimum of t ̲ 1 and t ̲ 2 and starting from there. The score-decreasing algorithm terminates at stable score vector t ̲ 1 t ̲ 2 .
Remark 5. If we consider L-stable score vectors, they also form a lattice, since the permissive scoring choice function used in L-stability is also loser-free.

6. Connection between Different Stability Notions

For a given two-sided model with choice functions F and G for each side, we have defined four kinds of stability:
  • Subset S of E is three-stable, if there exists subsets A and B of E, such that F ( A ) = S = G ( B ) and A B = E , A B = S .
  • Subset S of E is four-stable, if there exists subsets A and B of E, such that F ( A ) = S = G ( B ) and A B = S and D F ( A ) = E B and D G ( B ) = E A .
  • Subset S of E is dominating stable, if D F ( S ) D G ( S ) = E S .
  • If F is substitutable, G is substitutable and loser-free; we defined generalized score-stability in SubSection 3.5
Theorem 15. If F and G are substitutable and path independent, then S is three-stable ⇔S is four-stable ⇔S is dominating stable.
Theorem 16. If F and G are substitutable choice functions, F is path independent, (but G may not be); then, every four-stable set is three-stable.
Compared to other stability concepts, three-stability, four-stability and dominating stability are defined on every substitutable choice functions, F and G, but for score stability, we need substitutability on one side and a substitutable, loser-free function on the other side.
As we showed in Theorem 13, if choice function F is substitutable and path independent and G is substitutable loser-free, then every score-stable set is also four-stable.
Theorem 17. If F is substitutable and path independent and G is substitutable and loser-free, then every score-stable solution is three-stable.
Theorems 13, 15, 16 and 17 are summarized in Figure 5 below. In the notations, 3 stands for three-stable, 4 for four-stable, d for dominating stable and s for score-stable sets.
Figure 5. Graphs of the connections.
Figure 5. Graphs of the connections.
Algorithms 07 00032 g005
If the graph is simple: If F and G are path independent, all four properties are equivalent; If F is path independent, four-stablility is equivalent to score-stability; If F and G are not path independent, similarly to the upper picture, only score-stable ⇒ three-stable is true.
Statement 7. For all the other directions in Theorems 13, 15, 16 and 17, if one implication “if S is x-stable, then it is y-stable” does not appear in the upper diagram, then there exists a counterexample for it.

7. Conclusions

We worked with four different stability definitions: dominating stable, three-stable, four-stable and score-stable, from which the first three are rather theoretic, and score-stability can be applied to the Hungarian college admission system. All of them, except for dominating stability, can be found with simple algorithms and have some kind of lattice property, for the characteristic ( A , B ) pairs or for the stable contract sets themselves. Moreover, under given conditions, the lattice of the four-stable and score-stable sets are the same. We used Tarski’s theorem to prove the lattice property, except for the last case: score-stability with non-simple graphs.

Acknowledgments

We thank the two anonymous referees for their remarks that helped to improve the presentation of the work. Both authors are members of the Hungarian Academy of Sciences-Eötvös Loránd University Egerváry Research Group. Research was supported by Hungarian Scientific Research Fund OTKA grant K 108383.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Gale, D.; Shapley, L.S. College admissions and the stability of marriage. Am. Math. Mon. 1962, 69, 9–15. [Google Scholar] [CrossRef]
  2. Kelso, A.S., Jr.; Crawford, V.P. Job matching, coalition formation, and gross substitutes. Econometrica 1982, 50, 1483–1504. [Google Scholar] [CrossRef]
  3. Blair, C. The lattice structure of the set of stable marriages with multiple partners. Math. Oper. Res. 1988, 13, 619–628. [Google Scholar] [CrossRef]
  4. Aygün, O.; Sönmez, T. Matching with Contracts: The Critical Role of Irrelevance of Rejected Contracts; Mimeo, Boston College: Chestnut Hill, MA, USA, 2012. [Google Scholar]
  5. Azevedo, E.M.; Leshno, J.D. A Supply and Demand Framework for Two-Sided Matching Markets; Working Paper; MATCH-UP 2012; The Second International Workshop on Matching Under Preferences: Budapest, Hungary, 2012. [Google Scholar]
  6. Hatfield, J.W.; Milgrom, P.R. Matching with contracts. Am. Econ. Rev. 2005, 95, 913–935. [Google Scholar] [CrossRef]
  7. Knuth, D. Marriages Stables; Les Presses de l’Universite de Montreal: Montreal, QC, Canada, 1976. [Google Scholar]
  8. Fleiner, T. A fixed-point approach to stable matchings and some applications. Math. Oper. Res. 2003, 28, 103–126. [Google Scholar] [CrossRef]
  9. Biró, P.; Kiselgof, S. College Admissions with Stable Score-Limits. Cent. Eur. J. Oper. Res. 2013, 1–15. [Google Scholar]
  10. Tarski, A. A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math. 1955, 5, 285–310. [Google Scholar] [CrossRef]

Appendix

Proof of Lemma 1. If F ( A ) = S , then for every x A S , we have S ( S { x } ) A . Therefore, by F path independence, F ( S { x } ) = S ; so D F ( S ) A S . Consequently, F ( A ) D F ( S ) = A S .
If D F ( S ) A = A S , then F ¯ ( S { x } ) = x , for every x A S ; so, from substitutability, x F ¯ ( A ) . Thus, F ¯ ( A ) A S , which means F ( A ) S .
By the path independence of F, we have F ( A ) S A F ( A ) = F ( S ) = S
Proof of Lemma 2. We have seen that D F is monotone; hence D F ( S ) D F ( A ) .
If x D F ( A ) , then F ( A { x } ) A ( A { x } ) ; so F ( A { x } ) = F ( A ) = S by the path independency.
Therefore, F ( A { x } ) S { x } A { x } ; hence F ( S { x } ) = F ( A { x } ) = S . This means S dominates any x D F ( A ) , i.e., D F ( A ) = D F ( S ) . ☐
The proof of statement 3 is included in the proof of Theorem 11.
Proof of Lemma 5. If A i is a student of C j when the score vector is t ̲ ( i.e., A i C j F ( P ( t ̲ ) ) ), then A i can leave C j at t ̲ if she does not reach t j or got a better opportunity at another college.
If student A l does not go to college C j at the score vector, t ̲ , ( A l C j F ( P ( t ̲ ) ) ), then she will not go to C j under score vector t ̲ , because if A l does not reach t j , then she does not reach the higher limit, t j . If A l reaches t j , but chooses better college C k instead, since t k t k , she will stay in college C k . Therefore, the set of students assigned to C j with t ̲ is the subset of the set of students going to C j under t ̲ . ( F ( P ( t ̲ ) ) E ( C j ) ) ( F ( P ( t ̲ ) ) E ( C j ) ) The choice function, G j , of college C j is substitutable. Therefore, F ( P ( t ̲ ) ) E ( C j ) is valid; then, a subset of it is also valid. Therefore, t ̲ is C j -valid. ☐
Proof of Lemma 6. Let the set of contracts above score vectors t ̲ 1 and t ̲ 2 be P ( t ̲ 1 ) = A and P ( t ̲ 2 ) = B . Then, P ( t m i n ) = A B . Suppose that t j 1 = t j m i n for college C j . Since A A B , from substitutability F ¯ ( A ) F ¯ ( A B ) . Considering the set of contracts of college C j , E ( C j ) A = E ( C j ) ( A B ) , i.e., C j accepts the same set of contracts with score vector t ̲ 1 as with t ̲ m i n . Therefore, E ( C j ) F ( A ) E ( C j ) F ( A B ) . Since G is substitutable, if a set is valid, then its subset is also valid. G ( E ( C j ) F ( A ) ) = E ( C j ) F ( A ) so G ¯ ( E ( C j ) F ( A ) ) = . For a smaller set, G ¯ ( E ( C j ) F ( A B ) ) = ; so, ( A B ) is also valid for college C j .
In other words, if we change the score limit from t ̲ 1 to t ̲ m i n , college C j keeps its score limit, while other colleges may decrease it. Applicants may leave C j , but no new students will arrive to C j ; so, score limit t ̲ m i n is C j -valid. We can use the same argument for every college; therefore t ̲ m i n is valid. ☐
In the proofs of Theorems 5 and 6, we use the alternative versions of the score-decreasing/increasing algorithms, where in every step, a college decreases/increases its score limit only by one. These modified algorithms also find stable solutions, as one step of the score decreasing or score increasing can be regarded as several steps of this modified algorithm. From Lemma 5, if score vector t ̲ is valid and t ̲ = ( t 1 , t j - 1 , t j - k t m ) is also valid, then for every 1 k k , t ̲ = ( t 1 , t j - 1 , t j - k , t m ) is valid (it is C j -valid, because t is valid, and valid for other colleges, because t is valid). ☐
From the maximal/minimal property of the output solution, we see that the output of the algorithm does not depend on what order by which the colleges modify their score limits. Note that these algorithms may use m ( M + 1 ) steps, for example, if we start decreasing from t C ̲ : = ( M + 1 , , M + 1 ) ), but only ( 0 , , 0 ) is a stable score vector.
Proof of Theorem 5. From the algorithm, the fact that no college can decrease its score limit implies that t ̲ is a stable vector.
Suppose that there exist a stable score vector t ̲ 1 t ̲ 0 , where t ̲ 1 ¬ t ̲ . Therefore, t ̲ = ( t 1 , t m ) and t ̲ 1 = ( t 1 1 , t m 1 ) , and t i 1 > t i for some i. Define the set:
T = { x ̲ N m : x j t j 1 j { 1 , m } }
The algorithm starts from t ̲ 0 T and ends in t ̲ T ; so, there is a step, when the score vector leaves T: from score vector w ̲ 1 = ( w 1 , w 2 , t k 1 w m ) T , we move to w ̲ 2 = ( w 1 , w 2 , t k 1 - 1 w m ) T . Since this step is possible, both w ̲ 1 and w ̲ 2 are valid score vectors. We know that w ̲ 1 t ̲ 1 . Using Lemma 6, both t ̲ 1 and w ̲ 2 are valid; so, their minimum w ̲ 3 = ( t 1 1 , t 2 1 , t k 1 - 1 t m 1 ) is also valid. Therefore, w ̲ 3 is stable, and it can be reached from t ̲ 1 by lowering the score limit of C k . Therefore, t ̲ 1 is not critical, hence it cannot be stable; a contradiction.
Since every stable score vector are less than or equal to t 0 ̲ = ( M + 1 , M + 1 ) , the biggest of all stable score vectors is s C ̲ . Every student is accepted by fewer colleges than in any other stable admissions; so, s ̲ C is applicant-pessimal. Figure 6 is showing a possible layout. ☐
Figure 6. Score-decreasing algorithm.
Figure 6. Score-decreasing algorithm.
Algorithms 07 00032 g006
Proof of Theorem 6. It follows from the algorithm that t ̲ is valid. Suppose that it is not stable, i.e., there is a college, C j , such that t ̲ = ( t 1 , t 2 , , t j - 1 , t j - 1 , t j + 1 , , t m ) is still valid.
If t j 0 t j - 1 , look at the step where college C j raises its score from t j - 1 to t j , moving from score vector v ̲ 1 to v ̲ 2 .
Since the score limits in the algorithm always increase, v ̲ 1 t ̲ and v j 1 = t j - 1 ; therefore, v ̲ 1 t ̲ . We can use Lemma 5: score limit t ̲ is valid, so v ̲ 1 is also C j -valid. However, then, the algorithm would not have increased v ̲ 1 to v ̲ 2 ; a contradiction; Therefore, t ̲ is stable.
If t j 0 = t j , since t ̲ 0 is critical, the score vector t ̲ 0 = ( t 1 0 , t 2 0 , , t j - 1 0 , t j 0 - 1 , t j + 1 0 , , t m 0 ) is not valid for C j . From t ̲ 0 t ̲ , we get that t ̲ 0 t ̲ . Using Lemma 5 again, if t ̲ was valid, then t ̲ 0 would be C j -valid. Therefore, t ̲ is not valid; therefore, t ̲ is indeed stable.
To show that t ̲ is minimal, suppose that there is a stable score limit, t ̲ 1 , such that t ̲ 0 t ̲ 1 , but t ̲ t ̲ 1 , i.e., t j 1 < t j for some j. Let:
T = { x ̲ N n : x i t i 1 i { 1 , m } }
Since t ̲ T , but t ̲ 0 T , there is a step such that when we leave T , we move from w ̲ 1 to w ̲ 2 . There is a college, C i , where w ̲ i 1 = t ̲ i 1 . For other colleges, w ̲ k 1 t ̲ k 1 ; so, by Lemma 5, w ̲ 1 was C i -stable. Therefore, C i does not want to increase its score limit.
Therefore, s ̲ A is the smallest of all stable score vectors; so, every student gets accepted at as many colleges as possible, and they choose what is best for them. Therefore, s ̲ A is applicant-optimal. Figure 7 is showing a possible layout. ☐
Figure 7. Score-increasing algorithm.
Figure 7. Score-increasing algorithm.
Algorithms 07 00032 g007
Proof of Theorem 7. In this proof, we return to the algorithm versions where colleges increase/lower their score limits as much as they can. We call the set of realized contracts at some score vector enrollment.
Each of the n students can go to one of the m colleges or remain unmatched. Therefore, there are at most n m + 1 possible enrollments. In the score-decreasing algorithm, the applicants always change to better. In the score-increasing algorithm, the students’ positions get worse. Therefore, we cannot return to an earlier enrollment in these algorithms.
If we order all enrollments according to the applicants’ preference order, the longest chain contains n ( m + 1 ) enrollments. It goes from “everyone gets the best college” to “everyone gets the worst college”. In the score-decreasing algorithm, college C i may lower its score limit without changing the enrollment, taking the same students as before. If all m colleges do the same, we get the minimal score vector for that given enrollment; next time it came to college C i , it has to change to a different enrollment or stop. Therefore, in the algorithm, there can be at most m consecutive steps without changing the enrollment. Therefore, the number of steps is O ( m 2 n ) .
In the score-increasing algorithm, every step will change the enrollment; hence, if C i increase its score limit, the set of students going to C i was infeasible before this step and feasible after the step. Thus, the number of steps is O ( m n ) .
Proof of Theorem 11. (i) First, we show that for any given stable set S there is a unique four-stable pair ( A , B ) .
Suppose that there are two different stable pairs for S: ( A , B ) and ( A , B ) .
We can assume that there exists a b for which b B , but b B . Since S B , it follows that b S . Moreover b F ( A { b } ) , but b F ( A { b } ) , because b F ( A { b } ) b B .
By A S = F ¯ ( A ) F ¯ ( A { b } ) , we get F ( A { b } ) S A { b } ; hence F ( A { b } ) = S .
We know that ( A { b } ) S = F ¯ ( A { b } ) and A S = F ¯ ( A ) .
Since F is substitutable, F ¯ ( A A { b } ) contains both sets, ( A A { b } ) S F ¯ ( A A { b } ) ; so, F ( A A { b } ) S .
From F ( A { b } ) = S , we get F ( A { b } ) F ( A { b } ) F ( A { b } ) A { b } ; so, F ( A { b } ) = F ( F ( A { b } ) F ( A { b } ) ) .
Using that F is path independent, from Theorem 3, b F ( A { b } ) = F ( F ( A { b } ) F ( A { b } ) ) = F ( A { b } ) ( A { b } ) ) = F ( A A { b } ) S . Therefore, b S ; a contradiction.
Let S and S be two different stable sets. Let four-stable pairs ( A , B ) and ( A , B ) correspond to stable sets S and S , respectively.
(ii) ( A , B ) ( A , B ) S F S .
From the ordering of the four-stable pairs, S A A and S A ; so, S S A .
Since F is path independent, from S = F ( A ) S S A , we get that F ( S S ) = S .
(iii) S F S , ⇒ ( A , B ) ( A , B ) .
Suppose that B B . Consequently, b , such that b B , but b B . From Lemma 2, D F ( A ) = D F ( S ) ; so:
b B b D F ( A ) = D F ( S ) b F ( S { b } )
b B b D F ( A ) = D F ( S ) b F ( S { b } )
We know that F ( S S ) = S ; therefore, F ( S S { b } ) S { b } S S { b } . Since F is path independent, F ( S S { b } ) = F ( S { b } ) b ; hence b F ( S { b } ) ; a contradiction.
Similarly, from B B , we get D F ( B ) D F ( B ) by the monotonicity of D F and E A E A ; hence A A .
(iv) The stable sets form a lattice.
We have seen that there is an order preserving bijection between the stable sets and stable pairs. As stable pairs form a lattice, stable sets do, as well. ☐
Proof of Statement 5. Let J = { e P ( t ̲ ) : e F ( { e } P ( t ̲ ) ) } be the set of contracts that F prefers to F ( P ( t ̲ ) ) . In other words, J = ( E D F ( P ( t ̲ ) ) ) P ( t ̲ ) ; therefore, E D F ( P ( t ̲ ) ) = F ( P ( t ̲ ) ) J . (See Figure 8.)
Suppose t ̲ is a fixed point. Let B = E D F ( P ( t ̲ ) ) , and we use that: P ( P G ( B ) ) B = G ( B ) . From this, P ( t ̲ ) ( E D F ( P ( t ̲ ) ) ) = P ( P G ( E D F ( P ( t ̲ ) ) ) ) ( E D F ( P ( t ̲ ) ) ) = G ( E D F ( P ( t ̲ ) ) ) .
Since P ( t ̲ ) ( E D F ( P ( t ̲ ) ) ) = F ( P ( t ) ) , we get that G ( F ( P ( t ̲ ) ) J ) = F ( P ( t ̲ ) ) , and since G is substitutable, G ¯ ( F ( P ( t ̲ ) ) ) G ¯ ( F ( P ( t ̲ ) ) J ) = J . Therefore, G ( F ( P ( t ̲ ) ) ) = F ( P ( t ̲ ) ) ; so, t ̲ is valid.
To prove that t ̲ is critical, assume that college C j lowers its score limit by one. Let
t ̲ = ( t 1 , t 2 , , t j - 1 , t j - 1 , t j + 1 , , t m ) . Then, at college C j , the accepted P ( t ̲ ) increases with some contracts.
Now, we use that the graph is simple. If A i C j P ( t ̲ ) , then applicant A i will also be accepted under t ̲ . If A i is not accepted at college C j with score vector t ̲ , but she has a score of at least t j - 1 , then she will go to C j if and only if C j A i J , because she got only one new chance. Therefore, F ( P ( t ̲ ) ) E ( C j ) = ( F ( P ( t ̲ ) ) J ) E ( C j ) .
Other colleges cannot have new students; so, they stay valid.
From F ( P ( t ̲ ) ) J , the scoring function, P G j , for college C j chooses score limit t j ; therefore, it also chooses t j from F ( P ( t ̲ ) . Therefore, t ̲ is not valid.
Now, assume that t ̲ is valid and critical. Therefore, G ( F ( P ( t ̲ ) ) ) = F ( P ( t ̲ ) ) ; so, G ( F ( P ( t ̲ ) ) J ) accepts contracts in F ( P ( t ̲ ) ) (because contracts in J do not reach score limit t ̲ ). Therefore, P G ( E D F ( P ( t ̲ ) ) ) t ̲ .
As before, t ̲ = ( t 1 , t 2 , , t j - 1 , t j - 1 , t j + 1 , , t m ) . Function P is antitone; so
P ( t ̲ ) P ( t ̲ ) . Since D F is monotone, D F ( P ( t ̲ ) ) D F ( P ( t ̲ ) ) ; so, E D F ( P ( t ̲ ) ) E D F ( P ( t ̲ ) ) F ( P ( t ̲ ) ) . As t ̲ is critical, F ( P ( t ) ) is infeasible for college C j ; so, E D F ( P ( t ̲ ) ) , too, and we get P G j ( E D F ( P ( t ̲ ) ) ) t j . This is valid for every college; therefore, P G ( E D F ( P ( t ̲ ) ) ) = t ̲ .
We did not use that G is simple in the second direction and in the “valid” part of the first direction; so, these parts remain true for general bipartite graphs. ☐
Figure 8. Four-partition.
Figure 8. Four-partition.
Algorithms 07 00032 g008
Proof of Statement 6. (i)⇒ (ii) If t ̲ is a fixed point, t ̲ = P G ( E D F ( P ( t ̲ ) ) ) , then let B = E D F ( P ( t ̲ ) .
As we have seen in the proof of Statement 5, F ( P ( t ̲ ) ) = P ( t ̲ ) ( E D F ( P ( t ̲ ) ) = G ( E D F ( P ( t ̲ ) ) ) = G ( F ( P ( t ̲ ) ) J ) ; so, S = G ( B ) .
This gives D G ( B ) B = G ¯ ( B ) = J . From the contracts outside B, the set, B, must dominate contracts under score limit t ̲ , since if colleges do not accept contracts from J, then they will not accept other contracts with the same or lower scores. (It cannot happen that for some college, C j , all contracts in J have a score of t j - 2 or less and some e B has a score of t j - 1 , because in that case, P G j would have chosen t j - 1 and t ̲ would not be stable.) Therefore, D G ( B ) E P ( t ̲ ) . Therefore, A = E D G ( B ) P ( t ̲ ) .
Since F is path independent and S = F ( P ( t ̲ ) ) A P ( t ̲ ) , we get that F ( A ) = S .
From Lemma 2, D F ( A ) = D F ( P ( t ) ) = E B ; so, S is indeed four-stable.
(i)⇐ (ii)
If S is four-stable, then there exists A , B , such that F ( A ) = S , G ( B ) = S . Let the score limit be t ̲ = P G ( B ) . We want to know what P ( t ̲ ) is. It is sure that P ( t ̲ ) B = S , because P ( P G ( B ) ) B = G ( B ) , and since D G ( B ) = E A and D G ( B ) E P ( t ) , so A = E D G ( B ) P ( t ̲ ) .
Since D F ( A ) = E B , substitutability implies that dominated contracts will not be chosen from P ( t ̲ ) , since A P ( t ̲ ) A ( E B ) . Therefore, F ¯ ( P ( t ̲ ) ) P ( t ̲ ) A . Then, F ( P ( t ̲ ) ) A P ( t ̲ ) . From the path-independent property, S = F ( A ) = F ( P ( t ̲ ) ) .
Using Lemma 2 again, D F ( P ( t ̲ ) ) = D F ( A ) = E B , E D F ( P ( t ̲ ) ) = B and P G ( E D F ( P ( t ̲ ) ) ) = P G ( B ) = t ̲ ; therefore, t ̲ is a fixed point. ☐
Proof of Theorem 14. We know from Theorems 5 and 6 that there exist a greatest and a least stable score vector. Let t ̲ 1 and t ̲ 2 be two arbitrary stable score vectors. We want to show that they have a join and a meet. Using Lemma 6, t m i n = min ( t ̲ 1 , t ̲ 2 ) is valid. Let us start the score-decreasing algorithm from t m i n ; from the algorithm, we get a stable score vector, t ̲ . From Theorem 5, t ̲ is the biggest among all the stable score vectors smaller than or equal to t m i n . Therefore, t ̲ = t ̲ 1 t ̲ 2 , because for every stable vector, such that t ̲ t 1 , t 2 , t t m i n ; therefore, t ̲ t .
We finish by showing the existence of t ̲ 1 t ̲ 2 . There exists a common upper bound of t ̲ 1 and t ̲ 2 , for example s ̲ C . Since the lattice is finite, there has to be at least one least common upper bound. Suppose there exist two least common upper bounds: a ̲ and b ̲ . Since t ̲ 1 is a lower bound of a ̲ and b ̲ , t ̲ 1 a ̲ b ̲ ; similarly, t ̲ 2 a ̲ b ̲ . Therefore, we found a common upper bound of t ̲ 1 and t ̲ 2 smaller than a; a contradiction. ☐
Proof of Theorem 15. Three-stable ⇒ dominating
There are A and B, such that F ( A ) = S = G ( B ) . From Lemma 1, D F ( S ) A S . The same goes for G ( B ) ; so, D G ( S ) B S . Their union is
D F ( S ) D G ( S ) ( ( A S ) ( B S ) ) = E S .
Additionally, S does not dominate itself; so, D F ( S ) D G ( S ) = E S .
Dominating ⇒ four-stable
We know that D F ( S ) D G ( S ) = E S . Let A = E D G ( S ) and B = E D F ( S ) .
A S D F ( S ) , so F ( A ) = S . From Lemma 2, D F ( A ) = D F ( S ) = E B . Similarly, D G ( B ) = D G ( S ) = E A . With this ( A , B ) pair, S is four-stable.
Four-stable ⇒ three-stable
There exists subsets A and B of E, such that F ( A ) = S = G ( B ) and A B = S , and D F ( A ) = E B , D G ( B ) = E A .
Let D = E ( A B ) and A = A D , B = B .
Now, A B = E , A B = A B = S , and from Lemma 2, D F ( S ) = D F ( A ) = E B = ( A S ) D = A S . From Lemma 1, F ( A ) = S , G ( B ) = G ( B ) = S ; so, with the ( A , B ) pair, S is three-stable. ☐
Proof of Theorem 16. In the third part of the proof of Theorem 15, we did not use that G was path independent. ☐
Proof of Theorem 17. Let S E be the enrollment realized from stable score vector t ̲ . Define A as the set of contracts above score vector t ̲ . Let B be the union of S and the set of contracts under score limit t ̲ .
From all the accepted contracts above score vector t ̲ , the applicants choose contract set S; so, F ( S ) = S . If colleges choose from contract set B, just like from all contracts, they would set score limit to t ̲ ; so, G ( B ) = S . It is easy to see that A B = E , A B = S ; therefore, S is three-stable. ☐
Proof of Statement 7. In Figure 2 and Figure 4 and in the following Figure 9 to Figure 13, the upper nodes symbolize the colleges, the lower nodes the applicants and the edges between them are the possible contracts. If we write a > b to a node, that means the given applicant prefers contract a to b. In all examples, every student gets a score of zero everywhere, except in Figure 13, where contract b has a score of one; so, b is better for the college.
If a node has only one incident edge, it always chooses that, if it is available.
Figure 9. Example graph 3.
Figure 9. Example graph 3.
Algorithms 07 00032 g009
Figure 10. Example graph 4.
Figure 10. Example graph 4.
Algorithms 07 00032 g010
Figure 11. Example graph 5.
Figure 11. Example graph 5.
Algorithms 07 00032 g011
Figure 12. Example graph 6.
Figure 12. Example graph 6.
Algorithms 07 00032 g012
Figure 13. Example graph 7.
Figure 13. Example graph 7.
Algorithms 07 00032 g013
Table 1 describes the choice functions, usually as a direct sum of the choice functions of individual colleges/applicants. Notation Q 1 ( a , b ) means a college chooses from equally good contracts a and b and its quota is one. We use the abbreviation “path ind." for path independence. Table 2 shows the stable sets for each notion for the seven examples.
Table 1. The choice functions for the seven examples.
Table 1. The choice functions for the seven examples.
FigureSimple F Path ind. G Path ind.
2no Q 1 no Q 1 no
4no a > b yes Q 1 no
9yes ( a > c ) + ( b > d ) yes Q 1 ( a , b ) + Q 2 ( c , d ) no
10yes a + Q 1 ( b , c ) no Q 1 ( a , b ) + c no
11yes a + Q 1 ( b , c , d ) no Q 1 ( a , b ) + c + d no
12yes ( a > c ) + ( b > d ) yes Q 1 ( a , b ) + Q 1 ( c , d ) no
13no a > b yes b > a yes
Table 2. Stable sets in case of different stability notions.
Table 2. Stable sets in case of different stability notions.
FigureThree-StableFour-StableDominating StableScore-Stable t ̲ Fixed
2 , { a } , { b } { a } , { b }
4 , { a } , { a } { a } , { b } { a } , { a }
9 { a , d } , { c , d } { a , d } { a , d } { a , d } { a , d }
10 { a } , { c } { a , c } { a , c } { a } { a } ,
11 , { a } { a } { b } , { a , c } , { a , d } { a } { a }
12 , { a , d } , { a , d } { a , d } , { b , c } , { a , d } , { a , d }
13 { a } , { b } { a } , { b } { a } , { b } { a } { a } , { b }
Back to TopTop