Non-uniformly Stable Matchings^††thanks: This work was supported by JST ERATO Grant Number JPMJER2301, Japan.

In the one-to-one setting, Irving [7] proposed polynomial-time algorithms for the super-stable matching problem and the strongly stable matching problem (see also [23]). Kunysz, Paluch, and Ghosal [21] considered a characterization of the set of all strongly stable matchings. Kunysz [19] considered the weighted version of the strongly stable matching problem. In the many-to-one setting, Irving, Manlove, and Scott [8] proposed a polynomial-time algorithm for the super-stable matching problem. Furthermore, Irving, Manlove, and Scott [9] and Kavitha, Mehlhorn, Michail, and Paluch [17] proposed polynomial-time algorithms for the strongly stable matching problem. In the many-to-many setting, Scott [33] considered the super-stable matching problem, and the papers [1, 20, 22] considered the strongly stable matching problem. Olaosebikan and Manlove [28, 29] considered super-stability and strong stability in the student-project allocation problem. Furthermore, Kamiyama [15, 16] considered strong stability and super-stability under matroid constraints. Strong stability and super-stability with master lists were considered in, e.g., [10, 13, 14, 30].

Throughout this paper, we are given a finite simple undirected bipartite graph $G=(V,E)$ such that the vertex set $V$ of $G$ is partitioned into $V_{1}$ and $V_{2}$, and every edge in the edge set $E$ of $G$ connects a vertex in $V_{1}$ and a vertex in $V_{2}$. In addition, we are given subsets $E_{1},E_{2}\subseteq E$ such that $E_{1}\cap E_{2}=\emptyset$ and $E_{1}\cup E_{2}=E$. In this paper, we do not distinguish between an edge $e\in E$ and the set consisting of the two end vertices of $e$. For each edge $e\in E$, if we write $e=(v,w)$, then this means that $e\cap V_{1}=\{v\}$ and $e\cap V_{2}=\{w\}$.

For each subset $F\subseteq E$ and each vertex $v\in V$, let $F(v)$ denote the set of edges $e\in F$ such that $v\in e$. Thus, $E(v)$ denotes the set of edges in $E$ incident to $v$. A subset $\mu\subseteq E$ is called a matching in $G$ if $|\mu(v)|\leq 1$ for every vertex $v\in V$. For each matching $\mu$ in $G$ and each vertex $v\in V$ such that $|\mu(v)|=1$, we do not distinguish between $\mu(v)$ and the element in $\mu(v)$. For each subset $F\subseteq E$, a matching $\mu$ in $G$ is called a matching in $F$ if $\mu\subseteq F$. Furthermore, for each subset $F\subseteq E$, a matching $\mu$ in $F$ is called a maximum-size matching in $F$ if $|\mu|\geq|\sigma|$ for every matching $\sigma$ in $F$.

For each vertex $v\in V$, we are given a transitive and complete binary relation $\succsim_{v}$ on $E(v)\cup\{\emptyset\}$ such that $e\succsim_{v}\emptyset$ and $\emptyset\not\succsim_{v}e$ for every edge $e\in E(v)$. (In this paper, the completeness of a binary relation means that, for every pair of elements $e,f\in E(v)\cup\{\emptyset\}$, at least one of $e\succsim_{v}f$ and $f\succsim_{v}e$ holds.) For each vertex $v\in V$ and each pair of elements $e,f\in E(v)\cup\{\emptyset\}$, if $e\succsim_{v}f$ and $f\not\succsim_{v}e$ (resp. $e\succsim_{v}f$ and $f\succsim_{v}e$), then we write $e\succ_{v}f$ (resp. $e\sim_{v}f$). Intuitively speaking, $e\succ_{v}f$ means that $v$ prefers $e$ to $f$, and $e\sim_{v}f$ means that $v$ is indifferent between $e$ and $f$.

Let $\mu$ be a matching in $G$. For each edge $e\in E\setminus\mu$, we say that $e$ weakly blocks $\mu$ if $e\succsim_{v}\mu(v)$ for every vertex $v\in e$. Furthermore, for each edge $e\in E\setminus\mu$, we say that $e$ strongly blocks $\mu$ if $e\succsim_{v}\mu(v)$ for every vertex $v\in e$ and there exists a vertex $w\in e$ such that $e\succ_{w}\mu(w)$. Then $\mu$ is said to be non-uniformly stable if the following two conditions are satisfied.

(S1)

Any edge $e\in E_{1}\setminus\mu$ does not weakly block $\mu$.

(S2)

Any edge $e\in E_{2}\setminus\mu$ does not strongly block $\mu$.

If $E_{1}=E$, then non-uniform stability is equivalent to super-stability. Furthermore, if $E_{2}=E$, then non-uniform stability is equivalent to strong stability. Thus, non-uniform stability is a common generalization of super-stability and strong stability. For simplicity, we may say that an edge $e\in E\setminus\mu$ blocks $\mu$ if the following condition is satisfied. If $e\in E_{1}$, then $e$ weakly blocks $\mu$. Otherwise (i.e., $e\in E_{2}$), $e$ strongly blocks $\mu$.

Let $F$ be a subset of $E$. Let $i$ be an integer in $\{1,2\}$. Then we define the characteristic vector $\chi_{F}\in\{0,1\}^{E}$ of $F$ by $\chi_{F}(e):=1$ for each edge $e\in F$ and $\chi_{F}(e):=0$ for each edge $e\in E\setminus F$. For each subset $X\subseteq V$, we define $X(F)$ as the set of vertices $v\in X$ such that $F(v)\neq\emptyset$. Thus, for each integer $i\in\{1,2\}$, $V_{i}(F)$ denotes the set of vertices $v\in V_{i}$ such that $F(v)\neq\emptyset$. For each subset $X\subseteq V_{i}$, we define $F(X):=\bigcup_{v\in X}F(v)$. For each subset $X\subseteq V_{i}$, we define $\Gamma_{F}(X)$ as the set of vertices $v\in V_{3-i}$ such that $F(X)\cap E(v)\neq\emptyset$. That is, $\Gamma_{F}(X)$ is the set of vertices in $V_{3-i}$ adjacent to a vertex in $X$ via an edges in $F$. For each vertex $v\in V$, we use $\Gamma_{F}(v)$ instead of $\Gamma_{F}(\{v\})$. Define the real-valued function $\rho_{i,F}$ on $2^{V_{i}(F)}$ by $\rho_{i,F}(X):=|\Gamma_{F}(X)|-|X|$ for each subset $X\subseteq V_{i}(F)$. It is not difficult to see that, for every pair of subsets $X,Y\subseteq V_{i}(F)$,

i.e., $\rho_{i,F}$ is submodular. Then it is known that there exists the unique (inclusion-wise) minimal minimizer of $\rho_{i,F}$, and we can find it in polynomial time (see, e.g., [27, Note 10.12]). In addition, it is known that there exists a matching $\mu$ in $F$ such that $|\mu|=|V_{i}(F)|$ if and only if, for every subset $X\subseteq V_{i}(F)$, $|X|\leq|\Gamma_{F}(X)|$ holds [4] (see also [32, Theorem 16.7]).

Let $v$ be a vertex in $V$. Then, for each edge $e\in E(v)$ and each symbol $\odot\in\{\succ_{v},\succsim_{v},\sim_{v}\}$, we define $E[\mathop{\odot}e]$ as the set of edges $f\in E(v)$ such that $f\odot e$. Furthermore, for each edge $e\in E(v)$ and each symbol $\odot\in\{\succ_{v},\succsim_{v}\}$, we define $E[e\mathop{\odot}]$ as the set of edges $f\in E(v)$ such that $e\odot f$.

Let $F$ be a subset of $E$. A sequence $(v_{1},v_{2},\dots,v_{k})$ of distinct vertices in $V$ is called a path in $F$ if $\{v_{i},v_{i+1}\}\in F$ for every integer $i\in[k-1]$. A sequence $(v_{1},v_{2},\dots,v_{k+1})$ of vertices in $V$ is called a cycle in $F$ if $(v_{1},v_{2},\dots,v_{k})$ is a path in $F$, $v_{1}=v_{k+1}$, and $\{v_{k},v_{1}\}\in F$.

In this subsection, we prove Lemma 4.

An edge $e\in E$ is called a bad edge if $e\in{\sf R}_{k}$ and there exists a non-uniformly stable matching $\sigma$ in $G$ such that $e\in\sigma$. If there does not exist a bad edge in $E$, then the proof is done. Thus, we assume that there exists a bad edge in $E$. Then we define $\Delta$ as the set of integers $t\in[k]$ such that ${\sf R}_{t}\setminus{\sf R}_{t-1}$ contains a bad edge in $E$. Furthermore, we define $z$ as the minimum integer in $\Delta$. We divide the proof into the following two cases.

Case 1.

There exists an integer $i\in[i_{z}]$ such that ${\sf P}_{z,i}\setminus{\sf P}_{z,i-1}$ contains a bad edge in $E$.

Case 2.

${\sf P}_{z,i_{z}}\setminus{\sf R}_{z-1}$ does not contain a bad edge in $E$.

Case 1. Define $q$ as the minimum integer in $[i_{z}]$ such that ${\sf P}_{z,q}\setminus{\sf P}_{z,q-1}$ contains a bad edge in $E$. Let $f=(v,w)$ be a bad edge in $E$ that is contained in ${\sf P}_{z,q}\setminus{\sf P}_{z,q-1}$. Then there exists a non-uniformly stable matching $\sigma$ in $G$ such that $f\in\sigma$. If $\sigma\cap{\sf P}_{z,q-1}\neq\emptyset$, then this contradicts the minimality of $q$. Thus, $\sigma\subseteq E\setminus{\sf P}_{z,q-1}$.

First, we consider the case where $f\in{\sf Q}_{z,q}$. The definition of Algorithm 1 implies that there exists an edge $g=(u,w)\in{\rm Ch}_{1}(E\setminus{\sf P}_{z,q-1})$ satisfying one of the following conditions.

• •

  $g\succ_{w}f$.

• •

  $g\sim_{w}f$, $g\neq f$, and $g\in E_{1}$.

Furthermore, since $\sigma\subseteq E\setminus{\sf P}_{z,q-1}$, $g\succsim_{u}\sigma(u)$. Thus, $g$ blocks $\sigma$. This is a contradiction.

Next, we consider the case where $f\in L_{z,q}(N_{z,q})$. In this case, ${\sf Q}_{z,q}=\emptyset$. For simplicity, we define $L:=L_{z,q}$ and $N:=N_{z,q}$. Since ${\sf Q}_{z,q}=\emptyset$, $L={\rm Ch}_{1}(E\setminus{\sf P}_{z,q-1})$.

Let $v$ be a vertex in $N$ satisfying the conditions in Claim 1. Furthermore, let $w$ be a vertex in $\Gamma_{L}(v)$ such that $\sigma(w)\in L$. Let $e$ be the edge in $L$ such that $e=(v,w)$. Since $e,\sigma(w)\in L$, we have $e\sim_{w}\sigma(w)$. Since ${\sf P}_{z,q-1}$ does not contain a bad edge in $E$, $\sigma(v)\in E\setminus{\sf P}_{z,q-1}$.

Claim 2 implies that $e$ blocks $\sigma$. This contradicts the fact that $\sigma$ is non-uniformly stable.

Case 2. In this case, $\mu_{z,i_{z}}(w_{z})$ is a bad edge in $E$. Thus, there exists a non-uniformly stable matching $\sigma$ in $G$ such that $\mu_{z,i_{z}}(w_{z})\in\sigma$. Since ${\sf P}_{z,i_{z}}$ does not contain a bad edge in $E$, we have $\sigma\cap{\sf P}_{z,i_{z}}=\emptyset$ and $e_{z}\notin\sigma$. Since $e_{z}$ blocks $\mu_{z,i_{z}}$, if $\mu_{z,i_{z}}(v_{z})\succsim_{v_{z}}\sigma(v_{z})$, then $e_{z}$ blocks $\sigma$. Since

and $\sigma\subseteq E\setminus{\sf P}_{z,i_{z}}$, we have $\mu_{z,i_{z}}(v_{z})\succsim_{v_{z}}\sigma(v_{z})$. This completes the proof.

In this proof, we fix an extreme point $x$ of ${\bf S}$. Then we prove that there exists a non-uniformly stable matching $\mu$ in $G$ such that $\chi_{\mu}=x$. The following lemma implies that it is sufficient to prove that $x\in\{0,1\}^{E}$.

In the rest of this proof, we prove that $x\in\{0,1\}^{E}$.

Define ${\sf supp}$ as the set of edges $e\in E$ such that $x(e)>0$. For each vertex $v\in V$ such that ${\sf supp}(v)\neq\emptyset$, we define ${\sf T}(v)$ (resp. ${\sf B}(v)$) as the set of edges $e\in{\sf supp}(v)$ such that $e\succsim_{v}f$ (resp. $f\succsim_{v}e$) for every edge $f\in{\sf supp}(v)$. For each integer $i\in\{1,2\}$, we define $S_{i}$ as the set of vertices $v\in V_{i}$ such that ${\sf supp}(v)\neq\emptyset$. For each integer $i\in\{1,2\}$, we define $F_{i}:=\bigcup_{v\in S_{i}}{\sf T}(v)$. It should be noted that $S_{i}=V_{i}(F_{i})$.