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

^{1}

^{2}

^{3}

^{*}

*Keywords:*stable matchings; college admission; choice function; lattice

Next Article in Journal

Next Article in Special Issue

Next Article in Special Issue

Previous Article in Journal

Previous Article in Special Issue

Previous Article in Special Issue

Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar tudósok körútja 2., Budapest 1117, Hungary

MTA-ELTE Egerváry Reseach Group, Pázmány Péter sétány 1/C, Budapest 1117, Hungary

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)

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.

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}\vee {S}_{2}$. If men choose their less preferred partners, we get the stable scheme ${S}_{1}\wedge {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.

In the stable marriage model, there are n men: $M={m}_{1},\cdots {m}_{n}$; and women: $W={w}_{1},\cdots {w}_{n}$; each of them having a strict preference order on the members of the other gender. Let $\mathcal{G}$ be a bipartite graph with color classes M and W, and let E—the set of edges in $\mathcal{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, $\mathcal{G}$. However, we may allow multiple edges between two vertices of $\mathcal{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}^{\prime}$ means that man m prefers woman ${w}^{\prime}$ to w. A subset, S, of contracts is a matching or marriage scheme in $\mathcal{G}$ if no vertex of $\mathcal{G}$ is adjacent to more than one edge in S. A matching $S\subseteq E$ can also be described as an involution $\mu :M\cup W\to M\cup W$, such that if m and w are married (that is, $(m,w)\in S$), then $\mu \left(m\right)=w$ and $\mu \left(w\right)=m$, and for an unmatched agent, a, we define $\mu \left(a\right)=a$. A marriage scheme S is called stable if, for any pair, $(m,w)\notin S$, $\mu \left(m\right){>}_{m}w$ or $\mu \left(w\right){>}_{w}m$ holds. Men’s preferences define a partial order on stable marriage schemes: $S{\ge}_{M}{S}^{\prime}$, if $\mu \left({m}_{i}\right){\ge}_{{m}_{i}}{\mu}^{\prime}\left({m}_{i}\right)$, for all ${m}_{i}\in M$ and $S{>}_{M}{S}^{\prime}$, if $S{\ge}_{M}{S}^{\prime}$ and there exists a man ${m}_{i}$ such that $\mu \left({m}_{i}\right){>}_{{m}_{i}}{\mu}^{\prime}\left({m}_{i}\right)$. Similarly, there is another partial ordering, ${\ge}_{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.

A stable matching, S, is male-pessimal (female-pessimal) if $S{\le}_{M}{S}^{\prime}$ ($S{\le}_{W}{S}^{\prime}$) for every stable matching, ${S}^{\prime}$.

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 $const\xb7{n}^{2}$ steps, since every man proposes to every women at most once. The outcome of the algorithm is always a stable marriage scheme.

Knuth in [7] attributes the observation to John Conway that stable marriages form a distributive lattice.

If the women choose their better partner, we get stable matching ${S}_{1}\wedge {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.

For convenience, for a choice function, F, let $\overline{F}\left(A\right)=A\setminus F\left(A\right)$ denote the set of unselected elements. We list some important properties of set functions.

A set function, $F:{2}^{E}\to {2}^{E}$, is antitone if $F\left(A\right)\supseteq F\left(B\right)$ whenever $A\subseteq B\subseteq E$ holds.

A choice function, $F:{2}^{E}\to {2}^{E}$, is substitutable (sometimes called comonotone) if $\overline{F}\left(A\right)\subseteq \overline{F}\left(B\right)$ for any $A\subseteq B$ (that is, if $\overline{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.

Path independence is called “irrelevance of rejected contracts (IRC)” in the paper of Aygün and Sönmez [4]:

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]):

Sometimes, the choice function is defined by a strict preference order over all subsets of E, such that $F\left(A\right)$ 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\subseteq B\subseteq 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\cap Y=\varnothing $ and ${F}_{1}:{2}^{X}\to {2}^{X}$, ${F}_{2}:{2}^{Y}\to {2}^{Y}$, $F:{2}^{X\cup Y}\to {2}^{X\cup Y}$; then, $F={F}_{1}+{F}_{2}$ means that for every $A\subseteq X\cup Y$, $F\left(A\right)={F}_{1}(A\cap X)\cup {F}_{2}(A\cap 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.

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\left(v\right)$ 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\left(X\right)=$ 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\left(X\right)=$ the best k members of X. If $\left|X\right|\le k$, then $F\left(X\right)=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\left(v\right)$: for $A\subseteq E\left(v\right)$, if $\left|A\right|\le k$, then ${Q}_{k}\left(A\right)=A$, and if $\left|A\right|>k$, then ${Q}_{k}\left(A\right)=\varnothing $.
- 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\le 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}\ge q$ contracts in a way that it chooses the best $k\le 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:

and the budget is 10, then v chooses only ${a}_{1}$. (Agent v cannot skip some applicants and choose a cost of $9+1$.)${a}_{1}$ ${a}_{2}$ ${a}_{3}$ ${a}_{4}$ scores 4 3 2 1 cost 9 5 5 1 - Strict hierarchical choice function: Agent v has a linear preference list over contracts, and there is a downward closed set system, $\mathcal{I}$, of subsets of $E\left(v\right)$ (that is, if $A\in \mathcal{I},B\subseteq A$, then $B\in \mathcal{I}$). Let k be the greatest number, such that the set of k best contracts of set X belongs to $\mathcal{I}$. Now, $C\left(X\right)$ 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, $\mathcal{I}$, of subsets of $E\left(v\right)$. Let k be the greatest number, such that the set of k best contracts of set A is in $\mathcal{I}$, and among equally good contracts, we choose all or none. Now, $C\left(A\right)$ is the set of these k best applicants.

Proof. From set A, the college’s preference order is ${c}_{1}\ge {c}_{2}\cdots \ge {c}_{n}$ (contract ${c}_{1}$ has the best score; ${c}_{n}$ has the worst). If $F\left(A\right)\subseteq B\subseteq A$ and $F\left(A\right)=\{{c}_{1},{c}_{2}\cdots {c}_{k}\}$, then by definition, the college cannot add the next best applicant, ${c}_{k+1}$, to $F\left(A\right)$. Other contracts in $B\setminus F\left(A\right)$ are more expensive than ${c}_{k+1}$, so the college cannot choose any of them. Therefore, $F\left(B\right)=F\left(A\right)$. ☐

Note that the above Examples 1, 2, 4 and 7 are path independent. All of the above examples are substitutable and loser-free.

Not every weak hierarchical function is a weighted scoring choice function:

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

In the original stable marriage model, a matching is stable, if it dominates every other contract; so, for every $e=(m,w)\notin S$, either $\mu \left(m\right){>}_{m}e$ or $\mu \left(w\right){>}_{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.

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:

$${\mathcal{D}}_{F}\left(A\right):=\{x\in X:x\notin F(A\cup \left\{x\right\})\}$$

Note that ${\mathcal{D}}_{F}\left(A\right)\cap A=\overline{F}\left(A\right)$.

Proof. Let $A\subseteq B$. If $x\in {\mathcal{D}}_{F}\left(A\right)$ then $x\notin F(A\cup \{x\left\}\right)$$\Rightarrow x\in \overline{F}(A\cup \left\{x\right\})$. Since F is substitutable, $x\in \overline{F}(B\cup \left\{x\right\})$$\Rightarrow x\notin F(B\cup \{x\left\}\right)$ so $x\in {\mathcal{D}}_{F}\left(B\right)$. ☐

Examples for choice functions and corresponding dominating functions:

${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.

∅ | $\left\{a\right\}$ | $\left\{b\right\}$ | $\{a,b\}$ | |

${F}_{1}$ | ∅ | $\left\{a\right\}$ | $\left\{b\right\}$ | ∅ |

${\mathcal{D}}_{{F}_{1}}$ | ∅ | $\left\{b\right\}$ | $\left\{a\right\}$ | $\{a,b\}$ |

${F}_{2}$ | ∅ | $\left\{a\right\}$ | $\left\{b\right\}$ | $\{a,b\}$ |

${\mathcal{D}}_{{F}_{2}}$ | ∅ | ∅ | ∅ | ∅ |

${F}_{3}$ | ∅ | $\left\{a\right\}$ | $\left\{b\right\}$ | $\left\{a\right\}$ |

${\mathcal{D}}_{{F}_{2}}$ | ∅ | $\left\{b\right\}$ | ∅ | $\left\{b\right\}$ |

The dominating function has some properties that will be useful later.

Therefore, every $e\notin S$ is either F-dominated or G-dominated by S.

Proof. Suppose that $s\in S\setminus F\left(S\right)$. Then, by definition, $s\in {\mathcal{D}}_{F}\left(S\right)$, but ${\mathcal{D}}_{F}\left(S\right)\subseteq E\setminus S$; a contradiction. For G, a similar proof applies. ☐

Note that even for substitutable F and G, a dominating stable solution does not always exists.

Now, F is substitutable and path independent, and G is substitutable, but not path independent.

∅ | $\left\{a\right\}$ | $\left\{b\right\}$ | $\left\{c\right\}$ | $\{a,b\}$ | $\{b,c\}$ | $\{a,c\}$ | $\{a,b,c\}$ | |

F | ∅ | $\left\{a\right\}$ | $\left\{b\right\}$ | $\left\{c\right\}$ | $\{a,b\}$ | $\{b,c\}$ | $\{a,c\}$ | $\{a,b,c\}$ |

G | ∅ | $\left\{a\right\}$ | $\left\{b\right\}$ | $\left\{c\right\}$ | $\left\{a\right\}$ | $\left\{b\right\}$ | $\left\{c\right\}$ | ∅ |

${\mathcal{D}}_{F}$ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ |

${\mathcal{D}}_{G}$ | ∅ | $\left\{b\right\}$ | $\left\{c\right\}$ | $\left\{a\right\}$ | $\{b,c\}$ | $\{c,a\}$ | $\{a,b\}$ | $\{a,b,c\}$ |

Suppose that S is dominating stable. Since $G\left(S\right)=S$, the cardinality of S is at most one. However, then, ${\mathcal{D}}_{F}\left(S\right)\cup {\mathcal{D}}_{G}\left(S\right)={\mathcal{D}}_{G}\left(S\right)\ne E\setminus S$, because every contract dominates only one other contract.

A similar example appeared in [4].

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:

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\setminus S$ and $B\setminus S$, where S is stable, $A\setminus S$ is F-dominated by S and $B\setminus 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\setminus S$ and women prefer S to $B\setminus 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\setminus S$ as the set of contracts that the men prefer less than the contracts of S and $B:=S\cup (E\setminus A)$.

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.

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\setminus S$ is F-dominated by S; $B\setminus S$ is G-dominated by S; and the contracts in $E\setminus (A\cup B)$ are both F- and G-dominated.

$S=\varnothing $, where $A=\{a,b\}$, $B=\varnothing $ or $A=\varnothing $, $B=\{a,b\}$

$S=\left\{a\right\}$, $A=\left\{a\right\},B=\left\{a\right\}$

$S=\left\{b\right\},A=\left\{b\right\},B=\left\{b\right\}$

Proof. Since $F\left(A\right)=S$ and $\overline{F}\left(S\right)\subseteq \overline{F}\left(A\right)=A\setminus S$, $F\left(S\right)=S$. Similarly, $G\left(B\right)=S$ implies $G\left(S\right)=S$. ☐

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},\dots ,{A}_{n}$ and m colleges ${C}_{1},{C}_{2},\dots {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},\dots ,{A}_{n}\}$ and $\{{C}_{1},\dots ,{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\left({A}_{i}{C}_{j}\right)$ (an integer between one and M) to each of its applicants. Moreover, each college, C, has a quota, $q\left(C\right)$, 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\left({A}_{i}{C}_{j}\right)$, 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},\dots {C}_{m}$ be ${t}_{1},{t}_{2},\dots {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\left({A}_{i}{C}_{j}\right)\ge {t}_{j}$ ( i.e., score $s\left({A}_{i}{C}_{j}\right)$ of ${A}_{i}$ at ${C}_{j}$ is not less than threshold ${t}_{j}$ for ${C}_{j}$) and $s\left({A}_{i}{C}_{{j}^{\prime}n}\right)<{t}_{{j}^{\prime}}$ for ${j}^{\prime}{>}_{i}j$ ( i.e., score $s\left({A}_{i}{C}_{{j}^{\prime}}\right)$ of ${A}_{i}$ at ${C}_{{j}^{\prime}}$ is less than the score limit, ${t}_{{j}^{\prime}}$, if ${A}_{i}$ likes ${C}_{{j}^{\prime}}$ more than ${C}_{j}$). The vector of declared score limits $({t}_{1},{t}_{2},\dots ,{t}_{m})$ is called a score vector. The stability notion below is defined according to the requirements of Hungarian law.

Score vector $({t}_{1},{t}_{2},\dots {t}_{m})$ is critical if for every college, ${C}_{j}$, either ${t}_{j}=0$ or score vector $({t}_{1},{t}_{2},\dots ,{t}_{j-1},{t}_{j}-1,{t}_{j+1},\dots ,{t}_{m})$ would assign more than $q\left({C}_{j}\right)$ students to ${C}_{j}$ (that is, no single college can decrease its score limit without exceeding its quota).

A score vector, $\underline{s}$, is score-stable if $\underline{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\subseteq E$ of contracts, ${F}_{i}\left(X\right)$ denotes the most preferred contract from X of applicant ${A}_{i}$, and $F\left(X\right)$ is the common choice function of all applicants. Therefore, $F={F}_{1}+{F}_{2}+\cdots {F}_{n}$. Similarly, ${G}_{j}\left(X\right)$ 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\left({C}_{j}\right)$ contracts from ${X}_{j}$ has score of at least ${t}_{j}$, but either ${t}_{j}=0$ or more than $q\left({C}_{j}\right)$ contracts has a score of at least ${t}_{j}-1$. Let ${G}_{j}\left(X\right)$ be the set of all contracts in ${X}_{j}$ above the score limit, ${t}_{j}$. Define choice function $G:{2}^{E}\to {2}^{E}$ as the common choice function of all colleges, $G={G}_{1}+{G}_{2}+\cdots {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\left(\right\{a,b\left\}\right)=\varnothing \subseteq \left\{a\right\}\subseteq \{a,b\}$ and $G\left(\right\{a\left\}\right)\ne G\left(\right\{a,b\left\}\right)$, so it is not path independent.

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}+\cdots {G}_{m}$.

We say a set $\{{A}_{{i}_{1}},{A}_{{i}_{2}},\cdots {A}_{{i}_{k}}\}$ of applicants is feasible for college ${C}_{j}$ if ${G}_{j}\left(X\right)=X$ for the contract set $X=\{{A}_{{i}_{1}}{C}_{j},{A}_{{i}_{2}}{C}_{j},\cdots {A}_{{i}_{k}}{C}_{j}\}$; otherwise, it is infeasible. Each contract, c, has a score, $s\left(c\right)$.

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}\left(A\right)$. 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:{\mathbb{N}}^{E}\to {2}^{E}$ be a function, that codes the scores of the applicants: $P\left(t\right)$ is the set of contracts above the score limit given by score vector $\underline{t}$. $P\left(\underline{t}\right)=\{AC\in E:s\left(AC\right)\ge t\left(C\right)\}$. Therefore, $P\left(\underline{0}\right)=E$ and P is antitone on the scores: if ${\underline{t}}_{1}\le {\underline{t}}_{2}$, then $P\left({\underline{t}}_{1}\right)\supseteq P\left({\underline{t}}_{2}\right)$.

Note that $P\left({P}_{G}\left(A\right)\right)\cap A=G\left(A\right)$ for every $A\subseteq E$.

There exists a score vector $\underline{T}$ (a highest possible score of +1 for every college), where $P\left(\underline{T}\right)=\varnothing $. From contracts above the score limit, the students choose $F\left(P\left(\underline{t}\right)\right)$, and contract set $G\left(F\left(P\left(\underline{t}\right)\right)\right)$ is acceptable for the colleges. Therefore, score vector $\underline{t}$ is valid if and only if $G\left(F\left(P\left(\underline{t}\right)\right)\right)=F\left(P\left(\underline{t}\right)\right)$.

The score vector, $\underline{t}$, is critical if for any $1\le j\le m$, the new score vector $({t}_{1},{t}_{2},\dots ,{t}_{j-1},{t}_{j}-1,{t}_{j+1},\dots ,{t}_{m})$ is not valid for college ${C}_{j}$, or ${t}_{j}=0$. We call $\underline{t}$ stable if it is both valid and critical.

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}\ne {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 $\underline{t}$, the set of students going to college ${C}_{k}$ is $F\left(P\left(\underline{t}\right)\right)\cap E\left({C}_{k}\right)$; denote it by Z. Additionally, with score limit ${\underline{t}}^{\prime}$, it is ${Z}^{\prime}$. As we have seen, ${Z}^{\prime}\subseteq Z$, and from the substitutability, ${G}_{k}\left(Z\right)=Z$ implies ${G}_{k}\left({Z}^{\prime}\right)={Z}^{\prime}$. ☐

The following two lemmas help to understand how the set of the valid score vectors look:

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.

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\wedge y$ and a least upper bound $x\vee y$. A lattice, L, is complete if any subset, X, of L has a greatest lower bound $\bigwedge X$ and a least upper bound $\bigvee X$. Function $f:L\to {L}^{\prime}$ from lattice L to lattice ${L}^{\prime}$ is monotone if $x\le y$ implies $f\left(x\right)\le f\left(y\right)$ for any elements, $x,y$, of L.

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\le f\left(0\right)$ and from monotonity $0\le f\left(0\right)\le f\left(f\right(0\left)\right)\le f\left(f\right(f\left(0\right)\left)\right)\le \cdots $. Since the lattice is finite, there exists an i, where ${f}^{i}\left(0\right)={f}^{i+1}\left(0\right)$. Therefore, ${f}^{i}\left(0\right)$ is a fixed point.

Proof. Let x be an arbitrary fixed point of f. Since f is monotone, $0\le x$⇒$f\left(0\right)\le f\left(x\right)=x$ and ${f}^{j}\left(0\right)\le {f}^{j}\left(x\right)=x$ for every $j\ge 1$. We get that $a={f}^{i}\left(0\right)\le x$. ☐

Similarly, we can start with the greatest element one. From $1\ge f\left(1\right)\ge f\left(f\right(1\left)\right)\ge f\left(f\right(f\left(1\right)\left)\right)\cdots $, we see that there is a j, such that ${f}^{j}\left(1\right)={f}^{j+1}\left(1\right)$.

This ${f}^{j}\left(1\right)$ is the greatest of all fixed points of f.

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\left(E\right)=E\setminus \phantom{\rule{3.33333pt}{0ex}}\overline{F}\left(E\right)$. Women choose $G\left(F\right(E\left)\right)$ and reject $\overline{G}\left(F\left(E\right)\right)$. In the second step, men choose from all contracts, except for the rejected ones: ${X}_{2}=E\setminus \overline{G}\left({Y}_{1}\right)=E\setminus \overline{G}\left(F\left({X}_{1}\right)\right)$. They choose $F\left({X}_{2}\right)$. The women take these contracts and the previously rejected contracts and choose from ${Y}_{2}=F\left({X}_{2}\right)\cup \overline{G}(F\left({X}_{1}\right)=E\setminus \overline{F}\left({X}_{2}\right)$. 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\left({Y}_{2}\right)\subseteq F\left({X}_{2}\right)\subseteq {Y}_{2}$ implies $G\left({Y}_{2}\right)=G\left(F\left({X}_{2}\right)\right)$; 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\setminus \overline{F}\left({X}_{i}\right)$, and let ${X}_{i+1}=E\setminus \overline{G}\left({Y}_{i}\right)$. Define the following function, f:

$$f({X}_{i},{Y}_{i})=(E\setminus \overline{G}\left({Y}_{i}\right),E\setminus \overline{F}(E\setminus \overline{G}\left({Y}_{i}\right)))$$

We can define a partial order on pairs $({A}^{\prime},{B}^{\prime})\le (A,B)$, if ${A}^{\prime}\subseteq A$ and ${B}^{\prime}\supseteq 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\left(E\right))$, we get the male-optimal matching; if we start from $({X}_{1},{Y}_{1})=(\varnothing ,\varnothing )$, we get the female-optimal one.

There is an alternative algorithm similar to the previous one:

Define function ${f}^{\prime}:{2}^{E}\times {2}^{E}\to {2}^{E}\times {2}^{E}$ by:

$${f}^{\prime}(A,B):=(E\setminus \left(\overline{G}\left(B\right)\right),E\setminus \left(\overline{F}\left(A\right)\right)$$

If F and G are substitutable, then ${f}^{\prime}$ is monotone for order ≤, since, if B decreases, then $\overline{G}\left(B\right)$ decreases; so $E\setminus \overline{G}\left(B\right)$ increases. Similarly, if A increases, then $E\setminus \overline{F}\left(A\right)$ decreases.

As before, three-stable pairs are exactly the fixed points of ${f}^{\prime}$. We start the iteration from $({A}_{1},{B}_{1})=(E,\varnothing )$ for the men-optimal or with $({A}_{1},{B}_{1})=(\varnothing ,E)$ for the women-optimal solution.

For four-stability, we define monotone function ${f}^{\prime \prime}$ as follows:

$${f}^{\prime \prime}(A,B):=(E\setminus \left({\mathcal{D}}_{G}\left(B\right)\right),E\setminus \left({\mathcal{D}}_{F}\left(A\right)\right))$$

If $F,G$ are substitutable, then ${\mathcal{D}}_{F},{\mathcal{D}}_{G}$ are monotone; therefore, ${f}^{\prime \prime}$ is monotone for order ≤. Fixed points of ${f}^{\prime \prime}$ are four-stable pairs $(A,B)$, since $A=E\setminus \left({\mathcal{D}}_{G}\left(B\right)\right)$, $B=E\setminus \left({\mathcal{D}}_{F}\left(A\right)\right))$.

If we start the iteration of ${f}^{\prime \prime}$ from $({A}_{1},{B}_{1})=(E,\varnothing )$, 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})=(\varnothing ,E)$ leads to the women-optimal solution.

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 $\underline{{t}_{0}}$ (e.g., $\underline{{t}_{C}}:=(M+\phantom{\rule{3.33333pt}{0ex}}1,\dots ,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\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)$. 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 $\underline{{s}_{C}}$ denote the stable score vector that we get by running the score-decreasing algorithm on $\underline{{t}_{C}}$.

2. **The score-increasing algorithm:** colleges start with some critical score vector, $\underline{{t}_{0}}$ (e.g., $\underline{{t}_{A}}=(0,\dots ,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\left(P\left(\underline{t}\right)\right)$. 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 $\underline{{s}_{A}}$ be the stable score vector the score-increasing algorithm outputs from input $\underline{{t}_{A}}$.

Tarski’s Theorem implies the following corollary for three-stability.

Define function $f:{2}^{E}\times {2}^{E}\to {2}^{E}\times {2}^{E}$ by:
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.

$$f(A,B):=(E\setminus \left(\overline{G}\left(B\right)\right),E\setminus \left(\overline{F}\left(A\right)\right)=(E\setminus (B\setminus G\left(B\right)),E\setminus (A\setminus F\left(A\right))$$

A similar theorem can be proven for the four-stable $(A,B)$ pairs:

Function
$${f}^{\prime \prime}(A,B):=(E\setminus \left({\mathcal{D}}_{G}\left(B\right)\right),E\setminus \left({\mathcal{D}}_{F}\left(A\right)\right))$$
is monotone, and its fixed points are exactly the four-stable pairs; so, we can use Tarski’s theorem again.

In this subsection, we show a lattice property of stable sets (rather than stable pairs).

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.

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.

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.

$A=\varnothing $ | $B=\{a,b\}$ | $S=\varnothing $ |

$A=\left\{a\right\}$ | $B=\left\{a\right\}$ | $S=\left\{a\right\}$ |

$A=\left\{b\right\}$ | $B=\left\{b\right\}$ | $S=\left\{b\right\}$ |

$A=\{a,b\}$ | $B=\varnothing $ | $S=\varnothing $ |

Now, $\varnothing {\le}_{F}\left\{a\right\}$ and $\varnothing {\le}_{F}\left\{b\right\}$, but $\left\{a\right\}$ and $\left\{b\right\}$ are uncomparable. Therefore, these two sets do not have a supremum.

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:{\mathbb{N}}^{E}\to {\mathbb{N}}^{E}$:

$$f\left(\underline{t}\right)={P}_{G}(E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))$$

Therefore, we take all contracts above score limit $\underline{t}$ (this is $P\left(\underline{t}\right)$) and add those contracts that are not dominated by $P\left(\underline{t}\right)$. Then, $f\left(\underline{t}\right)$ is the score limit that the colleges choose for this set.

If ${\underline{t}}_{1}\le {\underline{t}}_{2}$, then $P\left({\underline{t}}_{1}\right)\supseteq P\left({\underline{t}}_{2}\right)$. Since ${\mathcal{D}}_{F}$ is monotone, $E\setminus {\mathcal{D}}_{F}\left(P\left({\underline{t}}_{1}\right)\right))\subseteq E\setminus {\mathcal{D}}_{F}\left(P\left({\underline{t}}_{2}\right)\right))$. For a greater set, ${P}_{G}$ gives a higher score limit; so, ${P}_{G}(E\setminus {\mathcal{D}}_{F}\left(P\left({\underline{t}}_{1}\right)\right))\le {P}_{G}(E\setminus {\mathcal{D}}_{F}\left(P\left({\underline{t}}_{2}\right)\right))$. Therefore, f is a monotone function, indeed.

Tarski’s fixed point theorem implies the following corollary:

Moreover, we can achieve a connection with four-stability for every bipartite graph.

As a corollary of Statements 5 and 6, we get the following theorem:

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 $\underline{t}=0$, $S=F\left(P\left(\underline{t}\right)\right)=\left\{a\right\}$. There are two four-stable sets: $S=\varnothing $ with $A=\varnothing ,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:

In the Appendix, we prove Theorem 14 by taking a pointwise minimum of ${\underline{t}}^{1}$ and ${\underline{t}}^{2}$ and starting from there. The score-decreasing algorithm terminates at stable score vector ${\underline{t}}^{1}\wedge {\underline{t}}^{2}$.

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\left(A\right)=S=G\left(B\right)$ and $A\cup B=E$, $A\cap B=S$.
- Subset S of E is four-stable, if there exists subsets A and B of E, such that $F\left(A\right)=S=G\left(B\right)$ and $A\cap B=S$ and ${\mathcal{D}}_{F}\left(A\right)=E\setminus B$ and ${\mathcal{D}}_{G}\left(B\right)=E\setminus A$.
- Subset S of E is dominating stable, if ${\mathcal{D}}_{F}\left(S\right)\cup {\mathcal{D}}_{G}\left(S\right)=E\setminus S$.
- If F is substitutable, G is substitutable and loser-free; we defined generalized score-stability in SubSection 3.5

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.

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.

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.

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.

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.

The authors declare no conflict of interest.

- Gale, D.; Shapley, L.S. College admissions and the stability of marriage. Am. Math. Mon.
**1962**, 69, 9–15. [Google Scholar] [CrossRef] - Kelso, A.S., Jr.; Crawford, V.P. Job matching, coalition formation, and gross substitutes. Econometrica
**1982**, 50, 1483–1504. [Google Scholar] [CrossRef] - Blair, C. The lattice structure of the set of stable marriages with multiple partners. Math. Oper. Res.
**1988**, 13, 619–628. [Google Scholar] [CrossRef] - 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]
- 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]
- Hatfield, J.W.; Milgrom, P.R. Matching with contracts. Am. Econ. Rev.
**2005**, 95, 913–935. [Google Scholar] [CrossRef] - Knuth, D. Marriages Stables; Les Presses de l’Universite de Montreal: Montreal, QC, Canada, 1976. [Google Scholar]
- Fleiner, T. A fixed-point approach to stable matchings and some applications. Math. Oper. Res.
**2003**, 28, 103–126. [Google Scholar] [CrossRef] - Biró, P.; Kiselgof, S. College Admissions with Stable Score-Limits. Cent. Eur. J. Oper. Res.
**2013**, 1–15. [Google Scholar] - Tarski, A. A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math.
**1955**, 5, 285–310. [Google Scholar] [CrossRef]

Proof of Lemma 1. If $F\left(A\right)=S$, then for every $x\in A\setminus S$, we have $S\subset (S\cup \{x\left\}\right)\subseteq A$. Therefore, by F path independence, $F(S\cup \{x\left\}\right)=S$; so ${\mathcal{D}}_{F}\left(S\right)\supseteq A\setminus S$. Consequently, $F\left(A\right)\cap {\mathcal{D}}_{F}\left(S\right)=A\setminus S$.

If ${\mathcal{D}}_{F}\left(S\right)\cap A=A\setminus S$, then $\overline{F}(S\cup \left\{x\right\})=x$, for every $x\in A\setminus S$; so, from substitutability, $x\in \overline{F}\left(A\right)$. Thus, $\overline{F}\left(A\right)\supseteq A\setminus S$, which means $F\left(A\right)\subseteq S$.

By the path independence of F, we have $F\left(A\right)\subseteq S\subseteq A$⇒$F\left(A\right)=F\left(S\right)=S$ ☐

Proof of Lemma 2. We have seen that ${\mathcal{D}}_{F}$ is monotone; hence ${\mathcal{D}}_{F}\left(S\right)\subseteq {\mathcal{D}}_{F}\left(A\right)$.

If $x\in {\mathcal{D}}_{F}\left(A\right)$, then $F(A\cup \{x\left\}\right)\subseteq A\subseteq (A\cup \{x\left\}\right)$; so $F(A\cup \{x\left\}\right)=F\left(A\right)=S$ by the path independency.

Therefore, $F(A\cup \{x\left\}\right)\subseteq S\cup \left\{x\right\}\subseteq A\cup \left\{x\right\}$; hence $F(S\cup \{x\left\}\right)=F(A\cup \{x\left\}\right)=S$. This means S dominates any $x\in {\mathcal{D}}_{F}\left(A\right)$, i.e., ${\mathcal{D}}_{F}\left(A\right)={\mathcal{D}}_{F}\left(S\right)$. ☐

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 $\underline{t}$ ( i.e., ${A}_{i}{C}_{j}\in F\left(P\left(\underline{t}\right)\right)$), then ${A}_{i}$ can leave ${C}_{j}$ at ${\underline{t}}^{\prime}$ if she does not reach ${t}_{j}^{\prime}$ or got a better opportunity at another college.

If student ${A}_{l}$ does not go to college ${C}_{j}$ at the score vector, $\underline{t}$, (${A}_{l}{C}_{j}\notin F\left(P\left(\underline{t}\right)\right)$), then she will not go to ${C}_{j}$ under score vector ${\underline{t}}^{\prime}$, because if ${A}_{l}$ does not reach ${t}_{j}$, then she does not reach the higher limit, ${t}_{j}^{\prime}$. If ${A}_{l}$ reaches ${t}_{j}$, but chooses better college ${C}_{k}$ instead, since ${t}_{k}^{\prime}\le {t}_{k}$, she will stay in college ${C}_{k}$. Therefore, the set of students assigned to ${C}_{j}$ with ${\underline{t}}^{\prime}$ is the subset of the set of students going to ${C}_{j}$ under $\underline{t}$. $(F\left(P\left({\underline{t}}^{\prime}\right)\right)\cap E\left({C}_{j}\right))\subseteq (F\left(P\left(\underline{t}\right)\right)\cap E\left({C}_{j}\right))$ The choice function, ${G}_{j}$, of college ${C}_{j}$ is substitutable. Therefore, $F\left(P\left(\underline{t}\right)\right)\cap E\left({C}_{j}\right)$ is valid; then, a subset of it is also valid. Therefore, ${\underline{t}}^{\prime}$ is ${C}_{j}$-valid. ☐

Proof of Lemma 6. Let the set of contracts above score vectors ${\underline{t}}^{1}$ and ${\underline{t}}^{2}$ be $P\left({\underline{t}}^{1}\right)=A$ and $P\left({\underline{t}}^{2}\right)=B$. Then, $P\left({t}_{min}\right)=A\cup B$. Suppose that ${t}_{j}^{1}={t}_{j}^{min}$ for college ${C}_{j}$. Since $A\subseteq A\cup B$, from substitutability $\overline{F}\left(A\right)\subseteq \overline{F}(A\cup B)$. Considering the set of contracts of college ${C}_{j}$, $E\left({C}_{j}\right)\cap A=E\left({C}_{j}\right)\cap (A\cup B)$, i.e., ${C}_{j}$ accepts the same set of contracts with score vector ${\underline{t}}^{1}$ as with ${\underline{t}}^{min}$. Therefore, $E\left({C}_{j}\right)\cap F\left(A\right)\supseteq E\left({C}_{j}\right)\cap F(A\cup B)$. Since G is substitutable, if a set is valid, then its subset is also valid. $G(E\left({C}_{j}\right)\cap F\left(A\right))=E\left({C}_{j}\right)\cap F\left(A\right)$ so $\overline{G}(E\left({C}_{j}\right)\cap F\left(A\right))=\varnothing $. For a smaller set, $\overline{G}(E\left({C}_{j}\right)\cap F(A\cup B))=\varnothing $; so, $(A\cup B)$ is also valid for college ${C}_{j}$.

In other words, if we change the score limit from ${\underline{t}}^{1}$ to ${\underline{t}}^{min}$, 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 ${\underline{t}}^{min}$ is ${C}_{j}$-valid. We can use the same argument for every college; therefore ${\underline{t}}^{min}$ 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 $\underline{t}$ is valid and ${\underline{t}}^{\prime}=({t}_{1},\cdots {t}_{j-1},{t}_{j}-k\cdots {t}_{m})$ is also valid, then for every $1\le {k}^{\prime}\le k$, ${\underline{t}}^{\prime \prime}=({t}_{1},\cdots {t}_{j-1},{t}_{j}-{k}^{\prime},\cdots {t}_{m})$ is valid (it is ${C}_{j}$-valid, because ${t}^{\prime}$ 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 $\underline{{t}_{C}}:=(M+1,\dots ,M+1)$), but only $(0,\dots ,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 $\underline{t}$ is a stable vector.

Suppose that there exist a stable score vector ${\underline{t}}^{1}\le {\underline{t}}_{0}$, where ${\underline{t}}^{1}\neg \le \underline{t}$. Therefore, $\underline{t}=({t}_{1},\cdots {t}_{m})$ and ${\underline{t}}^{1}=({t}_{1}^{1},\cdots {t}_{m}^{1})$, and ${t}_{i}^{1}>{t}_{i}$ for some i. Define the set:

$$T=\{\underline{x}\in {\mathbb{N}}^{m}:{x}_{j}\ge {t}_{j}^{1}\phantom{\rule{1.em}{0ex}}\forall j\in \{1,\cdots m\}\}$$

The algorithm starts from ${\underline{t}}_{0}\in T$ and ends in $\underline{t}\notin T$; so, there is a step, when the score vector leaves T: from score vector ${\underline{w}}^{1}=({w}_{1},{w}_{2},\cdots {t}_{k}^{1}\cdots {w}_{m})\in T$, we move to ${\underline{w}}^{2}=({w}_{1},{w}_{2},\cdots {t}_{k}^{1}-1\cdots {w}_{m})\notin T$. Since this step is possible, both ${\underline{w}}^{1}$ and ${\underline{w}}^{2}$ are valid score vectors. We know that ${\underline{w}}^{1}\ge {\underline{t}}^{1}$. Using Lemma 6, both ${\underline{t}}^{1}$ and ${\underline{w}}^{2}$ are valid; so, their minimum ${\underline{w}}^{3}=({t}_{1}^{1},{t}_{2}^{1},\cdots {t}_{k}^{1}-1\cdots {t}_{m}^{1})$ is also valid. Therefore, ${\underline{w}}^{3}$ is stable, and it can be reached from ${\underline{t}}^{1}$ by lowering the score limit of ${C}_{k}$. Therefore, ${\underline{t}}^{1}$ is not critical, hence it cannot be stable; a contradiction.

Since every stable score vector are less than or equal to $\underline{{t}_{0}}=(M+1,\cdots M+1)$, the biggest of all stable score vectors is $\underline{{s}_{C}}$. Every student is accepted by fewer colleges than in any other stable admissions; so, ${\underline{s}}_{C}$ is applicant-pessimal. Figure 6 is showing a possible layout. ☐

Proof of Theorem 6. It follows from the algorithm that $\underline{t}$ is valid. Suppose that it is not stable, i.e., there is a college, ${C}_{j}$, such that ${\underline{t}}^{\prime}=({t}_{1},{t}_{2},\dots ,{t}_{j-1},{t}_{j}-1,{t}_{j+1},\dots ,{t}_{m})$ is still valid.

If ${t}_{j}^{0}\le {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 ${\underline{v}}^{1}$ to ${\underline{v}}^{2}$.

Since the score limits in the algorithm always increase, ${\underline{v}}^{1}\le \underline{t}$ and ${v}_{j}^{1}={t}_{j}-1$; therefore, ${\underline{v}}^{1}\le {\underline{t}}^{\prime}$. We can use Lemma 5: score limit ${\underline{t}}^{\prime}$ is valid, so ${\underline{v}}^{1}$ is also ${C}_{j}$-valid. However, then, the algorithm would not have increased ${\underline{v}}^{1}$ to ${\underline{v}}^{2}$; a contradiction; Therefore, $\underline{t}$ is stable.

If ${t}_{j}^{0}={t}_{j}$, since ${\underline{t}}_{0}$ is critical, the score vector ${\underline{t}}_{0}^{\prime}=({t}_{1}^{0},{t}_{2}^{0},\dots ,{t}_{j-1}^{0},{t}_{j}^{0}-1,{t}_{j+1}^{0},\dots ,{t}_{m}^{0})$ is not valid for ${C}_{j}$. From ${\underline{t}}_{0}\le \underline{t}$, we get that ${\underline{t}}_{0}^{\prime}\le {\underline{t}}^{\prime}$. Using Lemma 5 again, if ${\underline{t}}^{\prime}$ was valid, then ${\underline{t}}_{0}^{\prime}$ would be ${C}_{j}$-valid. Therefore, ${\underline{t}}^{\prime}$ is not valid; therefore, $\underline{t}$ is indeed stable.

To show that $\underline{t}$ is minimal, suppose that there is a stable score limit, ${\underline{t}}^{1}$, such that ${\underline{t}}_{0}\le {\underline{t}}^{1}$, but $\underline{t}\nleqq {\underline{t}}^{1}$, i.e., ${t}_{j}^{1}<{t}_{j}$ for some j. Let:
Since $\underline{t}\notin {T}^{\prime}$, but ${\underline{t}}_{0}\in {T}^{\prime}$, there is a step such that when we leave ${T}^{\prime}$, we move from ${\underline{w}}^{1}$ to ${\underline{w}}^{2}$. There is a college, ${C}_{i}$, where ${\underline{w}}_{i}^{1}={\underline{t}}_{i}^{1}$. For other colleges, ${\underline{w}}_{k}^{1}\le {\underline{t}}_{k}^{1}$; so, by Lemma 5, ${\underline{w}}^{1}$ was ${C}_{i}$-stable. Therefore, ${C}_{i}$ does not want to increase its score limit.

$${T}^{\prime}=\{\underline{x}\in {\mathbb{N}}^{n}:{x}_{i}\le {t}_{i}^{1}\phantom{\rule{1.em}{0ex}}\forall i\in \{1,\cdots m\}\}$$

Therefore, ${\underline{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, ${\underline{s}}_{A}$ is applicant-optimal. Figure 7 is showing a possible layout. ☐

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\left({m}^{2}n\right)$.

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\left(mn\right)$.

☐

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}^{\prime},{B}^{\prime})$.

We can assume that there exists a b for which $b\in B$, but $b\notin {B}^{\prime}$. Since $S\subseteq {B}^{\prime}$, it follows that $b\notin S$. Moreover $b\in F(A\cup \{b\left\}\right)$, but $b\notin F({A}^{\prime}\cup \left\{b\right\})$, because $b\in F(A\cup \{b\left\}\right)\iff b\notin B$.

By ${A}^{\prime}\setminus S=\overline{F}\left({A}^{\prime}\right)\subseteq \overline{F}({A}^{\prime}\cup \left\{b\right\})$, we get $F({A}^{\prime}\cup \left\{b\right\})\subseteq S\subseteq {A}^{\prime}\cup \left\{b\right\}$; hence $F({A}^{\prime}\cup \left\{b\right\})=S$.

We know that $({A}^{\prime}\cup \left\{b\right\})\setminus S=\overline{F}({A}^{\prime}\cup \left\{b\right\})$ and $A\setminus S=\overline{F}\left(A\right)$.

Since F is substitutable, $\overline{F}({A}^{\prime}\cup A\cup \left\{b\right\})$ contains both sets, $({A}^{\prime}\cup A\cup \left\{b\right\})\setminus S\subseteq \overline{F}({A}^{\prime}\cup A\cup \left\{b\right\})$; so, $F({A}^{\prime}\cup A\cup \left\{b\right\})\subseteq S$.

From $F({A}^{\prime}\cup \left\{b\right\})=S$, we get $F(A\cup \left\{b\right\})\subseteq F(A\cup \left\{b\right\})\cup F({A}^{\prime}\cup \left\{b\right\})\subseteq A\cup \left\{b\right\}$; so, $F(A\cup \left\{b\right\})=F(F(A\cup \left\{b\right\})\cup F({A}^{\prime}\cup \left\{b\right\}))$.

Using that F is path independent, from Theorem 3, $b\in F(A\cup \left\{b\right\})=F(F(A\cup \left\{b\right\})\cup F({A}^{\prime}\cup \left\{b\right\}))=F(A\cup \left\{b\right\})\cup ({A}^{\prime}\cup \left\{b\right\}))=F({A}^{\prime}\cup A\cup \left\{b\right\})\subseteq S$. Therefore, $b\in S$; a contradiction.

Let S and ${S}^{\prime}$ be two different stable sets. Let four-stable pairs $(A,B)$ and $({A}^{\prime},{B}^{\prime})$ correspond to stable sets S and ${S}^{\prime}$, respectively.

(ii) $(A,B)\le ({A}^{\prime},{B}^{\prime})$⇒$S{\le}_{F}{S}^{\prime}$.

From the ordering of the four-stable pairs, $S\subseteq A\subseteq {A}^{\prime}$ and ${S}^{\prime}\subseteq {A}^{\prime}$; so, $S\cup {S}^{\prime}\subseteq {A}^{\prime}$.

Since F is path independent, from ${S}^{\prime}=F\left({A}^{\prime}\right)\subseteq S\cup {S}^{\prime}\subseteq {A}^{\prime}$, we get that $F(S\cup {S}^{\prime})={S}^{\prime}$.

(iii) $S{\le}_{F}{S}^{\prime}$, ⇒$(A,B)\le ({A}^{\prime},{B}^{\prime})$ .

Suppose that ${B}^{\prime}\u2288B$. Consequently, $\exists \phantom{\rule{4pt}{0ex}}b$, such that $b\notin B$, but $b\in {B}^{\prime}$. From Lemma 2, ${\mathcal{D}}_{F}\left(A\right)={\mathcal{D}}_{F}\left(S\right)$; so:

$b\notin B$⇒$b\in {\mathcal{D}}_{F}\left(A\right)={\mathcal{D}}_{F}\left(S\right)$⇒$b\notin F(S\cup \{b\left\}\right)$

$b\in {B}^{\prime}$⇒$b\notin {\mathcal{D}}_{F}\left({A}^{\prime}\right)={\mathcal{D}}_{F}\left({S}^{\prime}\right)$⇒$b\in F({S}^{\prime}\cup \left\{b\right\})$

We know that $F(S\cup {S}^{\prime})={S}^{\prime}$; therefore, $F(S\cup {S}^{\prime}\cup \left\{b\right\})\subseteq {S}^{\prime}\cup \left\{b\right\}\subseteq S\cup {S}^{\prime}\cup \left\{b\right\}$. Since F is path independent, $F(S\cup {S}^{\prime}\cup \left\{b\right\})=F({S}^{\prime}\cup \left\{b\right\})\ni b$; hence $b\in F(S\cup \{b\left\}\right)$; a contradiction.

Similarly, from ${B}^{\prime}\subseteq B$, we get ${\mathcal{D}}_{F}\left({B}^{\prime}\right)\subseteq {\mathcal{D}}_{F}\left(B\right)$ by the monotonicity of ${\mathcal{D}}_{F}$ and $E\setminus {A}^{\prime}\subseteq E\setminus A$; hence ${A}^{\prime}\supseteq 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\notin P\left(\underline{t}\right):e\in F(\left\{e\right\}\cup P\left(\underline{t}\right))\}$ be the set of contracts that F prefers to $F\left(P\left(\underline{t}\right)\right)$. In other words, $J=(E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))\setminus P\left(\underline{t}\right)$; therefore, $E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)=F\left(P\left(\underline{t}\right)\right)\cup J$. (See Figure 8.)

Suppose $\underline{t}$ is a fixed point. Let $B=E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)$, and we use that: $P\left({P}_{G}\left(B\right)\right)\cap B=G\left(B\right)$. From this, $P\left(\underline{t}\right)\cap (E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))=P\left({P}_{G}(E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))\right)\cap (E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))=G(E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)).$

Since $P\left(\underline{t}\right)\cap (E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))=F\left(P\left(t\right)\right)$, we get that $G(F\left(P\left(\underline{t}\right)\right)\cup J)=F\left(P\left(\underline{t}\right)\right)$, and since G is substitutable, $\overline{G}\left(F\left(P\left(\underline{t}\right)\right)\right)\subseteq \overline{G}(F\left(P\left(\underline{t}\right)\right)\cup J)=J$. Therefore, $G\left(F\left(P\left(\underline{t}\right)\right)\right)=F\left(P\left(\underline{t}\right)\right)$; so, $\underline{t}$ is valid.

To prove that $\underline{t}$ is critical, assume that college ${C}_{j}$ lowers its score limit by one. Let

${\underline{t}}^{\prime}=({t}_{1},{t}_{2},\dots ,{t}_{j-1},{t}_{j}-1,{t}_{j+1},\dots ,{t}_{m})$. Then, at college ${C}_{j}$, the accepted $P\left(\underline{t}\right)$ increases with some contracts.

Now, we use that the graph is simple. If ${A}_{i}{C}_{j}\in P\left(\underline{t}\right)$, then applicant ${A}_{i}$ will also be accepted under ${\underline{t}}^{\prime}$. If ${A}_{i}$ is not accepted at college ${C}_{j}$ with score vector $\underline{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}\in J$, because she got only one new chance. Therefore, $F\left(P\left({\underline{t}}^{\prime}\right)\right)\cap E\left({C}_{j}\right)=(F\left(P\left(\underline{t}\right)\right)\cup J)\cap E\left({C}_{j}\right)$.

Other colleges cannot have new students; so, they stay valid.

From $F\left(P\left(\underline{t}\right)\right)\cup 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\left({\underline{t}}^{\prime}\right)$. Therefore, ${\underline{t}}^{\prime}$ is not valid.

Now, assume that $\underline{t}$ is valid and critical. Therefore, $G\left(F\left(P\left(\underline{t}\right)\right)\right)=F\left(P\left(\underline{t}\right)\right)$; so, $G(F\left(P\left(\underline{t}\right)\right)\cup J)$ accepts contracts in $F\left(P\left(\underline{t}\right)\right)$ (because contracts in J do not reach score limit $\underline{t}$). Therefore, ${P}_{G}(E\setminus {D}_{F}\left(P\left(\underline{t}\right)\right))\le \underline{t}$.

As before, ${\underline{t}}^{\prime}=({t}_{1},{t}_{2},\dots ,{t}_{j-1},{t}_{j}-1,{t}_{j+1},\dots ,{t}_{m})$. Function P is antitone; so

$P\left(\underline{t}\right)\subseteq P\left({\underline{t}}^{\prime}\right)$. Since ${\mathcal{D}}_{F}$ is monotone, ${\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)\subseteq {\mathcal{D}}_{F}\left(P\left({\underline{t}}^{\prime}\right)\right)$; so, $E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)\supseteq E\setminus {\mathcal{D}}_{F}\left(P\left({\underline{t}}^{\prime}\right)\right)\supseteq F\left(P\left({\underline{t}}^{\prime}\right)\right)$. As $\underline{t}$ is critical, $F\left(P\left({t}^{\prime}\right)\right)$ is infeasible for college ${C}_{j}$; so, $E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)$, too, and we get ${P}_{{G}_{j}}(E\setminus {D}_{F}\left(P\left(\underline{t}\right)\right))\ge {t}_{j}$. This is valid for every college; therefore, ${P}_{G}(E\setminus {D}_{F}\left(P\left(\underline{t}\right)\right))=\underline{t}$.

We did not use that $\mathcal{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. ☐

Proof of Statement 6. (i)⇒ (ii) If $\underline{t}$ is a fixed point, $\underline{t}={P}_{G}(E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))$, then let $B=E\setminus {\mathcal{D}}_{F}(P\left(\underline{t}\right).$

As we have seen in the proof of Statement 5, $F\left(P\left(\underline{t}\right)\right)=P\left(\underline{t}\right)\cap (E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)=G(E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))=G(F\left(P\left(\underline{t}\right)\right)\cup J)$; so, $S=G\left(B\right)$.

This gives ${\mathcal{D}}_{G}\left(B\right)\cap B=\overline{G}\left(B\right)=J$. From the contracts outside B, the set, B, must dominate contracts under score limit $\underline{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\notin B$ has a score of ${t}_{j}-1$, because in that case, ${P}_{{G}_{j}}$ would have chosen ${t}_{j}-1$ and $\underline{t}$ would not be stable.) Therefore, ${\mathcal{D}}_{G}\left(B\right)\supseteq E\setminus P\left(\underline{t}\right)$. Therefore, $A=E\setminus {\mathcal{D}}_{G}\left(B\right)\subseteq P\left(\underline{t}\right)$.

Since F is path independent and $S=F\left(P\left(\underline{t}\right)\right)\subseteq A\subseteq P\left(\underline{t}\right)$, we get that $F\left(A\right)=S$.

From Lemma 2, ${D}_{F}\left(A\right)={D}_{F}\left(P\left(t\right)\right)=E\setminus B$; so, S is indeed four-stable.

(i)⇐ (ii)

If S is four-stable, then there exists $A,B$, such that $F\left(A\right)=S,G\left(B\right)=S$. Let the score limit be $\underline{t}={P}_{G}\left(B\right)$. We want to know what $P\left(\underline{t}\right)$ is. It is sure that $P\left(\underline{t}\right)\cap B=S$, because $P\left({P}_{G}\left(B\right)\right)\cap B=G\left(B\right)$, and since ${\mathcal{D}}_{G}\left(B\right)=E\setminus A$ and ${\mathcal{D}}_{G}\left(B\right)\supseteq E\setminus P\left(t\right)$, so $A=E\setminus {\mathcal{D}}_{G}\left(B\right)\subseteq P\left(\underline{t}\right)$.

Since ${\mathcal{D}}_{F}\left(A\right)=E\setminus B$, substitutability implies that dominated contracts will not be chosen from $P\left(\underline{t}\right)$, since $A\subseteq P\left(\underline{t}\right)\subseteq A\cup (E\setminus B)$. Therefore, $\overline{F}\left(P\left(\underline{t}\right)\right)\supseteq P\left(\underline{t}\right)\setminus A$. Then, $F\left(P\left(\underline{t}\right)\right)\subseteq A\subseteq P\left(\underline{t}\right)$. From the path-independent property, $S=F\left(A\right)=F\left(P\left(\underline{t}\right)\right)$.

Using Lemma 2 again, ${\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)={\mathcal{D}}_{F}\left(A\right)=E\setminus B$, $E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right)=B$ and ${P}_{G}(E\setminus {\mathcal{D}}_{F}\left(P\left(\underline{t}\right)\right))={P}_{G}\left(B\right)=\underline{t}$; therefore, $\underline{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 ${\underline{t}}^{1}$ and ${\underline{t}}^{2}$ be two arbitrary stable score vectors. We want to show that they have a join and a meet. Using Lemma 6, ${t}^{min}=min({\underline{t}}^{1},{\underline{t}}^{2})$ is valid. Let us start the score-decreasing algorithm from ${t}^{min}$; from the algorithm, we get a stable score vector, $\underline{t}$. From Theorem 5, $\underline{t}$ is the biggest among all the stable score vectors smaller than or equal to ${t}^{min}$. Therefore, $\underline{t}={\underline{t}}^{1}\wedge {\underline{t}}^{2}$, because for every stable vector, such that ${\underline{t}}^{\prime}\le {t}^{1},{t}^{2}$, ${t}^{\prime}\le {t}^{min}$; therefore, ${\underline{t}}^{\prime}\le t$.

We finish by showing the existence of ${\underline{t}}^{1}\vee {\underline{t}}^{2}$. There exists a common upper bound of ${\underline{t}}^{1}$ and ${\underline{t}}^{2}$, for example ${\underline{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: $\underline{a}$ and $\underline{b}$. Since ${\underline{t}}^{1}$ is a lower bound of $\underline{a}$ and $\underline{b}$, ${\underline{t}}^{1}\le \underline{a}\wedge \underline{b}$; similarly, ${\underline{t}}^{2}\le \underline{a}\wedge \underline{b}$. Therefore, we found a common upper bound of ${\underline{t}}^{1}$ and ${\underline{t}}^{2}$ smaller than a; a contradiction. ☐

Proof of Theorem 15. Three-stable ⇒ dominating

There are A and B, such that $F\left(A\right)=S=G\left(B\right)$. From Lemma 1, ${\mathcal{D}}_{F}\left(S\right)\supseteq A\setminus S$. The same goes for $G\left(B\right)$; so, ${\mathcal{D}}_{G}\left(S\right)\supseteq B\setminus S$. Their union is

${\mathcal{D}}_{F}\left(S\right)\cup {\mathcal{D}}_{G}\left(S\right)\supseteq ((A\setminus S)\cup (B\setminus S))=E\setminus S$.

Additionally, S does not dominate itself; so, ${\mathcal{D}}_{F}\left(S\right)\cup {\mathcal{D}}_{G}\left(S\right)=E\setminus S$.

Dominating ⇒ four-stable

We know that ${\mathcal{D}}_{F}\left(S\right)\cup {\mathcal{D}}_{G}\left(S\right)=E\setminus S$. Let $A=E\setminus {\mathcal{D}}_{G}\left(S\right)$ and $B=E\setminus {\mathcal{D}}_{F}\left(S\right)$.

$A\subseteq S\cup {\mathcal{D}}_{F}\left(S\right)$, so $F\left(A\right)=S$. From Lemma 2, ${\mathcal{D}}_{F}\left(A\right)={\mathcal{D}}_{F}\left(S\right)=E\setminus B$. Similarly, ${\mathcal{D}}_{G}\left(B\right)={\mathcal{D}}_{G}\left(S\right)=E\setminus 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\left(A\right)=S=G\left(B\right)$ and $A\cap B=S$, and ${\mathcal{D}}_{F}\left(A\right)=E\setminus B,{\mathcal{D}}_{G}\left(B\right)=E\setminus A$.

Let $D=E\setminus (A\cup B)$ and ${A}^{\prime}=A\cup D,{B}^{\prime}=B$.

Now, ${A}^{\prime}\cup {B}^{\prime}=E$, ${A}^{\prime}\cap {B}^{\prime}=A\cap B=S$, and from Lemma 2, ${\mathcal{D}}_{F}\left(S\right)={\mathcal{D}}_{F}\left(A\right)=E\setminus B=(A\setminus S)\cup D={A}^{\prime}\setminus S$. From Lemma 1, $F\left({A}^{\prime}\right)=S$, $G\left({B}^{\prime}\right)=G\left(B\right)=S$; so, with the $({A}^{\prime},{B}^{\prime})$ 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\subseteq E$ be the enrollment realized from stable score vector $\underline{t}$. Define A as the set of contracts above score vector $\underline{t}$. Let B be the union of S and the set of contracts under score limit $\underline{t}$.

From all the accepted contracts above score vector $\underline{t}$, the applicants choose contract set S; so, $F\left(S\right)=S$. If colleges choose from contract set B, just like from all contracts, they would set score limit to $\underline{t}$; so, $G\left(B\right)=S$. It is easy to see that $A\cup B=E,A\cap 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.

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.

Figure | Simple | $\mathit{F}$ | Path ind. | $\mathbf{G}$ | Path ind. |
---|---|---|---|---|---|

2 | no | ${Q}_{1}$ | no | ${Q}_{1}$ | no |

4 | no | $a>b$ | yes | ${Q}_{1}$ | no |

9 | yes | $(a>c)+(b>d)$ | yes | ${Q}_{1}(a,b)+{Q}_{2}(c,d)$ | no |

10 | yes | $a+{Q}_{1}(b,c)$ | no | ${Q}_{1}(a,b)+c$ | no |

11 | yes | $a+{Q}_{1}(b,c,d)$ | no | ${Q}_{1}(a,b)+c+d$ | no |

12 | yes | $(a>c)+(b>d)$ | yes | ${Q}_{1}(a,b)+{Q}_{1}(c,d)$ | no |

13 | no | $a>b$ | yes | $b>a$ | yes |

Figure | Three-Stable | Four-Stable | Dominating Stable | Score-Stable | $\underline{t}$ Fixed |
---|---|---|---|---|---|

2 | ∅ | $\varnothing ,\left\{a\right\},\left\{b\right\}$ | $\left\{a\right\},\left\{b\right\}$ | ∅ | ∅ |

4 | $\varnothing ,\left\{a\right\}$ | $\varnothing ,\left\{a\right\}$ | $\left\{a\right\},\left\{b\right\}$ | $\left\{a\right\}$ | $\varnothing ,\left\{a\right\}$ |

9 | $\{a,d\},\{c,d\}$ | $\{a,d\}$ | $\{a,d\}$ | $\{a,d\}$ | $\{a,d\}$ |

10 | $\left\{a\right\},\left\{c\right\}$ | $\{a,c\}$ | $\{a,c\}$ | $\left\{a\right\}$ | $\left\{a\right\},$ |

11 | $\varnothing ,\left\{a\right\}$ | $\left\{a\right\}$ | $\left\{b\right\},\{a,c\},\{a,d\}$ | $\left\{a\right\}$ | $\left\{a\right\}$ |

12 | $\varnothing ,\{a,d\}$ | $\varnothing ,\{a,d\}$ | $\{a,d\},\{b,c\}$ | $\varnothing ,\{a,d\}$ | $\varnothing ,\{a,d\}$ |

13 | $\left\{a\right\},\left\{b\right\}$ | $\left\{a\right\},\left\{b\right\}$ | $\left\{a\right\},\left\{b\right\}$ | $\left\{a\right\}$ | $\left\{a\right\},\left\{b\right\}$ |

© 2014 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/3.0/).