6.4 安定結婚問題

同人数の男性の集まりと女性の集まりがあり、それぞれの人物は異性の集まりに含まれるそれぞれの人物について「どれくらい結婚したいか」を順位付けているとする: 任意の男性は全女性のランキングを、任意の女性は全男性のランキングを持っている。このランキングが対称的とは限らない。例えば Jenniferジェニファー が Bradブラッド を \(1\) 位にランク付けしたとしても、Brad にとって Jennifer は \(2\) 位以下かもしれない。

この状況で、全ての人物を結婚させる ── 任意の男性を一人の女性と結び付け、逆も成り立たせる ── マッチング (matching) を考えよう (複婚や同性婚は考えないものとする¹)。追加の条件として、マッチングは「お互いが相手を現在の結婚相手より好んでいる男女の組が存在しない」という意味で安定 (stable) でなければならないとする。

例えば Brad の \(1\) 位は Angelinaアンジェリーナ で、Angelina の \(1\) 位は Brad だとする。このとき Brad と Angelina を結婚させない任意のマッチングは安定でない。なぜなら、そのようなマッチングでは Brad と Angelina が「お互いが相手を現在の結婚相手より好んでいる男女の組」となるからである。こういった男女の組は結婚生活のリスクである。すぐにでも夜中まで問題集を一緒に解く仲になることだろう！

この不幸な状況を図 \(\text{6.4}\) に示す。図中の人名の近くに書かれた数字 \(1\), \(2\) は、その人物のランキングにおける順位を表す。

一般に任意のマッチングにおいて、お互いが相手を現在の結婚相手より好んでいる男女の組を不穏カップル (rogue couple) と呼ぶことにする。図 \(\text{6.4}\) に示した状況では、Brad と Angelina が結婚していない全てのマッチングで二人は不穏カップルとなる。

不穏カップルが存在すると結婚生活が脅かされるので望ましくない。逆に不穏カップルが存在しなければ、結婚していない全ての男女の組において、少なくとも一方は組のもう一方より現在の結婚相手を好んでいる。そのため浮気を始める誘惑が双方向に生じることは絶対にない。この特徴を持つマッチングに名前を付けておく:

男女全員のランキングが与えられたとき、どうすれば安定マッチングを見つけられるだろうか？ そもそも安定マッチングは存在するだろうか？ \(4\) 人からなる図 \(\text{6.4}\) の例を考えると、まず Brad と Angelina は結婚させても構わないと分かる。そうすれば Brad と Angelina には結婚相手よりランキングが上位の人物が存在しないからである。これを受けて Jennifer と Bobボブ があまり幸せでない結婚をするものの、こうしても二人に浮気相手は生まれない。以上で安定マッチングが得られる。

実は、どんな男女の集まりにも安定マッチングは必ず存在する。この事実は全く明らかでないので、驚くべき結果と言える。また、同性婚を許す場合のマッチング問題では安定マッチングが存在しない状況があり得る。この状況の \(4\) 人からなる例は問題 6.22 にある。しかし男女の結婚だけが許されるときは安定マッチングを構築する単純な手続きが存在し、その手続きの理解・検証で役立つ見事な手法が保存不変条件によって提供される。

6.4.1 婚礼儀式

安定マッチングを構築する手続きは、数日にわたる婚礼儀式 (mating ritual) として説明すると分かりやすく説明できる。初日、全ての男性は女性のランキングを、全ての女性は男性のランキングを持った状態で婚礼儀式は始まる。一日ごとに、次の手続きが実行される:

1. 朝: 男性は自身のランキングで最上位の女性を確認し、その女性の部屋のバルコニーの下に立って求婚のセレナーデを歌う。セレナーデを歌う男性を、それを聞く女性に対する求婚者 (suitor) と呼ぶ。もしランキングに女性が残っていないなら、その男性は部屋から出ずに数学の宿題をする。

2. 昼: 一人以上の求婚者がいる女性は、自身のランキングで最上位の求婚者に向けて「興味が無いわけではありませんの。残ってくださる？」と伝える。他の求婚者には「結婚なんてしないよ！ 失せな！」と叫ぶ。

3. 夜: 「失せな！」と言われた男性は、求婚した女性をランキングから消去する。

4. 停止条件: 求婚者が \(2\) 人以上いる女性がいなくなったとき婚礼儀式は終了し、求婚者が存在する女性は (唯一の) 求婚者と結婚する。

この婚礼儀式に関して、証明したい性質がいくつかある:

• いずれ停止する。

• 全員が結婚する。

• 最終的なマッチングは安定である。

これらの性質は婚礼儀式を状態機械の定義とみなすと証明できる。この状態機械の状態は一日の始まりに更新され、その日にそれぞれの男性がセレナーデを歌う相手の女性 ── つまり、今までに拒絶されていない女性の中でランキングが最上位の女性 ── を保持する。

6.4.2 結婚式はやってくる

婚礼儀式が終了することは簡単に示せる。婚礼儀式が終了しないなら、\(2\) 人以上の求婚者を持つ女性が少なくとも一人いる。よって、その日の終わりに少なくとも \(1\) 人の男性が自身のランキングから女性の名前を消去する。男性と女性がそれぞれ \(n\) 人いるとすれば、初日の朝の時点で男性のランキングの要素数を全て合わせると \(n^{2}\) となる。女性が途中で追加されることはないので、婚礼儀式が一日進むごとに男性のランキングに残る女性の名前の総個数は必ず減少する。よって婚礼儀式は最長でも \(n^{2}\) 日しか続かない。

6.4.3 みんな幸せに暮らしましたとさ...

続いて婚礼儀式が安定マッチングを構築することを証明しよう。この証明では次の非常に有用な事実が利用される: ある日の朝、ある女性に \(1\) 人以上の求婚者がいたとする。このとき、その女性のランキングで最上位の求婚者は (「失せろ！」と言われないので) 次の日もその女性の求婚者となる。このため、任意の女性に対する求婚者には「その女性がこれまでに最も気に入った求婚者」が常に含まれる。よって、\(2\) 日目以降の任意の女性に対する最良の求婚者は前日より良くなるかそのままかのどちらかで、悪くなることはない。これは保存不変条件のような響きを持った性質であり、実際にそうである。これを示そう。述語 \(P\) を次のように定める:

証明 \(m\) のランキングで女性 \(w\) が消去されるのは、\(w\) が \(m\) よりランキング上位の求婚者を持つときのみである。さらに、任意の女性に対する最良の求婚者はそれより優れた求婚者としか入れ替わらない。よって、ある日に \(w\) の最良の求婚者になれなかった男性は、その後の任意の時点で \(w\) の最良の求婚者より \(w\) のランキングで下位のままである。 ■

婚礼儀式が始まるとき男性のランキングからはどの女性の名前も消去されていないので \(P\) は成り立つ。よって不変条件の原理より、\(P\) は婚礼儀式の任意の時点で成り立つ。このことが分かれば、次の定理を証明できる:

証明 背理法で示す。婚礼儀式が終了した時点で結婚していない人物がいると仮定する。男性と女性の人数は等しいから、結婚相手のいない男性 (Bobボブ と呼ぶ) と女性 (Aliceアリス と呼ぶ) が少なくとも一人ずつ存在する。Bob が結婚していないことから、最終日に Bob は誰に対してもセレナーデを歌っておらず、Bob のランキングには女性の名前が残っていないと分かる。特に、Alice は Bob のランキングから消去されている。このとき保存不変条件 \(P\) より Alice は (Bob より優れた) 求婚者を持つ。このとき Alice は結婚していなければならないので、これは矛盾である。 ■

証明 Brad, Jen を婚礼儀式が終わったときに結婚していない男女とする。マッチングが安定だと示すために、これから Brad と Jen が不穏カップルでないと示す。二つの場合を分けて考える:

■

6.4.4 ...特に男性は

婚礼儀式で有利な立場にいるのは男性と女性のどちらだろうか？ 一見すると、それは女性に思える: 女性は自身にとって最良の求婚者を選択し、それ以外の求婚者を拒否できるからである。さらに、日を追うごとに最良の求婚者はさらに優れた男性にだけ変更されることも分かっている。男性は結婚を拒否されていない最良の女性にセレナーデを歌い、そこで拒否されれば二番目に優れた女性にセレナーデを歌う。そのため男性の視点では、選択する女性は悪くなる一方となる。このように考えると、女性が得に思える。

しかし、それは間違っている！ これから婚礼儀式で優先される性別が間違いなく男であることを証明する。

婚礼儀式は一つの安定マッチングを構築するものの、安定マッチングが一つだけとは限らない。例えば、男性と女性の役割を逆転させて婚礼儀式を行うと異なる安定マッチングが得られる場合が多い。異なる安定マッチングではそれぞれの男性が結婚する女性が異なる。ときには特定の男性をどの女性と結婚させても安定マッチングが存在するケースもある。しかし多くの場合では、任意の安定マッチングで結婚相手にならない女性が男性ごとに存在する。例えば図 \(\text{6.4}\) に示した状況では、任意のマッチングで Jennifer と Brad は結婚しない。なぜなら、もし二人が結婚すると Brad と Angelina が不穏カップルになるからである。つまり Jennifer と Brad の安定な結婚は実現不可能である。

証明 ある日が始まるとき \(Q\) が成り立っていて、その日の夜 Bob のランキングから Alice が消去されると仮定する。これから Alice は Bob の実現可能な結婚相手でないと示す。このとき次の日にも \(Q\) が成り立つので、\(Q\) が保存不変条件だと証明される。

Bob が自身のランキングから Alice を消去するとき、Alice には Bob よりも優れた求婚者が存在する。この求婚者を Tedテッド とする。仮定より、今考えている日が始まった時点で \(Q\) が成り立つので、Ted の実現可能な求婚者は全て Ted のランキングに残っている。よって Ted のランキングで Alice は他の実現可能な求婚者より上位にいる。そのため Alice と Bob が結婚するとき、Ted は Alice より下位の女性と結婚する。このとき Alice と Ted は不穏カップルとなるので、マッチングは安定でない。よって任意の安定マッチングで Alice と Bob は結婚しない。つまり Alice は Bob の実現可能な結婚相手ではない。 ■

安定マッチングは少なくとも一つ存在する (婚礼儀式で構築できる) ので、どの人物にも最適な結婚相手 (そして最悪な結婚相手) が存在する。補題 6.4.7 からは、婚礼儀式に関する重要な性質が分かる:

証明 婚礼儀式で結婚した任意の男女を Bob, Alice とする。Bob のランキングで Alice より上位の人物は全員ランキングから消去されている。保存不変条件 \(Q\) より、それらの消去された女性は Bob にとって実現可能な結婚相手ではない。よって Bob にとって Alice は実現可能な結婚相手の中で最上位の女性、つまり最適な結婚相手である。 ■

証明 対称性より、任意の男性の最適な妻の最悪な夫がその男性自身だと示せば十分である。

Bob の最適な結婚相手が Alice だと仮定する。このとき任意の安定マッチングにおいて、もし Alice のランキングで Alice の結婚相手より Bob の方が上位なら、そのとき Bob は Alice 以外の女性と結婚しているので、Alice と Bob が不穏カップルとなる。よって Alice の実現可能な結婚相手は全員 Alice のランキングで Bob と同じか Bob より上位にある。つまり Bob は Alice の最悪の結婚相手である。 ■

6.4.5 応用

本節で紹介した「婚礼儀式」アルゴリズムは 1962 年に D. Galeゲール と L. S. Shapleyシャープレイ によって初めて発表された。ただ、両氏も知らなかったことだが、似たアルゴリズムは全国研修医マッチングプログラム (National Resident Matching Program, NRMP) で研修医を病院に割り当てるために十年も前から使われていた。NRMP は 1952 年に設立された機関であり、研修医 (以前は「インターンシップ」と呼ばれた) を始める医学部の卒業生を医療機関に割り当てる。病院と卒業生がそれぞれ婚礼儀式における男性および女性となる³。この儀式的なアルゴリズムが採用される前は、安定でないマッチングが原因の割り当て結果に対する不満がよく聞かれ、それに対する場当たり的な対策が取られていた。しかし婚礼儀式アルゴリズムが問題を非常に鮮やかに解決したので、この方法は少なくとも 1989 年から本質的に変化していない⁴。このアルゴリズムの発見と関連する研究が評価され、Shapley は 2012 年にノーベル経済学賞を受賞した。

驚くことではないが、この「婚礼儀式」は少なくとも一つの大規模な婚活サイトで利用されている。もちろんセレナーデの歌唱は含まれない ── 全てはコンピューター上で行われる。