安定結婚問題

同義語:stable marriage problem安定マッチング問題stable matching problem

概要

安定結婚問題(stable marriage problem)とは、$n$ 人ずつの男女が異性全員に狭義の順位を付けているとき、互いに今の相手より相手を好む男女の組(不安定な組)がないように全員を 1 対 1 に組にする問題である。男性が順に申し込み女性が良いほうを保留する受け入れ保留方式(Gale–Shapley)は、申し込みの順によらず $n^2-n+1$ 回以下の申し込みで止まり、男性全員に最良で女性全員に最悪の安定マッチングを返す。安定マッチングの全体は分配束をなし、申し込む側は順位を偽っても得をしないが、申し込まれる側は得をすることがある。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 二部グラフ, マッチング

安定結婚問題(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$」を表す。

  1. マッチング とは全単射 $\mu\colon M\to W$ のことである。$\mu(m)=w$ のとき $\mu(w):=m$ とも書き、$m$ と $w$ は 組 であるという。
  2. マッチング $\mu$ について、組でない男女 $(m,w)$ が $w\succ_m\mu(m)$ かつ $m\succ_w\mu(w)$ をみたすとき、$(m,w)$ を $\mu$ の 不安定な組(ブロックする組)という。
  3. 不安定な組をもたないマッチングを 安定マッチング という。

$\mu$ は完全 二部グラフ $K_{n,n}$ の完全マッチングと同じものである。安定性は辺の集合だけでなく順位にもよる条件であり、マッチングの大きさを最大にする問題とは別の問題である。
この記事の結論が成り立つのは、次の条件のもとである。

  1. 2 つの側:組は必ず男性と女性からなる。
  2. 狭義の順位:同順位を許さない。
  3. 完全な順位表:各人は異性全員に順位を付け、組にならないより誰かと組になるほうを好む。両側の人数は等しい。
    各条件を外した反例は「使える条件と反例」の節にある。
到達可能な相手

ある安定マッチング $\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)は次の手順である。各女性は申し込みを受けると、それまで保留していた相手と比べて良いほうを保留し(受け入れを保留し)、他方を断る。

  1. はじめ、どの男性も保留されておらず、どの女性も誰も保留していない。
  2. 保留されていない男性がいなければ、保留の組をマッチングとして出力して止まる。
  3. 保留されていない男性を 1 人選ぶ(誰を選んでもよい)。その男性は、まだ断られていない女性のうち最も好む女性に申し込む。
  4. 申し込まれた女性が誰も保留していなければ、その男性を保留する。保留している相手がいれば、2 人のうち好むほうを保留し、他方を断る。手順 2 に戻る。
    断られた男性は保留されていない状態に戻り、後で次の順位の女性に申し込む。この手順から、次の 2 つがすぐ分かる。
  • 各男性は好む順に申し込み、同じ女性に 2 度申し込まない。
  • 一度申し込まれた女性は、以後つねに誰かを保留し、保留する相手は彼女の順位で下がらない。
    「保留」が要点である。女性が最初の申し込みをすぐ確定させる方式では、後からもっと好む男性が申し込んでも組を変えられない。たとえば ex-sm-seven の順位で、番号の小さい男性から申し込ませて即座に確定させると、$m_1w_1$、$m_2w_2$ が確定したあと $m_3$ は $w_1,w_2$ に断られて $w_3$ と組になる。ところが $m_3$ は $w_3$ より $w_1$ を好み、$w_1$ は $m_1$ より $m_3$ を好むので、$(m_3,w_1)$ が不安定な組として残る。
Gale–Shapley の定理

定義の条件のもとで、男性が申し込む受け入れ保留方式は、手順 3 での男性の選び方によらず次をみたす。

  1. 申し込みが $n^2-n+1$ 回以下で止まり、出力はマッチングである。
  2. 出力 $\mu_M$ は安定マッチングである。とくに安定マッチングは存在する。
  3. $\mu_M$ は男性最適かつ女性最悪である。
誰も到達可能な相手に断られない

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) である。 図: 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)。

計算の手順

順位の表から安定マッチングを求め、確かめるには次のようにする。

  1. 入力を確かめる。両側が $n$ 人ずつで、各人の順位が異性全員の並べ替えになっていること。
  2. 女性ごとに、男性の番号から順位を引く表 $\mathrm{rank}_w(m)$ を作る($O(n^2)$)。比較が 1 回の参照で済む。
  3. 男性が申し込む受け入れ保留方式を実行する。各男性について「次に申し込む女性の位置」を、各女性について「保留している男性」を記録する。申し込みは $n^2-n+1$ 回以下なので、全体で $O(n^2)$ の時間である。
  4. 得たマッチングの安定性を、$n^2$ 個の男女の組について「互いに今の相手より好むか」を調べて確かめる。
  5. 男女の役割を入れ替えてもう一度実行し、女性最適な $\mu_W$ を得る。$\mu_M=\mu_W$ なら安定マッチングは 1 つだけである(cor-sm-unique)。異なれば、すべての安定マッチングは男性の好みで $\mu_M$ と $\mu_W$ の間にある。

例題

以下の例では $n=3$ とし、順位を「$m_1:w_1>w_2>w_3$」($m_1$ は $w_1$ を最も好む)の形で書く。手順 3 では、保留されていない男性のうち番号の最も小さい人を選ぶ。

巡回する順位:安定マッチングが 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$ 個である(全数の計算)。

申し込みが上限の 7 回に達する例

男性 $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 行目

補足

  • 人数が異なる場合.男性 $n$ 人・女性 $n'$ 人で、各人が異性全員に順位を付け、組にならないより誰かと組になるほうを好むとする。組にならない人も許して不安定な組を定めると、受け入れ保留方式は安定な割り当てを返し(KP17 Theorem 10.2.3、p. 181)、申し込む側に最良で申し込まれる側に最悪である(同 Theorem 10.3.1、p. 182)。さらに、組になる人の集合はどの安定な割り当てでも同じである(同 Corollary 10.3.3、pp. 183–184)。この記事ではこれらを証明しない。
  • 病院と研修医.各病院が複数の定員をもつ割り当ても考えられ、KP17 Exercise 10.10(p. 190)はそれを安定結婚問題に帰着させて解く問題である。
  • 整数計画との関係.変数 $x_{m,w}\in\{0,1\}$ を「$m$ と $w$ が組」とすると、安定性は各組 $(m,w)$ について「$m$ が $w$ より好む女性との組の変数の和、$w$ が $m$ より好む男性との組の変数の和、$x_{m,w}$ の合計が $1$ 以上」という線形不等式で書ける(KP17 Exercise 10.12、pp. 190–191)。線形計画法 の緩和との比較は同じ問題で扱われている。

関連項目

参考文献

[1]
Anna R. Karlin; Yuval Peres, Game Theory, Alive, 著者公開版(2016 年 12 月 13 日), American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号と頁:Chapter 10、Theorem 10.2.3(p. 181)、Theorem 10.3.1(p. 182)、Corollary 10.3.3(pp. 183–184)、Lemma 10.3.5・Corollary 10.3.6(p. 185)、Notes(pp. 186–187)、Exercises 10.10・10.12(pp. 190–191)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する