ゲール・シャープレーのアルゴリズムの耐戦略性
はじめに
自分のために，勉強したことを逐次まとめます．以下の教科書を参考にしています．
マッチング
男性の集合を$\mathcal{A} = \{ 1, 2, ... \}$，女性の集合を$\mathcal{B} = \{ a, b, ... \}$，男女の和集合を$\mathcal{U} = \mathcal{A} \cup \mathcal{B}$とする．男性と女性の数はどちらも$|\mathcal{A}| = |\mathcal{B}| = n$とする．
以下の性質を満たすペアの集合$\mathcal{M} = \{ (i_1, j_1), (i_2, j_2), ..., (i_n, j_n) \}$をマッチングと呼ぶ．
- ペアは男女：$\forall (i, j) \in \mathcal{M}, i \in \mathcal{A}, j \in \mathcal{B}$
- ペアは$n$組：$|\mathcal{M}| = n$
- ペアに重複なし：$\forall (i, j), (i', j') \in \mathcal{M}, i \neq i', j \neq j'$
すべてのマッチングの集合を$\mathfrak{M}$とする．
男性$i \in \mathcal{A}$の選好$\succsim_i = (j_{i, 1}, j_{i, 2}, ..., j_{i, n})$をすべての女性$\mathcal{B}$の順列とする．男性$i \in \mathcal{A}$の選好$\succsim_i$の集合を$\mathcal{P}_i$とする．男性$i \in \mathcal{A}$が女性$j' \in \mathcal{B}$以上に女性$j \in \mathcal{B}$を好み（弱好み）であるとき$j \succsim_i j'$，女性$j' \in \mathcal{B}$よりも女性$j \in \mathcal{B}$を好み（強好み）であるとき$j \succ_i j'$と書く．マッチング$\mathcal{M} \in \mathfrak{M}$での男性$i \in \mathcal{A}$の相手の女性を$\mathcal{M}(i) \in \mathcal{B}$と書く．女性についても同様に定義する．すべてのユーザの選好の組（単に選好と呼ぶ）を$\succsim = (\succsim_{i_1}, \succsim_{i_2}, ..., \succsim_{i_n}, \succsim_{j_1}, \succsim_{j_2}, ..., \succsim_{j_n})$とする．選好の集合を$\mathcal{P}$とする．
耐戦略性
マッチングアルゴリズム$f : \mathcal{P} \rightarrow \mathfrak{M}$を，入力が選好，出力がマッチングの関数とする．
マッチングアルゴリズム$f$が男性耐戦略性を満たすとは，以下を満たすことである．
\begin{align}
\forall \succsim \in \mathcal{P}, \forall i \in \mathcal{A}, \forall \succsim_i' \in \mathcal{P}_i, f(\succsim_i, \succsim_{\bar{i}})(i) \succsim_i f(\succsim_i', \succsim_{\bar{i}})(i)
\end{align}
ここで，$\succsim_{\bar{i}}$は男性$i \in \mathcal{A}$以外のユーザの選好の組である．
マッチングアルゴリズムが男性耐戦略性を満たすとき，任意の真の選好$\succsim \in \mathcal{P}$に対して，どの男性$i \in \mathcal{A}$も，自身の選好$\succsim_i \in \succsim$を任意の選好$\succsim_i' \in \mathcal{P}_i$に変更しても，より好みの女性を得られない．
ゲール・シャープレーのアルゴリズム
以下に（男性告白）ゲール・シャープレーのアルゴリズム（（男性）ＧＳアルゴリズム）の処理を示す．
- 各男性$i \in \mathcal{A}$の女性のリスト$\mathcal{B}_i$をその男性の選好順$[ j_{i, 1}, j_{i, 2}, ..., j_{i, n} ]$に初期化
- while フリーの男性がいる間：
- フリーの男性$i \in \mathcal{A}$を選択
- 男性$i$の女性リストの先頭の女性$j \in \mathcal{B}_i$を選択
- if 女性$j$がフリーの場合：
- 女性$j$は男性$i$をキープ
- else：
- 女性$j$のキープの男性を$i'$とする
- 男性$i, i'$のうち，女性$j$の好み男性を$i^*$，もう一方を$i_*$とする
- 女性$j$は男性$i_*$を振って男性$i^*$キープ
- 男性$i_*$は女性リストから女性$j$を除外
選好$\succsim \in \mathcal{P}$をＧＳアルゴリズムに入力したときの出力のマッチングを$\mathcal{M}_{\text{gs}}(\succsim)$とし，（男性）ＧＳマッチングと呼ぶ．
ゲール・シャープレーのアルゴリズムの耐戦略性
ゲール・シャープレーのアルゴリズムは耐戦略性を満たす．
背理法で証明する．以下には証明の本筋に関わる主張を示す．その他の主張は補足に示す．
- ある男性を$i_* \in \mathcal{A}$とする
- 真の選好を$\succsim \in \mathcal{P}$，ＧＳマッチングを$\mathcal{M} = \mathcal{M}_{\text{gs}}(\succsim)$，ＧＳマッチングでの男性$i_*$の相手の女性を$j_* = \mathcal{M}(i_*)$とする
- 真の選好$\succsim = (\succsim_{i_*}, \succsim_{\bar{i_*}})$のうち，男性$i_*$の選好$\succsim_{i_*}$を別の選好$\succsim_{i_*}' \in \mathcal{P}$に変更した選好を$\succsim' = (\succsim_{i_*}', \succsim_{\bar{i_*}}) \in \mathcal{P}$，ＧＳマッチングを$\mathcal{M}' = \mathcal{M}_{\text{gs}}(\succsim')$，そのＧＳマッチングでの男性$i_*$の相手の女性を$j_*' = \mathcal{M}'(i_*)$とする
- 選好$\succsim' = (\succsim_{i_*}', \succsim_{\bar{i_*}})$のうち，男性$i_*$の選好$\succsim_{i_*}'$を女性$j_*'$を先頭に移動した選好$\succsim_{i_*}''$に変更した選好$\succsim'' = (\succsim_{i_*}'', \succsim_{\bar{i_*}}) \in \mathcal{P}$，ＧＳマッチングを$\mathcal{M}'' = \mathcal{M}_{\text{gs}}(\succsim'')$，そのＧＳマッチングでの男性$i_*$の相手の女性を$j_*'' = \mathcal{M}''(i_*)$とする
【背理法の仮定】男性$i_*$は真の選好$\succsim$での相手の女性$j_*$よりも，選好$\succsim'$での相手の女性$j_*'$の方が強好み：$j_*' \succ_{i_*} j_*$
任意の男性$i \in \mathcal{A}$に対して，男性$i$は真の選好$\succsim$での相手の女性$\mathcal{M}(i)$よりも，選好$\succsim''$での相手の女性$\mathcal{M}''(i)$の方が弱好み：
\begin{align}
\forall i \in \mathcal{A}, \mathcal{M}''(i) \succsim_{i} \mathcal{M}(i)
\end{align}
真の選好$\succsim$での相手の女性$\mathcal{M}(i)$よりも，選好$\succsim''$での相手の女性$\mathcal{M}''(i)$の方が強好みな男性の集合を$\mathcal{X}$とする：
\begin{align}
\mathcal{X} = \{ \forall i \in \mathcal{A} : \mathcal{M}''(i) \succ_{i} \mathcal{M}(i) \}
\end{align}
真の選好$\succsim$でのＧＳアルゴリズムにおいて，男性集合$\mathcal{X}$で最後に告白する男性を$i_t \in \mathcal{X}$，その相手の女性を$j_t = \mathcal{M}(i_t)$，アルゴリズムでのステップを$t$番目とする．
真の選好$\succsim$でのＧＳアルゴリズムにおいて，女性$j_t$に告白する男性の集合を$\mathcal{Y}$とする．同様に，選好$\succsim''$でのＧＳアルゴリズムにおいて，女性$j_t$に告白する男性の集合を$\mathcal{Y}''$とする．
男性集合$\mathcal{Y}''$に含まれる男性$i \in \mathcal{Y}''$は，男性集合$\mathcal{Y}$にも含まれる．
男性$i$が男性集合$\mathcal{Y}''$に含まれるとする．このとき，選好$\succsim''$でのＧＳアルゴリズムで男性$i$は女性$j_t$に告白する．補題２と補題８より，男性$i$の女性の好みは$j_t \succsim_i \mathcal{M}''(i) \succsim_i \mathcal{M}(i)$である．さらに，補題９より，選好$\succsim$でのＧＳアルゴリズムで，男性$i$は女性$\mathcal{M}(i)$よりも好みの女性$j_t$にも告白している．したがって，男性$i$が男性集合$\mathcal{Y}''$に含まれるのならば，男性集合$\mathcal{Y}$にも含まれる．■
男性集合$\mathcal{Y}$は男性$i_t$を含む．
定義５より成り立つ．■
男性集合$\mathcal{Y}$は男性$i_t$以外の男性も含む．
男性集合$\mathcal{Y}$は男性$i_t$のみを含むとする．補題３より，男性集合$\mathcal{Y}$に含まれない男性は，男性集合$\mathcal{Y}''$にも含まれない．したがって，男性集合$\mathcal{Y}''$も男性$i$のみを含む．このとき，選好$\succsim''$での男性$i_t$の相手も$j_t$である．よって，真の選好$\succsim$と選好$\succsim''$で男性$i_t$の相手は女性$j_t$で等しい．これは，男性$i_t$が男性集合$\mathcal{X}$に含まれることに矛盾する．■
男性集合$\mathcal{Y}$で女性$j_t$が二番目に好みの男性$i$は，真の選好$\succsim$での相手の女性$\mathcal{M}(i)$と選好$\succsim''$での相手の女性$\mathcal{M}''(i)$が等しい．
男性$i$がステップ$t$以前に女性$j_t$に告白していないとする．このとき，男性$i$はステップ$t$以降に女性$j_t$に告白する．定義５より，男性$i$は男性集合$\mathcal{X}$に含まれない．したがって，真の選好$\succsim$と選好$\succsim''$での男性$i$の相手は同じ女性である．
一方，男性$i$がステップ$t$以前に女性$j_t$に告白しているとする．このとき，ステップ$t$で男性$i_t$が女性$j_t$に告白し，男性$i$は女性$j_t$から振られる．男性$i$はフリーになるため，男性$i$はステップ$t$以降にも他の女性に告白する．定義５より，男性$i$は男性集合$\mathcal{X}$に含まれない．したがって，真の選好$\succsim$と選好$\succsim''$での男性$i$の相手は同じ女性である．■
選好$\succsim''$での男性$i_t$の相手も女性$j_t$．
【矛盾】男性$i_t$は男性集合$\mathcal{X}$に含まれること（定義３）に矛盾
したがって，定理１が成り立つ．■
補足
以下の補題８と補題９は，背理法の仮定に依存しない，ＧＳアルゴリズムの本質的な性質である．
任意の選好$\succsim \in \mathcal{P}$，任意の男性$i \in \mathcal{A}$，ＧＳマッチングで男性$i$が告白した任意の女性$j \in \mathcal{B}$に対して，男性$i$は女性$\mathcal{M}_{\text{sg}}(\succsim)(i)$よりも女性$j$の方が好みである．
ＧＳアルゴリズムでは男性は好みの女性から告白し，男性$i$とペアの女性$j \in \mathcal{B}$は男性$i$が最後に告白する女性であるため．■
任意の選好$\succsim \in \mathcal{P}$，任意の男性$i \in \mathcal{A}$，任意の女性$j, j' \in \mathcal{B}$に対して，男性$i$が女性$j'$よりも女性$j$の方が弱好みであるとき，男性$i$が女性$j$に告白しているのなら，より好みの女性$j'$にも告白する．
ＧＳアルゴリズムでは男性は好みの女性から告白するため．■
