安定マッチングとは、駆け落ちが出ない組み合わせ

安定結婚問題では、「安定マッチング(stable matching)」がゴールになる。

 

安定マッチングとは、簡単に言うと「駆け落ちするペアが出ない状態」を言う。

 

現状の組み合わせから、ペアをどう変更しても、「今と同じか、今より悪くなる」。

 

つまり経済学で言う「パレトー最適(パレトー効率性)」が、達成されている状態が「安定マッチング」ということだ。

 

この安定マッチングを達成するための手順が、アメリカの数理経済学者のデイヴィッド・ゲールとロイド・シャプレーによって定式化されたゲール=シャプレー・アルゴリズム(Gale-Shapley)だ。

 

ゲール=シャプレー・アルゴリズムは、個人としてはベストではないが、全体としてはベストなマッチングを提供する。

 

また手順も簡単なため、社会の様々な組み合わせに利用されている。

 

たとえば公立学校に受験生を振り分ける場合だとか、病院に研修医を派遣する際に、学校や病院の受け入れ基準と、学生や研修医の希望先リストを、ゲール=シャプレー・アルゴリズムによって決めたりしている。

 

ロイド・シャプレーは、この安定マッチングで、ノーベル賞経済学賞を2012年に受賞している。

 

ただゲール=シャプレー・アルゴリズムで一つ問題なのが、「組み合わせは、行動を起こす側にとって有利になる」ということだ。

 

男女のペアを作るというマッチングでは、男性側からプロポーズするか、女性側からプロポーズするかで、安定マッチングの組み合わせが異なる場合が多い。



ゲール=シャプレー・アルゴリズムの問題点

ゲール=シャプレー・アルゴリズムは、安定マッチング問題を解決する、合理的な手順だ。

 

ただしゲール=シャプレー・アルゴリズムには一つ問題がある。

 

というのは、選ぶ側と選ばれる側では、選ぶ側の方が満足度が高くなってしまうのだ。

 

例えば次のような男女グループで、ペアを作るとする。

 

選好順序は次のようになっているとする。

男性陣
  • 東くん (亜香里、花音、すみれ)
  • 小畑くん (亜香里、花音、すみれ)
  • 松村くん (すみれ、花音、亜香里)
女性陣
  • 亜香里 (東くん、松村くん、小畑くん)
  • すみれ (東くん、小畑くん、松村くん)
  • 花音 (松村くん、小畑くん、東くん)

この場合、男性陣からプロポーズすると、誰から選び初めても、

東くん−亜香里、小畑くん−花音、松村くん−すみれ
(男性最良安定マッチング)

というペアができる。

 

一方、女性陣からプロポーズすると

亜香里−東くん、すみれ−小畑くん、花音−松村くん
(女性最良安定マッチング)

というペアになる。

 

ペアの評価

東くんと亜香里さんは、選好順位1位同士なので、男女どちらから選び始めても、このペアは必ずできるし、本人達の満足度も最高だね。

 

小畑くんにとって花音さんは2位、花音さんにとって小畑くんは2位で、まあまあの結果。

 

一方、小畑くんにとって、すみれさんは3位、すみれさんにとって小畑くんは2位なので、女性最良マッチングでは、小畑くんはあまり好まない結果になる。

 

また、松村くんにとって、すみれさんは1位だが、すみれさんにとって松村くんは3位なので、松村くんにとっては最良の結果だが、すみれさんにとっては余り良くない結果。

 

一方、松村くんにとって花音さんは2位だが、花音さんにとって松村くんは1位となるので、松村くんはまあまあの結果、花音さんは最良の結果となっている。


株式投資必勝法 人気ランキング

★第1位★相場師朗の超短期トレードショットガン投資法

★第2位★ラジオNIKKEIでおなじみ相場師朗の株は技術だ、一生モノ!

★第3位★株は5日で利益を出せ!「5日株トレード法」

★第4位★銘柄選びは不要!日経225で稼げ!FURAIBO225

★第5位★週末イチ時間でお宝銘柄!ワンWEEK副業投資プログラム

★第6位★デイトレで稼ぎたい!紫垣デイトレード塾

★第7位★日経225ミニ爆益トレードDVDダブルファントムトレード

このエントリーをはてなブックマークに追加
Z会 大学生・社会人の英数講座