Restabilization Process in Matching Markets with Workers Proposing ()
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 structure1 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.2
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.3
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
has a strict, transitive, and complete preference relation
over the set of all of W subsets, and each worker has a strict, transitive, and complete preference relation
over
. Preferences profiles are
-tuples of preference relations and they are represented by
. Given a
preference profile, then the many-to-one bilateral matching market is the triplet
.
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
is a mapping from the set
into the set of all subsets of
such that for all
and
:
1) Either
and
or else
.
2)
.
3)
if and only if
.4
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.
denotes all of the possible matchings in
.
We are following the convention of extending preferences from the original sets (
and
) 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
and
. For instance, to say that all firms prefer
to another matching
means that for every
we have that
(that is, either
or else
).
We define the unanimous partial orders
and
in
as follows:
for all
for all
We sometimes add superscripts and write, for example
o
to emphasize dependence on particular preferences.
Given a preference relation of a firm
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
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
set, let
denote firm f's most-preferred subset of S according to its preference ordering
and we refer to this set as choice.
A matching
is blocked by a worker w if
; that is, worker w prefers being unemployed rather than working for firm
. Similarly,
is blocked by a firm f if
. We say that a matching is individually rational if it is not blocked by any individual agent. A matching
is blocked by a worker-firm pair
if
,
, and
; that is, if they are not matched through
, firm f wants to hire w, and worker w prefers firm f rather than firm
.
Definition 2. A matching
is stable if it is not blocked by any individual agent or any firm-worker pair.
We denote by
the set of stable matchings of market
. 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.5
Definition 3. A firm f’s preference relation
satisfies substitutability if for any set S containing workers w and
, if
then
.
A preference profile
is substitutable if for each firm f, the preference relation
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
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
is the best stable matching, and the optimal stable matching for one side is the worst stable matching for the other side. That is,
; and for all
we have that
and
.
Blair in [1] defines the partial order
as follows: given the matchings
and
,
for all
.
In some cases, we add superscripts and write
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
be a profile of substitutable. Then
if and only if
for all
.
We will assume that firms’ preferences satisfy a further restriction called q-separability.6 This is based on two ideas. First, separability, which says that the division between good workers (
) and bad workers (
) 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
. This limitation may arise from, for example, technological, legal, or budgetary reasons.
Formally,
Definition 5. A firm f’s preference relation
is
-separable if: 1) for all
such that
and
we have that
if and only if
, and 2)
for all S such that
.
We will denote by
the list of quotas and we will say that a preference profile
is q-separable if each
is
-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
and
, only asking each worker to select the best firm matched with them through
and
. In this way, we define the pointing function
on
by:
for all
and
for all
.
Symmetrically, define the pointing function
on
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
be a profile of substitutable and q-separable preferences. Then,
is a lattice, where
and
.
As a conclusion of the Theorem 6, Martínez, Massó, Neme y Oviedo in [11] stated the following corollary.
Corollary 1. Let
be a substitutable and q-separable preference profile. Then
is a lattice, where
and
.
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
be a profile of substitutable and q-separable preferences. Then, all pairs
, and all
:
1)
.
2) If
, then
.
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
is worker quasi-stable (WQS) if it is individually rational and for every pair
that blocks
,
.
We denote
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
be an arbitrary matching. A matching
is
-acceptable if
and for all
, such that
we have that
.
Definition 10. Let
be an arbitrary matching. A matching
is
-stable if it is
-acceptable and for every blocking pair
for
,
.
We denote by
the set of
-stable matching. The following lemma shows that any instability in a
-stable matching
is also present in
.
Lemma 11. Let
be a arbitrary matching and let
. If
is a blocking pair for
, then
is a blocking pair for
.
Proof. Assume that
is a blocking pair for
, that is,
and
. Then by the
-stability of
,
. Hence,
. Further, by the
-acceptability of
,
; hence,
By the substitutability condition
and have that
is a blocking pair for
.
We start by characterizing stability with respect to worker quasi-stable matchings.
Lemma 12. Let
. Then
.
Proof. The inclusion
is trivial. To see the reverse inclusion assume that
is
-stable and suppose that there exists
such that
. Then by the
acceptability of
,
, in contradiction to the individually rational of
. So
is individually rational for the workers. The
acceptability of
assures that
. So
, for all
, then
. Therefore
is individually rational for the firms.
Finally, if
is blocking pair for
. Then by the
-stability of
,
. Then by Lemma 11
is a blocking pair of
, which contradicts that
is worker quasi-stable. Therefore
is a stable matching and
, 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
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
, the set of acceptable firms to which w has not been previously matched or has not yet made them an offer. Formally:
Input
Let
be a model and
be an matching.
Initialization
(a) We define
for all
and
.
(b) For all
, let
.
Main iteration
(1) If there is no
such that
and
, output will be
.
(2) All
such that
and
make an offers to f, the most preferred firm of w in
. For all f, denote by
the set of workers who made an offer to f.
(3) Define
for all
who received an offer (
) and
for all
who did not (
).
(4) Set
for all w who made offer an offer (
and
) and
for all
such that
and/or
.
(5)
, go to (1).
Cantala in [4] showed that the AF algorithm restabilizes any worker quasi-stable matching. Formally:
Theorem 13. Let
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
be an arbitrary matching. Then
.
Proof. Let
be the sequence of the different matchings generated by the application of the AF algorithm with input
. We will show by induction that
.
For
it is verified.
Suppose as an inductive hypothesis
, it is i.e.,
for all
.
Consider the matching
and
. By inductive hypothesis and properties of the choice set, we have that
Therefore,
(5)
Then
. From (1) and properties of the choice set we have that
. Then
.
Lemma 15. Let
be the sequence of matchings generated by the application of the AF algorithm with input
. Then
for
.
Proof. Let
. If f receives a bid in step (2) of the iteration in which
was generated, then
Then iff does not receive an offer in step (2) of the iteration in which
was generated, then
. Then
.
Lemma 16. Let
be an arbitrary matching. Then
is
-stable.
Proof. Let
. We first show that
is
-acceptable. By Lemma 14
. Let
, such that
and suppose that
. Then w made bids during the execution of the algorithm. Then since w only bids to acceptable firms
, which contradicts the assumption. Therefore
. Then
es
-acceptable.
Let
be a blocking pair for
, then
and
. Suppose w made bids during the execution of the algorithm. Then
, since all his bids were rejected or he is assigned to an acceptable bid. Then as
, then
o
. In both cases, as
, f rejected w at some step k of the algorithm. Then
. On the other hand, since
by Lemma 15 we have that
By the substitutability condition
, which is a contradiction.
Lemma 17. If
is a
-stable matching, then
.
Proof. Let
be the matchings generated during the execution. of the AF algorithm with input
. We show by induction that
,
.
For
, since
is
-acceptable. Suppose that
and let
. Then there exists
such that
. If
with
, by Lemma 15
(where the last equality follows by properties of the choice set).
Then
for all
, then
, which contradicts that
(our inductive hypothesis). Therefore there exists
such that
. By the substitutability condition
, (6)
then there exists
such that
. Suppose
, then there exists
such that
, which contradicts that
(our inductive hypothesis). Therefore
, from this, it follows that
y
(7)
Suppose that
, then from (6) we have that
block a
. Then since
-stable
. By inductive hypothesis and the property that
(established in the proof of Lemma 14) we have that
Then by the substitutability condition
, since
. Therefore
(8)
Then (7) and (8) contradict each other, so
.
Now since w makes an offer to a f at iteration i of the algorithm, then
. Therefore
. Then since
is a maximal blocking pair for
, then
by the substitutability condition
. Then
which contradicts that
.
The following theorem shows that the result of the execution of the algorithm (AF) with input
, is the worst matching for the firms (according to Blair's order) in
.
Theorem 18. Let
be an arbitrary matching. Then
and
for all
.
Proof. It follows from Lemmas 16 and 17.
Given an matching
, we define the set of stable matchings that firms weakly prefer to
,
, i.e.
In Lemma 12 we show that if
is a worker quasi-stable matching, then
.
We show in the following two lemmas that if
is a worker quasi-stable matching, then
is a nonempty sub-lattice of
under partial order
.
Lemma 19. Let
be an arbitrary matching. Then
.
Proof. Let
then
, by Lemma 17
. Therefore
. In the other direction, let
such that
. By Lemma 14
, hence
.
Lemma 20. Let
be a worker quasi-stable matching. Then
is a non-empty sub-lattice of
.
Proof. Let
be a worker quasi-stable matching. Then by theorem 13
is stable and by Lemma 19
.
Let
, by Corollary 1
,
. Since
, the theorems 4 and 13 imply that
, then
and
. By the theorem 4
and
, then
and
. Therefore
with
,
is a sub-lattice of
.
We are going to describe the result of the algorithm execution when the input is a worker quasi-stable matching. Since
is a non-empty sub-lattice of
, it contains the matching
. The matching
is the worst stable matching for the firms in the sub-lattice
. We show below that this matching is the result of running the AF algorithm with input
.
Theorem 21. Let
be a worker quasi-stable matching
. Then
.
Proof. The proof follows from theorem 18 and Lemmas 12 and 20.
NOTES
1Using a partial order first studied by Blair in [1].
2Firm quasi-stability is a relaxation of stability that allows blocking pairs involving a worker and an empty position of a firm.
3They 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].
4We will often abuse notation by omitting the brackets to denote a set with a unique element. For instance here, we write
instead of
.
5Kelso 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.
6See Martnez et al. in [8] [11] for a detailed discussion of this restriction.