2

ゲール・シャープレーのアルゴリズムの耐戦略性

378
0
$$$$

はじめに

自分のために,勉強したことを逐次まとめます.以下の教科書を参考にしています.

マッチング

男性の集合を$\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$に変更しても,より好みの女性を得られない.

ゲール・シャープレーのアルゴリズム

以下に(男性告白)ゲール・シャープレーのアルゴリズム((男性)GSアルゴリズム)の処理を示す.

ゲール・シャープレーのアルゴリズム
  1. 各男性$i \in \mathcal{A}$の女性のリスト$\mathcal{B}_i$をその男性の選好順$[ j_{i, 1}, j_{i, 2}, ..., j_{i, n} ]$に初期化
  2. while フリーの男性がいる間:
  3.   フリーの男性$i \in \mathcal{A}$を選択
  4.   男性$i$の女性リストの先頭の女性$j \in \mathcal{B}_i$を選択
  5.   if 女性$j$がフリーの場合:
  6.     女性$j$は男性$i$をキープ
  7.   else:
  8.     女性$j$のキープの男性を$i'$とする
  9.     男性$i, i'$のうち,女性$j$の好み男性を$i^*$,もう一方を$i_*$とする
  10.     女性$j$は男性$i_*$を振って男性$i^*$キープ
  11.     男性$i_*$は女性リストから女性$j$を除外

選好$\succsim \in \mathcal{P}$をGSアルゴリズムに入力したときの出力のマッチングを$\mathcal{M}_{\text{gs}}(\succsim)$とし,(男性)GSマッチングと呼ぶ.

ゲール・シャープレーのアルゴリズムの耐戦略性

ゲール・シャープレーのアルゴリズムは耐戦略性を満たす.

背理法で証明する.以下には証明の本筋に関わる主張を示す.その他の主張は補足に示す.

  • ある男性を$i_* \in \mathcal{A}$とする
  • 真の選好を$\succsim \in \mathcal{P}$,GSマッチングを$\mathcal{M} = \mathcal{M}_{\text{gs}}(\succsim)$,GSマッチングでの男性$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}$,GSマッチングを$\mathcal{M}' = \mathcal{M}_{\text{gs}}(\succsim')$,そのGSマッチングでの男性$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}$,GSマッチングを$\mathcal{M}'' = \mathcal{M}_{\text{gs}}(\succsim'')$,そのGSマッチングでの男性$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$でのGSアルゴリズムにおいて,男性集合$\mathcal{X}$で最後に告白する男性を$i_t \in \mathcal{X}$,その相手の女性を$j_t = \mathcal{M}(i_t)$,アルゴリズムでのステップを$t$番目とする.

真の選好$\succsim$でのGSアルゴリズムにおいて,女性$j_t$に告白する男性の集合を$\mathcal{Y}$とする.同様に,選好$\succsim''$でのGSアルゴリズムにおいて,女性$j_t$に告白する男性の集合を$\mathcal{Y}''$とする.

男性集合$\mathcal{Y}''$に含まれる男性$i \in \mathcal{Y}''$は,男性集合$\mathcal{Y}$にも含まれる.

男性$i$が男性集合$\mathcal{Y}''$に含まれるとする.このとき,選好$\succsim''$でのGSアルゴリズムで男性$i$は女性$j_t$に告白する.補題2と補題8より,男性$i$の女性の好みは$j_t \succsim_i \mathcal{M}''(i) \succsim_i \mathcal{M}(i)$である.さらに,補題9より,選好$\succsim$でのGSアルゴリズムで,男性$i$は女性$\mathcal{M}(i)$よりも好みの女性$j_t$にも告白している.したがって,男性$i$が男性集合$\mathcal{Y}''$に含まれるのならば,男性集合$\mathcal{Y}$にも含まれる.■

男性集合$\mathcal{Y}$は男性$i_t$を含む.

定義5より成り立つ.■

男性集合$\mathcal{Y}$は男性$i_t$以外の男性も含む.

男性集合$\mathcal{Y}$は男性$i_t$のみを含むとする.補題3より,男性集合$\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$に告白する.定義5より,男性$i$は男性集合$\mathcal{X}$に含まれない.したがって,真の選好$\succsim$と選好$\succsim''$での男性$i$の相手は同じ女性である.

一方,男性$i$がステップ$t$以前に女性$j_t$に告白しているとする.このとき,ステップ$t$で男性$i_t$が女性$j_t$に告白し,男性$i$は女性$j_t$から振られる.男性$i$はフリーになるため,男性$i$はステップ$t$以降にも他の女性に告白する.定義5より,男性$i$は男性集合$\mathcal{X}$に含まれない.したがって,真の選好$\succsim$と選好$\succsim''$での男性$i$の相手は同じ女性である.■

選好$\succsim''$での男性$i_t$の相手も女性$j_t$

【矛盾】男性$i_t$は男性集合$\mathcal{X}$に含まれること(定義3)に矛盾

したがって,定理1が成り立つ.■

補足

以下の補題8と補題9は,背理法の仮定に依存しない,GSアルゴリズムの本質的な性質である.

任意の選好$\succsim \in \mathcal{P}$,任意の男性$i \in \mathcal{A}$,GSマッチングで男性$i$が告白した任意の女性$j \in \mathcal{B}$に対して,男性$i$は女性$\mathcal{M}_{\text{sg}}(\succsim)(i)$よりも女性$j$の方が好みである.

GSアルゴリズムでは男性は好みの女性から告白し,男性$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'$にも告白する.

GSアルゴリズムでは男性は好みの女性から告白するため.■

投稿日:20201116

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

seytwo
12
2990

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中