Restabilization Process in Matching Markets with Workers Proposing

Millán Beatriz^1,2

¹Instituto de Matemática Aplicada San Luis, IMASL, Universidad Nacional de San Luis and CONICET, San Luis, Argentina.
²Departamento de Matemática, Universidad Nacional de San Juan, San Juan, Argentina.

DOI: 10.4236/ojdm.2022.124007                

Abstract

This paper is focused on the analysis, in the framework of lattice theory, of the matchings obtained from restabilization (after disruption) of stable matchings. When the disruption is due to entry workers or closure of firms the unemployed workers make offers to firms. The stable matching obtained is the firms-worst stable matching of the set of stable matchings that the firms weakly prefer to the initial stable matching (i.e., before being disrupted by changes in the population). More precisely, their position within the lattice of stable matchings is shown.

Keywords

Stable Matchings, Restabilization, Lattice

1. Introduction

This paper studies the matchings obtained through the restabilization process of disrupted many-to-one stable matchings by a change in the population. When the disruption is due to entry of workers or closure of firms we describe accurately the restabilization process by means of the lattice structure¹ of the set of stable matchings unanimously preferred by firms to the initial stable (before being disrupted by changes in the population). We characterize the outcome matching of the restabilization process.

A stable matching disrupted by the entrance of new workers on the market or the closure of firms is a worker quasi-stable matching. Worker quasi-stability is a relaxation of stability that allows blocking pairs involving a firm and an unemployed worker. The new workers and workers previously matched a firm that closed have to look for employment elsewhere.

Blum et al. in [2] study in a one-to-one model the restabilization process triggered by the disruption of a pairwise stable matching due to the retirement of some workers or the creation of firms. In these cases, they show that their modified version of the Deferred Acceptance (DA) algorithm introduced by Gale and Shapley in [3] always reaches a pairwise stable matching. They also show that the output of DA Algorithm on inputs that are firm quasi-stable are always stable and provide several characterizations of such outputs.²

David Cantala in [4] studies, in many-to-one matching markets, the restabilization process of a stable matching disrupted by a change in the population, extending that way the work of Blum et al. in [2], as he considers that firms may hire many workers. He designs the Set Offering (SO) Algorithm so as to mimic the restabilization process of a decentralized market, which always leads to a stable matching whenever the disruption is due to the opening of positions or the retirement of workers. When the disruption is due to the entrance of workers or the closure of positions, he constructs another algorithm (Acceptance Firing (AF) Algorithm) which produces a stable matching. In this algorithm, unemployed workers make offers to firms and captures the main feature of a decentralized process.

David Cantala in [5] shows that the set of stable matchings unanimously preferred by workers to a firm quasi-stable matching contains an element which is unanimously least preferred by workers, and most preferred by firms. He also shows that when a firm quasi-stable matching is fed into the Set Offering (SO) Algorithm (where firms propose), the existence of this matching guarantees the success of the algorithm and provides a characterization of the outcome of the algorithm.

The specific aim of this paper is to extend the work of Cantala in [5] considering the counterpart for the workers’ side, that is, when the disruption is due to the entrance of workers or the closure of positions. We show that the set of stable matchings unanimously preferred by firms to the initial stable matching has a lattice structure according to Blair’s order. Thus, it contains the firms-worst stable matching in the set. We show that this matching is the outcome of the restabilization process.

Wu and Roth in [6] show that the set of firm quasi-stable matchings forms a lattice; and the set of stable matchings equals the set of fixed points of a Tarski operator on this lattice. This Tarski operator describes a possible re-stabilization process following retirements or the creation of new positions. They identify the fixed point of the operator that can be obtained by iterating it starting at a firm quasi-stable matching: it is the join of that firm quasi-stable matching and the firm optimal stable matching.³

Another relevant aspect of our work is that it studies the previously mentioned results in a more general model of matching where the firms have q-separable and substitutable preferences. Substitutability and q-separability together produce a less restrictive condition that q-responsiveness. Martnez et al. in [8] illustrate the fact that the set of q-responsive preferences is a proper subset of the set of q-separable and substitutable preferences.

An implication of the characterization is that feeding AF algorithm with all possible worker quasi-stable matchings does not allow to reach all existing stable matchings since, in particular, stable matchings that cannot be ordered unanimously by firms, according to Blair’s order, are not outcomes of the procedure.

In the next section we describe the formal matching model, and review some results on stable matchings. Section 3 introduces worker quasi-stable matchings, and we prove some technical results. Section 4 studies the characterisation of the outcome matching of the restabilization process.

2. Preliminaries

The many-to-one bilateral matching market possesses two disjoint sets of agents (two-sided many-to-one matching model), the n firms F set and the m workers W set. Each firm $f\in F$ has a strict, transitive, and complete preference relation $P\left(f\right)$ over the set of all of W subsets, and each worker has a strict, transitive, and complete preference relation $P\left(w\right)$ over $F\cup \varnothing$. Preferences profiles are $\left(n+m\right)$ -tuples of preference relations and they are represented by $P=\left(P\left(f_1\right)\mathrm{,}\cdots \mathrm{,}P\left(f_n\right)\mathrm{<mo>\; ;\; </mo>}P\left(w_1\right)\mathrm{,}\cdots \mathrm{,}P\left(w_m\right)\right)$. Given a $P$ preference profile, then the many-to-one bilateral matching market is the triplet $\left(F\mathrm{,}W\mathrm{,}P\right)$.

The matching problem consists of matching workers with firms maintaining the bilateral nature of their relationship and allowing for the possibility that both, firms and workers, may remain unmatched. Formally,

Definition 1. A matching $\mu$ is a mapping from the set $F\cup W$ into the set of all subsets of $F\cup W$ such that for all $w\in W$ and $F\in F$ :

1) Either $\left|\mu \left(w\right)\right|=1$ and $\mu \left(w\right)\subseteq F$ or else $\mu \left(w\right)=\varnothing$.

2) $\mu \left(F\right)\in 2^W$.

3) $\mu \left(w\right)=f$ if and only if $w\in \mu \left(f\right)$.⁴

Criterion 1 indicates that a worker is either matched to a firm or remains single. Criterion 2 shows that a firm is either matched to a subset of workers or remains single. Lastly, criterion 3 states that the relationship is reciprocal. $\mathcal{M}\left(F\mathrm{,}W\mathrm{,}P\right)$ denotes all of the possible matchings in $\left(F\mathrm{,}W\mathrm{,}P\right)$.

We are following the convention of extending preferences from the original sets ( $2^W$ and $F\cup \varnothing$ ) to the set of matchings. However, we now have to consider weak preference relations since two matchings may associate to an agent the same partner. These preference relations will be denoted by $R\left(f\right)$ and $R\left(w\right)$. For instance, to say that all firms prefer ${\mu }_1$ to another matching ${\mu }_2$ means that for every $f\in F$ we have that ${\mu }_1\left(f\right)R\left(f\right){\mu }_2\left(f\right)$ (that is, either ${\mu }_1\left(f\right)={\mu }_2\left(f\right)$ or else ${\mu }_1\left(f\right)P\left(f\right){\mu }_2\left(f\right)$ ).

We define the unanimous partial orders ${\succcurlyeq }_F$ and ${\succcurlyeq }_W$ in $\mathcal{M}\left(F\mathrm{,}W\mathrm{,}P\right)$ as follows:

${\mu }_1{\succcurlyeq }_F{\mu }_2\iff {\mu }_1\left(f\right)R\left(f\right){\mu }_2\left(f\right)$ for all $f\in F$

${\mu }_1{\succcurlyeq }_W{\mu }_2\iff {\mu }_1\left(w\right)R\left(w\right){\mu }_2\left(w\right)$ for all $w\in W$

We sometimes add superscripts and write, for example ${\succcurlyeq }_F^P$ o ${\succcurlyeq }_W^P$ to emphasize dependence on particular preferences.

Given a preference relation of a firm $P\left(f\right)$ the subsets of workers preferred to the empty set by f are called acceptable. Therefore, we are allowing that firm f may prefer not hiring any workers rather than hiring unacceptable subsets of workers. Similarly, given a preference relation of a $P\left(w\right)$ worker, the firms preferred by w to the empty set are called acceptable. In this case we are allowing that worker w may prefer to remain unemployed rather than working for an unacceptable firm. Given a $S\subseteq W$ set, let $Ch\left(S\mathrm{,}P\left(f\right)\right)$ denote firm f's most-preferred subset of S according to its preference ordering $P\left(f\right)$ and we refer to this set as choice.

A matching $\mu$ is blocked by a worker w if $\varnothing P\left(w\right)\mu \left(w\right)$ ; that is, worker w prefers being unemployed rather than working for firm $\mu \left(w\right)$. Similarly, $\mu$ is blocked by a firm f if $\mu \left(f\right)\ne Ch\left(\mu \left(f\right)\mathrm{,}P\left(f\right)\right)$. We say that a matching is individually rational if it is not blocked by any individual agent. A matching $\mu$ is blocked by a worker-firm pair $\left(w\mathrm{,}f\right)$ if $w\notin \mu \left(f\right)$, $w\in Ch\left(\mu \left(f\right)\cup \left\{w\right\}\mathrm{,}P\left(f\right)\right)$, and $fP\left(w\right)\mu \left(w\right)$ ; that is, if they are not matched through $\mu$, firm f wants to hire w, and worker w prefers firm f rather than firm $\mu \left(w\right)$.

Definition 2. A matching $\mu$ is stable if it is not blocked by any individual agent or any firm-worker pair.

We denote by $S\left(F\mathrm{,}W\mathrm{,}P\right)$ the set of stable matchings of market $\left(F\mathrm{,}W\mathrm{,}P\right)$. There are preference profiles in which the set of stable matchings is empty. These examples share the feature that at least one firm regards a subset of workers as complements. This is the reason why the literature has focused on the restriction where workers are regarded as substitutes. The objective of substitutability condition is to make the hiring of a worker independent of the hiring of other workers.⁵

Definition 3. A firm f’s preference relation $P\left(f\right)$ satisfies substitutability if for any set S containing workers w and $\bar{w}$ $\left(w\ne \bar{w}\right)$, if $w\in Ch\left(S\mathrm{,}P\left(f\right)\right)$ then $w\in Ch\left(S\backslash \left\{\bar{w}\right\}\mathrm{,}P\left(f\right)\right)$.

A preference profile $P$ is substitutable if for each firm f, the preference relation $P\left(f\right)$ satisfies substitutability. Kelso and Crawford in [9] shows that if all firms have substitutable preferences then the set of stable matchings is non-empty, and firms unanimously agree that a stable matching ${\mu }_F$ is the best stable matching. Roth in [10] extends these results and shows that if all firms have substitutable preferences then workers unanimously agree that a stable matching ${\mu }_W$ is the best stable matching, and the optimal stable matching for one side is the worst stable matching for the other side. That is, $S\left(F\mathrm{,}W\mathrm{,}P\right)\ne \varnothing$ ; and for all $\mu \in \left(F\mathrm{,}W\mathrm{,}P\right)$ we have that ${\mu }_F{\succcurlyeq }_F\mu {\succcurlyeq }_F{\mu }_W$ and ${\mu }_W{\succcurlyeq }_W\mu {\succcurlyeq }_W{\mu }_F$.

Blair in [1] defines the partial order ${\succcurlyeq }_F^B$ as follows: given the matchings ${\mu }_1$ and ${\mu }_2$, ${\mu }_1{\succcurlyeq }_F^B{\mu }_2\iff Ch\left({\mu }_1\left(f\right)\cup {\mu }_2\left(f\right)\mathrm{,}P\left(f\right)\right)={\mu }_1\left(f\right)$ for all $f\in F$.

In some cases, we add superscripts and write ${\succcurlyeq }_F^{P_B}$ to emphasize the dependence on a particular preference.

Blair in [1] showed that if firms have substitutable preferences the following theorem holds.

Theorem 4. Let $P$ be a profile of substitutable. Then ${\mu }_1{\succcurlyeq }_F^B{\mu }_2$ if and only if ${\mu }_2{\succcurlyeq }_W{\mu }_1$ for all ${\mu }_1\mathrm{,}{\mu }_2\in S\left(F\mathrm{,}W\mathrm{,}P\right)$.

We will assume that firms’ preferences satisfy a further restriction called q-separability.⁶ This is based on two ideas. First, separability, which says that the division between good workers ( $wP\left(f\right)\varnothing$ ) and bad workers ( $\varnothing P\left(f\right)w$ ) guides the ordering of subsets in the sense that adding a good worker leads to a better set, while adding a bad worker leads to a worse set. Second, each firm f has in addition a maximum number of positions to be filled: its quota $q_f$. This limitation may arise from, for example, technological, legal, or budgetary reasons.

Formally,

Definition 5. A firm f’s preference relation $P\left(f\right)$ is $q_f$ -separable if: 1) for all $S⊊W$ such that $\left|S\right|<q_f$ and $w\notin S$ we have that $\left(S\cup \left\{w\right\}\right)P\left(f\right)S$ if and only if $wP\left(f\right)\varnothing$, and 2) $\varnothing P\left(f\right)S$ for all S such that $\left|S\right|>q_f$.

We will denote by $q={\left(q_f\right)}_{f\in F}$ the list of quotas and we will say that a preference profile $P$ is q-separable if each $P\left(f\right)$ is $q_f$ -separable.

As we study the properties of firm quasi-stable matchings, it will be useful to recall the following properties of stable matchings. From now on we will assume that firms have q-separable and substitutable preferences. Martínez et al. in [11] establishes the fact that, under these assumptions, the set of stable matching has a lattice structure. Given matchings ${\mu }_1$ and ${\mu }_2$, only asking each worker to select the best firm matched with them through ${\mu }_1$ and ${\mu }_2$. In this way, we define the pointing function ${\mu }_1{\underset{\_}{\vee }}_W{\mu }_2$ on $F\cup W$ by:

${\mu }_1{\underset{\_}{\vee }}_W{\mu }_2\left(w\right)=\{\begin{array}{l}{\mu }_1\left(w\right)\text{if}{\mu }_1\left(w\right)P\left(w\right){\mu }_2\left(w\right)\\ {\mu }_2\left(w\right)\text{otherwise}\end{array}$

for all $w\in W$ and

${\mu }_1{\underset{\_}{\vee }}_W{\mu }_2\left(f\right)=\left\{w\mathrm{<mo>\; :\; </mo>}{\mu }_1{\underset{\_}{\vee }}_W{\mu }_2\left(w\right)=f\right\}$

for all $f\in F$.

Symmetrically, define the pointing function ${\mu }_1{\underset{\_}{\wedge }}_W{\mu }_2$ on $F\cup W$ by matching each worker with their worst firm and each firm with the corresponding set of workers that selected it, if any.

Theorem 6. Let $P$ be a profile of substitutable and q-separable preferences. Then, $\left(S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{,}{\succcurlyeq }_W\mathrm{,}\wedge \mathrm{,}\vee \right)$ is a lattice, where $\wedge ={\bar{\wedge }}_W$ and $\vee ={\underset{\_}{\vee }}_W$.

As a conclusion of the Theorem 6, Martínez, Massó, Neme y Oviedo in [11] stated the following corollary.

Corollary 1. Let $P$ be a substitutable and q-separable preference profile. Then $\left(S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{,}{\succcurlyeq }_F^B\mathrm{,}\wedge \mathrm{,}\vee \right)$ is a lattice, where $\wedge ={\underset{\_}{\vee }}_W$ and $\vee ={\bar{\wedge }}_W$.

The following theorem, which has been proved by Martnez et al. in [8], states that the number of workers assigned to a firm through stable matchings is the same; if the firm does not complete its quota under some stable matching, then it gets the same set of workers at any stable matching.

Theorem 7. Let $P$ be a profile of substitutable and q-separable preferences. Then, all pairs $\mu \mathrm{,}{\mu }^{\prime }\in S\left(F\mathrm{,}W\mathrm{,}P\right)$, and all $f\in F$ :

1) $\left|\mu \left(f\right)\right|=\left|{\mu }^{\prime }\left(f\right)\right|$.

2) If $\mu \left(f\right)<q_f$, then $\mu \left(f\right)={\mu }^{\prime }\left(f\right)$.

3. Worker Quasi-Stable Matching

The concept of quasi-stable matchings was introduced by Sotomayor in [7] when he presented a non-constructive proof of the existence of stable matchings. It was also analyzed by Blum, Roth and Rothblum in [2] in one-to-one matching models and extended to the many-to-one model by Cantala in [4].

When the disruption of stable matchings is due to entry workers or closure of firms, the resulting matching is worker quasi-stable. This condition means that blocking pairs can exist as long as, in order to satisfy such pairs, workers do not have to quit. Formally:

Definition 8. An matching $\mu$ is worker quasi-stable (WQS) if it is individually rational and for every pair $\left(w\mathrm{,}f\right)$ that blocks $\mu$, $\mu \left(w\right)=\varnothing$.

We denote $WQS\left(F\mathrm{,}W\mathrm{,}P\right)$ the set of worker quasi-stable matchings.

We next develop representations the outcome the restabilization process, for that purpose we need some further definitions.

Definition 9. Let ${\mu }^{\prime }$ be an arbitrary matching. A matching $\mu$ is ${\mu }^{\prime }$ -acceptable if $\mu {\succcurlyeq }_F^B{\mu }^{\prime }$ and for all $w\in W$, such that $\varnothing P\left(w\right)\mu \left(w\right)$ we have that $\mu \left(w\right)={\mu }^{\prime }\left(w\right)$.

Definition 10. Let ${\mu }^{\prime }$ be an arbitrary matching. A matching $\mu$ is ${\mu }^{\prime }$ -stable if it is ${\mu }^{\prime }$ -acceptable and for every blocking pair $\left(f\mathrm{,}w\right)$ for $\mu$, $\mu \left(w\right)={\mu }^{\prime }\left(w\right)\in F$.

We denote by $S\left({\mu }^{\prime }\mathrm{,}P\right)$ the set of ${\mu }^{\prime }$ -stable matching. The following lemma shows that any instability in a ${\mu }^{\prime }$ -stable matching $\mu$ is also present in ${\mu }^{\prime }$.

Lemma 11. Let ${\mu }^{\prime }$ be a arbitrary matching and let $\mu \in S\left({\mu }^{\prime }\mathrm{,}P\right)$. If $\left(w\mathrm{,}f\right)$ is a blocking pair for $\mu$, then $\left(w\mathrm{,}f\right)$ is a blocking pair for ${\mu }^{\prime }$.

Proof. Assume that $\left(w\mathrm{,}f\right)$ is a blocking pair for $\mu$, that is, $fP\left(w\right)\mu \left(w\right)$ and $w\in Ch\left(\mu \left(f\right)\cup w\mathrm{,}P\left(f\right)\right)$. Then by the ${\mu }^{\prime }$ -stability of $\mu$, $\mu \left(w\right)={\mu }^{\prime }\left(w\right)$. Hence, $fP\left(w\right)\mu \left(w\right)={\mu }^{\prime }\left(w\right)$. Further, by the ${\mu }^{\prime }$ -acceptability of $\mu$, $Ch\left(\mu \left(f\right)\cup {\mu }^{\prime }\left(f\right)\mathrm{,}P\left(f\right)\right)=\mu \left(f\right)$ ; hence,

$\begin{array}{l}w\in C{h}_f\left(\mu \left(f\right)\cup w,P\left(f\right)\right)=Ch\left(C{h}_f\left(\mu \left(f\right)\cup {\mu }^{\prime }\left(f\right),P\left(f\right)\right)\cup w,P\left(f\right)\right)\\ =Ch\left(\mu \left(f\right)\cup {\mu }^{\prime }\left(f\right)\cup w,P\left(f\right)\right).\end{array}$

By the substitutability condition $w\in Ch\left({\mu }^{\prime }\left(f\right)\cup w\mathrm{,}P\left(f\right)\right)$ and have that $\left(w\mathrm{,}f\right)$ is a blocking pair for ${\mu }^{\prime }$.

We start by characterizing stability with respect to worker quasi-stable matchings.

Lemma 12. Let ${\mu }^{\prime }\in WQS\left(F\mathrm{,}W\mathrm{,}P\right)$. Then $S\left({\mu }^{\prime }\mathrm{,}P\right)=\left\{\mu \in S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{<mo>\; :\; </mo>}\mu {\succcurlyeq }_F^B{\mu }^{\prime }\right\}$.

Proof. The inclusion $\left\{\mu \in S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{<mo>\; :\; </mo>}\mu {\succcurlyeq }_F^B{\mu }^{\prime }\right\}\subseteq S\left({\mu }^{\prime }\mathrm{,}P\right)$ is trivial. To see the reverse inclusion assume that $\mu$ is ${\mu }^{\prime }$ -stable and suppose that there exists $w\in W$ such that $\varnothing P\left(w\right)\mu \left(w\right)$. Then by the ${\mu }^{\prime }$ acceptability of $\mu$, $\varnothing P\left(w\right)\mu \left(w\right)={\mu }^{\prime }\left(w\right)$, in contradiction to the individually rational of ${\mu }^{\prime }$. So $\mu$ is individually rational for the workers. The ${\mu }^{\prime }$ acceptability of $\mu$ assures that $Ch\left(\mu \left(f\right)\cup {\mu }^{\prime }\left(f\right)\mathrm{,}P\left(f\right)\right)=\mu \left(f\right)$. So $\mu \left(f\right)R\left(f\right)A$, for all $A\subseteq \mu \left(f\right)$, then $Ch\left(\mu \left(f\right)\mathrm{,}P\left(f\right)\right)=\mu \left(f\right)$. Therefore $\mu$ is individually rational for the firms.

Finally, if $\left(f\mathrm{,}w\right)$ is blocking pair for $\mu$. Then by the ${\mu }^{\prime }$ -stability of $\mu$, $\mu \left(w\right)={\mu }^{\prime }\left(w\right)=f_1\in F$. Then by Lemma 11 $\left(f\mathrm{,}w\right)$ is a blocking pair of ${\mu }^{\prime }$, which contradicts that ${\mu }^{\prime }$ is worker quasi-stable. Therefore $\mu$ is a stable matching and $\mu {\succcurlyeq }_F^B{\mu }^{\prime }$, which completes the demonstration.

4. Acceptance Firing (AF) Algorithm

The algorithm (AF) was introduced by Cantala in [4] as a restabilization process of a stable matching disrupted by population changes. This simple dynamic restabilizes any stable matching disrupted by the entrance of workers or the closure of firms. Cantala showed that if the input of the AF algorithm is worker quasi-stable matching, so all the intermediate matchings along the algorithm; in particular, the output matching is stable.

In this section, we show a way to compute the outcome of the AF algorithm when the input belongs to the class of worker quasi-stable matchings.

We consider a market $\left(F\mathrm{,}W\mathrm{,}P\right)$ and a worker quasi-stable matching, that is, one that emerges from the disruption of a stable matching due to the entrance of workers or the closure of firms. New workers and workers previously matched to closing firms are the agents most seriously affected. At each iteration, such workers propose their favorite firm in $A_w^{i-1}$, the set of acceptable firms to which w has not been previously matched or has not yet made them an offer. Formally:

Input

Let $\left(F\mathrm{,}W\mathrm{,}P\right)$ be a model and $\mu$ be an matching.

Initialization

(a) We define ${\mu }^0\left(f\right)=Ch\left(\mu \left(f\right),P\left(f\right)\right)$ for all $f\in F$ and $i=1$.

(b) For all $w\in W$, let $A_w^0=\left\{f\in F\mathrm{<mo>\; :\; </mo>}fP\left(w\right)\varnothing \right\}\backslash {\mu }^0\left(w\right)$.

Main iteration

(1) If there is no $w\in W$ such that ${\mu }^{i-1}\left(w\right)=\varnothing$ and $A_w^{i-1}\ne \varnothing$, output will be ${\mu }^{i-1}$.

(2) All $w\in W$ such that ${\mu }^{i-1}\left(w\right)=\varnothing$ and $A_w^{i-1}\ne \varnothing$ make an offers to f, the most preferred firm of w in $A_w^{i-1}$. For all f, denote by $S_f^{i-1}$ the set of workers who made an offer to f.

(3) Define ${\mu }^i\left(f^{\prime }\right)=Ch\left({\mu }^{i-1}\left(f^{\prime }\right)\cup S_{f^{\prime }}^{i-1}\mathrm{,}P\left(f^{\prime }\right)\right)$ for all $f^{\prime }$ who received an offer ( $S_{f^{\prime }}^{i-1}\ne \varnothing$ ) and ${\mu }^i\left(f^{\prime }\right)={\mu }^{i-1}\left(f^{\prime }\right)$ for all $f^{\prime }$ who did not ( $S_{f^{\prime }}^{i-1}=\varnothing$ ).

(4) Set $A_w^i=A_w^{i-1}\backslash \left\{f\right\}$ for all w who made offer an offer ( ${\mu }^{i-1}\left(w\right)=\varnothing$ and $A_w^{i-1}\ne \varnothing$ ) and $A_{w^{\prime }}^i=A_{w^{\prime }}^{i-1}$ for all $w^{\prime }$ such that ${\mu }^{i-1}\left(w\right)\ne \varnothing$ and/or $A_w^{i-1}=\varnothing$.

(5) $i=i+1$, go to (1).

Cantala in [4] showed that the AF algorithm restabilizes any worker quasi-stable matching. Formally:

Theorem 13. Let $\left(F\mathrm{,}W\mathrm{,}P\right)$ be a matching market. If the input of the (AF) Algorithm is worker quasi-stable, so are all the intermediate matchings along the algorithm and in particular the output matching is stable.

To describe the result of the algorithm execution (AF) we need the following lemmas, which show properties of the algorithm result in terms of the preferences.

Lemma 14. Let ${\mu }^{\prime }$ be an arbitrary matching. Then $AF\left({\mu }^{\prime }\right){\succcurlyeq }_F^B{\mu }^{\prime }$.

Proof. Let ${\mu }^0={\mu }^{\prime }\mathrm{,}{\mu }_1\mathrm{,}\cdots \mathrm{,}{\mu }_k$ be the sequence of the different matchings generated by the application of the AF algorithm with input ${\mu }^{\prime }$. We will show by induction that ${\mu }^i{\succcurlyeq }_F^B{\mu }^{\prime }$.

For $i=0$ it is verified.

Suppose as an inductive hypothesis ${\mu }^{i-1}{\succcurlyeq }_F^B{\mu }^{\prime }$, it is i.e., $Ch\left({\mu }^{i-1}\left(f\right)\cup {\mu }^{\prime }\left(f\right)\mathrm{,}P\left(f\right)\right)={\mu }^{i-1}\left(f\right)$ for all $f\in F$.

Consider the matching ${\mu }^i$ and $f\in F$. By inductive hypothesis and properties of the choice set, we have that

$\begin{array}{c}{\mu }^i\left(f\right)=Ch\left({\mu }^{i-1}\left(f\right)\cup S_f^{i-1}\mathrm{,}P\left(f\right)\right)\\ =Ch\left(Ch\left({\mu }^{i-1}\left(f\right)\cup {\mu }^{\prime }\left(f\right)\mathrm{,}P\left(f\right)\right)\cup S_f^{i-1}\mathrm{,}P\left(f\right)\right)\\ =Ch\left({\mu }^{i-1}\left(f\right)\cup {\mu }^{\prime }\left(f\right)\cup S_f^{i-1}\mathrm{,}P\left(f\right)\right).\end{array}$

Therefore,

${\mu }^i\left(f\right)=Ch\left({\mu }^{i-1}\left(f\right)\cup {\mu }^{\prime }\left(f\right)\cup S_f^{i-1}\mathrm{,}P\left(f\right)\right)$ (5)

Then ${\mu }^{k+1}\left(f\right)\cup {\mu }^{\prime }\left(f\right)=Ch\left({\mu }^k\left(f\right)\cup {\mu }^{\prime }\left(f\right)\cup S_f^k\mathrm{,}P\left(f\right)\right)\cup {\mu }^{\prime }\left(f\right)$. From (1) and properties of the choice set we have that

$\begin{array}{l}Ch\left({\mu }^i\left(f\right)\cup {\mu }^{\prime }\left(f\right),P\left(f\right)\right)\\ =Ch\left(Ch\left({\mu }^{i-1}\left(f\right)\cup {\mu }^{\prime }\left(f\right)\cup S_f^{i-1},P\left(f\right)\right)\cup {\mu }^{\prime }\left(f\right),P\left(f\right)\right)\end{array}$ $=Ch\left({\mu }^{i-1}\left(f\right)\cup {\mu }^{\prime }\left(f\right)\cup S_f^{i-1},P\left(f\right)\right)={\mu }^i\left(f\right)$. Then ${\mu }^i{\succcurlyeq }_F^B{\mu }^{\prime }$.

Lemma 15. Let ${\mu }^0={\mu }^{\prime },{\mu }_1,\cdots ,{\mu }_k$ be the sequence of matchings generated by the application of the AF algorithm with input ${\mu }^{\prime }$. Then ${\mu }^i{\succcurlyeq }_F^B{\mu }^{i-1}$ for $i=0,\cdots ,k$.

Proof. Let $f\in F$. If f receives a bid in step (2) of the iteration in which ${\mu }^i$ was generated, then

$\begin{array}{l}Ch\left({\mu }^i\left(f\right)\cup {\mu }^{i-1}\left(f\right),P\left(f\right)\right)\\ =Ch\left(Ch\left({\mu }^{i-1}\left(f\right)\cup S_f^{i-1},P\left(f\right)\right)\cup {\mu }^{i-1}\left(f\right),P\left(f\right)\right)\\ =Ch\left({\mu }^{i-1}\left(f\right)\cup S_f^{i-1},P\left(f\right)\right)={\mu }^i\left(f\right).\end{array}$

Then iff does not receive an offer in step (2) of the iteration in which ${\mu }^i$ was generated, then ${\mu }^i\left(f\right)={\mu }^{i-1}\left(f\right)$. Then ${\mu }^i{\succcurlyeq }_F^B{\mu }^{i-1}$.

Lemma 16. Let ${\mu }^i$ be an arbitrary matching. Then $AF\left({\mu }^{\prime }\right)$ is ${\mu }^{\prime }$ -stable.

Proof. Let $\mu =AF\left({\mu }^{\prime }\right)$. We first show that $\mu$ is ${\mu }^{\prime }$ -acceptable. By Lemma 14 $\mu {\succcurlyeq }_F^B{\mu }^{\prime }$. Let $w\in W$, such that $\varnothing P\left(w\right)\mu \left(w\right)$ and suppose that $\mu \left(w\right)\ne {\mu }^{\prime }\left(w\right)$. Then w made bids during the execution of the algorithm. Then since w only bids to acceptable firms $\mu \left(w\right)R\left(w\right)\varnothing$, which contradicts the assumption. Therefore $\mu \left(w\right)={\mu }^{\prime }\left(w\right)$. Then $\mu$ es ${\mu }^{\prime }$ -acceptable.

Let $\left(f\mathrm{,}w\right)$ be a blocking pair for $\mu$, then $fP\left(w\right)\mu \left(w\right)$ and $w\in C{h}_f\left(\mu \left(f\right)\cup w\mathrm{,}P\left(f\right)\right)$. Suppose w made bids during the execution of the algorithm. Then $\mu \left(w\right)R\left(w\right)\varnothing$, since all his bids were rejected or he is assigned to an acceptable bid. Then as $fP\left(w\right)\mu \left(w\right)R\left(w\right)\varnothing$, then $f\in A_w^0$ o ${\mu }^{\prime }\left(w\right)=f$. In both cases, as $fP\left(w\right)\mu \left(w\right)$, f rejected w at some step k of the algorithm. Then $w\notin Ch\left({\mu }^k\left(f\right)\cup w\mathrm{,}P\left(f\right)\right)$. On the other hand, since $w\in Ch\left(\mu \left(f\right)\cup w\mathrm{,}P\left(f\right)\right)$ by Lemma 15 we have that

$\begin{array}{c}w\in Ch\left(Ch\left({\mu }^k\left(f\right)\cup \mu \left(f\right),P\left(f\right)\right)\cup w,P\left(f\right)\right)\\ =Ch\left({\mu }^k\left(f\right)\cup \mu \left(f\right)\cup w,P\left(f\right)\right).\end{array}$

By the substitutability condition $w\in Ch\left({\mu }^k\left(f\right)\cup w\right)$, which is a contradiction.

Lemma 17. If ${\mu }^{\mathrm{<mo>\; *\; </mo>}}$ is a ${\mu }^{\prime }$ -stable matching, then ${\mu }^{\mathrm{<mo>\; *\; </mo>}}{\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)$.

Proof. Let ${\mu }^0={\mu }^{\prime },{\mu }^1,\cdots ,{\mu }^k$ be the matchings generated during the execution. of the AF algorithm with input ${\mu }^{\prime }$. We show by induction that ${\mu }^{\mathrm{<mo>\; *\; </mo>}}{\succcurlyeq }_F^B{\mu }^i$, $i=0,\cdots ,k$.

For ${\mu }^{\mathrm{<mo>\; *\; </mo>}}{\succcurlyeq }_F^B{\mu }^{\prime }$, since ${\mu }^{\mathrm{<mo>\; *\; </mo>}}$ is ${\mu }^{\prime }$ -acceptable. Suppose that ${\mu }^{\mathrm{<mo>\; *\; </mo>}}{\succcurlyeq }_F^B{\mu }^{i-1}$ and let ${\mu }^{\mathrm{<mo>\; *\; </mo>}}{\cancel{\succcurlyeq }}_F^B{\mu }^i$. Then there exists $f\in F$ such that $Ch\left({\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)\cup {\mu }^i\left(f\right)\mathrm{,}P\left(f\right)\right)\ne {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)$. If $Ch\left({\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)\cup {\mu }^i\left(f\right)\mathrm{,}P\left(f\right)\right)=A$ with $A\subset {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)$, by Lemma 15

$\begin{array}{c}A=Ch\left({\mu }^{*}\left(f\right)\cup Ch\left({\mu }^i\left(f\right)\cup {\mu }^{i-1}\left(f\right),P\left(f\right)\right),P\left(f\right)\right)\\ =Ch({\mu }^{*}\left(f\right)\cup {\mu }^i\left(f\right)\cup {\mu }^{i-1}\left(f\right),P(\; f\; ))\end{array}$

(where the last equality follows by properties of the choice set).

Then $AP\left(f\right)B$ for all $B\subseteq {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)\cup {\mu }^{i-1}\left(f\right)$, then $Ch\left({\mu }^{*}\left(f\right)\cup {\mu }^{i-1}\left(f\right),P\left(f\right)\right)=A\ne {\mu }^{*}\left(f\right)$, which contradicts that ${\mu }^{\mathrm{<mo>\; *\; </mo>}}{\succcurlyeq }_F^B{\mu }^{i-1}$ (our inductive hypothesis). Therefore there exists $w\in {\mu }^i\left(f\right)\backslash {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)$ such that $w\in Ch\left({\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)\cup {\mu }^i\left(f\right)\mathrm{,}P\left(f\right)\right)$. By the substitutability condition

$w\in Ch\left({\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)\cup w\mathrm{,}P\left(f\right)\right)$, (6)

then there exists $S\subseteq {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)$ such that $S\cup wR\left(f\right){\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)$. Suppose $w\in {\mu }^{i-1}\left(f\right)$, then there exists $S\cup w\subseteq {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)\cup {\mu }^{i-1}\left(f\right)$ such that $S\cup wR\left(f\right){\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)$, which contradicts that $Ch\left({\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)\cup {\mu }^{i-1}\left(f\right)\mathrm{,}P\left(f\right)\right)={\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f\right)$ (our inductive hypothesis). Therefore $w\notin {\mu }^{i-1}\left(f\right)$, from this, it follows that

$f\in A_w^{i-1}$ y ${\mu }^{i-1}\left(w\right)=w$ (7)

Suppose that $fP\left(w\right){\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(w\right)$, then from (6) we have that $\left(f\mathrm{,}w\right)$ block a ${\mu }^{\mathrm{<mo>\; *\; </mo>}}$. Then since ${\mu }^{\prime }$ -stable ${\mu }^{*}\left(w\right)={\mu }^{\prime }\left(w\right)=f_1\in F$. By inductive hypothesis and the property that ${\mu }^{i-1}{\succcurlyeq }_F^B{\mu }^{\prime }$ (established in the proof of Lemma 14) we have that

$\begin{array}{c}w\in {\mu }^{*}\left(f_1\right)=Ch\left({\mu }^{*}\left(f_1\right)\cup {\mu }^{i-1}\left(f_1\right),P\left(f_1\right)\right)\\ =Ch\left({\mu }^{*}\left(f_1\right)\cup Ch\left({\mu }^{i-1}\left(f_1\right)\cup {\mu }^{\prime }\left(f_1\right),P\left(f_1\right)\right),P\left(f_1\right)\right)\\ =Ch\left({\mu }^{*}\left(f_1\right)\cup {\mu }^{i-1}\left(f_1\right)\cup {\mu }^{\prime }\left(f_1\right),P\left(f_1\right)\right).\end{array}$ Then by the substitutability condition $w\in Ch\left({\mu }^{i-1}\left(f_1\right)\cup {\mu }^{\prime }\left(f_1\right)\mathrm{,}P\left(f_1\right)\right)={\mu }^{i-1}\left(f_1\right)$, since $w\in {\mu }^{\prime }\left(f_1\right)$. Therefore

${\mu }^{i-1}\left(w\right)=f_1$ (8)

Then (7) and (8) contradict each other, so ${\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(w\right)R\left(w\right)f$.

Now since w makes an offer to a f at iteration i of the algorithm, then ${\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(w\right)R\left(w\right)fP\left(w\right){\mu }^{i-1}\left(w\right)=\varnothing$. Therefore ${\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(w\right)=f^{\mathrm{<mo>\; *\; </mo>}}\in F$. Then since $\left(f\mathrm{,}w\right)$ is a maximal blocking pair for ${\mu }^{i-1}$, then $w\notin Ch\left({\mu }^{i-1}\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)\cup w\mathrm{,}P\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)\right)$ by the substitutability condition $w\notin Ch\left({\mu }^{i-1}\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)\cup {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}P\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)\right)$. Then $Ch\left({\mu }^{i-1}\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)\cup {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}P\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)\right)\ne {\mu }^{\mathrm{<mo>\; *\; </mo>}}\left(f^{\mathrm{<mo>\; *\; </mo>}}\right)$ which contradicts that ${\mu }^{\mathrm{<mo>\; *\; </mo>}}{\succcurlyeq }_F^B{\mu }^{i-1}$.

The following theorem shows that the result of the execution of the algorithm (AF) with input ${\mu }^{\prime }$, is the worst matching for the firms (according to Blair's order) in $S\left({\mu }^{\prime }\mathrm{,}P\right)$.

Theorem 18. Let ${\mu }^{\prime }$ be an arbitrary matching. Then $AF\left({\mu }^{\prime }\right)\in S\left({\mu }^{\prime }\mathrm{,}P\right)$ and $\mu {\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)$ for all $\mu \in S\left({\mu }^{\prime }\mathrm{,}P\right)$.

Proof. It follows from Lemmas 16 and 17.

Given an matching ${\mu }^{\prime }$, we define the set of stable matchings that firms weakly prefer to ${\mu }^{\prime }$, $S_F\left({\mu }^{\prime }\right)$, i.e.

$S_F\left({\mu }^{\prime }\right)=\left\{\mu \in S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{<mo>\; :\; </mo>}\mu {\succcurlyeq }_F^B{\mu }^{\prime }\right\}\mathrm{.}$

In Lemma 12 we show that if ${\mu }^{\prime }$ is a worker quasi-stable matching, then $S_F\left({\mu }^{\prime }\right)=S\left({\mu }^{\prime }\mathrm{,}P\right)$.

We show in the following two lemmas that if ${\mu }^{\prime }$ is a worker quasi-stable matching, then $S_F\left({\mu }^{\prime }\right)$ is a nonempty sub-lattice of $S\left(F\mathrm{,}W\mathrm{,}P\right)$ under partial order ${\succcurlyeq }_F^B$.

Lemma 19. Let ${\mu }^{\prime }$ be an arbitrary matching. Then $S_F\left({\mu }^{\prime }\right)=\left\{\mu \in S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{<mo>\; :\; </mo>}\mu {\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)\right\}$.

Proof. Let $\mu \in S_F\left({\mu }^{\prime }\right)$ then $\mu {\succcurlyeq }_F^B{\mu }^{\prime }$, by Lemma 17 $\mu {\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)$. Therefore $\mu \in \left\{\mu \in S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{<mo>\; :\; </mo>}\mu {\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)\right\}$. In the other direction, let $\mu \in S\left(F\mathrm{,}W\mathrm{,}P\right)$ such that $\mu {\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)$. By Lemma 14 $AF\left({\mu }^{\prime }\right){\succcurlyeq }_F^B{\mu }^{\prime }$, hence $\mu {\succcurlyeq }_F^B{\mu }^{\prime }$.

Lemma 20. Let ${\mu }^{\prime }$ be a worker quasi-stable matching. Then $S_F\left({\mu }^{\prime }\right)=\left\{\mu \in S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{<mo>\; :\; </mo>}\mu {\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)\right\}$ is a non-empty sub-lattice of $\left(S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{,}{\succcurlyeq }_F^B\right)$.

Proof. Let ${\mu }^{\prime }$ be a worker quasi-stable matching. Then by theorem 13 $AF\left({\mu }^{\prime }\right)$ is stable and by Lemma 19 $S_F\left({\mu }^{\prime }\right)\ne \varnothing$.

Let ${\mu }_1\mathrm{,}{\mu }_2\in S_F\left({\mu }^{\prime }\right)$, by Corollary 1 ${\mu }_1\vee {\mu }_2={\mu }_1{\bar{\wedge }}_W{\mu }_2$, ${\mu }_1\wedge {\mu }_2={\mu }_1{\underset{\_}{\vee }}_W{\mu }_2\in S\left(F\mathrm{,}W\mathrm{,}P\right)$. Since ${\mu }_1\mathrm{,}{\mu }_2{\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)$, the theorems 4 and 13 imply that $AF\left({\mu }^{\prime }\right){\succcurlyeq }_W{\mu }_1\mathrm{,}{\mu }_2$, then $AF\left({\mu }^{\prime }\right){\succcurlyeq }_W{\mu }_1{\underset{\_}{\vee }}_W{\mu }_2={\mu }_1\wedge {\mu }_2$ and $AF\left({\mu }^{\prime }\right){\succcurlyeq }_W{\mu }_1{\bar{\wedge }}_W{\mu }_2={\mu }_1\vee {\mu }_2$. By the theorem 4 ${\mu }_1\wedge {\mu }_2{\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)$ and ${\mu }_1\vee {\mu }_2{\succcurlyeq }_F^{B}AF\left({\mu }^{\prime }\right)$, then ${\mu }_1\wedge {\mu }_2\in S_F\left({\mu }^{\prime }\right)$ and ${\mu }_1\vee {\mu }_2\in S_F\left({\mu }^{\prime }\right)$. Therefore $S_F\left({\mu }^{\prime }\right)$ with $\wedge$, $\vee$ is a sub-lattice of $S\left(F\mathrm{,}W\mathrm{,}P\right)$.

We are going to describe the result of the algorithm execution when the input is a worker quasi-stable matching. Since $S_F\left({\mu }^{\prime }\right)$ is a non-empty sub-lattice of $\left(S\left(F\mathrm{,}W\mathrm{,}P\right)\mathrm{,}{\succ }_F^B\right)$, it contains the matching $\wedge S_F\left({\mu }^{\prime }\right)$. The matching $\wedge S_F\left({\mu }^{\prime }\right)$ is the worst stable matching for the firms in the sub-lattice $S_F\left({\mu }^{\prime }\right)$. We show below that this matching is the result of running the AF algorithm with input ${\mu }^{\prime }$.

Theorem 21. Let ${\mu }^{\prime }$ be a worker quasi-stable matching $\left(F\mathrm{,}W\mathrm{,}P\right)$. Then $AF\left({\mu }^{\prime }\right)=\wedge S_F\left({\mu }^{\prime }\right)$ .

Proof. The proof follows from theorem 18 and Lemmas 12 and 20.

NOTES

¹Using a partial order first studied by Blair in [1].

²Firm quasi-stability is a relaxation of stability that allows blocking pairs involving a worker and an empty position of a firm.

³They use the term envy-free matchings to generalize the “simple” matchings studied by Sotomayor in [7] and the “firm quasi-stable” matchings studied by Blum et al. in [2].

⁴We will often abuse notation by omitting the brackets to denote a set with a unique element. For instance here, we write $\mu \left(w\right)=f$ instead of $\mu \left(w\right)=\left\{f\right\}$.

⁵Kelso and Crawford in [9] were the first to use this property (under the name of “gross substitutability condition”) in a cardinal matching model with salaries.

⁶See Martnez et al. in [8] [11] for a detailed discussion of this restriction.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Blair, C. (1988) The Lattice Structure of the Set of Stable Matchings with Multiple Partners. Mathematics of Operations Research, 13, 619-628. https://doi.org/10.1287/moor.13.4.619
[2]	Blum, Y., Roth, A.E. and Rothblum, U.G. (1997) Vacancy Chains and Equilibration in Senior-Level Labor Markets. Journal of Economic Theory, 76, 362-411. https://doi.org/10.1006/jeth.1997.2307
[3]	Gale, D. and Shapley, L. (1962) Collage Admissions and Stability of Marriage. The American Mathematical Monthly, 69, 9-15. https://doi.org/10.1080/00029890.1962.11989827
[4]	Cantala, D. (2004) Restabilizing Matching Markets at Senior Level. Games and Economic Behavior, 48, 1-17. https://doi.org/10.1016/j.geb.2003.07.005
[5]	Cantala, D. (2011) Agreement toward Stability in Matching Markets. Review of Economic Design, 15, 293-316. https://doi.org/10.1007/s10058-009-0098-3
[6]	Wu, Q.Y. and Roth, A.E. (2018) The Lattice of Envy-Free Matchings. Games and Economic Behavior, 109, 201-211. https://doi.org/10.1016/j.geb.2017.12.016
[7]	Sotomayor M. (1996) A Non-Constructive Elementary Proof of the Existence of Stable Marriages. Games and Economic Behavior, 13, 135-137. https://doi.org/10.1006/game.1996.0029
[8]	Martnez R. and Massó J. and Neme A. and Oviedo J. (2000) Single Agents and the Set of Many-to-One Stable Matchings. Journal of Economic Theory, 91, 91-105. https://doi.org/10.1006/jeth.1999.2586
[9]	Kelso, A.S. and Crawford, V.P. (1982) Job Matching, Coalition Formation, and Gross Substitutes. Econometrica, 50, 1483-1504. https://doi.org/10.2307/1913392
[10]	Roth, A. (1984) Stability and Polarization of Interests in Job Matching. Econometrica, 52, 47-57. https://doi.org/10.2307/1911460
[11]	Martnez, R. and Massó, J. and Neme, A. and Oviedo, J. (2001) On the Lattice Structure of the Set of Stable Matchings for a Many-to-One Model. Optimization, 50, 439-457. https://doi.org/10.1080/02331930108844574