# The common envelope origins of the fast jet in the planetary nebula M 3-38

J. S. Rechy-García Instituto de Radioastronomía y Astrofísica, UNAM, Antigua
Carretera a Pátzcuaro 8701, Ex-Hda. San José de la Huerta, Morelia 58089,
Mich., Mexico  J. A. Toalá Visiting astronomer at the Instituto de Astrofísica
de Andalucía (IAA-CSIS, Spain) as part of the Centro de Excelencia Severo
Ochoa Visiting-Incoming programme.  Instituto de Radioastronomía y
Astrofísica, UNAM, Antigua Carretera a Pátzcuaro 8701, Ex-Hda. San José de la
Huerta, Morelia 58089, Mich., Mexico  M. A. Guerrero Instituto de Astrofísica
de Andalucía, IAA-CSIC, Glorieta de la Astronomía S/N, E-18008 Granada, Spain
C. Rodríguez-López Instituto de Astrofísica de Andalucía, IAA-CSIC, Glorieta
de la Astronomía S/N, E-18008 Granada, Spain  L. Sabin Instituto de
Astronomía, UNAM, Apdo. Postal 877, Ensenada 22860, B.C., Mexico  G. Ramos-
Larios Instituto de Astronomía y Meteorología, CUCEI, Universidad de
Guadalajara, Av. Vallarta 2602, Arcos Vallarta, 44130 Guadalajara, Mexico

([)

###### Abstract

We present the analysis of Multi-Espectrógrafo en GTC de Alta Resolución para
Astronomía (MEGARA) high-dispersion integral field spectroscopic observations
of the bipolar planetary nebula (PN) M 3-38. These observations unveil the
presence of a fast outflow aligned with the symmetry axis of M 3-38 that
expands with a velocity up to $\pm$225 km s-1. The deprojected space velocity
of this feature can be estimated to be $\approx$320${}^{+130}_{-60}$ km s-1,
which together with its highly collimated morphology suggests that it is one
of the fastest jet detected in a PN. We have also used Kepler observations of
the central star of M 3-38 to unveil variability associated with a dominant
period of 17.7 days. We attribute this to the presence of a low-mass star with
an orbital separation of $\approx$0.12–0.16 au. The fast and collimated
ejection and the close binary system point towards a common envelope formation
scenario for M 3-38.

Planetary nebulae (1249); Stellar jets (1607); Stellar winds (1636); Low mass
stars(2050)

††software: megararss2cube††facilities: Gran Telescopio Canarias (MEGARA),
Kepler/K2, HST (WFPC2)

]Submitted to ApJL

##  1 Introduction

Planetary nebulae (PNe) are formed by mass lost by solar-like stars on their
way of becoming white dwarfs, mostly during the asymptotic giant branch (AGB)
phase (Vassiliadis & Wood, 1993). The resultant stellar remnant becomes hot
enough to produce a high UV flux and fast stellar wind that ionizes and
compresses the material ejected in the late AGB phase, giving birth to a PN
(Kwok, 2000).

It has long been suggested that this generalized interacting stellar winds
model of PN formation (Balick, 1987) is too simple to explain the wild variety
of PN morphologies (e.g., Schwarz et al., 1992; Manchado et al., 1996).
Several mechanisms were soon invoked to explain this conundrum (Soker, 1997),
involving binary star interactions, including jet-like ejections during the
late AGB or early post-AGB phases (Sahai & Trauger, 1998).

Jets or bipolar fast outflows have been known to exist in PNe for a long time
since the first discovery in NGC 2392 (Gieseking et al., 1985). The
statistical analysis of a sample of 85 collimated outflows detected in 58 PNe
(Guerrero et al., 2020, and references therein) found a bimodal distribution,
with $\approx$30% of collimated outflows showing velocities $\geq$100 km s-1.
These high-velocity jets are prime candidates to have been launched by a
binary system at the core of the PN.

The presence of fast collimated outflows can be gleaned by observing images of
PNe as their action is typically associated with highly-elongated structures,
S-shaped filaments and V-shaped structures (Rechy-García et al., 2020a).
Complementary kinematical information has been traditionally obtained using
long-slit high-dispersion spectroscopic observations, which is otherwise the
only method to detect fast collimated outflows in compact PNe (Rechy-García et
al., 2017). The advent of high-dispersion integral field spectroscopy provides
kinematical information with broad spatial coverage. This technique has
allowed, for instance, to map for the first time the extension of the
extremely faint bipolar jet in NGC 2392 (Guerrero et al., 2021), to dissect
the abundances and kinematics of the born-again PN HuBi 1 (Rechy-García et
al., 2020b; Montoro-Molina et al., 2022) and the spatio-kinematical structure
of M 2-31 (Rechy-García et al., 2021).

Figure 1: GTC MEGARA tomography of the M 3-38 in the [N ii] $\lambda$6584
emission line. The Local Standard Rest velocity range is labeled at the
bottom-left corner of each panel. The central frame corresponds to the
systemic velocity. The red “cross” indicates the location of the CSPN of M
3-38, as determined from the emission of the stellar continuum, which is
consistent with the central position of the nebular waist. North is up, east
is to the left.

In this letter, we present the discovery of one of the fastest collimated
outflows in a PN. We use Multi-Espectrógrafo en GTC de Alta Resolución para
Astronomía (MEGARA; Gil de Paz et al., 2018) observations obtained at the Gran
Telescopio Canarias (GTC) of the PN M 3-38 (PN G356.9$+$04.4) to unveil its
extreme kinematic structure. Its central star (CSPN) is further found to
exhibit a Kepler/K2 light-curve consistent with a post-common envelope (post-
CE) binary system, which can be blamed as responsible for the collimation of
the fast outflow in the recent past. The observations and archival data
analysis of M 3-38 were motivated by the presence of extremely fast ejections
revealed in a long-slit echelle spectrum on the H$\alpha$+[N ii] emission
lines available at the San Pedro Mártir Spectroscopic Catalogue of PNe (López
et al., 2012), and by the highly elongated bipolar morphology displayed in a
narrow-band HST WFPC2 F656N image (see figure 14 in Guzman-Ramirez et al.,
2014).

This letter is organized as follows. In Section 2 we describe the observations
and the data preparation, in Section 3 we present our results, and finally the
discussion is addressed in Section 4.

##  2 Observations and data preparation

M 3-38 was observed with GTC MEGARA on 2021 August 29 using the Integral Field
Unit (IFU) mode. This provides a field of view of
12$\farcs$5$\times$11$\farcs$3 with a spaxel size of 0$\farcs$62\. We used the
high-resolution (HR) Volume-Phased Holographic (VPH) grism VPH665-HR covering
the 6405.6-6797.1 Å wavelength range at a spectral dispersion of 0.098 Å with
a resolution of $R=$18,700 ($\simeq 16$ km s-1). Three 900 s exposures were
obtained with a seeing of 1$\farcs$2.

The data reduction process was carried out using the Data Reduction Cookbook
provided by the Universidad Complutense de Madrid (Pascual et al., 2019).
Through the pipeline, we subtracted the sky and bias contributions, correct
for flat field effects, and perform wavelength calibration, spectra tracing
and extraction. Sky subtraction is performed via 56 ancillary fibers located
$\approx 2\farcm 0$ from the center of the IFU. We apply the regularization
grid task megararss2cube111Task developed by J. Zaragoza-Cardiel available at
https://github.com/javierzaragoza/megararss2cube to obtain square spaxels with
sizes of 0$\farcs$215\. The final cube has dimensiones of
52$\times$58$\times$4300 equivalent to a total of 3016 spectra in the
datacube. The flux calibration was done using observations of the
spectrophotometric standard star HR7596 taken immediately after the
observations of M 3-38.

Figure 2:  HST WFPC2 optical images of M 3-38. The left panel shows a grey-
scale F656N (H$\alpha$) image overimposed with contours from the MEGARA [N ii]
$\lambda$6584 Å emission line. The colors represent different velocity ranges
as labeled. The right panel shows a color-composite image obtained by
combining F656N H$\alpha$ (red), F547M (green), and F502N [O iii] (blue)
images. The dashed-line areas represent the extraction regions for the PV
diagrams shown in Figure 4.

M 3-38 was observed by the Kepler/K2 mission (Howell et al., 2014) during
Campaign 11 in 2016 during September 24 to December 8. Campaign 11 suffered a
three day interruption (October 18–20) to make a pointing correction of
$-0.32^{\circ}$ in the spacecraft attitude. As a result, the dataset was
splitted in two parts, designated Campaign 111 and 112, spanning 23 and 48
days, respectively (see Figure 5, upper left), that were processed separately
using new target apertures in the second part of the campaign (see the Data
Release
Notes222https://archive.stsci.edu/missions/k2/doc/drn/KSCI-19151-002_K2-DRN30_C11.pdf
for more information). We retrieved the two lightcurves from the Mikulski
Archives for Space
Telescopes333https://mast.stsci.edu/portal/Mashup/Clients/Mast/Portal.html and
used the Pre-search Data Conditioning Simple Aperture Photometry (PDCSAP)
datasets, already cleaned for systematic errors. After removing outliers, the
flux was normalized and the two datasets joined together resulting in a total
of 3166 useful points with a 30 minute cadence along a 74 days time baseline.

##  3 Results

###  3.1 Kinematics of the collimated outflow

The MEGARA IFS observations of M 3-38 indicate diffuse emission in the
H$\alpha$, [N ii] $\lambda\lambda$6548,6584, [S ii] $\lambda\lambda$6717,6731,
and He ii $\lambda$6560 lines. Emission from the [N ii]
$\lambda\lambda$6435.61,6527.23, C i $\lambda\lambda$6674.11,6683.95, and C ii
$\lambda$6578.05 lines is also detected in the innermost regions. The spatio-
kinematics of M 3-38 will be investigated here using the brightest H$\alpha$
and [N ii] $\lambda$6584 emission lines.

Figure 3:  GTC MEGARA continuum-subtracted H$\alpha$ (left) and [N ii]
$\lambda$6584 (centre) line emission maps, and electron density map derived
from the [S ii] $\lambda\lambda$6716,6731 line ratio (right, see text for
details). Contours are used to emphasize regions both of faint and bright
surface brightness. The blue and red contours in the density map correspond to
the same surface brightness levels in the [S ii] $\lambda$6716 and [S ii]
$\lambda$6731 images, respectively.  Figure 4: PV diagrams of the H$\alpha$
(left) and [N ii] $\lambda$6584 (right) emission lines extracted from MEGARA
pseudo-slits along the bipolar axis at PA 45∘ (top) and an orthogonal
direction at PA 320∘ (bottom). Colored contours are used to emphasize both
faint and bright emission. When the emission from high-velocity components
(see text) is too faint to be shown by these contours, red and blues arrows
are used to indicate receding and approaching features.

A tomographic view of M 3-38 is displayed in Figure 1, with channel maps of
the [N ii] $\lambda$6584 emission line spanning from radial velocities in the
range $-$480 to $+$160 km s-1 with a width of 40 km s-1. For a systemic
velocity in the Local Standard Rest (LSR) frame of $v_{\mathrm{sys}}=-$160.5
km s-1 (central panel of Fig. 1), the emission in the most extreme panels
implies expansion velocities in the range $\pm$225 km s-1. The emission of the
fast outflow of M 3-38 is aligned along a position angle (PA) of
$43^{\circ}\pm 2^{\circ}$, with the southwest emission approaching (blue-
shifted) and the northeast emission receding (red-shifted). The emission is
thus mostly aligned with the symmetry axis of M 3-38, as illustrated in the
left panel of Figure 2, where contours of the emission in different velocity
ranges are overplotted on an HST WFPC2 H$\alpha$ image. In this image, M 3-38
exhibits a highly axisymmetric morphology with two 5.3′′ in size bipolar lobes
aligned along a PA of $39^{\circ}\pm 6^{\circ}$ terminating in bow-shock-like
clumps. The emission from the intermediate-velocity ranges from $-40$ to 0 km
s-1 (orange in Fig. 2-left) and $-320$ to $-$280 km s-1 (blue in Fig. 2-left)
is associated with those clumps, but the emission from the extreme-velocity
ranges from $+80$ to $+120$ km s-1 (red in Fig. 2-left) and $-400$ to$-360$ km
s-1 (violet in Fig. 2-left) peaks at $\simeq 5^{\prime\prime}$ from the CSPN,
i.e., they extend beyond the emission detected in the HST H$\alpha$ image.

The extent of the emission detected by MEGARA is illustrated in the continuum-
subtracted H$\alpha$ and [N ii] $\lambda$6584 maps presented in Figure 3. A
density map is also presented in the right panel of this figure. The density
has been computed from the [S ii] $\lambda$6716 to [S ii] $\lambda$6731 ratio
map using in python getTemDen function of the PyNeb package (Luridiana et al.,
2015) for the analysis of emission lines assuming an electron
temperature444The calculation of the density using the [S ii] doublet is
rather insensitive to the adopted value of electron temperature for typical
values in the range 8000–12000 K found in PNe. of 10000 K. This map indicates
a clear density gradient from the innermost regions of M 3-38 to the inner
outflow ($N_{\rm e}\approx 2,500$ cm-3) and to its outermost tip ($N_{\rm
e}\approx 1,500$ cm-3).

To investigate the expansion-law of the outflow of M 3-38, classical position-
velocity (PV) diagrams in the H$\alpha$ and [N ii] $\lambda$6584 emission
lines have been extracted from a pseudo long-slit along its bipolar axis at PA
45∘ (Fig. 4-top). These PV diagrams are consistent with a homologous expansion
with a velocity gradient $\approx$60 km s-1 arcsec-1. We note that these PV
diagrams are suggestive of a double-S shape that could be attributed to
precession. The highest-velocity components at the tip of this outflow reach
expansion velocities $\pm$220 km s-1, with the SW clump showing an intriguing
hook-like shape extending up to $\approx$7′′ from the CSPN with expansion
velocity of $-$240 km s-1.

The MEGARA observations also detect another pair of high-velocity clumps, as
denoted by the violet and red contours in Fig. 2-left, located $\simeq
5.5^{\prime\prime}$ from the CSPN towards the SE and NW of M3-38,
respectively. Quite surprisingly, these clumps are aligned along a direction
which is almost orthogonal to the bipolar axis of M 3-38. To illustrate
further their presence, H$\alpha$ and [N ii] $\lambda$6584 PV diagrams have
also been extracted from a $1^{\prime\prime}$-wide pseudo long-slit along
PA=320∘ (Fig. 2-right). These PV diagrams (Fig. 4-bottom), and particularly
the [N ii] one, confirm the presence of high-velocity components along this
direction with an expansion velocity of $\pm$230 km s-1.

Incidentally, we shall mention that the PV diagrams shown in Figure 4 reveal
the presence of an extended component at the systemic velocity of M 3-38 that
seems to fill the whole field of view of the MEGARA IFU. This component is
broad and unresolved, with an intrinsic FWHM of 40 km s-1 and a line-tilt up
to $\simeq$6 km s-1. It can thus be interpreted as a low-velocity non-
spherical halo around M 3-38.

Figure 5:  Top-left panel: original (grey) and one day (magenta) binned
Kepler/K2 C111 and C112 light curve of the CSPN of M 3-38. The two campaigns
are separated by a three day gap. Bottom-left panel: light curve of the CSPN
of M 3-38 folded to 17.7 days (symbols are the same as in the upper plot).
Black points correspond to 0.01-phase binned data. Right panel: amplitude
spectra for the individual and one-day binned datasets. The horizontal lines
in the amplitude spectra are four times the mean amplitude in a 0.5 c/d range
around the main frequency. The insert zooms in the amplitude spectra up to the
Nyquist frequency of the binned data series.

###  3.2 Photometric variations of the central star

We used Period04 (Lenz & Breger, 2005) to search for periodicities in the
Kepler/K2 light curve of the CSPN of M 3-38 derived from Campaign C111 and
C112 (Fig. 5-left-top). The amplitude spectra was calculated up to the Nyquist
frequency, corresponding to 24 cycle day-1. A frequency is considered
significant when its amplitude is at least four times the noise level (Breger
et al., 1993), which is equivalent to a 99.9% confidence level (Kuschnig et
al., 1997). Since no significant frequencies were found in the high frequency
range, the original light curve was binned to one day bins to search for
periodicities up to the 0.5 cycle day-1 Nyquist limit (Fig. 5-top-left panel).
In both amplitude spectra (Fig. 5-right panel), we found the highest amplitude
frequency at 0.0565 cycle day-1 to be significant, corresponding to a main
period of $\sim$17.7 d, and its first harmonic at 0.1199 cycle day-1,
corresponding to $\sim$9.0 d period. We note that the analysis of the same
Kepler/K2 data by Jacoby et al. (2021) deemed it non-variable, as these
authors conservatively excluded cases of low-amplitude variability if the best
period was close to or more than half of the sampling window that could have
resulted from spurious variability.

Fig. 5-bottom-left panel shows the folded individual and one day binned light
curve to the main frequency, as well as mean values for a 0.01 phase bins for
better appreciation. The light curve shows a dominant peak at phase 0.2 with a
main minimum at phase 0.0 and a subtle through at phase 0.55. Within the
limits of the low signal, there seem to be a hint of a secondary peak at phase
0.75. The CSPN of M 3-38 is classified as an H-deficient, weak emission line
star (DePew et al., 2011), but the coherence of its light-curve precludes wind
variability (see, for instance, the light-curve of H 2-48 in Figure 3c of
Jacoby et al., 2021), whereas long-lived bright spots on the stellar surface
would have resulted in shorter periods associated with the stellar rotation.
The variations in the light-curve of M 3-38 could be attributed to irradiation
onto a companion, as an ellipsoidal modulation due to tidal distortion would
require a much shorter period.

##  4 Discussion

In the previous section we have discussed the presence of a fast collimated
outflow and a binary star in M 3-38. Their properties are discussed below.

The main outflow of M 3-38 is aligned along its bipolar axis and has expansion
velocities up to $\approx$225 km s-1 (Fig. 2 and 4). This makes the outflow in
M 3-38 one of the fastest among PNe, only surpassed by those in M 1-16 and
MyCn 18 and as fast as that in KjPn 8 (Guerrero et al., 2020, and references
therein). The high velocity, linear PV diagram, and elongated morphology of
this outflow makes it a “bona-fide” jet candidate. The jet space velocity
cannot be derived because its inclination angle with the line of sight is
unknown. If an inclination of 45${}^{\circ}\pm 15^{\circ}$ were to be adopted,
then the space velocity of the jet would be $320^{+130}_{-60}$ km s-1. The
outermost fastest component of this jet is projected about 5′′ from the
central star of M 3-38 (Fig. 2). Adopting the most recent distance estimate of
8 kpc to M 3-38555 Distance estimates to M 3-38 in the literature range from
5.3 to 14.1 kpc, with an average value very similar to the one adopted in the
text.  derived from MSX MIR flux densities by Ortiz et al. (2011) and a
similar $45^{\circ}\pm 15^{\circ}$ inclination angle, the projected distance
from the PN center of 0.19 pc would imply a true linear radius of
0.27${}^{+0.11}_{-0.05}$ pc. This translates into a jet kinematic age of
860${}^{+630}_{-360}$ yr. We remark that the values of the projected distance,
true linear radius, and kinematic age given above scale with the distance,
which has been adopted to be 8 kpc.

The ionized mass of the jet can be computed from the relationship (Pottasch,
1984):

$M_{\mathrm{ion}}\,[\mathrm{M}_{\odot}]=11.06\times
F(\mathrm{H}\beta)\frac{d^{2}(T_{\mathrm{e}}/10^{4})^{0.88}}{N_{\mathrm{e}}},$
(1)

where the intrinsic H$\beta$ flux is in units of $10^{-11}$ erg cm-2 s-1 and
$d$ in kpc. The intrinsic H$\beta$ flux of the jet is derived to be $4.2\times
10^{-12}$ erg cm-2 s-1 from the observed H$\alpha$ flux of $5.3\times
10^{-13}$ erg cm-2 s-1 for a logarithmic extinction $c$(H$\beta$) of 2.0
(Tylenda et al., 1992) and case B recombination. The density of the jet is
$\simeq$2,500 cm-3, as derived from the density-sensitive [S ii] doublet (Fig.
3-right). Assuming a value of 10,000 K for $T_{\rm e}$, an ionized mass of
0.011 M⊙ is derived. Alternatively, the volume occupied by the jet and its
density can be used to estimate the ionized mass assuming a conservative value
of 0.1 for the “filling factor” $\epsilon$ and a standard value of 1.4 for the
mean molecular weight. Adopting a single cylindrical geometry with radius
0.5′′ and height 5′′ tilted by $45^{\circ}\pm 15^{\circ}$ with the line of
sight, a value of $\approx 3\times$10-3 M⊙ is derived. Given the uncertainties
and assumptions of both methods, we shall adopt an intermediate value for the
ionized mass of $M_{\mathrm{ion}}=6\times$10-3 M⊙.

The values of space velocity666 An average radial expansion velocity of 70 km
s-1, which is representative of the bulk of emission, was adopted in the
calculations of the linear momentum and mechanical luminosity, rather than the
extreme 225 km s-1 expansion velocity., kinematic age, and ionized mass can be
combined to derive a mass-loss rate in the range $2\times 10^{-6}-2\times
10^{-5}$ M⊙ yr-1, a linear momentum from $6\times 10^{34}$ to $2.8\times
10^{35}$ dyn, and a mechanical luminosity of $2-20$ L⊙ for the bulk of the
emission.

The analysis of the Kepler/K2 light-curve reveals a dominant frequency that
corresponds to a period of 17.7 d, suggesting that M 3-38 host a binary
system. The variability type is unclear as it can be assigned either to
irradiation of a main sequence companion (Hillwig et al., 2016a) or to
ellipsoidal modulation, which is always interpreted in CSPNe as a case for a
double degenerate system (DD; Hillwig et al., 2010). By adopting a total mass
for the binary CSPN of M 3-38 of 0.7–1.6 M⊙ (0.4-1.0 M⊙ for the CSPN and
0.3-0.6 M⊙ for the companion whatever it is a WD or a main sequence star), an
orbital separation of $\approx$0.12–0.16 au ($\approx$25–34 R⊙) is estimated.
This orbital separation favors irradiation as a viable mechanism to produce
the small amplitude variation seen in M 3-38 (see the top-left panel of figure
1 in De Marco et al., 2008), whereas it makes ellipsoidal variability highly
unlikely for the expected Roche lobe size of several solar radii.

The small orbital separation and the presence of highly-collimated, fast
ejections from M 3-38 leads us to suggest that it might have formed as the
result of CE evolution (e.g., Paczynski, 1976; Ivanova et al., 2013; Jones &
Boffin, 2017). During the CE phase the massive component overflows its Roche
lobe and the companion is engulfed. Models predict that the orbit decays and
orbital energy and angular momentum are transferred to the CE within a
timescale of months-to-years (e.g., Chamandy et al., 2020). The subsequent
evolution naturally explains the formation of bipolar ejections (see, e.g.,
García-Segura et al., 2021; Ondratschek et al., 2021; Zou et al., 2020; López-
Cámara et al., 2021, and references therein) of material in the direction
perpendicular to the orbital plane (see Hillwig et al., 2016b). Indeed, high-
resolution ALMA observations of water fountain objects, which are often
interpreted as transitional sources between the AGB and proto-PNe phases,
imply that they have experienced a recent ($<$200 yr) CE evolution (Khouri et
al., 2021).

Mass estimates and kinematics of PNe that experienced a CE phase can be
directly contrasted with theoretical predictions (Alcolea et al., 2007; Frew &
Parker, 2007; Corradi et al., 2015; Santander-García et al., 2022). The mass-
loss rate of the jets of M 3-38 is about one to two orders of magnitude larger
than those reported for the jets of PNe with post-CE close binaries (Tocknell
et al., 2014) and for the jet in NGC 2392 (Guerrero et al., 2021), but
consistent with those of the late AGB jets in BD$+$46∘442 and IRAS
19135$+$3937 reported by Bollen et al. (2020). The linear momentum and
mechanical luminosity of the jet in M 3-38 are in the high end of the range
presented by those authors, but still notably smaller than the values reported
for outflows in proto-PNe (Bujarrabal et al., 2001).

If the jet in M 3-38 were launched by a CE interaction, its velocity should be
of the order of the escape velocity of the secondary star launching the jet,

$v_{\mathrm{j}}=\sqrt{\frac{2GM}{R}},$ (2)

where $M$ and $R$ are its mass and radius, and $G$ is the gravitational
constant. Jet velocities of 540 and 480 km s-1 can be estimated for M5 V and
M8 V stars with masses of 0.21 and 0.06 M⊙, respectively (see Cox, 2000).
These values are close to the upper limit estimated for the real jet velocity,
but we note that the interaction of the jet with the material ejected
previously during the AGB phase might have slowed it down.

The 17.7 d period proposed for the binary CSPN of M 3-38 is relatively long
compared to the majority of binary CSPNe (see the compilation presented by
Boffin & Jones, 2019, and references therein). In contrast, simulations of CE
evolution result in relatively large separations of the order of 10–20 R⊙ and
periods larger than 3 d (see, e.g., Chamandy et al., 2018, 2020; Iaconi & De
Marco, 2019), more alike that of M 3-38.

To conclude, M 3-38 could be a new addition to the select group of PNe with
fast collimated outflows and post-CE CSPNe (e.g., Fleming 1, Boffin et al.,
2012). A more accurate characterization of the light-curve of its CSPN and
properties of its jet are urgent, as M 3-38 could be a case study of the late
evolution of low- and intermediate-mass stars in binary systems and the launch
of high-velocity jets in a CE phase. Its unusually long orbital period among
binary post-CE CSPNe makes it also a key case for the comparison of CE
evolution simulations and observations.

Finally, it is interesting to remark the presence of an additional high-
velocity ejection almost orthogonal to the main one. While astonishing, this
is not uncommon among PNe, with examples of collimated outflows almost
orthogonal (e.g. IC 4593; Corradi et al., 1997) or along very different
directions (see the compilation presented by Guerrero et al., 2021), with the
record case of NGC 6210 with five different symmetry axes (Henney et al.,
2021). It has been noted that jets misaligned with the main nebular axis might
be characteristic of PNe with a post-CE binary (Bond & Livio, 1990; De Marco,
2009). There is not an obvious interpretation for these phenomena (see, e.g.,
Bear & Soker, 2017), but, if associated with a CE phase, it is clearly
suggestive of dramatic changes in the preferential ejection direction of the
stellar system.

JSRG acknowledges support from the Programa de Becas posdoctorales of the
Direccion General de Asuntos del Personal Académico of the Universidad
Nacional Autonoma de México (DGAPA, UNAM, Mexico). JAT acknowledges support by
the Marcos Moshinsky Foundation (Mexico), UNAM PAPIIT project IA101622
(Mexico), and the Visiting-Incoming programme of the Centro de Excelencia
Severo Ochoa (Spain). MAG acknowledges support of grant PGC 2018-102184-B-I00
of the Ministerio de Educación, Innovación y Universidades cofunded with FEDER
funds. CR-L and MAG acknowledge financial support from the State Agency for
Research of the Spanish MCIU through the “Center of Excellence Severo Ochoa”
award to the Instituto de Astrofísica de Andalucía (SEV-2017-0709). LS
acknowledges support from UNAM PAPIIT Grant IN110122. JAT AND GR-L
acknowledges support from CONACyT (grant 263373). The authors are thankful to
the referee, Prof. Orsola De Marco, for comments and suggestions that improved
the interpretation of the results presented here, to E. Rodríguez for helpful
discussions on the binary nature of the CSPN of M 3-38, and to G. Jacoby and
D. Jones for discussions and further clarification of the methods and results
presented in their work (Jacoby et al., 2021). This work has made extensive
use of the NASA’s Astrophysics Data System.

## References

  * Alcolea et al. (2007) Alcolea, J., Neri, R., & Bujarrabal, V. 2007, A&A, 468, L41. doi:10.1051/0004-6361:20066956
  * Balick (1987) Balick, B. 1987, AJ, 94, 671. doi:10.1086/114504
  * Bear & Soker (2017) Bear, E. & Soker, N. 2017, ApJ, 837, L10. doi:10.3847/2041-8213/aa611c
  * Boffin & Jones (2019) Boffin, H. M. J. & Jones, D. 2019, The Importance of Binaries in the Formation and Evolution of Planetary Nebulae, Springer Briefs in Astronomy, Springer Nature Switzerland AG. ISBN 978-3-030-25058-4. doi:10.1007/978-3-030-25059-1
  * Boffin et al. (2012) Boffin, H. M. J., Miszalski, B., Rauch, T., et al. 2012, Science, 338, 773. doi:10.1126/science.1225386
  * Bollen et al. (2020) Bollen, D., Kamath, D., De Marco, O., et al. 2020, A&A, 641, A175. doi:10.1051/0004-6361/202038414
  * Bond & Livio (1990) Bond, H. E. & Livio, M. 1990, ApJ, 355, 568. doi:10.1086/168789
  * Breger et al. (1993) Breger, M., Stich, J., Garrido, R., et al. 1993, A&A, 271, 482
  * Bujarrabal et al. (2001) Bujarrabal, V., Castro-Carrizo, A., Alcolea, J., et al. 2001, A&A, 377, 868. doi:10.1051/0004-6361:20011090
  * Chamandy et al. (2020) Chamandy, L., Blackman, E. G., Frank, A., et al. 2020, MNRAS, 495, 4028. doi:10.1093/mnras/staa1273
  * Chamandy et al. (2018) Chamandy, L., Frank, A., Blackman, E. G., et al. 2018, MNRAS, 480, 1898. doi:10.1093/mnras/sty1950
  * Corradi et al. (2015) Corradi, R. L. M., García-Rojas, J., Jones, D., et al. 2015, ApJ, 803, 99. doi:10.1088/0004-637X/803/2/99
  * Corradi et al. (1997) Corradi, R. L. M., Guerrero, M., Manchado, A., et al. 1997, New A, 2, 461. doi:10.1016/S1384-1076(97)00032-8
  * Cox (2000) Cox, A. N. 2000, Allen’s Astrophysical Quantities, 1
  * DePew et al. (2011) DePew, K., Parker, Q. A., Miszalski, B., et al. 2011, MNRAS, 414, 2812. doi:10.1111/j.1365-2966.2011.18337.x
  * De Marco (2009) De Marco, O. 2009, PASP, 121, 316. doi:10.1086/597765
  * De Marco et al. (2008) De Marco, O., Hillwig, T. C., & Smith, A. J. 2008, AJ, 136, 323. doi:10.1088/0004-6256/136/1/323
  * Frew & Parker (2007) Frew, D. J. & Parker, Q. A. 2007, Asymmetrical Planetary Nebulae IV, 475
  * García-Segura et al. (2021) García-Segura, G., Taam, R. E., & Ricker, P. M. 2021, ApJ, 914, 111. doi:10.3847/1538-4357/abfc4e
  * Gieseking et al. (1985) Gieseking, F., Becker, I., & Solf, J. 1985, ApJ, 295, L17. doi:10.1086/184529
  * Gil de Paz et al. (2018) Gil de Paz, A., Carrasco, E., Gallego, J., et al. 2018, Proc. SPIE, 10702, 1070217. doi:10.1117/12.2313299
  * Guerrero et al. (2021) Guerrero, M. A., Cazzoli, S., Rechy-García, J. S., et al. 2021, ApJ, 909, 44. doi:10.3847/1538-4357/abe2aa
  * Guerrero et al. (2020) Guerrero, M. A., Suzett Rechy-García, J., & Ortiz, R. 2020, ApJ, 890, 50. doi:10.3847/1538-4357/ab61fa
  * Guzman-Ramirez et al. (2014) Guzman-Ramirez, L., Lagadec, E., Jones, D., et al. 2014, MNRAS, 441, 364. doi:10.1093/mnras/stu454
  * Henney et al. (2021) Henney, W. J., López, J. A., García-Díaz, M. T., et al. 2021, MNRAS, 502, 1070. doi:10.1093/mnras/staa4014
  * Hillwig et al. (2010) Hillwig, T. C., Bond, H. E., Afşar, M., et al. 2010, AJ, 140, 319. doi:10.1088/0004-6256/140/2/319
  * Hillwig et al. (2016a) Hillwig, T. C., Bond, H. E., Frew, D. J., et al. 2016, AJ, 152, 34. doi:10.3847/0004-6256/152/2/34
  * Hillwig et al. (2016b) Hillwig, T. C., Jones, D., De Marco, O., et al. 2016, ApJ, 832, 125. doi:10.3847/0004-637X/832/2/125
  * Howell et al. (2014) Howell, S. B., Sobeck, C., Haas, M., et al. 2014, PASP, 126, 398. doi:10.1086/676406
  * Iaconi & De Marco (2019) Iaconi, R. & De Marco, O. 2019, MNRAS, 490, 2550. doi:10.1093/mnras/stz2756
  * Ivanova et al. (2013) Ivanova, N., Justham, S., Chen, X., et al. 2013, A&A Rev., 21, 59. doi:10.1007/s00159-013-0059-2
  * Jacoby et al. (2021) Jacoby, G. H., Hillwig, T. C., Jones, D., et al. 2021, MNRAS, 506, 5223. doi:10.1093/mnras/stab2045
  * Jones & Boffin (2017) Jones, D. & Boffin, H. M. J. 2017, Nature Astronomy, 1, 0117. doi:10.1038/s41550-017-0117
  * Khouri et al. (2021) Khouri, T., Vlemmings, W. H. T., Tafoya, D., et al. 2021, Nature Astronomy. doi:10.1038/s41550-021-01528-4
  * Kuschnig et al. (1997) Kuschnig, R., Weiss, W. W., Gruber, R., et al. 1997, A&A, 328, 544
  * Kwok (2000) Kwok, S. 2000, The origin and evolution of planetary nebulae / Sun Kwok. Cambridge ; New York : Cambridge University Press, 2000. (Cambridge astrophysics series ; 33)
  * Lenz & Breger (2005) Lenz, P. & Breger, M. 2005, Communications in Asteroseismology, 146, 53. doi:10.1553/cia146s53
  * López et al. (2012) López, J. A., Richer, M. G., García-Díaz, M. T., et al. 2012, Rev. Mex. Astron. Astrofis., 48, 3
  * López-Cámara et al. (2021) López-Cámara, D., De Colle, F., Moreno Mendez, E., et al. 2021, arXiv:2110.02227
  * Luridiana et al. (2015) Luridiana V., Morisset C., Shaw R. A., 2015, A&A, 573, A42. doi:10.1051/0004-6361/201323152
  * Manchado et al. (1996) Manchado, A., Guerrero, M. A., Stanghellini, L., et al. 1996, The IAC morphological catalog of northern Galactic planetary nebulae, Publisher: La Laguna, Spain: Instituto de Astrof ısica de Canarias (IAC), ISBN: 8492180609
  * Montoro-Molina et al. (2022) Montoro-Molina, B., Guerrero, M. A., Pérez-Díaz, B., et al. 2022, MNRAS. doi:10.1093/mnras/stac336
  * Ondratschek et al. (2021) Ondratschek, P. A., Roepke, F. K., Schneider, F. R. N., et al. 2021, arXiv:2110.13177
  * Ortiz et al. (2011) Ortiz, R., Copetti, M. V. F., & Lorenz-Martins, S. 2011, MNRAS, 418, 2004. doi:10.1111/j.1365-2966.2011.19619.x
  * Paczynski (1976) Paczynski, B. 1976, Structure and Evolution of Close Binary Systems, 73, 75
  * Pascual et al. (2019) Pascual S., Cardiel N., Gil de Paz A., Carasco E., Gallego J., Iglesias-Páramo J., Cedazo R., 2019, hsax.conf, 227
  * Pottasch (1984) Pottasch, S. R. 1984, Astrophysics and Space Science Library, Dordrecht: Reidel, 1984. doi:10.1007/978-94-009-7233-9
  * Rechy-García et al. (2020a) Rechy-García, J. S., Guerrero, M. A., Duarte Puertas, S., et al. 2020a, MNRAS, 492, 1957. doi:10.1093/mnras/stz3326
  * Rechy-García et al. (2020b) Rechy-García, J. S., Guerrero, M. A., Santamaría, E., et al. 2020b, ApJ, 903, L4. doi:10.3847/2041-8213/abbe22
  * Rechy-García et al. (2021) Rechy-García, J. S., Toalá, J. A., Cazzoli, S., et al. 2021, MNRAS, 508, 2254. doi:10.1093/mnras/stab2531
  * Rechy-García et al. (2017) Rechy-García, J. S., Velázquez, P. F., Peña, M., et al. 2017, MNRAS, 464, 2318. doi:10.1093/mnras/stw2524
  * Sahai & Trauger (1998) Sahai, R. & Trauger, J. T. 1998, AJ, 116, 1357. doi:10.1086/300504
  * Santander-García et al. (2022) Santander-García, M., Jones, D., Alcolea, J., et al. 2022, A&A, 658, A17. doi:10.1051/0004-6361/202142233
  * Schwarz et al. (1992) Schwarz, H. E., Corradi, R. L. M., & Melnick, J. 1992, A&AS, 96, 23
  * Soker (1997) Soker N., 1997, ApJS, 112, 487. doi:10.1086/313040
  * Tocknell et al. (2014) Tocknell, J., De Marco, O., & Wardle, M. 2014, MNRAS, 439, 2014. doi:10.1093/mnras/stu079
  * Tylenda et al. (1992) Tylenda, R., Acker, A., Stenholm, B., et al. 1992, A&AS, 95, 337
  * Vassiliadis & Wood (1993) Vassiliadis, E. & Wood, P. R. 1993, ApJ, 413, 641. doi:10.1086/173033
  * Zou et al. (2020) Zou, Y., Frank, A., Chen, Z., et al. 2020, MNRAS, 497, 2855. doi:10.1093/mnras/staa2145


# The lattice of envy-free many-to-many matchings with contracts††thanks: We
thank Jordi Massó and Alejandro Neme for very detailed comments. We
acknowledge financial support from UNSL through grants 032016 and 030320, and
from Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET)
through grant PIP 112-200801-00655, and from Agencia Nacional de Promoción
Científica y Tecnológica through grant PICT 2017-2355.

Agustín G. Bonifacio Instituto de Matemática Aplicada San Luis, Universidad
Nacional de San Luis and CONICET, San Luis, Argentina, and RedNIE. Emails:
<EMAIL_ADDRESS>(A. G. Bonifacio<EMAIL_ADDRESS>(N. Guiñazu),
<EMAIL_ADDRESS>(N. Juarez<EMAIL_ADDRESS>(P. Neme) and
<EMAIL_ADDRESS>(J. Oviedo). Nadia Guiñazú 22footnotemark: 2 Noelia
Juarez22footnotemark: 2 Pablo Neme22footnotemark: 2 Jorge
Oviedo22footnotemark: 2

###### Abstract

We study envy-free allocations in a many-to-many matching model with contracts
in which agents on one side of the market (doctors) are endowed with
substitutable choice functions and agents on the other side of the market
(hospitals) are endowed with responsive preferences. Envy-freeness is a
weakening of stability that allows blocking contracts involving a hospital
with a vacant position and a doctor that does not envy any of the doctors that
the hospital currently employs. We show that the set of envy-free allocations
has a lattice structure. Furthermore, we define a Tarski operator on this
lattice and use it to model a vacancy chain dynamic process by which, starting
from any envy-free allocation, a stable one is reached.

_JEL classification:_ C78, D47.

_Keywords:_ Matching, envy-freeness, lattice, Tarski operator, re-
equilibration process, vacancy chain.

##  1 Introduction

Models of many-to-many matching with contracts subsume as special cases many-
to-many matching markets and buyer-seller markets with heterogeneous and
indivisible goods.

In this paper, we study envy-free allocations in a many-to-many matching model
with contracts in which agents on one side of the market (that we call
doctors) are endowed with substitutable choice functions and agents on the
other side of the market (that we call hospitals) are endowed with responsive
preferences. Loosely speaking, (doctor) envy-freeness is a weakening of
stability that allows blocking contracts involving a hospital with a vacant
position and a doctor that does not envy any of the doctors that the hospital
currently employs.

In this setting, we study the set of envy-free allocations and prove that it
has a lattice structure under a partial order by which an allocation dominates
another one if, for each doctor, when the contracts of both allocations are
available, she selects only the contracts of the first one. Moreover, we
define a Tarski operator on this lattice and show that the set of its fixed
points consists of the set of stable allocations.

The Tarski operator allows us to model vacancy chain dynamics as well.
Consider a situation in which some doctors retire and the vacant positions
generated are filled by doctors who do not have envy towards any of their new
co-workers. If the market is stable before the retirements, then it will be
envy-free after. Moreover, if our goal is to study how to restore stability, a
re-equilibration process can be carried out within the envy-free allocations.
To do this, we apply repeatedly the Tarski operator. In each stage, starting
from an envy-free allocation, the signing of new contracts filing vacant
positions (and generating new vacant positions elsewhere) produces a new envy-
free allocation. We show that the sequence of envy-free allocations thus
generated always converges to a stable allocation.

This process can be described more precisely if we also ask doctors’ choice
functions to satisfy the “law of aggregate demand”. This condition says that
when a doctor chooses from an expanded set of contracts, she signs at least as
many contracts as before. We show two further results under this requirement:
(i) the fixed point of the Tarski operator starting from an arbitrary envy-
free allocation is equal to the join of that allocation and the hospital-
optimal stable allocation, and (ii) the number of contracts signed by a doctor
in an envy-free allocations is at most equal to the number of contracts she
signs in any stable allocation.

The use of Tarski operators is not new in the matching literature. Results on
the existence of stable allocations rely on the construction of a lattice and
a Tarski operator on that lattice that has as its fixed points elements that
are in correspondence with the stable allocations (see Adachi, 2000; Fleiner,
2003; Echenique and Oviedo, 2004; Hatfield and Milgrom, 2005; Hatfield and
Kominers, 2017, for more details). However, in most cases, the elements of the
lattice are _not_ allocations themselves, and their economic interpretation is
not clear. The contribution of our paper, that generalizes the approach first
presented by Wu and Roth (2018) for the many-to-one model with responsive
preferences and then extended to substitutable preferences by Bonifacio et al.
(2021), is to provide a simpler and more economically meaningful construction.

The model and results studied in this paper encompass the many-to-one models
of Wu and Roth (2018) and Bonifacio et al. (2021) and the results therein.
When each doctor can be assigned to at most one hospital and hospitals have
responsive preferences, our model is equivalent to the one presented in Wu and
Roth (2018). When each doctor has substitutable preferences, and each hospital
can be assigned to at most one doctor, our model is equivalent to the one
presented in Bonifacio et al. (2021) in which doctors play the role of firms
and hospitals play the role of workers. Although the results in this paper are
generalizations of the ones presented in Bonifacio et al. (2021) for the many-
to-one case, the fact that our setting has a many-to-many nature and involves
contracts demands new techniques of proof for almost all results.

It is worth mentioning that many-to-many markets (let alone the inclusion of
contracts) are non-trivial extensions of one-to-one markets: many properties
of one-to-one markers do not extend to this wider class. Although many-to-one
markets (with responsive preferences) are isomorphic to one-to-one markets
(Roth and Sotomayor, 1990), there is no such isomorphism for many-to-many
markets, even under responsive preferences. Furthermore, (pairwise) stability
is no longer equivalent in this broader framework to other solution concepts
introduced in the literature such as core stability, group stability or
setwise stability, and stable allocations may even be inefficient (see Blair,
1988; Roth and Sotomayor, 1990; Sotomayor, 1999; Echenique and Oviedo, 2006,
for more detailed discussions).

The rest of the paper is organized as follows. Section 2 presents the model
and some preliminaries. All the results of the paper are presented in Section
3: the lattice structure of the set of envy-free allocations, the Tarski
operator with its related re-equilibration process, and some further results
assuming that doctors’ choice functions satisfy, besides substitutability, the
“law of aggregate demand”. In Section 4 some concluding remarks are in order.
Finally, an Appendix contains all the proofs for our results.

##  2 Model and preliminaries

A model of many-to-many matching with contracts is specified by a set of
_doctors_ $D$, a set of _hospitals_ $H$, and a set of _contracts_ $X$. For
each contract $x\in X$, $x_{D}\in D$ is the doctor associated to $x$ and
$x_{H}\in H$ is the hospital associated to $x.$ Given a set of contracts
$Y\subseteq X$ and an agent $a\in D\cup H,$ let $Y_{a}=\\{x\in
Y:a\in\\{x_{D},x_{H}\\}\\}$ be the set of contracts in $Y$ that name agent
$a$.

Each doctor $d\in D$ in endowed with a choice function $C_{d}$ that fulfills
the following properties:

  1. (i)

$C_{d}\left(Y\right)\subseteq Y_{d}$ and if $x,x^{\prime}\in
C_{d}\left(Y\right)$ and $x\neq x^{\prime}$, then $x_{H}\neq x^{\prime}_{H}.$

  2. (ii)

Substitutability: $C_{d}(Y)\cap Y^{\prime}\subseteq C_{d}(Y^{\prime})$
whenever $Y^{\prime}\subseteq Y\subseteq X$.111This is equivalent to the
following: $x\in C_{d}(Y)$ implies $x\in C_{d}(Y^{\prime}\cup\\{x\\})$
whenever $x\in X$ and $Y^{\prime}\subseteq Y\subseteq X$.

  3. (iii)

Consistency: $C_{d}(Y^{\prime})=C_{d}(Y)$ whenever $C_{d}(Y)\subseteq
Y^{\prime}\subseteq Y$.

  4. (iv)

Path independence: $C_{d}\left(Y\cup Y^{\prime}\right)=C_{d}\left(C_{d}(Y)\cup
Y^{\prime}\right)$ for each pair of subsets $Y$ and $Y^{\prime}$ of $X$.

Property (i) says that, given a set of contracts $Y$, the choice function of
doctor $d$ selects a subset of contracts of $Y$ that name doctor $d$ and that
different contracts of this choice set must name different hospitals. Property
(ii) requires the choice function to be substitutable in the sense that no
contract becomes desirable when some other contract becomes available.
Property (iii) says that the choice set of a subset of $Y$ that is a superset
of the choice set of $Y$ is equal to the choice set of $Y$. Lastly, Property
(iv) says that the choice over a set remains the same when the set is
segmented arbitrarily, the choice applied to one segment and finally the
choice applied again to all chosen contracts from the segments. It is
straightforward to see that Properties (ii) and (iii) imply Property (iv).

Given a set of contracts $Y$, as a consequence of Properties (i) and (iii),
since $C_{d}(Y)\subseteq Y_{d}\subseteq Y$ we have $C_{d}(Y_{d})=C_{d}(Y)$.
This fact is going to be used extensively throughout the paper.

Each hospital $h\in H$ has a quota denoted by $q_{h}$, and a strict preference
relation $\succ_{h}$ over all subsets of contracts in a responsive manner.
This is formalized by the following properties:

  1. (v)

for each $Y\subseteq X$ such that $|Y_{h}|>q_{h}$, $\emptyset\succ_{h}Y_{h},$

  2. (vi)

for each $Y\subseteq X$ such that $|Y_{h}|\leq q_{h}$ , each $x\in
Y_{h}\cup\\{\emptyset\\}$, and each $x^{\prime}\in X_{h}\setminus Y_{h}$,

$(Y_{h}\setminus\\{x\\})\cup\\{x^{\prime}\\}\succ_{h}Y_{h}\text{ if and only
if }x^{\prime}\succ_{h}x.$

Property (v) says that, for each hospital, each subset of contracts of
cardinality greater than its quota is not acceptable. Lastly, Property (vi)
says that, for each hospital, when a subset of contracts that name it has
cardinality less than or equal to its quota, replacing any contract of this
subset for a more preferred one leads to a more preferred subset of contracts.
Given preference $\succ_{h}$, define the choice function $C_{h}$ as follows:
for each $Y\subseteq X$, $C_{h}(Y)$ is the most preferred subset of $Y_{h}$
according to $\succ_{h}$. Notice that $C_{h}$ also fulfills Conditions (i) to
(iv) in the definition of $C_{d}$.

A set of contracts $Y\subseteq X$ is an allocation if:

  1. (i)

for distinct $x,x^{\prime}\in Y,$ $x_{D}\neq x^{\prime}_{D}$ or $x_{H}\neq
x^{\prime}_{H},$ and

  2. (ii)

$|Y_{h}|\leq q_{h}$ for each $h\in H.$

The empty allocation is denoted by $Y^{\emptyset}$ and contains no contract.
Furthermore, denote by $\mathcal{A}$ the set of all allocations. Condition (i)
says that, in an allocation, no doctor-hospital pair can sign more than one
contract. Condition (ii) says that, in an allocation, no hospital can sign
more contracts than its quota.

Given $Y\in\mathcal{A}$, we say that $Y$ is an individually rational
allocation if $C_{a}\left(Y\right)=Y_{a}$ for each $a\in D\cup H.$ This
implies, by substitutability, that for each contract $x\in Y$ we have $x\in
C_{x_{D}}\left(\\{x\\}\right)$ and $x\in
C_{x_{H}}\left(\\{x\\}\right).$333Notice that, by responsiveness, $x\in
C_{x_{H}}\left(\\{x\\}\right)$ is equivalent to $x\succ_{x_{H}}\emptyset$.
Denote by $\mathcal{I}$ the set of all individually rational allocations.
Given $Y\in\mathcal{A}$, $x\in X\setminus Y$ is a blocking contract for $Y$ if
$x\in C_{x_{D}}(Y\cup\\{x\\})$ and $x\in C_{x_{H}}(Y\cup\\{x\\})$.
Furthermore, allocation $Y$ is stable if $Y$ is individually rational and
there is no blocking contract for $Y$. Denote by $\mathcal{S}$ the set of all
stable allocations.

###### Remark 1

Given $Y\in\mathcal{A}$, $x\in X\setminus Y$ and $h=x_{H},$ the fact that
$x\in C_{h}(Y\cup\\{x\\})$ is, by responsiveness, equivalent to
$x\succ_{h}\emptyset$ when $|Y_{h}|<q_{h}$, and to the existence of
$x^{\prime}\in Y_{h}$ such that $x\succ_{h}x^{\prime}$ when $|Y_{h}|=q_{h}.$

The key notion that we introduce in this paper is the concept of envy-
freeness. In an envy-free allocation no doctor has justified envy towards any
other doctor. This is formalized in the following definition.

###### Definition 1

Given $Y\in\mathcal{A}$, doctor $d^{\prime}$ has justified envy towards doctor
$d$ at $Y$ (possibly $d=d^{\prime}$) if there are $x\in Y_{d}$ and
$x^{\prime}\in X_{d^{\prime}}\setminus Y$ such that:

  1. (i)

$x^{\prime}_{H}=x_{H}=h,$

  2. (ii)

$x^{\prime}\succ_{h}x$ and $x^{\prime}\in
C_{d^{\prime}}(Y\cup\\{x^{\prime}\\})$.

An allocation $Y$ is (doctor) envy-free if it is individually rational and no
doctor has justified envy at $Y$.

When a doctor has justified envy towards another doctor in an allocation there
are two contracts involved: one in the allocation, that names the doctor who
is envied; and another one outside the allocation, that names the envious
doctor. Condition (i) says that these two contracts name the same hospital.
Condition (ii) says that the named hospital prefers the contract that names
the envious doctor over the contract that names the envied doctor, and that
the envious doctor wishes to sign the new contract with that hospital. Envy-
freeness, therefore, is a weakening of stability that allows blocking
contracts involving a hospital with a vacant position and a doctor that has no
justified envy towards any doctor that the hospital currently employs. This
is, if $Y$ is an envy-free allocation and $x$ is a blocking contract for $Y$,
then $x\in C_{x_{D}}(Y\cup\\{x\\})$, $|Y_{x_{H}}|<q_{x_{H}}$,
$x\succ_{x_{H}}\emptyset$, and $x^{\prime}\succ_{x_{H}}x$ for each
$x^{\prime}\in Y$. Denote by $\mathcal{E}$ the set of all envy-free
allocations.

##  3 Results

In this section, we present our results. First, we show that the set of envy-
free allocations has a lattice structure. To do this, we define a partial
order and a binary operation within the set of envy-free allocations and prove
that this binary operation is the join with respect to that partial order.
Second, we define a Tarski operator on the lattice of envy-free allocations
and show that has the stable allocations as the set of fixed points. This
operator models a re-equilibration process that, starting from any envy-free
allocation, leads to a stable one. Moreover, in the final subsection, we
present some results that follows from requiring that doctors’ choice
functions fulfill, in addition, the law of aggregate demand. All proofs are
relegated to the Appendix.

###  3.1 Lattice structure of the set of envy-free allocations

In a many-to-many matching model, Blair (1988) defines a partial order that
can be generalized to a many-to-many model with contracts as follows. A set of
contracts dominates another if each doctor wishes to keep the contracts signed
under the first set, even if all contracts of the second set are also
available, and do not wish to sign any new contract. Formally, given two sets
of contracts $Y,Y^{\prime}\in X$, we say that $\boldsymbol{Y}$ weakly Blair-
dominates $\boldsymbol{Y^{\prime}}$ and write
$\boldsymbol{Y\succeq_{D}Y^{\prime}}$ when $Y=C_{d}\left(Y\cup
Y^{\prime}\right)$ for each $d\in D$. If $Y\succeq_{D}Y^{\prime}$ and $Y\neq
Y^{\prime},$ we say that $\boldsymbol{Y$Blair-dominates$Y^{\prime}}$ and write
$\boldsymbol{Y\succ_{D}Y^{\prime}}.$

Given two doctor envy-free allocations $Y$ and $Y^{\prime}$, we define
$\lambda^{Y,Y^{\prime}}\subseteq 2^{X}$ as follows:

  1. (i)

for each $d\in D,$ $\lambda^{Y,Y^{\prime}}_{d}=C_{d}\left(Y\cup
Y^{\prime}\right),$

  2. (ii)

for each $h\in H,$ $\lambda^{Y,Y^{\prime}}_{h}=\\{x\in\bigcup_{d\in
D}\lambda^{Y,Y^{\prime}}_{d}:x_{H}=h\\}.$

Under $\lambda^{Y,Y^{\prime}},$ (i) doctors want to sign the best subset of
contracts among those signed by them in either allocation, and (ii) hospitals
agree with doctors that want to sign a contract with them. Notice that by item
(i), if $Y_{d}=Y_{d}^{\prime}=\emptyset$, then
$\lambda^{Y,Y^{\prime}}_{d}=\emptyset.$ The following proposition shows that
$\lambda^{Y,Y^{\prime}}$ is an envy-free allocation, and that it is actually
the _join_ of $Y$ and $Y^{\prime}$.444Given a partially ordered set
$(\mathcal{L},\succeq)$, and two elements $x,y\in\mathcal{L}$, an element
$z\in\mathcal{L}$ is an upper bound of $x$ and $y$ if $z\succeq x$ and
$z\succeq y$. An element $w\in\mathcal{L}$ is the join of $x$ and $y$ if and
only if (i) $w$ is an upper bound of $x$ and $y$, and (ii) $t\succeq w$ for
each upper bound $t$ of $x$ and $y$. The definitions of lower bound and meet
of $x$ and $y$ are dual and we omit them.

###### Proposition 1

Let $Y$ and $Y^{\prime}$ be two distinct envy-free allocations. Then,

  1. (i)

$\lambda^{Y,Y^{\prime}}$ is a envy-free allocation.

  2. (ii)

$\lambda^{Y,Y^{\prime}}$ is the join of $Y$ and $Y^{\prime}$ under the partial
order $\succeq_{D}$.

From now on, given two envy-free allocations $Y$ and $Y^{\prime}$, we denote
$\lambda^{Y,Y^{\prime}}$ as $Y\vee Y^{\prime}$. Now we are in a position to
present the main theorem of this subsection. This result states that the set
of envy-free allocations has a lattice structure with respect to Blair’s
partial order.

###### Theorem 1

The set of envy-free allocations is a lattice under the partial order
$\succeq_{D}$.

In the following example, given two envy-free allocations, we show how to
compute the join between them.

###### Example 1

Consider a market in which $D=\\{d_{1},d_{2}\\}$ is the set of doctors and
$H=\\{h_{1},h_{2}\\}$ is the set of hospitals with quotas $q_{h_{i}}=2,$
$i=1,2$. A contract $x$ that is signed between doctor $d_{i}$ and hospital
$h_{j}$ is denote by $x_{ij}.$ The hospitals have the following responsive
preferences:

$\begin{array}[]{|c||c|}\hline\cr\succ_{h_{1}}&\succ_{h_{2}}\\\
\hline\cr\hline\cr x_{11},y_{11}&x_{12},y_{12}\\\
y_{11},y_{21}&y_{12},y_{22}\\\ x_{21},y_{11}&x_{12},y_{22}\\\
x_{11},y_{21}&x_{22},y_{12}\\\ x_{11},x_{21}&x_{12},x_{22}\\\
x_{21},y_{21}&x_{22},y_{22}\\\ y_{11}&y_{12}\\\ x_{11}&x_{12}\\\
y_{21}&y_{22}\\\ x_{21}&x_{22}\\\ \hline\cr\end{array}$

The doctors are endowed with the following choice functions:

$\begin{array}[]{|c|c||c|c|}\hline\cr
X_{d_{1}}&C_{d_{1}}&X_{d_{2}}&C_{d_{2}}\\\ \hline\cr\hline\cr
x_{11},x_{12},y_{11},y_{12}&x_{11},x_{12}&x_{21},x_{22},y_{21},y_{22}&x_{21},x_{22}\\\
x_{11},y_{11},y_{12}&x_{11}&x_{21},y_{21},y_{22}&x_{21},y_{22}\\\
x_{12},y_{11},y_{12}&x_{12},y_{11}&x_{22},y_{21},y_{22}&x_{22},y_{21}\\\
x_{11},x_{12},y_{11}&x_{11},x_{12}&x_{21},x_{22},y_{21}&x_{21},x_{22}\\\
x_{11},x_{12},y_{12}&x_{11},x_{12}&x_{21},x_{22},y_{22}&x_{21},x_{22}\\\
x_{11},x_{12}&x_{11},x_{12}&x_{21},x_{22}&x_{21},x_{22}\\\
x_{11},y_{11}&x_{11}&x_{21},y_{21}&x_{21}\\\
x_{11},y_{12}&x_{11}&x_{21},y_{22}&x_{21},y_{22}\\\
x_{12},y_{11}&x_{12},y_{11}&x_{22},y_{21}&x_{22},y_{21}\\\
x_{12},y_{12}&x_{12}&x_{22},y_{22}&x_{22}\\\
y_{11},y_{12}&y_{11},y_{12}&y_{21},y_{22}&y_{21},y_{22}\\\
x_{11}&x_{11}&x_{21}&x_{21}\\\ x_{12}&x_{12}&x_{22}&x_{22}\\\
y_{11}&y_{11}&y_{21}&y_{21}\\\ y_{12}&y_{12}&y_{22}&y_{22}\\\
\hline\cr\end{array}$

where, for instance, $X_{d_{1}}$ are all the possible subsets of contracts
that name doctor $d_{1}$. For the subset of contracts
$Y=\\{x_{11},x_{12},y_{11},y_{12}\\}$, $C_{d_{1}}(Y)=\\{x_{11},x_{12}\\}$. It
is easy to see that the choice functions satisfy substitutability and
consistency.

Notice that this market has twelve envy-free allocations, and only four of
them are also stable allocations. Now, consider the following two envy-free
allocations: $Y=\\{y_{11},y_{12},y_{21}\\}$ and
$Y^{\prime}=\\{y_{11},y_{12},y_{22}\\}$. In allocation
$Y=\\{y_{11},y_{12},y_{21}\\}$ $d_{1}$ signs two contracts, one with $h_{1}$
($y_{11}$) and the other one with $h_{2}$ ($y_{12}$) and $d_{2}$ signs
contract $y_{21}$ with $h_{1}$. Since
$C_{d_{1}}(\\{y_{11},y_{12}\\}\cup\\{y_{11},y_{12}\\})=\\{y_{11},y_{12}\\}$
and $C_{d_{2}}(\\{y_{21}\\}\cup\\{y_{22}\\})=\\{y_{21},y_{22}\\}$, $Y\vee
Y^{\prime}=\\{y_{11},y_{12},y_{21},y_{22}\\}.$ It is easy to see that $Y\vee
Y^{\prime}\in\mathcal{E}.$ Moreover, $Y\vee Y^{\prime}\in\mathcal{S}.$ In
Figure 1 we present all envy-free allocations and its lattice structure.
Stable allocations are depicted in boldface.

$\emptyset$$\\{y_{11}\\}$$\\{y_{12}\\}$$\\{y_{11},y_{21}\\}$$\\{y_{11},y_{12}\\}$$\\{y_{12},y_{21}\\}$$\\{y_{11},y_{12},y_{21}\\}$$\\{y_{11},y_{12},y_{22}\\}$$\boldsymbol{\\{y_{11},y_{12},y_{21},y_{22}\\}}$$\boldsymbol{\\{y_{11},x_{12},x_{21},y_{22}\\}}$$\boldsymbol{\\{y_{11},x_{12},y_{21},x_{22}\\}}$$\boldsymbol{\\{x_{11},x_{12},x_{21},x_{22}\\}}$
Figure 1: The lattice of Example 1.

###  3.2 Re-equilibration process

In this subsection, we define a Tarski operator in the envy-free lattice that
describes a possible re-equilibration process. This process models how,
starting from a worker-quasi-stable matching, a decentralized sequence of
offers in which unemployed workers are hired and cause new unemployments,
produces a sequence of worker-quasi-stable matchings that converges to a
stable matching. In the first subsection, we present the operator, show some
of its properties, and prove that the set of its fixed points is the set of
stable matchings. In the second subsection, we discuss the re-equilibration
process, based on our Tarski operator, that models a vacancy chain that leads
towards a stable matching.

For each $Y\in\mathcal{E}$, define the following sets:

$\mathcal{B}^{Y}=\\{x\in X\setminus Y:x\text{ is a blocking contract for
}Y\\}$

$\mathcal{B}^{Y}_{\star}=\\{x\in\mathcal{B}^{Y}:\text{ there is no
}x^{\prime}\in\mathcal{B}^{Y}\text{ such that }x^{\prime}\succ_{h}x\text{
where }h=x_{H}=x^{\prime}_{H}\\}$

and for each $d\in D$,

$\mathcal{B}_{d}^{Y}=\\{x\in\mathcal{B}^{Y}_{\star}:x_{D}=d\\}.$

Given an envy-free allocation $Y$, $\mathcal{B}^{Y}$ denotes the set of all
blocking contracts of $Y$. $\mathcal{B}^{Y}_{\star}$ contains, for each
hospital, the most preferred contract of $\mathcal{B}^{Y}$ among those that
name it. Finally, $\mathcal{B}^{Y}_{d}$ contains all contracts from
$\mathcal{B}^{Y}_{\star}$ that name doctor $d$. Note that for each $h\in H$,
there is at most one contract in $\mathcal{B}^{Y}_{\star}$ that names it.

Our Tarski operator $\mathcal{T}:\mathcal{E}\to\mathcal{E}$ assigns to each
envy-free allocation $Y\in\mathcal{E}$ another envy-free allocation
$\mathcal{T}^{Y}\in\mathcal{E}$ and is defined as follows:

  1. (i)

for each $d\in D$,
$\mathcal{T}^{Y}_{d}=C_{d}\left(Y\cup\mathcal{B}_{d}^{Y}\right)$

  2. (ii)

for each $h\in H$, $\mathcal{T}^{Y}_{h}=\\{x\in\mathcal{T}^{Y}:x_{H}=h\\}$.

The following theorem presents some good properties of operator $\mathcal{T}$.
It states that: (i) the image of an envy-free allocation under the operator is
also envy-free, (ii) the operator is weakly Pareto improving for the doctors,
and (iii) its set of fixed points is the set of stable allocations.

###### Theorem 2

For any $Y\in\mathcal{E}$, the following hold:

  1. (i)

$\mathcal{T}^{Y}\in\mathcal{E},$

  2. (ii)

$\mathcal{T}^{Y}\succeq_{D}Y,$

  3. (iii)

$\mathcal{T}^{Y}=Y$ if and only if $Y\in\mathcal{S}.$

Another important property of operator $\mathcal{T}$ is its isotonicity. This
is, $\mathcal{T}^{Y}\succeq_{D}\mathcal{T}^{Y^{\prime}}$ for envy-free
allocations $Y,Y^{\prime}$ such that $Y^{\prime}\succeq_{D}Y^{\prime}$.555This
property is proven in Lemma 1 in the Appendix. This facts toghether with
Tarski’s fixed point theorem666Remember that Tarski’s theorem (Tarski, 1955)
states that if $(\mathcal{L},\geq)$ is a complete lattice and
$T:\mathcal{L}\longrightarrow\mathcal{L}$ is isotone, then the set of fixed
points of $T$ is non-empty and forms a complete lattice with respect to
$\geq$. and Theorem 2 (iii) allow us to state the following result.

###### Theorem 3

The set of stable allocations is non-empty and forms a lattice with respect to
the partial order $\succeq_{D}.$

We can further observe that the repeated application of operator $\mathcal{T}$
can be interpreted as a vacancy chain dynamic within envy-free allocations as
follows. Consider a situation in which hospitals have vacant positions (for
instance, after the retirement of some doctors) and no doctor envies the
position filled by another doctor, i.e. and envy-free allocation $Y$. Applying
operator $\mathcal{T}$ to the aforementioned allocation involves the following
steps:

  1. (i)

Among the possible blocking contracts of the envy-free allocation, each
hospital selects its most preferred one ($\mathcal{B}_{\star}^{Y}$ defined in
the previous subsection).

  2. (ii)

Each doctor selects the most preferred subset of contracts among those
blocking contracts selected in the previous step that name her and her
currently signed contracts (generating the new envy-free allocation
$\mathcal{T}^{Y}$).

  3. (iii)

Once each doctor signs the new contracts, either some hospitals have new
vacant positions $(\mathcal{T}^{Y}\in\mathcal{E}\setminus\mathcal{S})$ or no
new blocking contract can be formed $(\mathcal{T}^{Y}\in\mathcal{S})$.

If the $\mathcal{T}^{Y}$ is stable, the process ends reaching a stable
allocation. If $\mathcal{T}^{Y}$ is not stable, the process continues applying
operator $\mathcal{T}$ to the envy-free allocation $\mathcal{T}^{Y}$. The
sequence of allocations generated by this process belongs to the set of envy-
free allocations by Theorem 2 (i) and each allocation in the sequence Pareto
improves (for the doctors) upon the previous allocation in the sequence by
Theorem 2 (ii). This process continues until, by finiteness, it reaches a
fixed point that turns out to be a stable allocation by Theorem 2 (iii).

In order to prove existence of stable allocations, both Hatfield and Milgrom
(2005) and Hatfield and Kominers (2017) define a lattice over the cartesian
product of contracts $X\times X.$ On this lattice, Hatfield and Kominers
(2017) define a Tarski operator and show that the fixed points of such
operator are in one-to-one correspondence with the stable allocations, while
Hatfield and Milgrom (2005) define a similar operator without such one-to-one
correspondence. Hatfield and Milgrom (2005) also study vacancy chain dynamics
by means of their Tarski operator. However, we believe that our description of
this process in terms of (envy-free) allocations instead of ordered pairs of
contracts is simpler and has a clearer economic interpretation.

###  3.3 Further results with LAD

In this subsection, by requiring an additional condition on doctors’ choice
functions, we can describe more accurately the re-equilibration process by
means of the lattice structure of the set of envy-free allocations. This
additional condition is the “law of aggregate demand”, that says that when a
doctor chooses from an expanded set of contracts, she signs at least as many
contracts as before. Formally,

###### Definition 2

Choice function $C_{d}$ satisfies the law of aggregate demand (LAD) if
$Y^{\prime}\subseteq Y\subseteq X$ implies
$|C_{d}(Y^{\prime})|\leq|C_{d}(Y)|.$

We know that, starting from an envy-free allocation and iterating our operator
$\mathcal{T}$, we reach a fixed point of $\mathcal{T}$. Assuming LAD, the
lattice structure can help us to identify this fixed point: it is the join of
the original envy-free allocation and the hospital-optimal stable allocation
$Y^{H}$.777The set of stable allocations under substitutable choice functions
is very well-structured. It contains two distinctive stable allocations: the
doctor-optimal stable allocation $Y^{D}$ and the hospital-optimal stable
allocation $Y^{H}$. The allocations $Y^{H}$ is unanimously considered by all
hospitals to be the best among all stable allocations and by all doctors to be
the pessimal stable allocation (see Hatfield and Kominers, 2017, for more
details). Analogous opposition of interests results have been identified in
most matching settings, including those of Roth (1984); Blair (1988); Hatfield
and Milgrom (2005); Echenique and Oviedo (2006).  To formally present this
result, for $Y\in\mathcal{E}$, let $\mathcal{F}^{Y}$ denote the fixed point of
$\mathcal{T}$ obtained by iterating it starting at allocation $Y$.

###### Theorem 4

Let $Y$ be an envy-free allocation. If doctors’ choice functions satisfy LAD,
then $\mathcal{F}^{Y}=Y\vee Y^{H}.$

The following corollary presents an important feature of the structure of the
set of envy-free allocations. It states that any envy-free allocation $Y$ that
Blair-dominates $Y^{H}$ is actually a stable allocation. This happens because
as $Y$ Blair-dominates $Y^{H}$ the join between them is $Y$ and, at the same
time, that join is equal to $\mathcal{F}^{Y}$ by Theorem 4. Therefore,
$Y=\mathcal{F}^{Y}$. Moreover, by Theorem 2 (iii), $\mathcal{F}^{Y}$ is a
stable allocation.

###### Corollary 1

Let $Y$ be an envy-free allocation. If doctors’ choice functions satisfy LAD
and $Y\succeq_{D}Y^{H}$, then $Y$ is a stable allocation.

Since, $Y^{H}$ is the doctor-pessimal stable allocation, the implications of
this corollary are twofold: (i) an envy-free allocation that Blair-dominates
any stable allocation is also stable, and (ii) an allocation that is envy-free
but not stable is either Blair-incomparable to or Blair-dominated by $Y^{H}.$

The following proposition states that, for each doctor, the amount of
contracts signed in an envy-free allocation is always less or equal to the
amount of contracts signed in any stable allocation. The proof of this
proposition uses the rural hospitals theorem that, adapted to the setting of
many-to-many matching markets with contracts, states that when preferences are
substitutable and satisfy LAD, each agent signs the same number of contracts
at every stable allocation (see Theorem 4 in Appendix B in Hatfield and
Kominers, 2017).

###### Proposition 2

Let $Y$ be an envy-free allocation and let $Y^{\prime}$ be a stable
allocation. If doctors’ choice functions satisfy LAD,
$|Y_{d}|\leq|Y^{\prime}_{d}|$ for each $d\in D.$

The following example shows that the requirement of LAD is necessary for all
the results of this subsection to hold.

###### Example 2

Consider a market in which $D=\\{d_{1},d_{2}\\}$ is the set of doctors and
$H=\\{h_{1},h_{2},h_{3}\\}$ is the set of hospitals with quotas $q_{h_{i}}=1,$
$i=1,2,3$. The hospitals have the following preferences:

$\begin{array}[]{|c||c||c|}\hline\cr\succ_{h_{1}}&\succ_{h_{2}}&\succ_{h_{3}}\\\
\hline\cr x_{21}&x_{22}&x_{13}\\\ x_{11}&x_{12}&x_{23}\\\
\hline\cr\end{array}$

The doctors are endowed with the following choice functions:

$\begin{array}[]{|c|c||c|c|}\hline\cr
X_{d_{1}}&C_{d_{1}}&X_{d_{2}}&C_{d_{2}}\\\ \hline\cr\hline\cr
x_{11},x_{12},x_{13}&x_{11},x_{12}&x_{21},x_{22},x_{23}&x_{23}\\\
x_{11},x_{12}&x_{11},x_{12}&x_{21},x_{22}&x_{21},x_{22}\\\
x_{11},x_{13}&x_{11}&x_{21},x_{23}&x_{23}\\\
x_{12},x_{13}&x_{12}&x_{22},x_{23}&x_{23}\\\ x_{11}&x_{11}&x_{21}&x_{21}\\\
x_{12}&x_{12}&x_{22}&x_{22}\\\ x_{13}&x_{13}&x_{23}&x_{23}\\\
\hline\cr\end{array}$

It is easy to see that $\succ_{d_{i}}$ is substitutable for $i=1,2$, but
$\succ_{d_{2}}$ does not fulfill LAD. Consider the following sets of contracts
$\\{x_{21},x_{22},x_{23}\\}$ and $\\{x_{21},x_{22}\\}$. We can observe that
$|C_{d_{2}}(\\{x_{21},x_{22},x_{23}\\})|=|\\{x_{23}\\}|<|\\{x_{21},x_{22}\\}|=|C_{d_{2}}(\\{x_{21},x_{22}\\})|$
contradicting the definition of LAD. Now, consider the following allocations:
$Y^{D}=\\{x_{11},x_{12},x_{23}\\},$ $Y=\\{x_{11},x_{23}\\},$
$Y^{H}=\\{x_{13},x_{21},x_{22}\\}$ and $Y^{\prime}=\\{x_{21},x_{22}\\}$. Note
that $Y,Y^{\prime}\in\mathcal{E}\setminus\mathcal{S}$ (contract $x_{12}$
blocks $Y$ and contract $x_{13}$ blocks $Y^{\prime}$), and $Y^{D}$ and $Y^{H}$
are the doctor-optimal and the hospital-optimal stable allocations
respectively. Now, we can make the following observations: (i) $Y\vee Y^{H}=Y$
showing that Theorem 4 does not hold without LAD. (ii)
$Y^{D}\succeq_{D}Y\succeq_{D}Y^{H}\succeq_{D}Y^{\prime}$ showing that
Corollary 1 does not hold without LAD. (iii) Consider allocations $Y^{D}$ and
$Y^{\prime}$, and doctor $d_{2}$. Then,
$|\\{x_{23}\\}|=|Y^{D}_{d_{2}}|<|Y^{\prime}_{d_{2}}|=|\\{x_{21},x_{22}\\}|$
showing that Proposition 2 does not hold without LAD.

##  4 Concluding remarks

The main motivation of this paper was to provide a framework to study a re-
equilibration process for the most general two-sided model in which stability
can be guaranteed (substitutable many-to-many matching with contracts). We
accomplish this goal by introducing the concept of envy-free allocation that
in itself has a meaningful economic interpretation.

The full set of stable allocations has been computed by means of several
algorithms in the matching literature, starting from the one-to-one model all
through the many-to-many model with contracts (see McVitie and Wilson, 1971;
Irving and Leather, 1986; Martínez et al., 2004; Dworczak, 2021; Pepa Risma,
2022; Bonifacio et al., 2022, among others). An interesting future line of
research is the development of an algorithm to compute the full set of envy-
free allocations.

## Appendix

_Proof of Proposition 1._ Let $Y,Y^{\prime}\in\mathcal{E}.$

(i) In order to see that $\lambda^{Y,Y^{\prime}}\in\mathcal{E},$ we proceed in
three steps.

Step 1: $\boldsymbol{\lambda^{Y,Y^{\prime}}\in\mathcal{A}}.$ Let
$x,x^{\prime}\in\lambda^{Y,Y^{\prime}}$ with $x\neq x^{\prime}$ and let $d\in
D.$ By definition of $\lambda^{Y,Y^{\prime}}$ and propoerty (i) of $C_{d}$ we
have $x_{H}\neq x^{\prime}_{H}.$ It remains to see that
$|\lambda^{Y,Y^{\prime}}_{h}|\leq q_{h}$ for each $h\in H$. Assume there is
$h\in H$ such that $|\lambda^{Y,Y^{\prime}}_{h}|>q_{h}$. Since $Y$ and
$Y^{\prime}$ are allocations, we have that $|Y_{h}|\leq q_{h}$ and
$|Y_{h}^{\prime}|\leq q_{h}$. Therefore, there are $x,x^{\prime}\in X$ such
that $x\in\lambda^{Y,Y^{\prime}}_{h}\setminus Y_{h}^{\prime}$ and
$x^{\prime}\in\lambda^{Y,Y^{\prime}}_{h}\setminus Y_{h}$. Moreover, as
$\lambda^{Y,Y^{\prime}}_{h}\subseteq\left(Y_{h}\cup
Y^{\prime}_{h}\right)\setminus Y_{h}^{\prime},$ it follows that $x\in
Y_{h}\setminus Y_{h}^{\prime}.$ Similarly, $x^{\prime}\in
Y^{\prime}_{h}\setminus Y_{h}$. Hence, $x\neq x^{\prime}.$ Let $d=x_{D}$ and
$d^{\prime}=x^{\prime}_{D}.$ Since $x\in\lambda^{Y,Y^{\prime}}_{d}=C_{d}(Y\cup
Y^{\prime})$ and $x\notin Y^{\prime}_{h}$, by substitutability,

$x\in C_{d}(Y^{\prime}\cup\\{x\\}).$ (1)

If $x\succ_{h}x^{\prime},$ then (1) implies that doctor $d$ has justified envy
towards doctor $d^{\prime}$ at $Y^{\prime},$ contradicting that
$Y^{\prime}\in\mathcal{E}.$ Thus,

$x^{\prime}\succ_{h}x.$ (2)

Since $x^{\prime}\in\lambda^{Y,Y^{\prime}}_{d^{\prime}}=C_{d}(Y\cup
Y^{\prime})$ and $x^{\prime}\notin Y_{h}$, by substitutability,

$x^{\prime}\in C_{d^{\prime}}(Y\cup\\{x^{\prime}\\}).$ (3)

Now, (2) and (3) imply that doctor $d^{\prime}$ has justifed envy towards
doctor $d$ at $Y,$ contradicting that $Y\in\mathcal{E}.$ Therefore,
$|\lambda^{Y,Y^{\prime}}_{h}|\leq q_{h}.$ We conclude that
$\lambda^{Y,Y^{\prime}}\in\mathcal{A}.$

Step 2: $\boldsymbol{\lambda^{Y,Y^{\prime}}\in\mathcal{I}}.$ Let $d\in D.$ By
definition of $\lambda^{Y,Y^{\prime}}$ and path-independence of $C_{d},$

$C_{d}\left(\lambda^{Y,Y^{\prime}}\right)=C_{d}\left(C_{d}(Y\cup
Y^{\prime})\right)=C_{d}(Y\cup Y^{\prime})=\lambda^{Y,Y^{\prime}}_{d}.$ (4)

Now, take any $h\in H$ and any $x\in\lambda^{Y,Y^{\prime}}_{h}$. By definition
of $\lambda^{Y,Y^{\prime}}$, $x\in Y\cup Y^{\prime}$. Hence, $x\in Y$ or $x\in
Y^{\prime}$. Since both $Y$ and $Y^{\prime}$ are individually rational
allocations, $x\succ_{h}\emptyset.$ Then, by responsiveness,
$C_{h}\left(\lambda^{Y,Y^{\prime}}\right)=\lambda^{Y,Y^{\prime}}_{h}.$ This
fact together with (4) proves that $\lambda^{Y,Y^{\prime}}\in\mathcal{I}.$

Step 3: $\boldsymbol{\lambda^{Y,Y^{\prime}}\in\mathcal{E}}.$ Assume this is
not the case. Then, there is a doctor $d^{\prime}\in D$ that has justified
envy towards a doctor $d\in D$ (possibly $d=d^{\prime}$) at
$\lambda^{Y,Y^{\prime}}.$ This implies that there are
$x\in\lambda^{Y,Y^{\prime}}_{d}$ and $x^{\prime}\in
X_{d^{\prime}}\setminus\lambda^{Y,Y^{\prime}}$ such that
$x^{\prime}_{H}=x_{H}=h,$

$x^{\prime}\succ_{h}x\text{ and }x^{\prime}\in
C_{d^{\prime}}(\lambda^{Y,Y^{\prime}}\cup\\{x^{\prime}\\}).$ (5)

By definition of $\lambda^{Y,Y^{\prime}}$, $x^{\prime}\in
C_{d^{\prime}}\left(C_{d^{\prime}}\left(Y\cup
Y^{\prime}\right)\cup\\{x^{\prime}\\}\right)$ and, by path independence,

$x^{\prime}\in C_{d^{\prime}}\left(Y\cup
Y^{\prime}\cup\\{x^{\prime}\\}\right).$ (6)

Notice that $x^{\prime}\notin Y\cup Y^{\prime}.$ Otherwise, (6) implies
$x^{\prime}\in\lambda^{Y,Y^{\prime}},$ contradicting our hypothesis. Since
$x\in\lambda^{Y,Y^{\prime}}\subseteq Y\cup Y^{\prime}$, assume w.l.o.g. that
$x\in Y.$ By (6) and the substitutability of $C_{d^{\prime}}$,

$x^{\prime}\in C_{d^{\prime}}(Y\cup\\{x^{\prime}\\}).$ (7)

By (5), $x^{\prime}\succ_{h}x.$ Therefore, by (7), doctor $d^{\prime}$ has
justified envy towards doctor $d$ at $Y$ since. This contradicts that
$Y\in\mathcal{E}.$ We conclude that $\lambda^{Y,Y^{\prime}}\in\mathcal{E}.$

(ii) In order to see that $\lambda^{Y,Y^{\prime}}$ is the join of $Y$ and
$Y^{\prime}$ under the partial order $\succeq_{D}$, we proceed as follows. By
Proposition 1 (i), $\lambda^{Y,Y^{\prime}}\in\mathcal{E}.$ First, we prove
that $\lambda^{Y,Y^{\prime}}$ is an upper bound of $Y$ and $Y^{\prime}$ for
the doctors. By definition of $\lambda^{Y,Y^{\prime}}$ and path independence,

$C_{d}(\lambda^{Y,Y^{\prime}}\cup Y)=C_{d}(C_{d}(Y\cup Y^{\prime})\cup
Y)=C_{d}(Y\cup Y^{\prime}\cup Y)=C_{d}(Y\cup
Y^{\prime})=\lambda^{Y,Y^{\prime}}_{d}$

for each $d\in D$. This implies that $\lambda^{Y,Y^{\prime}}\succeq_{D}Y.$
Similarly, $\lambda^{Y,Y^{\prime}}\succeq_{D}Y^{\prime}.$ Second, we prove
that $\lambda^{Y,Y^{\prime}}$ is the join of $Y$ and $Y^{\prime}$ for the
doctors. Let $\overline{Y}\in\mathcal{E}$ such that $\overline{Y}\succeq_{D}Y$
and $\overline{Y}\succeq_{D}Y^{\prime}.$ That is,

$\overline{Y}_{d}=C_{d}(\overline{Y}\cup Y)\text{ and
}\overline{Y}_{d}=C_{d}(\overline{Y}\cup Y^{\prime})$ (8)

for each $d\in D.$ We need to show that
$\overline{Y}\succeq_{D}\lambda^{Y,Y^{\prime}}$, that is
$\overline{Y}_{d}=C_{d}(\overline{Y}\cup\lambda^{Y,Y^{\prime}})$ for each
$d\in D$. Using repeatedly path independence, (8), and the definition of
$\lambda^{Y,Y^{\prime}}$,

$\overline{Y}_{d}=C_{d}(\overline{Y}\cup Y)=C_{d}(C_{d}(\overline{Y}\cup
Y^{\prime})\cup Y)=C_{d}(\overline{Y}\cup Y^{\prime}\cup Y)=$
$C_{d}(\overline{Y}\cup C_{d}(Y^{\prime}\cup
Y))=C_{d}(\overline{Y}\cup\lambda^{Y,Y^{\prime}})$

for each $d\in D.$ Thus, $\overline{Y}\succeq_{D}\lambda^{Y,Y^{\prime}}$.
Therefore, $\lambda^{Y,Y^{\prime}}$ is the join for $Y$ and $Y^{\prime}$.
$\square$

_Proof of Theorem 1._ First, by Proposition 1 (ii), the set of envy-free
allocations $\mathcal{E}$ forms a join-semilattice under the partial order
$\succeq_{D}$.888A partially ordered set $\mathcal{L}$ is called a join-
semilattice if any two elements in $\mathcal{L}$ have a join. If any two
elements in $\mathcal{L}$ also have a meet, then $\mathcal{L}$ is called a
lattice (see Stanley, 2011, for more details). Second, the empty allocation
$Y^{\emptyset}$ in which all hospitals have their positions unfilled (that is
by definition an envy-free allocation) is the minimum element of $\mathcal{E}$
under the partial order $\succeq_{D}$. To see this, let $Y\in\mathcal{E}$.
Since $Y_{d}=C_{d}(Y\cup Y^{\emptyset})$ for each $d\in D$, it follows that
$Y=Y\vee Y^{\emptyset}$. Thus, $Y\succeq_{D}Y^{\emptyset}$ for each
$Y\in\mathcal{E}.$ Finally, given that the set of envy-free allocations is
finite and is a join-semilattice with a minimum element, it follows that the
set of envy-free allocations forms a lattice under the partial order
$\succeq_{D}$ (see Stanley, 2011, for more details). $\square$

_Proof of Theorem 2._ Let $Y\in\mathcal{E}.$

  1. (i)

In order to see that $\mathcal{T}^{Y}\in\mathcal{E},$ we proceed in three
steps.

Step 1: $\boldsymbol{\mathcal{T}^{Y}\in\mathcal{A}}$. We need to show that

$\text{ for distinct }x,x^{\prime}\in\mathcal{T}^{Y},x_{D}\neq
x^{\prime}_{D}\text{ or }x_{H}\neq x^{\prime}_{H},$ (9)

and

$|\mathcal{T}^{Y}_{h}|\leq q_{h}\text{ for each }h\in H.$ (10)

If there are distinct $x,x^{\prime}\in\mathcal{T}^{Y}$ such that $x_{D}\neq
x^{\prime}_{D}$ we are done, so assume $x_{D}=x^{\prime}_{D}=d$. Since
$x,x^{\prime}\in C_{d}\left(Y\cup\mathcal{B}_{d}^{Y}\right),$ by definition of
$C_{d}$, $x_{H}\neq x^{\prime}_{H}.$ This proves (9). To see (10), assume
otherwise. Then, there is $h\in H$ such that $|\mathcal{T}^{Y}_{h}|>q_{h}.$
Since $Y\in\mathcal{A}$, we have that $|Y_{h}|\leq q_{h}.$ Hence, there is
$x\in\mathcal{T}^{Y}_{h}\setminus Y_{h}$. Let $d=x_{D}.$ Then
$x\in\mathcal{T}^{Y}_{d}$ and, as
$\mathcal{T}^{Y}_{d}=C_{d}\left(Y\cup\mathcal{B}_{d}^{Y}\right)\subseteq
Y\cup\mathcal{B}_{d}^{Y},$ $x\in\mathcal{B}_{d}^{Y}$ because $x\notin Y.$
Hence, $x$ is a blocking contract for $Y$, i.e.

$x\in C_{d}\left(Y\cup\\{x\\}\right)\text{ and }x\in
C_{h}\left(Y\cup\\{x\\}\right)$ (11)

Now, we claim $|Y_{h}|<q_{h}.$ Assume otherwise that $|Y_{h}|=q_{h}$. Since
$x$ is a blocking contract for $Y,$ there is $x^{\prime}\in Y$ with
$x_{H}=x^{\prime}_{H}=h$ such that
$\left(Y_{h}\setminus\\{x^{\prime}\\}\right)\cup\\{x\\}\succ_{h}Y_{h},$ and,
by responsiveness, this happens if and only if

$x\succ_{h}x^{\prime}.$ (12)

Thus, by (11) and (12) $d$ has justified envy towards doctor $x^{\prime}_{D}$
at $Y$. This contradicts that $Y\in\mathcal{E}$. Then, $|Y_{h}|<q_{h},$
proving our claim. Furthermore, since $|Y_{h}|<q_{h}$ and we assume that
$|\mathcal{T}^{Y}_{h}|>q_{h}$, there is $\widetilde{x}\in X$ such that
$\widetilde{x}\neq x$ and $\widetilde{x}\in\mathcal{T}^{Y}_{h}\setminus
Y_{h}.$ Let $d^{\prime}=\widetilde{x}_{D}.$ Then
$\widetilde{x}\in\mathcal{T}^{Y}_{d^{\prime}}$ and, as
$\mathcal{T}^{Y}_{d^{\prime}}=C_{d^{\prime}}\left(Y\cup\mathcal{B}_{d^{\prime}}^{Y}\right)\subseteq
Y\cup\mathcal{B}_{d^{\prime}}^{Y},$
$\widetilde{x}\in\mathcal{B}_{d^{\prime}}^{Y}$ because $\widetilde{x}\notin
Y.$ Remember that $x\in\mathcal{B}_{d}^{Y}$, thus $x\succ_{h}y$ for each
blocking contract $y$ for $Y$ such that $h=y_{H}$. In particular,
$x\succ_{h}\widetilde{x}.$ Then $\widetilde{x}\notin\mathcal{B}_{\star}^{Y},$
contradicting that $\widetilde{x}\in\mathcal{B}^{Y}_{d^{\prime}}.$ Therefore,
(10) holds. We conclude that $\mathcal{T}^{Y}\in\mathcal{A}.$

Step 2: $\boldsymbol{\mathcal{T}^{Y}\in\mathcal{I}}$. Assume otherwise, then
there is $x\in\mathcal{T}^{Y}$ such that $x\notin C_{d}(\mathcal{T}^{Y})$ or
$x\notin C_{h}(\mathcal{T}^{Y})$ where $d=x_{D}$ and $h=x_{H}$. By definition
of $\mathcal{T}^{Y}$ and path independence,
$\mathcal{T}^{Y}_{d}=C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\right)=C_{d}\left(C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\right)\right)=C_{d}(\mathcal{T}^{Y}).$
Hence, $x\in\mathcal{T}^{Y}_{d}$ implies $x\in C_{d}(\mathcal{T}^{Y})$ and, by
our contradiction hypothesis, $x\notin C_{h}(\mathcal{T}^{Y}).$ Since
$C_{h}(\mathcal{T}^{Y})\subseteq\mathcal{T}^{Y}_{h}\subseteq\mathcal{T}^{Y}$,
by consistency of $C_{h}$ it follows that
$C_{h}(\mathcal{T}^{Y}_{h})=C_{h}(\mathcal{T}^{Y}).$ Hence, $x\notin
C_{h}(\mathcal{T}^{Y}_{h}).$ As $|\mathcal{T}^{Y}_{h}\setminus\\{x\\}|<q_{h},$
by Remark (1), $x\notin
C_{h}(\mathcal{T}^{Y}_{h})=C_{h}(\left(\mathcal{T}^{Y}_{h}\setminus\\{x\\}\right)\cup\\{x\\})$
is equivalent to

$\emptyset\succ_{h}x.$ (13)

The fact that $Y\in\mathcal{I}$ and (13) imply that $x\notin Y.$ Moreover, as
$\mathcal{T}^{Y}_{d}=C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\right)\subseteq
Y\cup\mathcal{B}^{Y}_{d},$ $x\in\mathcal{T}^{Y}_{d}$ implies
$x\in\mathcal{B}^{Y}_{d}$ and, therefore, $x$ is a blocking contract for $Y$.
Thus, $x\in C_{h}(Y\cup\\{x\\}).$ Notice that, by consistency of $C_{h},$ we
have $C_{h}(Y\cup\\{x\\})=C_{h}(Y_{h}\cup\\{x\\}),$ so $x\in
C_{h}(Y_{h}\cup\\{x\\}).$ There are two cases to consider. If $|Y_{h}|=q_{h},$
by Remark 1, there is a contract $y\in Y$ such that $x\succ_{h}y$. As
$Y\in\mathcal{I}$ we have $y\succ_{h}\emptyset$ and, by transitivity,
$x\succ_{h}\emptyset.$ If $|Y_{h}|<q_{h}$, by Remark 1, we also obtain
$x\succ_{h}\emptyset.$ In either case, we contradict (13). We conclude that
$\mathcal{T}^{Y}\in\mathcal{I}.$

Step 3: $\boldsymbol{\mathcal{T}^{Y}\in\mathcal{E}}$. Assume otherwise. Then,
there are $x\in\mathcal{T}^{Y}$ and $x^{\prime}\in X\setminus\mathcal{T}^{Y}$
with $x_{D}=d,$ $x^{\prime}_{D}=d^{\prime},$ and $x_{H}=x^{\prime}_{H}=h$ such
that $x^{\prime}\succ_{h}x$ and $x^{\prime}\in
C_{d^{\prime}}(\mathcal{T}^{Y}\cup\\{x^{\prime}\\}).$ By definition of
$\mathcal{T}$ and path-independence,
$C_{d^{\prime}}(\mathcal{T}^{Y}\cup\\{x^{\prime}\\})=C_{d^{\prime}}(C_{d^{\prime}}(Y\cup\mathcal{B}_{d^{\prime}}^{Y})\cup\\{x^{\prime}\\})=C_{d^{\prime}}(Y\cup\mathcal{B}_{d^{\prime}}^{Y}\cup\\{x^{\prime}\\}).$
Therefore,

$x^{\prime}\in
C_{d^{\prime}}(Y\cup\mathcal{B}_{d^{\prime}}^{Y}\cup\\{x^{\prime}\\}).$ (14)

If $x^{\prime}\in Y,$ then $x^{\prime}\in
C_{d^{\prime}}(Y\cup\mathcal{B}_{d^{\prime}}^{Y})=\mathcal{T}^{Y}_{d^{\prime}}.$
This contradicts that $x^{\prime}\in X\setminus\mathcal{T}^{Y}.$ Hence,

$x^{\prime}\in X\setminus Y.$ (15)

Furthermore, (14) and substitutability imply

$x^{\prime}\in C_{d^{\prime}}(Y\cup\\{x^{\prime}\\}).$ (16)

As $\mathcal{T}^{Y}_{d}=C_{d}(Y\cup\mathcal{B}^{Y}_{d})\subseteq
Y\cup\mathcal{B}^{Y}_{d}$ and $x\in\mathcal{T}^{Y}_{d},$ we have $x\in
Y\cup\mathcal{B}^{Y}_{d}.$ There are two cases to consider:

    1. $\boldsymbol{1}.$

$\boldsymbol{x\in Y}.$ Then, (15) and (16) together with the facts that
$x_{D}=d,$ $x^{\prime}_{D}=d^{\prime},$ $x_{H}=x^{\prime}_{H}=h,$ and
$x^{\prime}\succ_{h}x$ imply that $d^{\prime}$ has justified envy towards $d$
at $Y,$ contradicting that $Y\in\mathcal{E}.$

    2. $\boldsymbol{2}.$

$\boldsymbol{x\in\mathcal{B}^{Y}_{d}}.$ Then, $x\in\mathcal{B}^{Y}_{\star}.$
This implies that $x$ is a blocking contract for $Y$ and, as
$Y\in\mathcal{E},$ $|Y_{h}|<q_{h}.$ As $\mathcal{T}^{Y}\in\mathcal{I}$ and
$x\in\mathcal{T}^{Y},$ $x\succ_{h}\emptyset.$ Moreover, as
$x^{\prime}\succ_{h}x$ by this step’s hypothesis, it follows that
$x^{\prime}\succ_{h}\emptyset.$ This last fact together with (16) and
$|Y_{h}|<q_{h}$ imply that $x^{\prime}\in\mathcal{B}^{Y}.$ Then,
$x^{\prime}\succ_{h}x$ contradicts that $x\in\mathcal{B}^{Y}_{\star}.$

In either case we reach a contradiction. We conclude that
$\mathcal{T}^{Y}\in\mathcal{E}.$

  2. (ii)

Let $d\in D.$ By definition of $\mathcal{T}$ and path-independence,

$C_{d}(\mathcal{T}^{Y}_{d}\cup Y)=C_{d}(C_{d}(Y\cup\mathcal{B}^{Y}_{d})\cup
Y)=C_{d}(Y\cup\mathcal{B}^{Y}_{d}\cup
Y)=C_{d}(Y\cup\mathcal{B}^{Y}_{d})=\mathcal{T}_{d}^{Y}.$

Thus, $C_{d}(\mathcal{T}^{Y}_{d}\cup Y)=\mathcal{T}^{Y}_{d}.$ As $d$ is
arbitrary, $\mathcal{T}^{Y}\succeq_{D}Y.$

  3. (iii)

($\Longrightarrow$) Assume $Y\in\mathcal{E}\setminus\mathcal{S}.$ Thus,
$\mathcal{B}^{Y}_{\star}\neq\emptyset.$ Therefore, there is $d\in D$ such that
$\mathcal{B}^{Y}_{d}\neq\emptyset.$ This implies that
$\mathcal{T}^{Y}_{d}=C_{d}(Y\cup\mathcal{B}^{Y}_{d})\neq Y_{d}.$ Hence,
$\mathcal{T}^{Y}\neq Y.$

($\Longleftarrow$) Assume $Y\in\mathcal{S}.$ Thus,
$\mathcal{B}^{Y}=\emptyset.$ Therefore, $\mathcal{B}^{Y}_{d}=\emptyset$ for
each $d\in D.$ Then, by definition of $\mathcal{T},$
$\mathcal{T}^{Y}_{d}=Y_{d}$ for each $d\in D.$ Hence, $\mathcal{T}^{Y}=Y.$

$\square$

In order to prove Theorem 3, we first prove the following lemma.

###### Lemma 1

If $Y$ and $Y^{\prime}$ are two doctor envy-free allocation such that
$Y\succeq_{D}Y^{\prime}$, then
$\mathcal{T}^{Y}\succeq_{D}\mathcal{T}^{Y^{\prime}}$.

_Proof._ Let $Y,Y^{\prime}\in\mathcal{E}$ be such that
$Y\succeq_{D}Y^{\prime}$ and assume that
$\mathcal{T}^{Y}\succeq_{D}\mathcal{T}^{Y^{\prime}}$ does not hold. This
implies the existence of $d\in D$ such that

$\mathcal{T}_{d}^{Y}\neq
C_{d}\left(\mathcal{T}^{Y}\cup\mathcal{T}^{Y^{\prime}}\right).$ (17)

Using the definition of $\mathcal{T}^{Y}$ and path-independence,

$C_{d}\left(\mathcal{T}^{Y}\cup\mathcal{T}^{Y^{\prime}}\right)=C_{d}\left(C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\right)\cup
C_{d}\left(Y^{\prime}\cup\mathcal{B}^{Y^{\prime}}_{d}\right)\right)$ (18)
$=C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\cup
C_{d}\left(Y^{\prime}\cup\mathcal{B}^{Y^{\prime}}_{d}\right)\right)=C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\cup
Y^{\prime}\cup\mathcal{B}^{Y^{\prime}}_{d}\right)$ $=C_{d}\left(Y\cup
Y^{\prime}\cup\mathcal{B}^{Y}_{d}\cup\mathcal{B}^{Y^{\prime}}_{d}\right).$

Using again path-independence, it follows that

$C_{d}\left(Y\cup
Y^{\prime}\cup\mathcal{B}^{Y}_{d}\cup\mathcal{B}^{Y^{\prime}}_{d}\right)=C_{d}\left(C_{d}\left(Y\cup
Y^{\prime}\right)\cup\mathcal{B}^{Y}_{d}\cup\mathcal{B}^{Y^{\prime}}_{d}\right)$
(19)

as by hypothesis $C_{d}\left(Y\cup Y^{\prime}\right)=Y$, using (18) and (19)
we get

$C_{d}\left(\mathcal{T}^{Y}\cup\mathcal{T}^{Y^{\prime}}\right)=C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\cup\mathcal{B}^{Y^{\prime}}_{d}\right)$
(20)

Now, using the definition of $\mathcal{T}$ and (17), (19) becomes

$C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\right)\neq
C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\cup\mathcal{B}^{Y^{\prime}}_{d}\right).$
(21)

By (21), there is a contract $x\in X$ such that

$x\in
C_{d}\left(Y\cup\mathcal{B}^{Y}_{d}\cup\mathcal{B}^{Y^{\prime}}_{d}\right)$
(22)

and

$x\in\mathcal{B}^{Y^{\prime}}_{d}\setminus\left(Y\cup\mathcal{B}^{Y}_{d}\right).$
(23)

Since $Y^{\prime}\in\mathcal{E}$ and $Y^{\prime}$ has a blocking contract $x,$
$|Y^{\prime}_{h}|<q_{h}$ with $h=x_{H}$. There are two cases to consider:

  1. $\boldsymbol{1}$.

$\boldsymbol{|Y_{h}|=q_{h}}.$ Let $x^{\prime}\in Y_{h}\setminus
Y^{\prime}_{h}$ and let $d^{\prime}=x^{\prime}_{D}$. Notice that, as
$Y\succeq_{D}Y^{\prime}$, $x^{\prime}\in Y=C_{d^{\prime}}\left(Y\cup
Y^{\prime}\right).$ This, together with $x^{\prime}\in Y_{h}\setminus
Y^{\prime}_{h}$ implies, by substitutability, that

$x^{\prime}\in
C_{d^{\prime}}\left(Y^{\prime}\cup\left\\{x^{\prime}\right\\}\right).$ (24)

By (23), $x\notin Y.$ This fact together with $x^{\prime}\in Y$ imply
$x^{\prime}\neq x.$ Furthermore, by (23),

$x\succ_{h}x^{\prime}.$ (25)

Now, by (22), (23), and substitutability,

$x\in C_{d}\left(Y\cup\left\\{x\right\\}\right).$ (26)

Since $x^{\prime}\in Y,$ $x\notin Y,$ (25), and (26), it follows that $d$ has
justified envy towards $d^{\prime}$ at $Y$, contradicting that
$Y\in\mathcal{E}.$

  2. $\boldsymbol{2}$.

$\boldsymbol{|Y_{h}|<q_{h}}.$ By (22), (23), $|Y_{h}|<q_{h},$ and
substitutability, it follows that $x\in C_{d}(Y\cup\\{x\\})$ and
$x\succ_{h}\emptyset.$ Therefore, $x\in\mathcal{B}^{Y}.$ Since, by (23),
$x\notin\mathcal{B}^{Y}_{d},$ it follows that there is
$x^{\prime}\in\mathcal{B}^{Y}$ such that $x^{\prime}\succ_{h}x.$ Let
$d^{\prime}=x^{\prime}_{D}.$ Then,

$x^{\prime}\in C_{d^{\prime}}(Y\cup\\{x^{\prime}\\}).$ (27)

By consistency,
$C_{d^{\prime}}(Y\cup\\{x^{\prime}\\})=C_{d^{\prime}}(Y_{d^{\prime}}\cup\\{x^{\prime}\\}).$
As $Y\succeq_{D}Y^{\prime},$ $Y_{d^{\prime}}=C_{d^{\prime}}(Y\cup
Y^{\prime}).$ Therefore, using also path independence,

$C_{d^{\prime}}(Y\cup\\{x^{\prime}\\})=C_{d^{\prime}}(C_{d^{\prime}}(Y\cup
Y^{\prime})\cup\\{x^{\prime}\\})=C_{d^{\prime}}(Y\cup
Y^{\prime}\cup\\{x^{\prime}\\}).$

Then, $x^{\prime}\in C_{d^{\prime}}(Y\cup\\{x^{\prime}\\})$ implies
$x^{\prime}\in C_{d^{\prime}}(Y\cup Y^{\prime}\cup\\{x^{\prime}\\})$ and in
turn, by substitutability,

$x^{\prime}\in C_{d^{\prime}}(Y^{\prime}\cup\\{x^{\prime}\\}).$ (28)

As $|Y_{h}^{\prime}|<q_{h},$ by (28) we have that
$x^{\prime}\in\mathcal{B}^{Y^{\prime}}.$ Moreover, as $x^{\prime}\succ_{h}x$
we have $x\notin\mathcal{B}^{Y^{\prime}}_{\star},$ contradicting (23).

As in each case we reach a contradiction, we conclude that
$\mathcal{T}^{Y}\succeq_{D}\mathcal{T}^{Y^{\prime}}.$ $\square$

_Proof of Theorem 3._ We need to see that operator $\mathcal{T}$ verifies the
hypothesis of Tarski’s theorem. First, notice that the envy-free lattice is
finite and therefore complete. Second, by Theorem 2 (i), $\mathcal{T}$ maps
the envy-free lattice to itself. Finally, $\mathcal{T}$ is isotone by Lemma 1.
Then, by Tarski’s theorem, the set of fixed points of $\mathcal{T}$ is non-
empty and forms a lattice under $\succeq_{D}$. Moreover, by Theorem 2 (iii),
the set of fixed points of operator $\mathcal{T}$ is the set of stable
allocations. $\square$

The following two lemmata are needed to prove Theorem 4.

###### Lemma 2

Let $Y$ be an allocation. Then, $\sum_{h\in H}|Y_{h}|=\sum_{d\in D}|Y_{d}|.$

_Proof._ Let $Y$ be an allocation. Recall that $Y_{d}$ is the subset of
contracts in $Y$ that name doctor $d$ and, similarly, $Y_{h}$ is the subset of
contracts in $Y$ that name hospital $h$. Therefore, $\sum_{h\in
H}|Y_{h}|=|Y|=\sum_{d\in D}|Y_{d}|.$ $\square$

###### Lemma 3

Let $Y$ be an envy-free allocation and $Y^{\prime}$ be a stable allocation.
Then, $Y\vee Y^{\prime}$ is a stable allocation.

_Proof._ Let $Y$ be an envy-free allocation and $Y^{\prime}$ be a stable
allocation. By, Proposition 1 (i), $Y\vee Y^{\prime}\in\mathcal{E}$. Assume
that $Y\vee Y^{\prime}\notin\mathcal{S}.$ Thus, there is a blocking contract
${x}$ for $Y\vee Y^{\prime}$. Let ${h}={x}_{H}$ and $d={x}_{D}.$ Then, ${x}\in
C_{{d}}(Y\vee Y^{\prime}\cup\\{{x}\\})$, ${x}\in C_{{h}}(Y\vee
Y^{\prime}\cup\\{{x}\\}),$ and

$|(Y\vee Y^{\prime})_{{h}}|<q_{{h}}.$ (29)

By definition of $Y\vee Y^{\prime}$ and path independence, $C_{{d}}(Y\vee
Y^{\prime}\cup\\{{x}\\})=C_{{d}}(C_{d}(Y\cup
Y^{\prime})\cup\\{{x}\\})=C_{{d}}(Y\cup Y^{\prime}\cup\\{{x}\\}).$ Thus, $x\in
C_{{d}}(Y\cup Y^{\prime}\cup\\{{x}\\}).$ Furthermore, by substitutability,

${x}\in C_{{d}}(Y^{\prime}\cup\\{{x}\\}).$ (30)

Since $x$ is a blocking contract for $Y\vee Y^{\prime}$, Remark 1 and (29)
imply ${x}\succ_{{h}}\emptyset$. This last fact together with the stability of
allocation $Y^{\prime}$ and (30) imply that

$|Y^{\prime}_{{h}}|=q_{h}.$ (31)

(Otherwise, ${x}$ is a blocking contract for $Y^{\prime}$ which is a
contradiction). Next, we claim that there is $\widetilde{h}\in H$ such that

$|(Y\vee Y^{\prime})_{\widetilde{h}}|>|Y^{\prime}_{\widetilde{h}}|.$ (32)

Assume that (32) does not hold. Then, $|(Y\vee
Y^{\prime})_{h}|\leq|Y^{\prime}_{h}|$ for each $h\in H$. Notice that, by (29)
and (31), for ${h}\in H$ we have $|(Y\vee
Y^{\prime})_{{h}}|<|Y^{\prime}_{{h}}|.$ This implies that $\sum_{h\in
H}|(Y\vee Y^{\prime})_{h}|<\sum_{h\in H}|Y^{\prime}_{h}|.$ Thus, by Lemma 2,

$\sum_{d\in D}|(Y\vee Y^{\prime})_{d}|<\sum_{d\in D}|Y^{\prime}_{d}|.$ (33)

Furthermore, since $Y^{\prime}\subseteq Y\cup Y^{\prime}$ we have, by LAD and
the fact that $Y^{\prime}\in\mathcal{I}$,
$|Y^{\prime}_{d}|=|C_{d}(Y^{\prime})|\leq|C_{d}(Y\cup Y^{\prime})|$. This
implies that, by definition of $Y\vee Y^{\prime}$, $\sum_{d\in
D}|Y^{\prime}_{d}|\leq\sum_{d\in D}|(Y\vee Y^{\prime})_{d}|.$ This contradicts
(33), implying that (32) holds and the claim is proven. Thus, there is
$\widetilde{h}\in H$ such that $|(Y\vee
Y^{\prime})_{\widetilde{h}}|>|Y^{\prime}_{\widetilde{h}}|.$ Then, there is a
contract $\widetilde{x}\in(Y\vee Y^{\prime})\setminus Y^{\prime}$ such that
$\widetilde{x}_{H}=\widetilde{h}.$ Let $\widetilde{d}=\widetilde{x}_{D}.$
Since $Y\vee Y^{\prime}\in\mathcal{I},$ $Y\vee
Y^{\prime}=C_{\widetilde{d}}(Y\vee Y^{\prime})=C_{\widetilde{d}}(Y\vee
Y^{\prime}\cup\\{\widetilde{x}\\}).$ Therefore, $x\in Y\vee Y^{\prime}$
implies $x\in C_{\widetilde{d}}(Y\vee Y^{\prime}\cup\\{\widetilde{x}\\}).$
Furthermore, by definition of $Y\vee Y^{\prime}$ and path independence,
$\widetilde{x}\in C_{\widetilde{d}}(Y\cup Y^{\prime}\cup\\{\widetilde{x}\\})$
and, by substitutability,

$\widetilde{x}\in C_{\widetilde{d}}(Y^{\prime}\cup\\{\widetilde{x}\\}).$ (34)

Given that $Y\vee Y^{\prime}$ is an allocation, by (32) we have that
$|Y^{\prime}_{\widetilde{h}}|<|(Y\vee Y^{\prime})_{\widetilde{h}}|\leq
q_{\widetilde{h}}$. Thus, $|Y^{\prime}_{\widetilde{h}}|<q_{\widetilde{h}}$,
$\widetilde{x}\notin Y^{\prime}$, and
$\widetilde{x}\succ_{\widetilde{h}}\emptyset$ imply, by Remark 1, that

$\widetilde{x}\in C_{\widetilde{h}}(Y^{\prime}\cup\\{\widetilde{x}\\}).$ (35)

Then, (34) and (35) imply that $\widetilde{x}$ is a blocking contract for
$Y^{\prime}$, contradicting the stability of allocation $Y^{\prime}$.
Therefore, $Y\vee Y^{\prime}$ is a stable allocation. $\square$

_Proof of Theorem 4._ Let $Y\in\mathcal{E}.$ By Lemma 3, $Y\vee Y^{H}$ is a
stable allocation. By Lemma 1 and Theorem 2 (iii), $Y\vee Y^{H}\succeq_{D}Y$
implies that $Y\vee Y^{H}\succeq_{D}\mathcal{F}^{Y}$. Moreover, given that
$\mathcal{T}$ is a weakly Pareto improving operator by Theorem 2 (ii),
$\mathcal{F}^{Y}\succeq_{D}Y$. Since $Y^{H}$ is the doctors’ pessimal stable
allocation, $\mathcal{F}^{Y}\succeq_{D}Y^{H}.$ As
$\mathcal{F}^{Y}\succeq_{D}Y$ and $\mathcal{F}^{Y}\succeq_{D}Y^{H},$ by
definition of join, $\mathcal{F}^{Y}\succeq_{D}Y\vee Y^{H}$. Thus, by
antisymmetry, $\mathcal{F}^{Y}=Y\vee Y^{H}.$ $\square$

_Proof of Proposition 2._ Let $Y\in\mathcal{E}$ and $d\in D.$ By _LAD_ and
individual rationality of $Y,$ we have that
$|\mathcal{T}^{Y}_{d}|=|C_{d}(Y\cup\mathcal{B}^{Y}_{d})|\geq|C_{d}(Y)|=|Y_{d}|.$
Iterating we obtain that $|\mathcal{F}^{Y}_{d}|\geq|Y_{d}|.$ By definition,
$\mathcal{F}^{Y}$ is a fixed point of our Tarski operator. Thus,
$\mathcal{F}^{Y}$ is stable by Theorem 2 (iii). Then, by the Rural Hospital
Theorem $|\mathcal{F}^{Y}_{d}|=|Y^{\prime}_{d}|$ for each
$Y^{\prime}\in\mathcal{S}$ and each $d\in D.$ Therefore,
$|Y_{d}|\leq|\mathcal{F}^{Y}_{d}|=|Y^{\prime}_{d}|$ for each
$Y^{\prime}\in\mathcal{S}$ and each $d\in D.$ $\square$

## References

  * Adachi (2000) Adachi, H. (2000): “On a characterization of stable matchings,” _Economics Letters_ , 68, 43–49.
  * Blair (1988) Blair, C. (1988): “The lattice structure of the set of stable matchings with multiple partners,” _Mathematics of Operations Research_ , 13, 619–628.
  * Bonifacio et al. (2021) Bonifacio, A., N. Guinazu, N. Juarez, P. Neme, and J. Oviedo (2021): “The lattice of worker-quasi-stable matchings,” _arXiv preprint arXiv:2103.16330_.
  * Bonifacio et al. (2022) Bonifacio, A. G., N. Juarez, P. Neme, and J. Oviedo (2022): “Cycles to compute the full set of many-to-many stable matchings,” _Mathematical Social Sciences_ , 117, 20–29.
  * Dworczak (2021) Dworczak, P. (2021): “Deferred acceptance with compensation chains,” _Operations Research_ , 69, 456–468.
  * Echenique and Oviedo (2004) Echenique, F. and J. Oviedo (2004): “Core many-to-one matchings by fixed-point methods,” _Journal of Economic Theory_ , 115, 358–376.
  * Echenique and Oviedo (2006) ——— (2006): “A theory of stability in many-to-many matching markets,” _Theoretical Economics_ , 1, 233–273.
  * Fleiner (2003) Fleiner, T. (2003): “A fixed-point approach to stable matchings and some applications,” _Mathematics of Operations Research_ , 28, 103–126.
  * Hatfield and Milgrom (2005) Hatfield, J. and P. Milgrom (2005): “Matching with contracts,” _American Economic Review_ , 95, 913–935.
  * Hatfield and Kominers (2017) Hatfield, J. W. and S. D. Kominers (2017): “Contract design and stability in many-to-many matching,” _Games and Economic Behavior_ , 101, 78–97.
  * Irving and Leather (1986) Irving, R. and P. Leather (1986): “The complexity of counting stable marriages,” _SIAM Journal on Computing_ , 15, 655–667.
  * Martínez et al. (2004) Martínez, R., J. Massó, A. Neme, and J. Oviedo (2004): “An algorithm to compute the full set of many-to-many stable matchings,” _Mathematical Social Sciences_ , 47, 187–210.
  * McVitie and Wilson (1971) McVitie, D. and L. Wilson (1971): “The stable marriage problem,” _Communications of the ACM_ , 14, 486–490.
  * Pepa Risma (2022) Pepa Risma, E. (2022): “Matching with contracts: calculation of the complete set of stable allocations,” _Theory and Decision_ , 1–13.
  * Roth (1984) Roth, A. (1984): “The evolution of the labor market for medical interns and residents: a case study in game theory,” _Journal of Political Economy_ , 92, 991–1016.
  * Roth and Sotomayor (1990) Roth, A. and M. Sotomayor (1990): _Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis_ , Cambridge University Press.
  * Sotomayor (1999) Sotomayor, M. (1999): “Three remarks on the many-to-many stable matching problem,” _Mathematical social sciences_ , 38, 55–70.
  * Stanley (2011) Stanley, R. (2011): _Enumerative Combinatorics, vol.1_ , Cambridge University Press.
  * Tarski (1955) Tarski, A. (1955): “A lattice-theoretical fixpoint theorem and its applications,” _Pacific Journal of Mathematics_ , 5, 285–309.
  * Wu and Roth (2018) Wu, Q. and A. Roth (2018): “The lattice of envy-free matchings,” _Games and Economic Behavior_ , 109, 201–211.