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

491

はじめに

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

安定マッチングの数理とアルゴリズム -トラブルのない配属を求めて-

マッチング

男性の集合を $A = {1, 2, . . .}$ ，女性の集合を $B = {a, b, . . .}$ ，男女の和集合を $U = A \cup B$ とする．男性と女性の数はどちらも $| A | = | B | = n$ とする．

以下の性質を満たすペアの集合 $M = {(i_{1}, j_{1}), (i_{2}, j_{2}), . . ., (i_{n}, j_{n})}$ をマッチングと呼ぶ．

ペアは男女： $\forall (i, j) \in M, i \in A, j \in B$
ペアは $n$ 組： $| M | = n$
ペアに重複なし： $\forall (i, j), (i^{'}, j^{'}) \in M, i \neq i^{'}, j \neq j^{'}$

すべてのマッチングの集合を $M$ とする．

男性 $i \in A$ の選好 $≿_{i} = (j_{i, 1}, j_{i, 2}, . . ., j_{i, n})$ をすべての女性 $B$ の順列とする．男性 $i \in A$ の選好 $≿_{i}$ の集合を $P_{i}$ とする．男性 $i \in A$ が女性 $j^{'} \in B$ 以上に女性 $j \in B$ を好み（弱好み）であるとき $j ≿_{i} j^{'}$ ，女性 $j^{'} \in B$ よりも女性 $j \in B$ を好み（強好み）であるとき $j ≻_{i} j^{'}$ と書く．マッチング $M \in M$ での男性 $i \in A$ の相手の女性を $M (i) \in B$ と書く．女性についても同様に定義する．すべてのユーザの選好の組（単に選好と呼ぶ）を $≿= (≿_{i_{1}}, ≿_{i_{2}}, . . ., ≿_{i_{n}}, ≿_{j_{1}}, ≿_{j_{2}}, . . ., ≿_{j_{n}})$ とする．選好の集合を $P$ とする．

耐戦略性

マッチングアルゴリズム $f : P \to M$ を，入力が選好，出力がマッチングの関数とする．

マッチングアルゴリズム $f$ が男性耐戦略性を満たすとは，以下を満たすことである．
$\begin{array}{r} \forall ≿\in P, \forall i \in A, \forall ≿_{i}^{'} \in P_{i}, f (≿_{i}, ≿_{\bar{i}}) (i) ≿_{i} f (≿_{i}^{'}, ≿_{\bar{i}}) (i) \end{array}$
ここで， $≿_{\bar{i}}$ は男性 $i \in A$ 以外のユーザの選好の組である．

マッチングアルゴリズムが男性耐戦略性を満たすとき，任意の真の選好 $≿\in P$ に対して，どの男性 $i \in A$ も，自身の選好 $≿_{i} \in≿$ を任意の選好 $≿_{i}^{'} \in P_{i}$ に変更しても，より好みの女性を得られない．

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

以下に（男性告白）ゲール・シャープレーのアルゴリズム（（男性）ＧＳアルゴリズム）の処理を示す．

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

各男性 $i \in A$ の女性のリスト $B_{i}$ をその男性の選好順 $[j_{i, 1}, j_{i, 2}, . . ., j_{i, n}]$ に初期化
while フリーの男性がいる間：
　　フリーの男性 $i \in A$ を選択
　　男性 $i$ の女性リストの先頭の女性 $j \in B_{i}$ を選択
　　if 女性 $j$ がフリーの場合：
　　　　女性 $j$ は男性 $i$ をキープ
　　else：
　　　　女性 $j$ のキープの男性を $i^{'}$ とする
　　　　男性 $i, i^{'}$ のうち，女性 $j$ の好み男性を $i^{*}$ ，もう一方を $i_{*}$ とする
　　　　女性 $j$ は男性 $i_{*}$ を振って男性 $i^{*}$ キープ
　　　　男性 $i_{*}$ は女性リストから女性 $j$ を除外

選好 $≿\in P$ をＧＳアルゴリズムに入力したときの出力のマッチングを $M_{gs} (≿)$ とし，（男性）ＧＳマッチングと呼ぶ．

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

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

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

ある男性を $i_{*} \in A$ とする
真の選好を $≿\in P$ ，ＧＳマッチングを $M = M_{gs} (≿)$ ，ＧＳマッチングでの男性 $i_{*}$ の相手の女性を $j_{*} = M (i_{*})$ とする
真の選好 $≿= (≿_{i_{*}}, ≿_{\bar{i_{*}}})$ のうち，男性 $i_{*}$ の選好 $≿_{i_{*}}$ を別の選好 $≿_{i_{*}}^{'} \in P$ に変更した選好を $≿^{'} = (≿_{i_{*}}^{'}, ≿_{\bar{i_{*}}}) \in P$ ，ＧＳマッチングを $M^{'} = M_{gs} (≿^{'})$ ，そのＧＳマッチングでの男性 $i_{*}$ の相手の女性を $j_{*}^{'} = M^{'} (i_{*})$ とする
選好 $≿^{'} = (≿_{i_{*}}^{'}, ≿_{\bar{i_{*}}})$ のうち，男性 $i_{*}$ の選好 $≿_{i_{*}}^{'}$ を女性 $j_{*}^{'}$ を先頭に移動した選好 $≿_{i_{*}}^{″}$ に変更した選好 $≿^{″} = (≿_{i_{*}}^{″}, ≿_{\bar{i_{*}}}) \in P$ ，ＧＳマッチングを $M^{″} = M_{gs} (≿^{″})$ ，そのＧＳマッチングでの男性 $i_{*}$ の相手の女性を $j_{*}^{″} = M^{″} (i_{*})$ とする

【背理法の仮定】男性 $i_{*}$ は真の選好 $≿$ での相手の女性 $j_{*}$ よりも，選好 $≿^{'}$ での相手の女性 $j_{*}^{'}$ の方が強好み： $j_{*}^{'} ≻_{i_{*}} j_{*}$

任意の男性 $i \in A$ に対して，男性 $i$ は真の選好 $≿$ での相手の女性 $M (i)$ よりも，選好 $≿^{″}$ での相手の女性 $M^{″} (i)$ の方が弱好み：
$\begin{array}{r} \forall i \in A, M^{″} (i) ≿_{i} M (i) \end{array}$

真の選好 $≿$ での相手の女性 $M (i)$ よりも，選好 $≿^{″}$ での相手の女性 $M^{″} (i)$ の方が強好みな男性の集合を $X$ とする：
$\begin{array}{r} X = {\forall i \in A : M^{″} (i) ≻_{i} M (i)} \end{array}$

真の選好 $≿$ でのＧＳアルゴリズムにおいて，男性集合 $X$ で最後に告白する男性を $i_{t} \in X$ ，その相手の女性を $j_{t} = M (i_{t})$ ，アルゴリズムでのステップを $t$ 番目とする．

真の選好 $≿$ でのＧＳアルゴリズムにおいて，女性 $j_{t}$ に告白する男性の集合を $Y$ とする．同様に，選好 $≿^{″}$ でのＧＳアルゴリズムにおいて，女性 $j_{t}$ に告白する男性の集合を $Y^{″}$ とする．

男性集合 $Y^{″}$ に含まれる男性 $i \in Y^{″}$ は，男性集合 $Y$ にも含まれる．

男性 $i$ が男性集合 $Y^{″}$ に含まれるとする．このとき，選好 $≿^{″}$ でのＧＳアルゴリズムで男性 $i$ は女性 $j_{t}$ に告白する．補題２と補題８より，男性 $i$ の女性の好みは $j_{t} ≿_{i} M^{″} (i) ≿_{i} M (i)$ である．さらに，補題９より，選好 $≿$ でのＧＳアルゴリズムで，男性 $i$ は女性 $M (i)$ よりも好みの女性 $j_{t}$ にも告白している．したがって，男性 $i$ が男性集合 $Y^{″}$ に含まれるのならば，男性集合 $Y$ にも含まれる．■

男性集合 $Y$ は男性 $i_{t}$ を含む．

定義５より成り立つ．■

男性集合 $Y$ は男性 $i_{t}$ 以外の男性も含む．

男性集合 $Y$ は男性 $i_{t}$ のみを含むとする．補題３より，男性集合 $Y$ に含まれない男性は，男性集合 $Y^{″}$ にも含まれない．したがって，男性集合 $Y^{″}$ も男性 $i$ のみを含む．このとき，選好 $≿^{″}$ での男性 $i_{t}$ の相手も $j_{t}$ である．よって，真の選好 $≿$ と選好 $≿^{″}$ で男性 $i_{t}$ の相手は女性 $j_{t}$ で等しい．これは，男性 $i_{t}$ が男性集合 $X$ に含まれることに矛盾する．■

男性集合 $Y$ で女性 $j_{t}$ が二番目に好みの男性 $i$ は，真の選好 $≿$ での相手の女性 $M (i)$ と選好 $≿^{″}$ での相手の女性 $M^{″} (i)$ が等しい．

男性 $i$ がステップ $t$ 以前に女性 $j_{t}$ に告白していないとする．このとき，男性 $i$ はステップ $t$ 以降に女性 $j_{t}$ に告白する．定義５より，男性 $i$ は男性集合 $X$ に含まれない．したがって，真の選好 $≿$ と選好 $≿^{″}$ での男性 $i$ の相手は同じ女性である．

一方，男性 $i$ がステップ $t$ 以前に女性 $j_{t}$ に告白しているとする．このとき，ステップ $t$ で男性 $i_{t}$ が女性 $j_{t}$ に告白し，男性 $i$ は女性 $j_{t}$ から振られる．男性 $i$ はフリーになるため，男性 $i$ はステップ $t$ 以降にも他の女性に告白する．定義５より，男性 $i$ は男性集合 $X$ に含まれない．したがって，真の選好 $≿$ と選好 $≿^{″}$ での男性 $i$ の相手は同じ女性である．■

選好 $≿^{″}$ での男性 $i_{t}$ の相手も女性 $j_{t}$ ．

【矛盾】男性 $i_{t}$ は男性集合 $X$ に含まれること（定義３）に矛盾

したがって，定理１が成り立つ．■

補足

以下の補題８と補題９は，背理法の仮定に依存しない，ＧＳアルゴリズムの本質的な性質である．

任意の選好 $≿\in P$ ，任意の男性 $i \in A$ ，ＧＳマッチングで男性 $i$ が告白した任意の女性 $j \in B$ に対して，男性 $i$ は女性 $M_{sg} (≿) (i)$ よりも女性 $j$ の方が好みである．

ＧＳアルゴリズムでは男性は好みの女性から告白し，男性 $i$ とペアの女性 $j \in B$ は男性 $i$ が最後に告白する女性であるため．■

任意の選好 $≿\in P$ ，任意の男性 $i \in A$ ，任意の女性 $j, j^{'} \in B$ に対して，男性 $i$ が女性 $j^{'}$ よりも女性 $j$ の方が弱好みであるとき，男性 $i$ が女性 $j$ に告白しているのなら，より好みの女性 $j^{'}$ にも告白する．

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

投稿日：2020年11月16日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

seytwo

5288

他の人のコメント

コメントはありません。

読み込み中

seytwo

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

はじめに
マッチング
耐戦略性
ゲール・シャープレーのアルゴリズム
ゲール・シャープレーのアルゴリズムの耐戦略性
補足