なかなかペアが決まらない理由

ゲール=シャプレー・アルゴリズムで安定マッチングを行う場合、コアな安定マッチングが可能だ。

 

しかし問題が一つあって、選択権をもらった側とそうでない側で、満足度が偏る場合があることだ。

 

たとえば必ず男女ペアを作るマッチングでは、男性側に選択権を与えると、男性メンバーにとってより良い選択結果が得られる。

 

しかし女性メンバーにとっては、余り良くないかも知れない。

 

逆に女性側に選択権を与えると、女性メンバーにとってはより良い選択結果になる。

 

しかし男性メンバーにとっては、余り満足度は高くないかも知れない。

 

なので一旦ペアが決まったとしても、ブーブー文句が出て、いつまでもペアが決まらない場合もよくある。

 

こういう場合、どうすればペアが決められるのか。

 

優先選択権が必要な例

たとえば前回の例では、(東くん、小畑くん、松村くん)という男性メンバーと、(亜香里さん、すみれさん、花音さん)という女性メンバーで、デートのペア決めをする。

 

メンバーそれぞれの選択順序は次のようになっている。

男性陣の選択順序(再掲)
  • 東くん (亜香里、花音、すみれ)
  • 小畑くん (亜香里、花音、すみれ)
  • 松村くん (すみれ、花音、亜香里)
女性陣の選択順序(再掲)
  • 亜香里 (東くん、松村くん、小畑くん)
  • すみれ (東くん、小畑くん、松村くん)
  • 花音 (松村くん、小畑くん、東くん)

 

この場合、東くんと亜香里さんは相思相愛関係なので、どういう順序で誰からプロポーズを行っても、必ずペアになる。

 

なので東くんと亜香里を除いた、選好順序は次のようになる。

  • 小畑くん (花音、すみれ)
  • 松村くん (すみれ、花音)
  • すみれ (小畑くん、松村くん)
  • 花音 (松村くん、小畑くん)

コレを見ると、小畑くん→花音→松村くん→すみれ→小畑くん→…という風に選択が循環している。

 

つまりここで、何らかの別の条件を設定しないと、ペア決めがいつまでも決まらないワケだね。



優先選択権を決めねば、決まらない

ゲール=シャプレー・アルゴリズムでは、どういう順序で誰から選ぼうと、選好順位の1位同士は必ずペアになる。

 

なので1位同士のペアを除いたメンバーだけで、残りのペアを組むことになる。

 

上の例のの場合、東くんと亜香里さんは、お互いに選好順位が1位同士なので、ペアが成立して最初に抜ける。

 

そして、東くんと亜香里さんを抜いた状態の選好順位でペアが決まる。

 

ところが、小畑くんは花音さんを選び、花音さんは松村くんを選ぶ。

 

松村くんは、すみれさんが良いと言うし、すみれさんは小畑くんと組みたいと言う。

 

この場合、小畑くん→花音→松村くん→すみれ→小畑くん→と言う風に、選択が循環してしまうわけだ。

 

これではペア決めできないので、何らかの別の条件を設定して、強制的にペアを決めることになる。

 

その一番簡単な方法が、「優先選択権」だ。

 

つまり誰かに優先選択権を与え、権利をもらった人がペアを組む相手を選ぶ。

 

誰かがペアを決めれば、残りのメンバーで組むことになるので、ペア決めは終了だ。

 

この例では、小畑くんに優先選択権を与えると、(小畑、花音)、(松村、すみれ)のペアができて、すみれさんに優先選択権を与えると、(すみれ、小畑)、(花音、松村)のペアができる。

 

この場合、優先権をもらった人の満足度は大きくなるが、その他のメンバーはもう一つってことになる。

 

こういう風に、安定マッチングとなる組み合わせが2コ以上ある場合は、何らかの別の判断基準が必要になるわけだ。

 

逆に言うと、ゲール=シャプレー・アルゴリズムでは、誰が選ぶかを最初に決めた時点で、優先選択権を決めていることになるわけだね。


株式投資必勝法 人気ランキング

★第1位★相場師朗の超短期トレードショットガン投資法

★第2位★ラジオNIKKEIでおなじみ相場師朗の株は技術だ、一生モノ!

★第3位★株は5日で利益を出せ!「5日株トレード法」

★第4位★銘柄選びは不要!日経225で稼げ!FURAIBO225

★第5位★週末イチ時間でお宝銘柄!ワンWEEK副業投資プログラム

★第6位★デイトレで稼ぎたい!紫垣デイトレード塾

★第7位★日経225ミニ爆益トレードDVDダブルファントムトレード

このエントリーをはてなブックマークに追加
Z会 大学生・社会人の英数講座