安定結婚問題(stable marriage problem)とは、$n$ 人ずつの男女が異性全員に狭義の順位を付けているとき、互いに今の相手より相手を好む男女の組(不安定な組)がないように全員を 1 対 1 に組にする問題である。男性が順に申し込み女性が良いほうを保留する受け入れ保留方式(Gale–Shapley)は、申し込みの順によらず $n^2-n+1$ 回以下の申し込みで止まり、男性全員に最良で女性全員に最悪の安定マッチングを返す。安定マッチングの全体は分配束をなし、申し込む側は順位を偽っても得をしないが、申し込まれる側は得をすることがある。
安定結婚問題(stable marriage problem)は、$n$ 人の男性と $n$ 人の女性がそれぞれ異性全員に順位を付けているとき、どの 2 人も「互いに今の相手より相手を好む」ことがないように全員を 1 対 1 に組にせよ、という問題である。このような組分けを 安定マッチング という。安定マッチングは必ず存在し、受け入れ保留方式(Gale–Shapley のアルゴリズム)で $n^2-n+1$ 回以下の申し込みで見つかる。この方式は Gale と Shapley が導入した(KP17 p. 186 の注)。
安定マッチングは一般に 1 つではない。受け入れ保留方式は、申し込む側の全員にとって最良で、申し込まれる側の全員にとって最悪の安定マッチングを返す。申し込む側は順位を偽っても得をしないが、申し込まれる側は得をすることがある。研修医と病院の割り当てや、学校の選択の制度は、この理論を土台にしている。
この記事では、問題を定式化し、受け入れ保留方式が止まって安定マッチングを返すこと、申し込む側に最適であることを完全に証明する。続いて、安定マッチングの全体が「男性ごとに良い方をとる」操作で閉じていること、申し込む側が偽っても得をしないことを証明し、条件を外したときの反例を挙げる。
以下、$M=\{m_1,\dots,m_n\}$ を男性の集合、$W=\{w_1,\dots,w_n\}$ を女性の集合とする($n\ge1$)。男性・女性という呼び名は 2 つの側を区別するための慣用で、学生と学校、研修医と病院などに読み替えてよい。
各男性 $m$ は $W$ の上の 全順序(狭義の順位)$\succ_m$ をもち、各女性 $w$ は $M$ の上の全順序 $\succ_w$ をもつとする。$a\succ_m b$ を「$m$ は $a$ を $b$ より好む」と読み、$a\succeq_m b$ は「$a\succ_m b$ または $a=b$」を表す。
$\mu$ は完全 二部グラフ $K_{n,n}$ の完全マッチングと同じものである。安定性は辺の集合だけでなく順位にもよる条件であり、マッチングの大きさを最大にする問題とは別の問題である。
この記事の結論が成り立つのは、次の条件のもとである。
ある安定マッチング $\mu$ で $\mu(m)=w$ となるとき、$w$ は $m$ にとって 到達可能、$m$ は $w$ にとって到達可能であるという。安定マッチング $\mu$ が 男性最適 であるとは、すべての男性 $m$ について $\mu(m)$ が $m$ にとって到達可能な女性の中で最も好ましいことをいう。女性最悪・女性最適 なども同様に定める。
男性最適な安定マッチングは、存在すれば 1 つだけである(各男性の相手が決まるため)。
| 性質 | 内容 | 根拠 |
|---|---|---|
| 存在 | 安定マッチングは必ず存在する | thm-sm-gs |
| 申し込みの回数 | 受け入れ保留方式の申し込みは $n^2-n+1$ 回以下 | thm-sm-gs |
| 回数の上限の達成 | $n=3$ で $7$ 回かかる例がある | ex-sm-seven |
| 申し込む側に最適 | 男性が申し込むと男性最適かつ女性最悪 | thm-sm-gs |
| 申し込みの順によらない | どの男性から申し込ませても結果は同じ | cor-sm-order |
| 一意性の判定 | 男性が申し込む結果と女性が申し込む結果が一致すれば安定マッチングは 1 つ | cor-sm-unique |
| 束の構造 | 2 つの安定マッチングから男性ごとに良い方をとると安定マッチング | thm-sm-lattice |
| 申し込む側の耐戦略性 | 男性は順位を偽っても真の順位で良くならない | thm-sm-strategy |
| 申し込まれる側の操作 | 女性は偽って得をすることがある | ex-sm-manipulate |
| 片側の人数が多い場合 | 組になる人の集合はどの安定な割り当てでも同じ | 証明しない:KP17 Corollary 10.3.3(pp. 183–184) |
男性が申し込む 受け入れ保留方式(deferred acceptance)は次の手順である。各女性は申し込みを受けると、それまで保留していた相手と比べて良いほうを保留し(受け入れを保留し)、他方を断る。
定義の条件のもとで、男性が申し込む受け入れ保留方式は、手順 3 での男性の選び方によらず次をみたす。
1.$k$ 人の女性が申し込まれたとき、彼女らはそれぞれ相異なる男性を保留しているので、保留されている男性はちょうど $k$ 人である。$n$ 人全員が申し込まれた時点で $n$ 人全員が保留され、手順は止まる。
ある男性が $n$ 回目の申し込みをするなら、その前にほかの $n-1$ 人の女性全員に断られているので、その申し込みで $n$ 人全員が申し込まれ、手順はその直後に止まる。したがって $n$ 回申し込む男性は高々 $1$ 人で、ほかの男性は $n-1$ 回以下しか申し込まない。申し込みの総数は $n+(n-1)^2=n^2-n+1$ 以下である。また、保留されていない男性が全員に断られていることはない(そうなら $n$ 人全員が申し込まれ、彼も保留されているはずである)ので、手順 3 はいつも実行できる。止まったとき全員が相異なる女性に保留されているので、出力は全単射である。
2.組でない男女 $(m,w)$ で $w\succ_m\mu_M(m)$ とする。$m$ は好む順に申し込むので、$\mu_M(m)$ より前に $w$ に申し込み、断られている。断ったとき $w$ は $m$ より好む男性を保留し、その後の保留は下がらないので $\mu_M(w)\succ_w m$ である。よって $(m,w)$ は不安定な組ではない。
3.まず、手順の途中で、どの男性も自分にとって到達可能な女性に断られないことを示す。そうでないとして、そのような断りのうち最初のものを考え、男性 $m$ が到達可能な女性 $w$ に断られたとする。このとき $w$ は $w$ の順位で $m$ より上の男性 $m'$ を保留する($m'$ が今申し込んだか、前から保留していたか)。$w$ は $m$ にとって到達可能なので、安定マッチング $\mu'$ で $\mu'(m)=w$ となるものがある。$m'\ne m$ なので $w':=\mu'(m')\ne w$ である。
$m'$ は好む順に申し込み、今 $w$ に保留されているので、$m'$ が $w$ より好む女性はすべて、この時点より前に $m'$ を断っている。いま考えている断りが最初のものなので、到達可能な $w'$ はそれより前に $m'$ を断っていない。よって $w'$ は $m'$ が $w$ より好む女性ではなく、$w\succ_{m'}w'=\mu'(m')$ である。一方 $m'\succ_w m=\mu'(w)$ なので、$(m',w)$ は $\mu'$ の不安定な組であり、$\mu'$ の安定性に反する。
したがって、各男性 $m$ が $\mu_M(m)$ より前に申し込んで断られた女性は、どれも $m$ にとって到達可能でない。2 により $\mu_M(m)$ は到達可能なので、$\mu_M(m)$ は $m$ にとって到達可能な女性の中で最も好ましい。
最後に女性最悪を示す。$\mu_M(w)=m$ とし、安定マッチング $\mu'$ で $\mu'(w)=m''$、$m\succ_w m''$ となるものがあったとする。$\mu'(m)=:w''$ は $w$ と異なり $m$ にとって到達可能なので、男性最適性から $w=\mu_M(m)\succ_m w''$ である。すると $(m,w)$ は $\mu'$ の不安定な組であり、矛盾する。$\square$
手順 3 での男性の選び方をどう変えても、出力は同じ男性最適な安定マッチングである。全員が同時に申し込み、各女性が申し込みと保留の相手のうち最良の 1 人を残す「回」の形の手順も、同じ結果を与える。
男性最適な安定マッチングは、各男性の相手が「到達可能な女性の中で最も好ましい女性」として決まるので 1 つしかない。thm-sm-gs の 3 により、どの選び方の出力もこれに等しい。回の形の手順は、1 つの回の申し込みを 1 つずつ処理し、その回に断られた男性の申し込みを次の回まで待たせる選び方にあたる。各女性が回の終わりに保留する相手は、その回の申し込みと前の保留の相手のうち最良の 1 人で、1 つずつ処理しても同じだからである。$\square$
男性が申し込む結果 $\mu_M$ と、役割を入れ替えて女性が申し込む結果 $\mu_W$ が一致するなら、安定マッチングはそれ 1 つだけである。
役割を入れ替えた thm-sm-gs の 3 により、$\mu_W$ は男性最悪である。安定マッチング $\mu'$ と男性 $m$ について、$\mu_M(m)\succeq_m\mu'(m)\succeq_m\mu_W(m)$ であり、両端が等しいので $\mu'(m)=\mu_M(m)$ である。$\square$
図: 3 人ずつの男女が巡回する順位をもつ例の 3 つの安定マッチングを、左から男性最適、中間、女性最適の順に、男性 m1, m2, m3 と女性 w1, w2, w3 を結ぶ線で描いた図。各線の横に、男性から見た順位と女性から見た順位の組が書いてあり、左では全員が (1,3)、中央では (2,2)、右では (3,1) である。
安定マッチングは一般に複数ある。それらは、男性の好みで比べると、2 つから「良い方」を作る操作で閉じている。
$\mu,\mu'$ を安定マッチングとし、各男性 $m$ に $\mu(m)$ と $\mu'(m)$ のうち $m$ が好むほうを対応させる写像を $\mu\vee\mu'$ とする。このとき $\mu\vee\mu'$ は安定マッチングであり、各女性 $w$ の相手 $(\mu\vee\mu')(w)$ は $\mu(w)$ と $\mu'(w)$ のうち $w$ が好まないほうである。男性ごとに悪い方をとる $\mu\wedge\mu'$ についても同様である。
$\lambda:=\mu\vee\mu'$ とおく。まず $\lambda$ が単射であることを示す。$m_1\ne m_2$ で $\lambda(m_1)=\lambda(m_2)=w$ とすると、$w$ は同じマッチングで 2 人の相手をもたないので、たとえば $w=\mu(m_1)=\mu'(m_2)$ である。$\mu(m_1)=\mu'(m_1)$ なら $\mu'(m_1)=\mu'(m_2)$ となって矛盾するから、$w=\mu(m_1)\succ_{m_1}\mu'(m_1)$ である。同様に $w=\mu'(m_2)\succ_{m_2}\mu(m_2)$ である。$\mu'$ は安定で $m_1$ は $w$ を $\mu'(m_1)$ より好むので、$\mu'(w)=m_2\succ_w m_1$ である。$\mu$ は安定で $m_2$ は $w$ を $\mu(m_2)$ より好むので、$\mu(w)=m_1\succ_w m_2$ である。これは矛盾である。$M,W$ は同じ大きさの有限集合なので、$\lambda$ は全単射である。
次に、$\lambda(m)=w$ で $\mu(m)=w\ne\mu'(m)$ とすると $w\succ_m\mu'(m)$ なので、$\mu'$ の安定性から $\mu'(w)\succ_w m=\mu(w)$ である。$\mu'(m)=w\ne\mu(m)$ の場合も同様で、各女性の $\lambda$ での相手は 2 人のうち彼女が好まないほうである(2 人が同じならそれ)。
最後に、$(m,w)$ が $\lambda$ の不安定な組だとする。$w\succ_m\lambda(m)$ は $\mu(m)$ と $\mu'(m)$ のどちらよりも $w$ を好むことを意味する。$\lambda(w)$ が $\mu(w)$ のとき、$m\succ_w\lambda(w)=\mu(w)$ と $w\succ_m\mu(m)$ から $(m,w)$ は $\mu$ の不安定な組になり矛盾する。$\lambda(w)=\mu'(w)$ のときも同様である。$\wedge$ については、男女の役割を入れ替えて同じ議論をすればよい。女性ごとに良い方をとる写像は安定マッチングで、各男性にはこのとき 2 人のうち好まないほうが対応するから、それが $\mu\wedge\mu'$ である。$\square$
したがって安定マッチングの全体は、「すべての男性が $\mu(m)\succeq_m\mu'(m)$」で定めた順序で束になる。$\vee$ と $\wedge$ は男性ごとに全順序の大きいほう・小さいほうをとる操作なので、この束は全順序の直積の部分束であり、分配束 である。最大元が $\mu_M$、最小元が $\mu_W$ であり、男性にとっての上下は女性にとっての上下と逆である。
制度として受け入れ保留方式を使うと、参加者が順位を偽る誘因があるかが問題になる。申し込む側にはその誘因がない。
真の順位の組で男性が申し込む受け入れ保留方式の結果を $\mu_M$ とする。男性の部分集合 $S_0\ne\emptyset$ が順位を偽り、ほかの全員が真の順位を出したときの結果を $\nu$ とする。このとき、$S_0$ のすべての男性が真の順位で $\nu(m)\succ_m\mu_M(m)$ となることはない。とくに 1 人の男性が偽っても、真の順位で真の結果より良い相手は得られない。
次の補題を示す:$\nu$ を任意のマッチングとし、$S:=\{m:\nu(m)\succ_m\mu_M(m)\}$ が空でないとすると、真の順位で $\nu$ の不安定な組 $(m,w)$ で $m\notin S$ となるものがある。
(a) $\nu(S)\ne\mu_M(S)$ の場合。両者の大きさは $|S|$ で等しいので $w\in\nu(S)\setminus\mu_M(S)$ がとれる。$m:=\mu_M(w)$ とおくと $w\notin\mu_M(S)$ より $m\notin S$ である。$\nu(w)=:m'\in S$ は $w$ を $\mu_M(m')$ より好むので、受け入れ保留方式の途中で $w$ に申し込んで断られている。断った後の $w$ の保留は下がらないので $m=\mu_M(w)\succ_w m'=\nu(w)$ である。また $m\notin S$ より $\mu_M(m)\succeq_m\nu(m)$ で、$\nu(m)\ne w$($\nu(w)=m'\ne m$)だから $w=\mu_M(m)\succ_m\nu(m)$ である。よって $(m,w)$ は $\nu$ の不安定な組である。
(b) $\nu(S)=\mu_M(S)=:W_0$ の場合。1 人ずつ申し込む手順を 1 つ固定して考える(cor-sm-order)。$m\in S$ が最後の相手 $\mu_M(m)$ に申し込む時刻を $t_m$ とし、$t_m$ が最大の $m^*\in S$ と $w:=\mu_M(m^*)\in W_0$ をとる。$w=\nu(m'')$ となる $m''\in S$ があり、$m''$ は $w$ に申し込んで断られ、その後の時刻 $t_{m''}< t_{m^*}$ に $\mu_M(m'')$ に申し込んでいる($\nu(m^*)\ne w$ なので $m''\ne m^*$)。よって時刻 $t_{m^*}$ の直前に $w$ は誰かを保留しており、それを $m$ とする。$w$ は $m^*$ を最後まで保留するので、$m^*\succ_w m$ で、$m$ はこのとき断られる。$m\in S$ なら $m$ はその後 $\mu_M(m)\in W_0$ に申し込むので $t_m>t_{m^*}$ となり、$m^*$ のとり方に反する。よって $m\notin S$ である。$w$ が $m''=\nu(w)$ を断った後の保留は $m''$ より上で下がらないので $m\succ_w\nu(w)$ である。$m$ は $w$ に申し込んで断られたので $w\succ_m\mu_M(m)\succeq_m\nu(m)$ である。よって $(m,w)$ は $\nu$ の不安定な組である。
定理を示す。偽った順位の組での結果 $\nu$ は、偽った順位の組で安定である。$S_0$ の全員が真の順位で得をするなら $S_0\subset S$ で、補題の組 $(m,w)$ は $m\notin S_0$ をみたす。$m$ と $w$ の順位は真の順位のままなので、$(m,w)$ は偽った順位の組でも $\nu$ の不安定な組であり、矛盾する。$\square$
この証明は KP17 Lemma 10.3.5 と Corollary 10.3.6(p. 185)の論法による。同書 p. 187 の注は、この結果を Dubins–Freedman と Roth に帰している。申し込まれる側には同じ結論は成り立たない(ex-sm-manipulate)。
順位の表から安定マッチングを求め、確かめるには次のようにする。
以下の例では $n=3$ とし、順位を「$m_1:w_1>w_2>w_3$」($m_1$ は $w_1$ を最も好む)の形で書く。手順 3 では、保留されていない男性のうち番号の最も小さい人を選ぶ。
男性 $m_1:w_1>w_2>w_3$、$m_2:w_2>w_3>w_1$、$m_3:w_3>w_1>w_2$、女性 $w_1:m_2>m_3>m_1$、$w_2:m_3>m_1>m_2$、$w_3:m_1>m_2>m_3$。
使う公式:thm-sm-gs、cor-sm-unique。
答え:安定マッチングは $\{m_1w_1,m_2w_2,m_3w_3\}$、$\{m_1w_2,m_2w_3,m_3w_1\}$、$\{m_1w_3,m_2w_1,m_3w_2\}$ の 3 つである。男性が申し込むと $3$ 回の申し込みで 1 つ目(全男性が第 1 希望、全女性が第 3 希望)、女性が申し込むと 3 つ目(その逆)が得られる。$\mu_M\ne\mu_W$ なので一意ではない。
この順位では、どの男女 $(m,w)$ についても「$m$ から見た $w$ の順位」と「$w$ から見た $m$ の順位」の和が $4$ である(たとえば $m_1$ と $w_2$ は $2+2$、$m_2$ と $w_1$ は $3+1$)。上の 3 つのマッチングでは、全男性の相手の順位が同じ $r$ で、全女性の相手の順位が $4-r$ である。不安定な組 $(m,w)$ があれば、2 つの順位はそれぞれ $r$ より小さく $4-r$ より小さいので和が $4$ より小さくなり、矛盾する。残りの 3 つのマッチングにはどれも不安定な組がある(たとえば $\{m_1w_1,m_2w_3,m_3w_2\}$ では $(m_3,w_3)$)。男性が申し込むと、各男性の第 1 希望が相異なるので誰も断られない。
$n=3$ の順位の組は全部で $(3!)^6=46656$ 通りあり、安定マッチングの個数はそのうち $34080$ 通りで $1$ 個、$11484$ 通りで $2$ 個、$1092$ 通りで $3$ 個である(全数の計算)。
男性 $m_1:w_1>w_2>w_3$、$m_2:w_2>w_1>w_3$、$m_3:w_1>w_2>w_3$、女性 $w_1:m_2>m_3>m_1$、$w_2:m_3>m_1>m_2$、$w_3:m_1>m_2>m_3$。
使う公式:受け入れ保留方式の手順、thm-sm-gs の 1。
答え:申し込みは $7=3^2-3+1$ 回で、結果は $\{m_1w_3,m_2w_1,m_3w_2\}$ である。thm-sm-gs の上限は $n=3$ で達成される。
(1) $m_1\to w_1$ 保留。(2) $m_2\to w_2$ 保留。(3) $m_3\to w_1$:$w_1$ は $m_3$ を保留し $m_1$ を断る。(4) $m_1\to w_2$:$w_2$ は $m_1$ を保留し $m_2$ を断る。(5) $m_2\to w_1$:$w_1$ は $m_2$ を保留し $m_3$ を断る。(6) $m_3\to w_2$:$w_2$ は $m_3$ を保留し $m_1$ を断る。(7) $m_1\to w_3$ 保留。全員が保留されたので止まる。$m_1$ だけが $3$ 回申し込み、ほかの 2 人は $2$ 回ずつで、prf-sm-gs の数え方の等号の場合である。
男性 $m_1:w_1>w_2>w_3$、$m_2:w_1>w_2>w_3$、$m_3:w_2>w_1>w_3$、女性 $w_1:m_3>m_1>m_2$、$w_2:m_1>m_3>m_2$、$w_3:m_1>m_2>m_3$。
使う公式:thm-sm-gs、thm-sm-strategy。
答え:真の順位では $\mu_M=\{m_1w_1,m_2w_3,m_3w_2\}$ で、$w_1$ の相手は第 2 希望の $m_1$ である。$w_1$ だけが順位を $m_3>m_2>m_1$ と偽ると、結果は $\{m_1w_2,m_2w_3,m_3w_1\}$ になり、$w_1$ は真の第 1 希望の $m_3$ を得る。
真の順位:(1) $m_1\to w_1$ 保留。(2) $m_2\to w_1$ 断られる。(3) $m_2\to w_2$ 保留。(4) $m_3\to w_2$:$w_2$ は $m_3$ を保留し $m_2$ を断る。(5) $m_2\to w_3$ 保留。
偽った順位:(1) $m_1\to w_1$ 保留。(2) $m_2\to w_1$:$w_1$ は(偽りの順位で)$m_2$ を保留し $m_1$ を断る。(3) $m_1\to w_2$ 保留。(4) $m_3\to w_2$ 断られる。(5) $m_3\to w_1$:$w_1$ は $m_3$ を保留し $m_2$ を断る。(6) $m_2\to w_2$ 断られる。(7) $m_2\to w_3$ 保留。
真の順位での安定マッチングは、この 2 つ($\mu_M$ と女性最適な $\mu_W$)だけである。$w_1$ は、断る必要のない $m_1$ を断ることで、$m_1$ を $w_2$ へ、$m_3$ を自分へ回した。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 2 つの側に分かれていること | 4 人 $p_1,\dots,p_4$ を 2 人ずつの組に分ける。$p_1:p_2>p_3>p_4$、$p_2:p_3>p_1>p_4$、$p_3:p_1>p_2>p_4$、$p_4$ の順位は任意 | 安定な組分けが存在しない(thm-sm-gs の 2 の存在) |
| 順位が狭義であること | $m_1,m_2$ はともに $w_1>w_2$、$w_1$ と $w_2$ はどちらも $m_1$ と $m_2$ を同順位とする | 2 つの完全マッチングがどちらも安定で、$m_1$ は一方を、$m_2$ は他方を狭義に好むので、男性最適な安定マッチングがない(thm-sm-gs の 3) |
| 全員が異性全員を受け入れること | $m_1,m_2$ はともに $w_1$ だけを受け入れ、$w_2$ とは組にならないほうを好む。女性の順位は任意 | 全員が受け入れる相手と組になる完全なマッチングがなく、どの安定な割り当てでも誰かが組にならない(thm-sm-gs の 1 の「出力はマッチング」) |
| 申し込む側であること | ex-sm-manipulate の $w_1$ | 偽って真の順位で良い相手を得る(thm-sm-strategy の結論) |
各行で外した条件のほかは、定義のとおりである。
1 行目:$p_4$ の相手で場合を分ける。$p_4$ が $p_1$ と組なら $p_2p_3$ が組で、$p_3$ は $p_2$ より $p_1$ を、$p_1$ は $p_4$ より $p_3$ を好むので $(p_1,p_3)$ が不安定である。$p_4$ が $p_2$ と組なら $p_1p_3$ が組で、$(p_1,p_2)$ が不安定である($p_1$ は $p_3$ より $p_2$ を、$p_2$ は $p_4$ より $p_1$ を好む)。$p_4$ が $p_3$ と組なら $p_1p_2$ が組で、$(p_2,p_3)$ が不安定である($p_2$ は $p_1$ より $p_3$ を、$p_3$ は $p_4$ より $p_2$ を好む)。
2 行目:同順位があるとき、不安定な組は「双方が今の相手より狭義に好む組」とする。$\{m_1w_1,m_2w_2\}$ では $m_2$ は $w_1$ を好むが $w_1$ は $m_2$ と $m_1$ を同順位とするので不安定な組はなく、$\{m_1w_2,m_2w_1\}$ も同様に安定である。$m_1$ は前者を、$m_2$ は後者を狭義に好むので、全男性にとって最良の安定マッチングはない。順位を狭義に直す(同順位を任意に解消する)と、thm-sm-gs によりそのどちらかが男性最適になる。
3 行目:完全なマッチングは $\{m_1w_1,m_2w_2\}$ と $\{m_1w_2,m_2w_1\}$ だけで、どちらも受け入れない相手との組を含む。したがって、受け入れない相手と組にならない割り当てでは、$m_1,m_2$ の一方は組にならない。
4 行目:ex-sm-manipulate で計算した。男性の側で同じことは起こらない(thm-sm-strategy)。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 安定マッチングは 1 つしかない | 一般に複数あり、男性最適と女性最適が異なりうる | ex-sm-cyclic |
| 受け入れ保留方式の結果は申し込む順で変わる | どの順でも同じ男性最適な安定マッチング | cor-sm-order |
| 男性最適な安定マッチングは女性にとっても良い | 女性全員にとって最悪の安定マッチングである | thm-sm-gs の 3 |
| 安定マッチングは全員の満足の和を最大にする | 安定性は不安定な組がないことだけを求める | 全男性が $w_1>w_2>w_3$、$w_1,w_2$ が $m_1>m_2>m_3$、$w_3$ が $m_2>m_1>m_3$ の順位では、ただ 1 つの安定マッチング $\{m_1w_1,m_2w_2,m_3w_3\}$ の順位の和は $12$ で、不安定な $\{m_1w_1,m_2w_3,m_3w_2\}$ の $11$ より大きい |
| 誰にとっても正直な申告が最善 | 申し込まれる側は偽って得をすることがある | ex-sm-manipulate |
| 同じ集団の中の組分けにも安定解がある | 2 つの側に分かれないと存在しないことがある | 反例の表の 1 行目 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する