第 11 章 安定結婚問題（宮下健輔）

76

第 11 章

安定結婚問題（宮下健輔）
はじめに

1

そのむかし「一目会ったその日から」「恋の花咲くこともある」という掛け合いで始まる人気テレビ番組があった．今では，SNS やまとめサイト等で結婚相談所やマッチングアプリの広告をよく見かけるかもしれない．ことほど左様に結婚は人々の関心を惹く事象である．
本稿では安定結婚問題を扱うが，ここでいう結婚は必ずしも現実世界のそれを意味しない．これは数学的に単なる 1 対 1 対応（または多対 1 対応）のことである．この問題が最初に定義されたときに“marriage” という単語が用いられたため，それを翻訳した「結婚」という単語が日本語として用いられているのである．また「男性」「女性」という呼称についても同様であり，1 対 1 対応における双方を区別する以上の意味はない．

安定結婚問題2

安定結婚問題が最初に定義された論文を参考文献 [1] に示す．これは David Gale 氏（1921–2008）と Lloyd Stowell Shapley 氏（1923–2016）により 1962 年に発表された論文である *1 ．論文のタイト
ルを日本語にすれば「大学入学および結婚の安定性」となるだろうか．結婚の安定性の問題（つまり安定結婚問題）とは男女が数人ずついるときにその中で安定なペアを見つけるもので，グループ内での交際が平和裡に行われることを目指す．大学入学（大学に限らないが）を「学生と大学とを結びつけること」と解釈すれば，これも安定結婚問題の応用であることがわかるだろう．安定結婚問題のように 1 対 1 対応を求めるのではなく，多数の学生が 1 つの大学に入学する多対 1 対応を求めることになるが，問題の本質は違わないと考えられる．

2.1

定義

安定結婚問題は以下のように定義できる．
数人ずつの男女（n 人ずつとしよう）がいるグループで，すべての人が異性すべてを自分の好意の順に並べたリストをそれぞれ持つとする．入力例 1（図 1）は n = 4 で，a〜d が男性，w〜z が女性であり，リストはそれぞれ異性を左から右へ好きな順に並べている．例えば男性 a は女性 x がいちばん好きで，その後 z ，y ，w の順に好きであることを示している．
次に，男女 n 人ずつのグループ内で作られる男女のペア n 組のことをマッチングと呼ぶことにす*1 Shapley 氏はこの論文を含む功績により 2012 年にノーベル経済学賞を受賞している．

第 11 章 安定結婚問題（宮下健輔）

77

a : x, z, y, w
b : x, y, w, z
c : y, x, w, z
d : z, y, x, w

w : d, b, c,
x : c, d, a,y : d, c, b,z : a, b, c,

abad

図 1 入力例 1（n = 4）

a : x, z, y, w
b : x, y, w, z
c : y, x, w, z
d : z, y, x, w

w : d, b, c, ax : c, d, a, b
y : d, c, b, az : a, b, c, d

図 2 マッチング M1る．例えば M1 = {(a, w), (b, x), (c, y), (d, z)} はマッチングであり，これを図示すれば図 2 のようになる（それぞれのペアの相手に下線を引いている）．
ここで，一般にマッチング M で p と q がペアになっていることを M (p) = q および M (q) = p と書くことにしよう．例えば上のマッチング M1 にはペア (a, w) が存在するので，M1 (a) = w でありM1 (w) = a である．
このとき，あるマッチング M において男性 m が M (m) よりも女性 f を好み，同時にその女性 fも M (f ) より男性 m を好むとき，このペア (m, f ) をブロッキングペアと呼ぶ．そして，このブロッキングペアが存在しないマッチングを安定マッチングという．例えばマッチング M1 においてペア(a, x) はブロッキングペアであり *2 ，M1 は安定マッチングではない．すなわち M1 は不安定なマッチングであるということになる．
安定結婚問題とは「どのようなリストを持つグループについても安定マッチングが存在するか」という問題であり，その答えは “Yes” である．そしてこれが “Yes” であれば，次はその安定マッチングを求めるアルゴリズムが存在するかが気になるが，文献 [1] によればこれも “Yes” である．文献 [1]では，そのグループ内で考えられるすべてのマッチングについて安定かどうかをチェックするのではなく，安定マッチングのひとつ *3 を効率よく求めるアルゴリズムを考案し，その解としている．それが Gale-Shapley アルゴリズムである．

2.2 Gale-Shapley アルゴリズム
Gale-Shapley アルゴリズムは，前述したように n 人ずつの男女が持つリストを入力とし，安定マッチングをひとつ出力して停止する *4 ．
このアルゴリズムにおいて各人は婚約中かフリー（free）かのどちらかの状態をとる．婚約中とはある異性とペアになっていることをいい，フリーとはそうでない状態である．アルゴリズム開始時
は，すべての人がフリーであるとする．
さて，任意のフリーな男性が自分のいちばん好きな女性にプロポーズすることからこのアルゴリズ*2 a にとって x は M1 (a) = w より上位であり，x にとっても a は M1 (x) = b より上位である．
*3 安定マッチングは一般に複数存在する．
*4 高校の情報の授業などで聞いたことがあると思うが，アルゴリズムはこの「停止すること」がとても重要であり，停止しないものをアルゴリズムとはいわない．ちなみに，あるアルゴリズムが停止するかどうかを判定するアルゴリズムは存在しない．

第 11 章 安定結婚問題（宮下健輔）

78

1. マッチング M = ∅（空集合）とし，全員の状態をフリーとする
2. フリーの男性がいる間，繰り返す
3.

任意のフリーの男性を選び，m とする

4.

m のリストの最上位の女性を f とする

5.

もし f がフリーなら：

6.
7.

ペア (m, f ) を M に追加し，m と f の状態を婚約中とする
そうでなければ：

8.

f の現在の婚約相手を m′ とする

9.

もし f のリスト中で m′ の方が m より上位なら：

m のリストから f を削除する

10.
11.

そうでなければ：

12.

ペア (m′ , f ) を M から削除し，ペア (m, f ) を M に追加する

13.

m′ をフリーに，m を婚約中にする

14.

m′ のリストから f を削除する

15.

2 に戻る

16. M を出力する
図3

Gale-Shapley アルゴリズム

ムは始まる．プロポーズされた女性は自分がフリーならそれを受け入れる（このときこの男女は婚約中となる）．プロポーズされた女性が婚約中の場合，その女性はプロポーズしてきた男性を現在の婚約相手と比べ，その女性のリスト中で上位の人を選ぶ．すなわち，プロポーズしてきた男性が現在の婚約相手より下位のときはその婚約を続け，そうでないときはプロポーズしてきた男性と婚約する（つまり現在の婚約は解消する）．このとき，プロポーズを断られた男性はフリーのままその女性を自分のリストから削除し，婚約を解消された男性はフリーに戻ってその女性を自分のリストから削除する．この動作を，フリーの男性がいなくなるまで繰り返すとマッチングがひとつ求まり，それが安定マッチングになっている *5 ．以上のアルゴリズムを箇条書きで表せば図 3 のようになる．
図 1 の入力例 1 で考えてみよう．最初は全員がフリーである．どの男性から始めても構わないが，簡単のため辞書順で男性 a から始めよう．a がいちばん好きな女性 x にプロポーズする．女性 x はフリーなのでプロポーズを受け入れ，ペア (a, x) が誕生し，a も x も婚約中となる．次にフリーの男性

b がいちばん好きな女性にプロポーズするが，これも x であるので，b は x にプロポーズする．するとプロポーズされた女性 x は自分のリストで a と b を比べ，a の方が上位であるので b のプロポーズを断り，ペア (a, x) は存続することになる．x に振られた b はフリーのまま自分のリストから x を削除し，次点の y にプロポーズする．y はフリーなのでこのプロポーズは成功し，(b, y) というペアが誕生する（b と y はどちらも婚約中の状態になる）．しかし次に c がやはりいちばん好きな y にプロポーズしてくると，y のリスト中で c の方が b より上位のため，ペア (b, y) は解消され (c, y) が誕生し，bはフリーに戻って y を自分のリストから削除する．b は今度は w にプロポーズし，w はフリーなのでペア (b, w) が誕生する（b は再び婚約中に，w も婚約中となる）．最後に d は自分のリストの最上位のz にプロポーズし，フリーの z はそれを受け入れてペア (d, z) ができる（d と z はそれぞれ婚約中となる）．以上の動作でフリーの男性がいなくなり，安定マッチング M2 = {(a, x), (b, w), (c, y), (d, z)}*5 くどいようだが，フリーの男性がいなくなるとこのアルゴリズムは停止する．アルゴリズムは停止するのである（くどい）．

第 11 章 安定結婚問題（宮下健輔）

79

a : x, z, y, w
b : x, y, w, z
c : y, x, w, z
d : z, y, x, w

w : d, b, c, a
x : c, d, a, b
y : d, c, b, az : a, b, c, d

図 4 マッチング M2が求められる（図 4）．
では，求められたマッチング M2 が安定であることをチェックしよう．図 4 で男性のリストを見ると a，c，d についてはすべて最上位の女性とペアになっているのでこれを上回る結果は存在しない．

b だけがリストの第 3 位の女性 w とペアになっているが，それより上位の x も y もそれぞれのリス
トで b よりも上位の男性とペアになっており *6 ，これらを覆すことができない．これは女性のリストからも同様のことがいえるので，すなわちマッチング M2 は安定であるということになる．
ここで，マッチング M2 では男性は 4 人中 3 人がリスト最上位の女性とペアになっているのに対して，女性はそれほど良い結果になっていないことに気付くだろう *7 ．これは男性から女性にプロポーズしたためであり，この手法ではプロポーズした側に最適な安定マッチング（すなわちこの場合は男性最適安定マッチング）が求められることが知られている *8 ．
このアルゴリズムで安定マッチングをひとつ求めるのにかかる手間はどのくらいだろうか．こうい
うときは最悪の場合で考える．上記の手法を振り返ると，最悪の場合，すべての男性がそれぞれ自分のリストの最下位の女性までプロポーズを繰り返すことになる．一度プロポーズに失敗したり婚約を解消されたりした女性は自分のリストから削除するので，同じ女性に二度プロポーズすることはない．ということは，最悪の場合には 1 人の男性についてそれぞれ女性の人数分だけプロポーズを繰り返すことになる．いま男女それぞれ n 人ずつを入力としているので，n 人の男性がそれぞれ n 人の女性にプロポーズすることになり，合計すると全体で n × n すなわち n2 回のプロポーズをしないといけないのが最悪の場合ということになる．実際はそこまで最悪のことは起きづらいだろうし，その他に比較したりペアを作ったりするのにも手間がかかることを考えなければならないが，このアルゴリズムの手間を考える上でいちばん大きな要因はこの繰り返しの数 n2 であり，これがこのアルゴリズムの効率を考える上での目安となる *9 ．これは入力の大きさ n に対してその二乗に比例する手間がかかると解釈できる．つまり，男女 8 人ずつのグループに対して安定マッチングを求めるには，男女4 人ずつのグループに対して求める手間の 4 倍かかるというわけである．このように n の多項式の形で表される手間の数を上限とするアルゴリズムを多項式時間アルゴリズムという．この手間の数をどう評価するかという問題は読者への課題とする．

2.3

安定結婚問題の応用

前節では安定結婚問題で 1 対 1 対応のペアを求めることを考えた．ここでこれを多対 1 対応に拡張して，より一般的な安定マッチング問題として考えてみよう．安定マッチング問題は文献 [1] を皮*6 x の相手 a および y の相手 c が，それぞれのリストで b より上位である．
*7 特に z は自分のリストで最下位の d とペアになっていてとてもかわいそうである．しかしこれは安定マッチングであり覆すことができない．

*8 では女性から男性にプロポーズするとどんなマッチングが求められるか，またそれは安定か等については読者への課題とした．

222*9 より正確に表せば O(n ) であり，「オーダ n 」または「n のオーダ」と読む．

第 11 章 安定結婚問題（宮下健輔）

80

切りに，数学はもちろん，情報科学や経済学など様々な分野で研究され，発表された論文は数百に上る．前述した 2012 年のノーベル賞は経済学賞であり *10 ，Alvin Elliot Roth 氏とともに「安定配分理論と市場設計の実践」に対して授与されている *11 ．
安定マッチング問題の例としてよく知られているのが研修医配属問題（Hospitals/Residents Prob-lem）である．これは大学の医学部を卒業した学生が実際の病院での研修を行う際に，どの研修医をどの病院に配属するかを決める問題である．研修制度は若い医師にとって現場で研鑽を積む絶好の機会であり，病院にとっては安価で貴重な労働力としての研修医を活用できるという，双方にとって重要な役割を担う制度である．文献 [2] によれば，前世紀半ばのアメリカで始まったこの制度は，その初期には優秀な研修医を巡って各病院が採用時期を早め，遂には 2 年前に採用となるまでの事態に至って，全米規模で安定マッチングを求める制度改革が行われた．日本でも従来は各病院で行われていたものが 2004 年度から必修の臨床研修制度となり，同時に開始された研修医マッチング制度でこの手法が採用されている．
研修医マッチング制度では，上述した安定結婚問題と同様に研修医は配属先として希望する病院のリストを，病院は受け入れたい研修医のリストをそれぞれ持つ．ただし，当然ながら研修医と病院の数は同数にはならず，ひとつの病院に複数の研修医を配属させられる点が安定結婚問題とは大きく異なる．研修医はそれぞれ希望する病院に，その病院の受け入れ可能人数の上限（これは病院によって異なる）まで配属できるのである．
安定結婚問題は容易に多対 1 に拡張できる．例えば，研修医配属問題の解としてマッチング M3 が求まったとしよう．ここで M3 には複数のペア (r0 , H0 )，(r1 , H1 )，(r2 , H1 )，(r3 , H1 ) が含まれるとする（ここで r0 , r1 , r2 , r3 は研修医，H0 , H1 は病院を表す）．これは研修医 r0 が病院 H0 で研修し，研修医 r1 ，r2 ，r3 は病院 H1 で研修することを表している．このとき，もし研修医 r0 が病院H0 より病院 H1 を好み，病院 H1 は研修医 r2 よりも研修医 r0 を好むのであれば，ブロッキングペア (r0 , H1 ) が存在することになり，M3 は不安定マッチングとなる．このように基本的な概念は安定結婚問題と同様である．
さて多対 1 の安定マッチング問題を解くには，上述した Gale-Shapley アルゴリズムを少し変更すればよい．まず，「男性から女性にプロポーズする」と表現していたものを「研修医から病院へ研修申請をする」と読み替える．また，病院は受け入れ可能な研修医の数の上限に達するまではその申請を受け入れ，上限を越えたときにはその病院の持つ希望研修医リストの順位に基づいて申請受け入れの是非を判断する *12 ．このアルゴリズムの手間の数は研修医の人数と病院の数との積に比例することになる．ただし，研修医がすべての病院をリストに列挙することは非現実的であり，その逆も然りである．正確な解析についての説明は本稿の主題を外れるため，ここでは言及しない．

1 対 1 の安定結婚問題の持つ性質は多対 1 の安定マッチング問題でも成り立つことが知られている．例えば，Gale-Shapley アルゴリズムではプロポーズする側にとって最適な安定マッチングが得られたのと同様に，研修医の方から申請すれば研修医にとって最適な安定マッチングが得られる．またGale-Shapley アルゴリズムでは誰かが嘘のリストを掲げることによってより良い相手とペアになることはできない（これを耐戦略性という）ことが知られており *13 ，多対 1 でも耐戦略性を持つ．これが現実世界での問題解決では特に重要となる性質であることは，研修医が嘘を吐くことで自身を有利*10 ノーベル賞には数学や情報科学の賞はない．数学ではフィールズ賞が，情報科学ではチューリング賞がそれぞれノーベル賞に匹敵すると言われている．

*11 Gale 氏がもう少し長く生きていたら 3 人で受賞したかもしれないと考えるととても残念である．
*12 つまり，新たに申請してきた研修医と既に配属を決定している研修医とを比較し，リストの最下位の研修医の配属を取り消す．

*13 この性質はぜひ具体的に確かめてほしい．

第 11 章 安定結婚問題（宮下健輔）

81に導くことができればどんな問題が生じるかを考えればすぐに理解できるだろう．

3

おわりに
本稿では安定結婚問題とそれを解く Gale-Shapley アルゴリズムを解説し，その応用として研修医配属問題（研修医マッチング制度）を紹介した．研修医配属問題が面白いと感じたら文献 [2] をぜひ読んでもらいたい．制度の歴史的な経緯や研修医配属問題の抱える現実の諸問題について平易に解説されており，WWW 上で検索すれば容易に見つかるだろう．また，安定結婚問題そのものに興味が持てたら文献 [3] もお勧めする．これはオンラインでは手に入らないが，有名な雑誌なので図書館を探すと良いだろう *14 ．
現実世界での問題を考えるとき，それを構成する要素を分析し問題を単純化することで，問題の基本的な構造が明らかなることがよくある．数学や情報科学の分野ではこれをモデル化といい，問題の本質を見極めるためにとても有効な手段とされている．モデル化がうまくいけば，複雑に見えた問題が既知の問題（またはその応用）に帰着し，先人の知恵をそこに適用できることがわかったりする．
まさに「複雑に入り組んだ現代社会に鋭いメスを入れ」るための道具として，この先の人生で活用してほしい．

課題
1. 図 1 の例を用い，Gale-Shapley アルゴリズムで女性側からプロポーズしてマッチングを求めてみよう．得られたマッチングが安定かどうかをチェックし，M2 との相違があればそれはどういう性質のものか，またどうして生じたのか考えてみよう．

2. あるグループ内で考えられるすべてのマッチングを求め，それぞれが安定かどうかを判定する手法が現実的でないのはなぜか，マッチングの総数や問題の規模（スケール）の観点から考え，Gale-Shapley アルゴリズムの手間と比較してみよう．
3. 研修医配属問題のように安定結婚問題の応用として考えられる現実世界の問題が他にないか考
え，実際に適用する際の課題や制約，メリット，デメリット等について具体的に列挙してみよう．

参考文献[1] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American
Mathematical Monthly, Vol. 69, No. 1, pp. 9–15, 1962.
[2] 鎌田雄一郎, 小島武仁, 和光純. マッチング理論とその応用: 研修医の 「地域偏在」 とその解決策.
医療経済研究: 医療経済学会雑誌医療経済研究機構機関紙/医療経済学会, 医療経済研究機構 編,

Vol. 23, No. 1, pp. 5–20, 2011.
[3] 岩間一雄. 安定結婚問題の数理と最近の話題. 数学セミナー, Vol. 47, No. 11, pp. 46–51, 2008.

*14 残念ながら本学図書館にはないようである．