メカニズム・デザインの受入保留アルゴリズム（ゲール=シャプレーアルゴリズム）について

はじめに

　世の中の仕組みにおいて、様々な場面でマッチングが重要であることが多くあります。

　例えば、

　　・婚活パーティーにおける男女の組み合わせ
　　・就職における企業と志望者の組み合わせ
　　・団体旅行における部屋の割り当て　　　　など

　この点で、経済学のメカニズム・デザインにおいては、どのようなマッチングがよいのかが研究されています。

　ここでは、カップル・パーティーを例に、受入保留アルゴリズム（ゲール=シャプレーアルゴリズム）について、説明します。

　男女3人ずつで、カップル・パーティーが開かれるとします。どの男女も、カップルになりたいと思っています。
　ただ、次のような順序で、それぞれの男女が好印象を抱いているとしましょう。

　例えば、男性Aは、女性1が最も好きで、次に女性3、3番目に女性2が好きといった具合です。

　カップルになれないことは、どの男女も嫌なので、誰かとカップルになりたいと思っています。
　このとき、男女それぞれがどのようなカップルになったら、全体として、よいのでしょうか。

　男性Aと女性1は、それぞれを1位に挙げているので、相思相愛で問題はないでしょうが、男性Bは女性2が最も好きですが、女性2は男性Cが最も好きといった具合で、少しややこしいことになっています。

　このときに使えるのが、受入保留アルゴリズム（ゲール=シャプレーアルゴリズム、GSアルゴリズム）です。

　受入保留アルゴリズムにおいては、次のような手順で、カップルを選んでいきます。

①告白1
　まずは、一方から告白を行います。この例では、男性から告白を行う場合を考えます。
　上記の表から、それぞれの1位の女性を選ぶので、次のようになります。

　　男性A ⇒　女性1
　　男性B ⇒　女性2
　　男性C ⇒　女性1

②選択1
　男性からの告白を受けた女性は、上記の好みから。

　　女性1　⇒　男性Aを仮受入
　　女性2　⇒　男性Bを仮受入

を行うことになります。男性Cは女性1に振られ、女性3は誰からも告白されていないことになります。
　また、あくまでも仮受入なので、まだカップルは成立していません。

③告白2
　次に、仮受入が行われていない男性Cについて考えます。
　男性Cは2番目に女性2が好きなので、女性2に告白します。

④選択2
　男性Cから告白を受けた女性2は、最初に告白された男性Bと今告白された男性Cを比べます。
　女性2にとっては、改めて告白された男性Cのほうが好印象なので、仮受入を変更します。

　　女性2　⇒　男性Cを仮受入

⑤告白3
　女性2に振られることになった男性Bは、2番目に好きな女性1に告白します。

⑥選択3
　しかし、女性1は男性Aのほうが好きなので、男性Bは振られます。

⑦告白4
　振られた男性Bは、残った女性3に告白します。

⑧選択4
　女性3は誰からも告白されてこなかったので、男性Bの告白を受け入れます。

　　女性3　⇒　男性Bを仮受入

　以上から、すべての男性の告白が女性に受入れられ、カップルの成立となります。

　　男性A　ー　女性1
　　男性B　ー　女性3
　　男性C　ー　女性2

　アルゴリズム自体は上記のとおりですが、このアルゴリズムの良さは、ベストではないが次善的には望ましいということです。

　そして、男性のうち1人が、ベストではないからといって、他の女性にアプローチをしても意味がないという点で、安定的なマッチングとなっています。

　例えば、男性Bを考えると、男性Bは3番目に好きな女性3とカップルになることになりました。
　しかし、男性Bがいくら他の女性が好きだといっても、

　　女性1にとって　⇒　男性A > 男性B
　　女性2にとって　⇒　男性C > 男性B

なので、男性Bにはどうしようもありません。

　同様に、男性Cにとっても、2番目に好きな女性2とカップルになることになりますが、

　　女性2にとって　⇒　男性A > 男性C

であることから、男性2は2番目の女性2とカップルになるのが、次善となります。

　このように、すべての人が最も望ましい結果ではありませんが、安定的なマッチングとなるのが、受入保留アルゴリズムとなっています。

　このほかに、この受入保留アルゴリズムは、告白する男性が、本当は好きではない相手に告白するといった嘘をつくというインセンティブが働かないことが知られています（耐戦略性と言います）。

　この点でも、受入保留アルゴリズムは、よいマッチング方法だとされます。
　（ただし、告白される女性には、好きな男性について嘘をつくインセンティブは排除できず、耐戦略性は満たしていません）

　　坂井豊貴、オークション・ラボ『メカニズムデザインで勝つ』