安定結婚問題のアルゴリズム

昨年度のノーベル経済学賞は、ロイドシャブレイ教授の「マッチング理論とその応用の功績」とのこと。そのマッチング理論について一夜漬けしてみた。
マッチング理論の基本は、安定結婚問題と呼ばれるもので次のような内容である。

""男性が$N$人、女性が$N$人いるとする。メンバーはそれぞれ相手方グループの好みの順序のリストを持っている。それぞれ一人ずつペアを作った状態をマッチングと呼ぶ。
""ペアになったそれぞれが、互いに現在組んでいる相手よりも好きであるペア(ブロッキングペア)が存在しないようなマッチングを安定マッチングと呼ぶ。

この安定マッチングを探すアルゴリズムが"ゲール-シャプレイ(GS)アルゴリズム"だ。http://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9%A1%8Cの内容を元に、pythonで書いてみた。

 import random
 
 N=6
 
 M=[[j for j in range(N)] for i in range(N)]
 F=[[j for j in range(N)] for i in range(N)]
 for j in range(N):
     for i in range(N*5):
         s=M[j][random.randint(0,N-1)]
         M[j].remove(s)
         M[j].append(s)
         s=F[j][random.randint(0,N-1)]
         F[j].remove(s)
         F[j].append(s)
 
 single=[ i for i in range(N)]
 pair=[ -1 for i in range(N)]
 
 while len(single)>0:
     x=single.pop()
     y=M[x].pop()
     if pair[y]!=-1:
         if F[y].index(pair[y]) < F[y].index(x):
             single.insert(0,pair[y])
             pair[y]=x
         else:
             single.insert(0,x)
     else:
         pair[y]=x
 print M
 print pair

Mが男性でFが女性だ。それぞれの好みの順序をrandomで事前に準備している。

アルゴリズムの仕組み的には、独身男性(single)のリストから一人選び、彼の好きな順に女性にプロポーズしていく。一方女性側は、プロポーズされたらとりあえずペアとなり、今の相手より好みの男子がプロポーズに来たら乗り換える、という戦法ををとる。

このアルゴリズムは性質として、
# 男性は一度プロポーズした女性には、２回目のチャレンジはない。
# 女性は一度プロポーズを受けると、必ず誰かとペアとなっている。
# 終了時点で、女子は、彼女にとって今まで逢った最良の好みの男子とペアとをなっており、それ以上の好みの男子は自分を選択していないので、安定マッチング。
を持っていて、これがアルゴリズムの停止性と解の正確さを担保している。

ちなみに、男子からプロポーズすると男子に有利な安定マッチング、女子からプロポーズすると女子に有利な安定マッチングとなる。このため、プロポーズする側に有利な不公平なアルゴリズムといえる。

「''確かに不公平だ、いまどきの女子は自分から告白するぞ''」と同じような仕組みで、女子の独身者からのプロポーズもさせようとすると、先の要素2.あたりが維持できなくなるため、単純にやると停止しなくなるので注意が必要。

この解のような不公平な安定マッチングではなく、公平な安定マッチングというのが存在することが証明されているらしい。が、この中間的な安定マッチングを探すアルゴリズムを開発する方法はNP困難らしい。

男性女性の結婚の問題だと、不公平感を感じるけれど、ほかの同様なマッチング問題に関してなら、有効に考えられるのでは？たとえば、プロポーズする側は、相手集団のすべての情報を持っていて、好みのリストを作れるが、プロポーズを受ける側は相手集団の情報は持っておらず、プロポーズされて始めて相手or過去の相手との比較ができるという場合。