2

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

468
0

はじめに

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

マッチング

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

以下の性質を満たすペアの集合M={(i1,j1),(i2,j2),...,(in,jn)}をマッチングと呼ぶ.

  • ペアは男女:(i,j)M,iA,jB
  • ペアはn組:|M|=n
  • ペアに重複なし:(i,j),(i,j)M,ii,jj

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

男性iAの選好i=(ji,1,ji,2,...,ji,n)をすべての女性Bの順列とする.男性iAの選好iの集合をPiとする.男性iAが女性jB以上に女性jBを好み(弱好み)であるときjij,女性jBよりも女性jBを好み(強好み)であるときjijと書く.マッチングMMでの男性iAの相手の女性をM(i)Bと書く.女性についても同様に定義する.すべてのユーザの選好の組(単に選好と呼ぶ)を≿=(i1,i2,...,in,j1,j2,...,jn)とする.選好の集合をPとする.

耐戦略性

マッチングアルゴリズムf:PMを,入力が選好,出力がマッチングの関数とする.

マッチングアルゴリズムfが男性耐戦略性を満たすとは,以下を満たすことである.
≿∈P,iA,iPi,f(i,i¯)(i)if(i,i¯)(i)
ここで,i¯は男性iA以外のユーザの選好の組である.

マッチングアルゴリズムが男性耐戦略性を満たすとき,任意の真の選好≿∈Pに対して,どの男性iAも,自身の選好i∈≿を任意の選好iPiに変更しても,より好みの女性を得られない.

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

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

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

選好≿∈PをGSアルゴリズムに入力したときの出力のマッチングをMgs()とし,(男性)GSマッチングと呼ぶ.

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

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

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

  • ある男性をiAとする
  • 真の選好を≿∈P,GSマッチングをM=Mgs(),GSマッチングでの男性iの相手の女性をj=M(i)とする
  • 真の選好≿=(i,i¯)のうち,男性iの選好iを別の選好iPに変更した選好を=(i,i¯)P,GSマッチングをM=Mgs(),そのGSマッチングでの男性iの相手の女性をj=M(i)とする
  • 選好=(i,i¯)のうち,男性iの選好iを女性jを先頭に移動した選好iに変更した選好=(i,i¯)P,GSマッチングをM=Mgs(),そのGSマッチングでの男性iの相手の女性をj=M(i)とする

【背理法の仮定】男性iは真の選好での相手の女性jよりも,選好での相手の女性jの方が強好み:jij

任意の男性iAに対して,男性iは真の選好での相手の女性M(i)よりも,選好での相手の女性M(i)の方が弱好み:
iA,M(i)iM(i)

真の選好での相手の女性M(i)よりも,選好での相手の女性M(i)の方が強好みな男性の集合をXとする:
X={iA:M(i)iM(i)}

真の選好でのGSアルゴリズムにおいて,男性集合Xで最後に告白する男性をitX,その相手の女性をjt=M(it),アルゴリズムでのステップをt番目とする.

真の選好でのGSアルゴリズムにおいて,女性jtに告白する男性の集合をYとする.同様に,選好でのGSアルゴリズムにおいて,女性jtに告白する男性の集合をYとする.

男性集合Yに含まれる男性iYは,男性集合Yにも含まれる.

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

男性集合Yは男性itを含む.

定義5より成り立つ.■

男性集合Yは男性it以外の男性も含む.

男性集合Yは男性itのみを含むとする.補題3より,男性集合Yに含まれない男性は,男性集合Yにも含まれない.したがって,男性集合Yも男性iのみを含む.このとき,選好での男性itの相手もjtである.よって,真の選好と選好で男性itの相手は女性jtで等しい.これは,男性itが男性集合Xに含まれることに矛盾する.■

男性集合Yで女性jtが二番目に好みの男性iは,真の選好での相手の女性M(i)と選好での相手の女性M(i)が等しい.

男性iがステップt以前に女性jtに告白していないとする.このとき,男性iはステップt以降に女性jtに告白する.定義5より,男性iは男性集合Xに含まれない.したがって,真の選好と選好での男性iの相手は同じ女性である.

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

選好での男性itの相手も女性jt

【矛盾】男性itは男性集合Xに含まれること(定義3)に矛盾

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

補足

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

任意の選好≿∈P,任意の男性iA,GSマッチングで男性iが告白した任意の女性jBに対して,男性iは女性Msg()(i)よりも女性jの方が好みである.

GSアルゴリズムでは男性は好みの女性から告白し,男性iとペアの女性jBは男性iが最後に告白する女性であるため.■

任意の選好≿∈P,任意の男性iA,任意の女性j,jBに対して,男性iが女性jよりも女性jの方が弱好みであるとき,男性iが女性jに告白しているのなら,より好みの女性jにも告白する.

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

投稿日:20201116
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。
バッチを贈って投稿者を応援しよう

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

投稿者

seytwo
15
4962

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. マッチング
  3. 耐戦略性
  4. ゲール・シャープレーのアルゴリズム
  5. ゲール・シャープレーのアルゴリズムの耐戦略性
  6. 補足