こんにちは。
このブログを通して、経済学やゲーム理論の面白い研究を色々と分かりやすく紹介していきたいと思います。
経済学やゲーム理論に興味のある方が少しでも増えたら嬉しい限りです。
最初のトピックとして、安定結婚問題と呼ばれるお話を中心に、マーケットデザイン（市場設計）という新たな経済学の分野を、何回かに分けて紹介していきたいと思います。
この記事ではまず安定結婚問題とその現実世界での応用を紹介していきます。
早速行ってみましょう！
安定結婚問題とは？
結婚問題とは言っても、実は「安月給で結婚生活が安定しない…」とか「夫が育児手伝ってくれない…」みたいな話ではありません。
そういった話を期待していた方には、お詫びと言っては何ですが東大の先生が書かれた以下の本をオススメします……！こちらもとても興味深い内容です。
気を取り直して、安定結婚問題とは、1962年にDavid GaleとLloyd Shapleyという2人の数学者・経済学者たちが考えた数学的な問題の名前です。
数学的といっても全くもって難しいものではありません。
非常にシンプルな話なので、内容自体は恐らく小学生でも理解できるものになっています。
安定結婚問題を婚活パーティーに例えると
簡単な例で見ていきましょう。
3人の男性と3人の女性が婚活パーティーに参加しています。彼らはパーティーを通して、最終的に誰か一人の異性とペアを作らないといけないとします。
さてパーティーでの交流を通して、それぞれの男性は3人の女性について好みの順番を決めました。それぞれの女性も同様に、3人の男性について好みの順番を決めました。
例えば、こんな感じに決まったとしましょう。
男性の好みは
- 男1の好み: 女1 > 女3 > 女2,
- 男2の好み: 女3 > 女1 > 女2,
- 男3の好み: 女1 > 女2 > 女3.
女性の好みは
- 女1の好み: 男2 > 男1 > 男3,
- 女2の好み: 男2 > 男3 > 男1,
- 女3の好み: 男1 > 男2 > 男3.
一応言っておくと">"は左の方が右より好きという事を意味します！
さて、この婚活パーティーでは、最終的にどのようなペアがマッチしそうでしょうか？
Gale-Shapleyアルゴリズム
先程の2人はこの問題に対して、ある1つの答え方を提案しました。この答え方は受入保留アルゴリズム、もしくは2人の名前をそのままとってGale-Shapleyアルゴリズムと呼ばれています。
Shapleyはこの研究とその後の応用への貢献に対して、2012年にいわゆるノーベル経済学賞を受賞しました（Galeは残念ながら当時すでに亡くなっていたので受賞はできませんでしたが、存命であれば受賞していただろうとされてます）。
どうしてこの答え方がそんなに評価されているのでしょうか？その答えは、Gale-Shapleyアルゴリズムの持つ「とても良い性質」にあります。
Gale-Shapleyアルゴリズムは以下のような手順によってペアを決めます。
① それぞれの男性が1番好きな女性にアプローチをする。
② 女性はアプローチを受けたら、そのアプローチの受入を保留する。アプローチを複数受けているなら一つだけ保留して、他は断る。アプローチがなければ何もしない。
③ 断られた男性は次のラウンドで他の好きな女性にアプローチをする。受入を保留された男性は次のラウンドは何もしない。
④ 以下②～③を繰り返して、全員が保留組となったら、それがそのままペアとなり終了。
ここでは男性がアプローチをする側としましたが、男女を逆にしても本質的な違いはなく、女性がアプローチする側とする事も可能です。
また、分かりやすいように順番にアプローチをするとしましたが、この手順自体は全員の好みさえ分かれば、コンピュータで自動的に行う事が出来ます。
さてこれのどこに「良い性質」があるのでしょうか？
さっきの例でGale-Shapleyアルゴリズムを使ってみる
まずは先程の例で実際にGale-Shapleyアルゴリズムを使って、どのペアがマッチしそうかをみてみましょう。先程の男女の好みを再掲しますので、皆さんも一緒に確認してみてください！
男性の好みは
- 男1の好み: 女1 > 女3 > 女2,
- 男2の好み: 女3 > 女1 > 女2,
- 男3の好み: 女1 > 女2 > 女3.
女性の好みは
- 女1の好み: 男2 > 男1 > 男3,
- 女2の好み: 男2 > 男3 > 男1,
- 女3の好み: 男1 > 男2 > 男3.
第1ラウンド
男1は1番好きな女1にアプローチする。
男2は1番好きな女3にアプローチする。
男3は1番好きな女1にアプローチする。
女1は複数のアプローチを受けているので、より好きな男1のアプローチを保留して男3のアプローチを断る。
女2はアプローチを受けていないので、何もしない。
女3は受けた男2のアプローチを保留する。
第2ラウンド
男1はアプローチを保留されているので、何もしない。
男2はアプローチを保留されているので、何もしない。
男3はアプローチを断られたので、2番目に好きな女2にアプローチする。
女1はそのまま男1のアプローチを保留する。
女2は2番目に好きな男3のアプローチを保留する。
女3はそのまま男2のアプローチを保留する。
全員が保留組となったので、それぞれの組がそのままペアとなり終了。
結果は(男1, 女1), (男2, 女3), (男3, 女2)となりました！
「良い性質」
Gale-Shapleyアルゴリズムには主に3つの良い性質があります。その3つとは、
① 有限回の手順で必ず結果が出る事、
② 出てくる結果が必ず"安定的"である事、
③ アプローチする側が自分の好みに嘘をつく必要がない事
の3つで、特に②と③は経済学的に非常に重要な性質です。
①は、問題の答え方として最低限必要な性質なのが分かると思います。GaleとShapleyはこの性質が、実は男女の数が有限であるなら必ず成り立つことを示しました。
②について、ここで安定的であるとは、「最後にマッチしたペアを崩して、別の異性とくっつきたがるような男女のペアがいない」事を言います。
先程の例では、(男1, 女1), (男2, 女3), (男3, 女2)が結果として現れました。仮に男3が女2とのペアを崩して、別の女性とペアを作ろうとするとしましょう。そうすると、女1は男1の方が男3より好きなので、今のペアを崩そうとしません。同様に、女2も男2の方が男3より好きなので、今のペアを崩そうとしません。結局、男3は今のペアで満足するしかありません。そしてこれは男3だけではなく全員に当てはまります。
このように、Gale-Shapleyアルゴリズムによって得られるマッチには、男女がどんな好みを持っていても、そのマッチから抜け出して新しいペアを作る男女が絶対にいない事が示されています。
実際に別の好みの組を作ってみて、Gale-Shapleyアルゴリズムを使ってみると、この事が確認できると思います。
最後に③はどういう事かというと、アプローチする側が自分の好みの順番について嘘をつくと損をするという事です。これは、Gale-Shapleyアルゴリズムの手順をみればほぼ明らかな事です。というのも、もし男性が自分の好みの順番について嘘を付いてアプローチをするならば、本当に好きな人から順番にアプローチすることが出来ず、好き度合いが高い人とマッチする可能性が低くなってしまうからです。
嘘をつくと損をするという性質は大変重要で、経済学ではこれを「耐戦略性を満たす」といいます。
市場設計への応用
さて、ここまで安定結婚問題とその答え方の1つであるGale-Shapleyアルゴリズムを紹介しました。
ここからは、これらが実際どのように現実世界で使われているのか軽く紹介します！
経済学やゲーム理論の知見を用いて、より良い市場を設計する事を目的とした分野を「マーケットデザイン」といいます。Gale-Shapleyアルゴリズムは、マーケットデザインの最初期の研究として現在位置づけられています。
さっきの通り、Gale-Shapleyアルゴリズムは非常に良い性質を持っていて、しかもアルゴリズム自体が非常にシンプルなので、国内外問わず様々な分野で応用されています。
まず、日本では研修医振り分け制度への応用が有名です。医学部の学生さんたちは、医学部を卒業した後、研修医としてどこかの病院に配属をしなければいけません。この配属先を研修医がアプローチするGale-Shapleyアルゴリズムを用いて決めているのです（正確には一つの病院は複数の研修医を受け入れるのでちょっと修正したものを使っています）。
マーケットデザインという分野はもっともっと色々な分野で応用がされており、東京大学の進学振り分け制度やアメリカの腎臓移植交換ネットワークなどがその代表例です。
次回はマーケットデザインについて、さらに詳しくお話していきたいと思います！
ここまで読んでいただきありがとうございました。
ではでは。
