こちらに男性と女性をマッチさせるDAアルゴリズムの実行ができるウェブアプリを公開しました。 このページでは、実装したDAアルゴリズム（Gale-Shapleyアルゴリズム）の解説を行います。

安定結婚問題

　DAアルゴリズムは「安定結婚問題」という問題を解くアルゴリズムとして知られています。 安定結婚問題とは、

• 男性と女性がそれぞれ複数人おり、
• 各男性はマッチしたい女性の希望順位表を、各女性はマッチしたい男性の希望順位表を提出し、
• 提出された希望順位表に基づいて男性と女性をマッチさせる

という状況において、参加者に不満の残らないようなマッチのさせ方はどのようなものかを考えるものです。

例

　男性は A、B、C の3人、女性は X、Y、Z の3人とし、提出された希望表は以下の通りであったとします。

　ここで Z さんの第3希望が空白となっているのは、「第2希望までの相手とマッチできなかった場合、それ以外の相手とマッチするよりは誰ともマッチしない方が良い」という意味です。¹ この状況において、不満の残らないマッチというのはどのようなものでしょうか。

安定マッチング

　安定結婚問題の目標は、参加者に不満の残らないマッチを見つけることです。では、まずどのようなマッチでは参加者に不満が残るか考えてみましょう。

　上記の例において、次のようなマッチを考えてみます。

• A さん – X さん
• B さん – Y さん
• C さん – Z さん

この例において、Z さんは自身が希望表に書いていない C さんとマッチしています。 この場合、Z さんは希望しない相手と無理矢理マッチさせられているという点で不満を持つでしょう。 したがって、安定結婚問題におけるマッチはまず次の条件を満たすことが望まれます。

条件 1.　誰も希望表に書いていない相手とはマッチしない。

　では次に、以下のようなマッチではどうでしょうか。

• A さん – X さん
• B さん – Z さん
• C さん – Y さん

B さんと Y さんに着目します。今 B さんは第3希望の Z さんとマッチしていますが、Y さんとのマッチをより希望しています。 一方、Y さんも今マッチしている C さんより、B さんとのマッチをより希望しています。 この場合、B さんと Y さんは抜け駆けして2人でマッチし直すと2人とも得できるため、このマッチ結果には納得しないでしょう。 したがって、次の条件も望まれます。

条件 2.　抜け駆けして2人でマッチし直すことで2人とも得できてしまうようなペアがない。

　上の条件 1. と 2. を満たすマッチならば、参加者は納得できるでしょう。 なぜなら、条件1.から今マッチした人がいるならその人は自分が希望表に書いた人であり、また条件2.から自分が今の結果より望んでいる人は、自分を希望していないか、またはその人にとってより望ましい人とマッチしているからです。 よって、安定結婚問題におけるマッチ結果は、次の安定マッチングであることが望ましいと考えられます。

定義 1.　安定マッチングとは、条件 1. と条件 2. を満たすようなマッチングである。

DAアルゴリズム

　では、その安定マッチングはどのようにして見つけたら良いのでしょうか。 それはDavid Gale氏とLloyd Shapley氏によって提案されたDAアルゴリズムによって見つけることができると知られています。^{2 3}

（男性側提案）DAアルゴリズム

1. 各男性は、最も希望順位の高い女性に申し込む。各女性は、申し込んできた男性の中に希望表に書いた人がいれば、そのうち最も希望順位の高い男性1人を保留し、それ以外の男性を断る。
2. 全ての男性が誰かに保留されるか、申し込める女性がいない状態になるまで、以下を繰り返す。
   • 保留されされていない男性は、希望表に書いていてまだ申し込んでいない女性のうち、最も希望順位の高い女性に申し込む。
   • 各女性は、前ステップで保留した男性と新たに申し込んできた男性のうち、希望表に書いた人がいればその中で最も希望順位の高い男性1人を保留し、それ以外の男性を断る。
3. 繰り返し終了時点において、誰かに保留されている男性は、その男性を保留している女性とマッチさせる。誰にも保留されていない男性と、誰も保留していない女性は、誰ともマッチしなかったという結果とする。

例

　冒頭の例にこの（男性側提案）DAアルゴリズムを適用すると、以下のようになります。

1. 男性 A、B、C はそれぞれ第1希望の女性 X、X、Y に申し込みます。

   	A	B	C	X	Y	Z
   第1希望	X	X	Y	C	A	B
   第2希望	Z	Y	Z	A	B	A
   第3希望	Y	Z	X	B	C

　女性 X は申し込んできた A と B を比較して、A を保留し B を断ります。女性 Y は申し込んできた C を保留します。

2. 前ステップで断られた男性 B は、女性 Y に申し込みます。

   	A	B	C	X	Y	Z
   第1希望	X	X	Y	C	A	B
   第2希望	Z	Y	Z	A	B	A
   第3希望	Y	Z	X	B	C

　女性 Y は、保留している C と新たに申し込んできた B を比較して、B を新たに保留し C を断ります。

3. 前ステップで断られた男性 C は、女性 Z に申し込みます。

   	A	B	C	X	Y	Z
   第1希望	X	X	Y	C	A	B
   第2希望	Z	Y	Z	A	B	A
   第3希望	Y	Z	X	B	C

　女性 Z は、申し込んできた男性 C とのマッチは希望していないので、C を断ります。

4. 前ステップで断られた男性 C は、女性 X に申し込みます。

   	A	B	C	X	Y	Z
   第1希望	X	X	Y	C	A	B
   第2希望	Z	Y	Z	A	B	A
   第3希望	Y	Z	X	B	C

　女性 X は、保留している男性 A と新たに申し込んできた C を比較して、C を新たに保留し A を断ります。

5. 前ステップで断られた男性 A は、女性 Z に申し込みます。

   	A	B	C	X	Y	Z
   第1希望	X	X	Y	C	A	B
   第2希望	Z	Y	Z	A	B	A
   第3希望	Y	Z	X	B	C

　女性 Z は、新たに申し込んできた A を希望表に書いているので、A を保留します。

6. 全ての男性が保留されたのでアルゴリズムが終了します。結果として得られるマッチングは以下の通りです。
   • A さん – Z さん
   • B さん – Y さん
   • C さん – X さん

　このマッチ結果では、全員が希望表に書いた相手とマッチしています（条件 1.）。 また、A、B さんが今の結果より望む X さんは、X さんにとってより望ましい C さんとマッチしており、また C さんが今の結果より望む Y、Z さんは、C さんより望ましい相手とマッチしているか、C さんとのマッチを希望していないため、抜け駆けして2人とも得するペアもありません（条件 2.）。
　よってこの例で（男性側提案）DAアルゴリズムによって得られた上記のマッチングは、安定マッチングとなっています。

DAアルゴリズムの安定性

　上の例に限らず、DAアルゴリズムは常に安定マッチングを返します。

命題 1.　安定結婚問題において、DAアルゴリズムによって得られるマッチングは、常に安定マッチングである。

（証明は末尾の補論参照）

　よって安定結婚問題問題において安定マッチングを得るためには、DAアルゴリズムを用いれば良いことがわかりました。

男性側提案と女性側提案

　これまでは男性側が申し込む形のDAアルゴリズムを説明してきました。 もちろん女性側が申し込む形の女性側提案DAアルゴリズムを考えることもでき、女性側提案DAアルゴリズムによっても安定マッチングを得ることができます。 男性側提案と女性側提案で、結果として得られるマッチングはどのように異なるのでしょうか。

例

　もう一度冒頭の男性 A、B、C 3人、女性 X、Y、Z 3人の例を考えます。

この例において、男性側提案DAアルゴリズムによって得られるマッチングは以下の通りでした。

• A さん – Z さん
• B さん – Y さん
• C さん – X さん

一方、女性側提案DAアルゴリズムを行うと、全ての女性が第1希望の男性に受け入れられ、結果は以下の通りとなります。

• A さん – Y さん
• B さん – Z さん
• C さん – X さん

　この2つのマッチ結果を比較してみましょう。 C さんと X さんの2人についてはどちらのアルゴリズムでも結果が変わりません。
　残りの4人のうち、男性の A さんと B さんについては、男性側提案DAアルゴリズムによって得られるマッチングではそれぞれ第2希望の相手と、女性側提案DAアルゴリズムによって得られるマッチングでは第3希望の相手とマッチしています。 よって、男性2人は男性側提案DAアルゴリズムによって得られるマッチングの方が望ましい結果となっています。
　一方、女性の Y さんと Z さんについては、男性側提案DAアルゴリズムによって得られるマッチングではそれぞれ第2希望の相手と、女性側提案DAアルゴリズムによって得られるマッチングではそれぞれ第1希望の相手とマッチしています。 したがって、女性2人は女性側提案DAアルゴリズムによって得られるマッチングの方が望ましい結果となっています。

男性側最適/女性側最適安定マッチング

　上記の例では、男性側提案DAアルゴリズムによって得られるマッチングは男性側にとって望ましく、女性側提案DAアルゴリズムによって得られるマッチングは女性側にとって望ましいものとなっていました。 この結果は上記の例に限らず一般に成り立つことが知られています。

定義 2.

• 男性 $m$ にとって女性 $w$ が達成可能であるとは、ある安定マッチングが存在して、その安定マッチングにおいて男性 $m$ は女性 $w$ とマッチしていることをいう。
• 男性側最適安定マッチングとは、全ての男性が達成可能な女性のうち最も望ましい女性とマッチするような安定マッチングのことをいう。
• 女性側についても同様に定義する。

命題 2.

• 男性側提案DAアルゴリズムによって得られるマッチングは、男性側最適安定マッチングである。
• 女性側提案DAアルゴリズムによって得られるマッチングは、女性側最適安定マッチングである。

（証明は末尾の補論参照）

　したがって、男性側提案DAアルゴリズムでは男性側にとって最も望ましい安定マッチングとなり、女性側提案DAアルゴリズムでは女性側にとって最も望ましい安定マッチングとなります。⁴

おわりに

　ここで紹介したDAアルゴリズムは、男性と女性のマッチングだけでなく、2つのグループをマッチさせる多くの状況で使うことができ、例えば公立学校と入学させる学生のマッチングや、研修医と病院とのマッチングなどで応用されています。 また、安定結婚問題・DAアルゴリズム以外にも興味深いマッチング問題・マッチングアルゴリズムはたくさんあります。そうした問題の研究を行う「マッチング理論」や、その知見を用いて実際の市場・制度設計を行う「マーケットデザイン」と呼ばれる分野の研究がいま経済学やコンピュータサイエンスの世界で盛んに行われています。 もし興味を持った方がいたらぜひ「マッチング理論」「マーケットデザイン」で調べてみてください。

補論: 命題の証明

命題 1. の証明

（条件 1.）DAアルゴリズムにおいて、男性は希望表に書かれていない女性には申し込みません。 また女性は、希望表に書かれていない男性に申し込まれても保留することはありません。 したがって、男性も女性も希望表に書かれていない相手とマッチすることはないため、DAアルゴリズムによって得られるマッチングは条件 1.を満たします。
（条件 2.）背理法によって示します。ある男性 $m$ と女性 $w$ がいて、DAアルゴリズムによって得られたマッチングにおいて、$m$ と $w$ が抜け駆けして2人とも得できるようなペアになっているとします（仮定A）。 $m$ は $w$ とマッチするよりも不本意な結果となっているので、DAアルゴリズムのどこかのステップで $w$ に申し込み、$w$ は $m$ を断っています。 $w$ は $m$ を希望表に書いているので、断った時点で $m$ よりも望ましい相手（$m’$ とする）を保留しているはずです。 その次のステップで、$w$ は $m’$ を保留しているので、$w$ はこのステップで $m’$ かあるいは $m’$ より望ましい人を保留します。 さらにその後のどのステップでも、$w$ は $m’$ かあるいは $m’$ より望ましい人を保留するはずです。 したがって、最終的に $w$ にとって $m$ とマッチするより不本意な結果となることはあり得ません。これは仮定Aに矛盾するため、DAアルゴリズムによって得られるマッチングは条件 2.を満たします。（証明終わり）

命題 2. の証明

　男性側についてのみ考えます。 男性が達成可能な女性に断られることはない、ということを示せばいいため、これを背理法によって示します。
　男性側提案DAアルゴリズムにおいて、達成可能な女性に断られる男性がいると仮定し、そのうち最も早いステップで断られる男性を $m$ とし（複数いる場合はそのうちの1人）、その時に $m$ が断られる達成可能な女性を $w$ と呼ぶことにします（仮定B）。 また $w$ は $m$ にとって達成可能なので、$m$ と $w$ がマッチする安定マッチングが存在するはずであり、そのうちの1つを $\mu$ とします。
　男性側提案DAにおいて $m$ が $w$ に断られる際、 $w$ が $m$ より望ましいとして保留した男性（$m’$とする）がいます（$*$）。 ここで、$\mu$ における $m’$ のマッチ結果は、$m’$ にとって $w$ とマッチするより望ましくない（$**$）はずです。 なぜなら、まず $\mu$ おいて $w$ は $m$ とマッチするため、$m’$ のマッチ相手は $w$ ではありえません。 また $w$ より望ましい相手とマッチするのであれば、男性側提案DAのステップにおいて $m’$ は $w$ に申し込む以前にその相手に断られているはずですが、その相手は $m’$ にとって達成可能なので「男性 $m$ が最も早いステップで達成可能な女性に断られる男性である」という仮定Bに反するからです。
　したがって、（$*$）より $w$ にとって $\mu$ でマッチする $m$ より $m’$ の方が望ましく、また、（$**$）より $m’$ にとっても $\mu$ でのマッチ結果より $w$ の方が望ましいということになります。 よって、マッチング $\mu$ において $m’$ と $w$ は条件 2.における「抜け駆けして2人も得をするペア」になっており、これは $\mu$ が安定マッチングであることに矛盾します。（証明終わり）