はじめに
自分のために,勉強したことを逐次まとめます.以下の教科書を参考にしています.
マッチング
男性の集合を,女性の集合を,男女の和集合をとする.男性と女性の数はどちらもとする.
以下の性質を満たすペアの集合をマッチングと呼ぶ.
すべてのマッチングの集合をとする.
男性の選好をすべての女性の順列とする.男性の選好の集合をとする.男性が女性以上に女性を好み(弱好み)であるとき,女性よりも女性を好み(強好み)であるときと書く.マッチングでの男性の相手の女性をと書く.女性についても同様に定義する.すべてのユーザの選好の組(単に選好と呼ぶ)をとする.選好の集合をとする.
耐戦略性
マッチングアルゴリズムを,入力が選好,出力がマッチングの関数とする.
マッチングアルゴリズムが男性耐戦略性を満たすとは,以下を満たすことである.
ここで,は男性以外のユーザの選好の組である.
マッチングアルゴリズムが男性耐戦略性を満たすとき,任意の真の選好に対して,どの男性も,自身の選好を任意の選好に変更しても,より好みの女性を得られない.
ゲール・シャープレーのアルゴリズム
以下に(男性告白)ゲール・シャープレーのアルゴリズム((男性)GSアルゴリズム)の処理を示す.
ゲール・シャープレーのアルゴリズム
- 各男性の女性のリストをその男性の選好順に初期化
- while フリーの男性がいる間:
- フリーの男性を選択
- 男性の女性リストの先頭の女性を選択
- if 女性がフリーの場合:
- 女性は男性をキープ
- else:
- 女性のキープの男性をとする
- 男性のうち,女性の好み男性を,もう一方をとする
- 女性は男性を振って男性キープ
- 男性は女性リストから女性を除外
選好をGSアルゴリズムに入力したときの出力のマッチングをとし,(男性)GSマッチングと呼ぶ.
ゲール・シャープレーのアルゴリズムの耐戦略性
ゲール・シャープレーのアルゴリズムは耐戦略性を満たす.
背理法で証明する.以下には証明の本筋に関わる主張を示す.その他の主張は補足に示す.
- ある男性をとする
- 真の選好を,GSマッチングを,GSマッチングでの男性の相手の女性をとする
- 真の選好のうち,男性の選好を別の選好に変更した選好を,GSマッチングを,そのGSマッチングでの男性の相手の女性をとする
- 選好のうち,男性の選好を女性を先頭に移動した選好に変更した選好,GSマッチングを,そのGSマッチングでの男性の相手の女性をとする
【背理法の仮定】男性は真の選好での相手の女性よりも,選好での相手の女性の方が強好み:
任意の男性に対して,男性は真の選好での相手の女性よりも,選好での相手の女性の方が弱好み:
真の選好での相手の女性よりも,選好での相手の女性の方が強好みな男性の集合をとする:
真の選好でのGSアルゴリズムにおいて,男性集合で最後に告白する男性を,その相手の女性を,アルゴリズムでのステップを番目とする.
真の選好でのGSアルゴリズムにおいて,女性に告白する男性の集合をとする.同様に,選好でのGSアルゴリズムにおいて,女性に告白する男性の集合をとする.
男性が男性集合に含まれるとする.このとき,選好でのGSアルゴリズムで男性は女性に告白する.補題2と補題8より,男性の女性の好みはである.さらに,補題9より,選好でのGSアルゴリズムで,男性は女性よりも好みの女性にも告白している.したがって,男性が男性集合に含まれるのならば,男性集合にも含まれる.■
男性集合は男性のみを含むとする.補題3より,男性集合に含まれない男性は,男性集合にも含まれない.したがって,男性集合も男性のみを含む.このとき,選好での男性の相手もである.よって,真の選好と選好で男性の相手は女性で等しい.これは,男性が男性集合に含まれることに矛盾する.■
男性集合で女性が二番目に好みの男性は,真の選好での相手の女性と選好での相手の女性が等しい.
男性がステップ以前に女性に告白していないとする.このとき,男性はステップ以降に女性に告白する.定義5より,男性は男性集合に含まれない.したがって,真の選好と選好での男性の相手は同じ女性である.
一方,男性がステップ以前に女性に告白しているとする.このとき,ステップで男性が女性に告白し,男性は女性から振られる.男性はフリーになるため,男性はステップ以降にも他の女性に告白する.定義5より,男性は男性集合に含まれない.したがって,真の選好と選好での男性の相手は同じ女性である.■
【矛盾】男性は男性集合に含まれること(定義3)に矛盾
したがって,定理1が成り立つ.■
補足
以下の補題8と補題9は,背理法の仮定に依存しない,GSアルゴリズムの本質的な性質である.
任意の選好,任意の男性,GSマッチングで男性が告白した任意の女性に対して,男性は女性よりも女性の方が好みである.
GSアルゴリズムでは男性は好みの女性から告白し,男性とペアの女性は男性が最後に告白する女性であるため.■
任意の選好,任意の男性,任意の女性に対して,男性が女性よりも女性の方が弱好みであるとき,男性が女性に告白しているのなら,より好みの女性にも告白する.
GSアルゴリズムでは男性は好みの女性から告白するため.■