A characterization of strongly stable fractional matchings

Abstract

In this paper, we characterize the strongly stable fractional matchings for the marriage model as the union of the convex hull of connected sets of stable matchings. Moreover, we present an algorithm that computes the set of matchings necessary to generate the above-mentioned connected sets. Finally, we show that the set of strongly stable fractional matchings has a lattice structure.

Appendix

Given two stable fractional matchings x and y, we say that x weakly dominates y in man $m^{\prime }s$ opinion, if

$$\begin{aligned} \sum _{j\ge _{m}w}x_{m,j}\ge \sum _{j\ge _{m}w}y_{m,j} \end{aligned}$$

for all w, which is denoted by $x\succeq _{m}y$. We also say that x strongly dominates y, $\left( x\succ _{m}y\right)$, if at least one inequality is strict. We can define domination in a woman’s opinion analogously.

Also, we say that x weakly dominates y in man $m^{\prime }s$ opinion under a profile of reduced lists $P^{\mu }$, if

$$\begin{aligned} \sum _{j\ge ^{\mu }_{m}w}x_{m,j}\ge \sum _{j\ge ^{\mu }_{m}w}y_{m,j} \end{aligned}$$

for all $w\in {P^{\mu }(m)}$, which is denoted by $x\succeq ^{\mu }_{m}y$. We also say that x strongly dominates y, $\left( x\succ ^{\mu } _{m}y\right)$, if at least one inequality is strict. We can define domination in a woman’s opinion under a profile of reduced lists, in the same way.

A partial order $\succeq _{M}$ can be defined on the set of stable fractional matchings where $x\succeq _{M}y$, if $x\succeq _{m}y$ for each $m\in M$. That is, $x\succeq _{M}y$, meaning that x weakly dominates y in every man’s opinion. This also applies for $\succeq ^{\mu }_{M}$ in the reduced preference lists $P^{\mu }$. In the same way, we can define domination in every woman’s opinion ($\succeq _{W}$ and $\succeq ^{\mu }_{W}$).

Remark 3

Let x be a stable fractional matching in the matching model $\left( M,W,P\right)$. Since x is a convex combination of stable matchings, then $x^{\mu _{M}}\succeq _{M}x\succeq _{M}x^{\mu _{W}}$ and $x^{\mu _{W}}\succeq _{W}x\succeq _{W}x^{\mu _{M}}$. Moreover, if x is a stable fractional matching for the matching model $\left( M,W,P^{\mu }\right)$, then $x^{\mu }\succeq _{M}x\succeq _{M}x^{\mu _{W}}$ and $x^{\mu _{W}}\succeq _{W}x\succeq _{W}x^{\mu }$. This follows from Lemma 1, which means that each stable matching for the matching model $\left( M,W,P^{\mu }\right)$ is also a stable matching for the matching model $\left( M,W,P\right)$.

Lemma 6

Let (M, W, P) be a matching model. Let $\mu \in S\left( P\right)$, and $P^{\mu }$ be the reduced lists. Let ${\bar{x}}$ be a stable fractional matching in the matching model (M, W, P). If ${\bar{x}}$ is strongly stable for the matching model $\left( M,W,P^{\mu }\right)$, then ${\bar{x}}$ is strongly stable for the matching model $\left( M,W,P\right)$.

Proof

Let $\left( M,W,P\right)$ be a matching model. Let $\mu \in S\left( P\right)$, and $P^{\mu }$ be the reduced lists. Let ${\bar{x}}$ be a stable fractional matching in the matching model (M, W, P) and let us assume that ${\bar{x}}$ is strongly stable in $\left( M,W,P^{\mu }\right)$. Hence:

$$\begin{aligned} \left[ 1-\sum _{j\ge _{m}^{\mu }w}{\bar{x}}_{m,j}\right] \cdot \left[ 1-\sum _{i\ge _{w}^{\mu }m}{\bar{x}}_{i,w}\right] =0 \end{aligned}$$

holds for each $\left( m,w\right) \in A\left( P^{\mu }\right)$. Then, we will prove that

$$\begin{aligned} \left[ 1-\sum _{j\ge _{m}w}{\bar{x}}_{m,j}\right] \cdot \left[ 1-\sum _{i\ge _{w} m}{\bar{x}}_{i,w}\right] =0 \end{aligned}$$

holds for each $\left( m,w\right) \in A\left( P\right)$, as well.

We will consider the following cases:

• (i) Let $\left( m,w\right) \in A\left( P^{\mu }\right)$. That is, $\left( m,w\right)$ was not eliminated in $P^{\mu }$. Therefore

  $$\begin{aligned} \sum _{j\ge _{m}w}{\bar{x}}_{m,j}\ge \sum _{j\ge _{m}^{\mu }w}{\bar{x}}_{m,j} \end{aligned}$$

  holds, since for each man m, there are more women in his original list of preferences than in his reduced list of preferences.

  Hence,

  $$\begin{aligned} 1-\sum _{j\ge _{m}w}{\bar{x}}_{m,j}\le 1-\sum _{j\ge _{m}^{\mu }w}{\bar{x}}_{m,j}. \end{aligned}$$

  With a similar argument, we have the following:

  $$\begin{aligned} 1-\sum _{i\ge _{w}m}{\bar{x}}_{i,w}\le 1-\sum _{i\ge _{w}^{\mu }m}{\bar{x}}_{i,w}. \end{aligned}$$

  By hypothesis and constraints (1) and (2) in (LP):

  $$\begin{aligned} 0= & {} \left[ 1-\sum _{j\ge _{m}^{\mu }w}{\bar{x}}_{m,j}\right] \cdot \left[ 1-\sum _{i\ge _{w}^{\mu }m}{\bar{x}}_{i,w}\right] \\\ge & {} \left[ 1-\sum _{j\ge _{m}w} {\bar{x}}_{m,j}\right] \cdot \left[ 1-\sum _{i\ge _{w}m}{\bar{x}}_{i,w}\right] \ge 0. \end{aligned}$$

  Then, for $\left( m,w\right) \in A\left( P^{\mu }\right)$

  $$\begin{aligned} \left[ 1-\sum _{j\ge _{m}w}{\bar{x}}_{m,j}\right] \cdot \left[ 1-\sum _{i\ge _{w} m}{\bar{x}}_{i,w}\right] =0. \end{aligned}$$

• (ii) Let $\left( m,w\right) \in A\left( P\right) -A\left( P^{\mu }\right)$. Considering that $\left( m,w\right)$ was eliminated in $P^{\mu }$, we analyze three cases separately:

  • (a) If $w>_{m}\mu (m)$.

    Since $x^{\mu }\succeq _{M}{\bar{x}}$, then

    $$\begin{aligned} \sum _{j>_{m}w}{\bar{x}}_{m,j}\le \sum _{j>_{m}w}x_{m,j}^{\mu }=0. \end{aligned}$$

    (14)

    As ${\bar{x}}$ is a stable fractional matching in (M, W, P), constraints (2) and (3) of (LP) hold, and by (14), we have $\sum _{i\ge _{w} m}{\bar{x}}_{i,w}=1$. Then:

    $$\begin{aligned} \left[ 1-\sum _{j\ge _{m}w}{\bar{x}}_{m,j}\right] \cdot \left[ 1-\sum _{i\ge _{w} m}{\bar{x}}_{i,w}\right] =0. \end{aligned}$$

  • (b) If $w<_{m}\mu _{W}(m)$.

    Since ${\bar{x}}$ is a stable fractional matching, we have that ${\bar{x}}$ is a convex combination of stable matchings. Then, ${\bar{x}}\succeq _{M}x^{\mu _{W}}$ holds by Remark 3. Therefore, we also have that $\sum _{j\ge _{m}w}{\bar{x}}_{m,j} \ge \sum _{j\ge _{m}w}x_{m,j}^{\mu _{W}}=1$. Then:

    $$\begin{aligned} \left[ 1-\sum _{j\ge _{m}w}{\bar{x}}_{m,j}\right] \cdot \left[ 1-\sum _{i\ge _{w} m}{\bar{x}}_{i,w}\right] =0. \end{aligned}$$

  • (c) If $\mu (m)>_{m}w>_{m}\mu _{W}(m)$.

    Since $\left( m,w\right) \not \in A\left( P^{\mu }\right)$, man m was eliminated by woman w in $P^{\mu }$. If $m>_{w}\mu (w)$, then (m, w) is a blocking pair for the stable matching $\mu _{W}$, and this is a. Hence, $\mu (w)>_{w}m$.

    Since ${\bar{x}}\succeq _{W}x^{\mu }$ by Remark 3, we have $\sum _{i\ge _{w}m}{\bar{x}}_{i,w}\ge \sum _{i\ge _{w}m}x_{i,w}^{\mu }=x^{\mu }_{\mu (w),w}=1$. Using constraint $\left( 2\right)$ of (LP) we have that

    $$\begin{aligned} \sum _{i\ge _{w}m}{\bar{x}}_{i,w}=1; \end{aligned}$$

    then

    $$\begin{aligned} \left[ 1-\sum _{j\ge _{m}w}{\bar{x}}_{m,j}\right] \cdot \left[ 1-\sum _{i\ge _{w} m}{\bar{x}}_{i,w}\right] =0. \end{aligned}$$

From cases (i) and (ii), we conclude that ${\bar{x}}$ is strongly stable in $\left( M,W,P\right)$. $\square$

Proof of Claim

We need to prove that there is a pair $({\bar{m}},{\bar{w}})\in {A(P^{\mu _{{\bar{x}}}})}$, such that $\mu _{{\bar{x}}}({\bar{m}})>_{{\bar{m}}}{\bar{w}}>_{{\bar{m}}}\mu ^{l}({\bar{m}})$ and $\mu ^{l}({\bar{w}})>_{{\bar{w}}}{\bar{m}}>_{{\bar{w}}}\mu _{{\bar{x}}}({\bar{w}})$.

To prove $\mu _{{\bar{x}}}({\bar{m}})>_{{\bar{m}}}{\bar{w}}>_{{\bar{m}}}\mu ^{l}({\bar{m}})$, we will analyze two cases:

• (i) Assume that there exists ${\bar{\sigma }}\in {{\varPhi }(\mu _{{\bar{x}}})}$ and ${\bar{m}}\in {{\bar{\sigma }}}$, such that $\mu _{{\bar{x}}}[{\bar{\sigma }}]({\bar{m}})>_{{\bar{m}}}\mu ^{l}({\bar{m}})$. Let ${\bar{w}}=\mu _{{\bar{x}}}[{\bar{\sigma }}]({\bar{m}})$. Then, $({\bar{m}},{\bar{w}})\in {A(P^{\mu _{{\bar{x}}}})}$. Since ${\bar{m}}\in {{\bar{\sigma }}}$, we have that $\mu _{{\bar{x}}}({\bar{m}})>_{{\bar{m}}}\mu _{{\bar{x}}}[{\bar{\sigma }}]({\bar{m}})$. Hence, for $({\bar{m}},{\bar{w}})\in {A(P^{\mu _{{\bar{x}}}})}$, we have that $\mu _{{\bar{x}}}({\bar{m}})>_{{\bar{m}}}{\bar{w}}>_{{\bar{m}}}\mu ^{l}({\bar{m}})$.

• (ii) If not, for all $\sigma \in {{\varPhi }(\mu _{{\bar{x}}})}$ and for all man $m\in {{\bar{\sigma }}}$, we have that $\mu _{{\bar{x}}}[{\bar{\sigma }}](m)=\mu ^{l}(m)$. Let $M_{0}=\{m\in {M}:m\in {{\bar{\sigma }}} \text{ for } \text{ some } {\bar{\sigma }}\in {{\varPhi }(\mu _{{\bar{x}}})}\}$. Then, there exists a pair $({\bar{m}},{\bar{w}})\in {A(P^{\mu _{{\bar{x}}}})}$, such that ${\bar{m}}\in {M\setminus M_{0}}$ and $\mu _{{\bar{x}}}({\bar{m}})>_{{\bar{m}}}{\bar{w}}>_{{\bar{m}}}\mu ^{l}({\bar{m}})$. If not, for each $m'\in {M\setminus M_{0}}$, there is no acceptable woman $w'$ such that $\mu _{{\bar{x}}}(m')>_{m'}w'>_{m'}\mu ^{l}(m')$. That is, for each $m'\in {M\setminus M_{0}}$, either we have that $\mu _{{\bar{x}}}(m')=\mu ^{l}(m')$, or $\mu ^{l}(m')$ is the second woman in the reduced preference list of man $m'$. Then $\mu ^{l}\in {{\mathcal {M}}_{\mu _{{\bar{x}}}}}$, which results in a contradiction. Then, we have that there exists a pair $({\bar{m}},{\bar{w}})\in {A(P^{\mu _{{\bar{x}}}})}$, such that ${\bar{m}}\in {M\setminus M_{0}}$ and $\mu _{{\bar{x}}}({\bar{m}})>_{{\bar{m}}}{\bar{w}}>_{{\bar{m}}}\mu ^{l}({\bar{m}})$.

Now, we will prove $\mu ^{l}({\bar{w}})>_{{\bar{w}}}{\bar{m}}>_{{\bar{w}}}\mu _{{\bar{x}}}({\bar{w}})$. By the stability of $\mu ^{l}$, we have that $\mu ^{l}({\bar{w}})>_{{\bar{w}}}{\bar{m}}$. We only need to prove that ${\bar{m}}>_{{\bar{w}}}\mu _{{\bar{x}}}({\bar{w}})$. If $\mu _{{\bar{x}}}({\bar{w}})>_{{\bar{w}}}{\bar{m}}$, then in step 2 of the reduction procedure, ${\bar{m}}$ will be eliminated by woman ${\bar{w}}$ from her reduced preference list, $P^{\mu _{{\bar{x}}}}({\bar{w}})$. Hence, in step 3, the man ${\bar{m}}$ will eliminate woman ${\bar{w}}$ from his reduced preference list, which results in a contradiction of the existence of the pair $({\bar{m}},{\bar{w}})\in A(P^{\mu _{{\bar{x}}}})$. Then, $\mu ^{l}({\bar{w}})>_{{\bar{w}}}{\bar{m}}>_{{\bar{w}}}\mu _{{\bar{x}}}({\bar{w}})$. $\square$