Gale-Shapleyのアルゴリズムに見る嗜好付き二部マッチングの不都合な真実(前編)
はじめに
ISer Advent Calendar 2020 - Adventar
の20日目の記事です。遅刻の上未完かつクソ記事で申し訳なさすぎる。
Advent Calendarも終わりが見えてきました。つまりクリスマスが近づいているということですね。クリスマス直近になると幸せになる人と不幸になる人が一定数いると思いますが、25日はきっちり5限まで受けるのが弊学の流儀のような気がしています。まあそんなわけでマッチングの話でもしようかなと。←は？
注意.この記事は端から端までネタで構成されています。生暖かい目でごらんください。苦手な方はブラウザバック推奨
もくじ
導入
世界は広く、しかし我々の行動範囲は狭く、出会いも少ないこのご時世。効率に追われる人々の間ではマッチングアプリとやらが蔓延っているとかいないとか。まぁ是非は置いといて、アレの中身がどうなってるかはここにいる人なら興味あるでしょう。と思ったらGale-Shapley's algorithmという有名なのがあるらしい。そいつの『処理』を面白おかしく追いかけてみるか、という企画。
※学術的内容は某講義の(議論を適当にした)受け売りとなります。参考文献にはしないでください。
定義
とりあえず、簡単のために世界に男女が同数ずついて、全員がいずれかの異性とマッチしなければならないものとする。んんん、プレッシャーだ。
全員、異性の希望順位というものを持っているとしよう。『誰でもいい』なら何も考える必要はないのだから当然の設定だな。男性にとって女性
よりも
の方が好きだということを
と書くことにする。先生とかはこの不等号の定義を逆に書くのだが、正直なところ直感に反する*1のでこれで行く。もちろん判定者によって順位は覆るから、不等号の下に判定者を書かないと意味がない。そして、この希望順位は、カッコよく言えば全順序であること(全ての対象が矛盾なく比較可能であること)が期待される。「うーん、どっちの方がいいかなんて選べないよ？」「さっきはA<BでB<Cだと思ったけど、改めて比べるとC<Aかな？」こういうのはダメである。既に現実離れしているような気もするが、これくらいの仮定はないと議論がややこしくなるだろ、それはそう。
で、全員が幸せになるマッチングとは何か？オイオイ、いきなり問いが重すぎるぞ。まずは落ち着いて「安定」の定義を読むんだ。
マッチング
において、
とマッチしている相手を
と書くことにする。
男女の組がマッチング
かつ
となることである。
マッチング
化学平衡なんぞを思い出してみると、不安定というのは『放っておくと別の状態になる』と捉えることができるが、不安定対の定義を眺めれば確かに放っておいて何も起きないはずがないなぁと納得できる。まさに不安定だ。
健全な見方をすれば、不安定対は『あの人の方が良い』という希望が反映されていない状態だとも言える。m→wまたはw→mという希望が一方的ならそりゃあ君の我儘というものだよ、と言えるわけだが、両方向ならそうでもない。いや、その2人の我儘と言えるのかもしれないが。
とにかく、不安定対あるいは各人の不満と呼べるものがないマッチングを安定と定義する。ただし、差し当たって不満がないマッチングが最終的に最良と言えるかについては疑義が残るし、実際1つの世界(男女の数、希望順位)に対して安定マッチングが一つしかないわけではない。なんなら現時点では安定マッチングが存在するかすら怪しいわけだが、とりあえず安定ですらないものは論外と思うことにして、安定マッチングを探すことを考えよう。
アルゴリズム
さて、Gale-Shapleyのアルゴリズム*2(以下GSと呼ぶことにする)を眺めてみると、やることは簡単。男女を適当に空間に放って、平衡(安定)になるまでひたすら『反応』させればよい。いやそれ、かなり想像したくないが？
ここで、このアルゴリズムの本質として『動いて良いのは男だけ』という重大な縛りを設ける。女の方は動かずに男を待つだけとする。これは致命的なまでに非対称な設計であるが、考察が簡単になる。
GSは各人の好みを反映して『反応』を起こしていき、何もできなくなったところで止まる。真面目な記事ではないので細々と手順を書くことはしないが、ルールに沿って自然に実行すれば、結局GSで起きうる反応は以下の2つだけである。
(1)独身の女wの所に男mが来た場合、w側からすると『全員が誰かとマッチしなければならない』というルール上、とりあえず引き止めておくしかない(拒否するメリットがない)。mは元々自分の希望でwの元へ来たのだから離れる理由はない。したがってマッチが成立する。
(2)マッチした男女(m,w)の所に男m'が来た場合、wはmとm'で好きな方を選んでマッチし、選ばなかった方を振る(mの場合別れるという方が適切か)。振られた男はwを諦めて、次点に希望する女の所へ向かう。なお手順上は『(潔く)諦める』と書かれるのだが、諦めなかったとしても再度振られる以外の結末はあり得ないので、やはり事実上諦めるしかない。
実践と性質の観察
GSを実践する様子を各人の視点で想像してみると理解が深まる(？)。
(1)女視点: 基本的に待つだけであり、男が複数来たら好きなのを選べばよい。一度男を『確保』すると、(運良く)よりいい男が来るか現状維持になるかだから、状況が悪化することがない(その意味で『確保』という語が適する)。至れり尽くせりに見える一方、自分から動くことはできないから、運悪くいい人が自分の元に来なかったらどうなるのか、という疑問は残る。実際には『運悪く』来なかった、という言い方はやや語弊があるのだが…
(2)男視点: 何も考えずに好きな人のところへ行く。振られたら次に好きな人のところへ行く。などと書くと単純で気楽そうだが、一度OKを頂いても安心できないところが非常に辛い。ある人の所に落ち着いても、いつ『自分よりいい男』が現れて放り出されるか分からないのである。振られるたびにその人とはマッチできないことが確定するので、第一志望から始めて、志望状況が1つずつ下がっていくとも言える。厳しいですなあ。
定理
GSが停止した暁にはどうなっているのか、というかまず停止するのかなどを考える。
まず停止性の確認は簡単で、いつか必ず野良の男がいなくなることが示せる。男が振られ続けた場合、最終的には全ての女のところへ(1回ずつ)行くはずであり、男女は同数だから『空いている』女がどこかでマッチして終わる。動ける男がいなくなればそれ以上反応は起きようがないから、これでGSは停止する。
次いで、当初の目標であった安定マッチングになることも割とすぐに示せる。GSで得られるマッチングのことを単にGSと書くことにしよう*3。マッチしていない男女対を任意にとると、まず
ならばこれが不安定対になることはない。一方、
ならばmはGS中に一度wを訪れたはずであり、その時に振られている。するとwは今は(wにとって)もっといい男
にマッチしているはずであり、不安定対になることはない。つまり、GSの不安定対は存在せず、必ず安定マッチング(の1つ)になる。
良い話
GSが少なくとも安定マッチングになっていることが分かったので、安定マッチングの中でもより良いものであるかを考えよう。
新たな指標として、各個人xについて
- 『安定マッチングをするという条件下で あり得る相手』を、xの妥当な相手
- xの妥当な相手の中で(xにとって)最上の人を、xの理想
と呼び、xの理想をと書くことにする。best(x)はxの希望順位トップにはならないかもしれないが、それ以上高望みすると安定マッチングにならないという意味でxにとって最善の人になる。
さて、以下のような素敵な定理が出る。
定理1.GSで男が妥当な相手に振られることはない.
証明がそれなりにややこしい。多分ここが正念場だ。
まず、GSで男mが男m'と競った上で女wに振られたとして、しかもwがmの妥当な相手だったと仮定する。GSでの状況からである。一方、妥当な相手の定義からM(m)=wとなる安定マッチングMが存在するが、(m',w)がMにおいて不安定対とならないことから
でなければならない。GSの状況に戻ると、今m'がwの元にいるので、m'はM(m')に振られてからここに来ているはず。ところでMは安定マッチングだから、m'もまた妥当な相手に振られていたことになる。
以上から分かることを簡潔に述べると、
ある男が妥当な相手に振られたとき、必ずそれより前に別の男が妥当な相手に振られている。
お分かりいただけただろうか。『では、最初の1人は？』という問いが矛盾を引き起こす。鶏と卵の議論、あるいは無限降下法。妥当な相手に振られる最初の1人が矛盾を起こすならば、その最初の1人すら存在しなかったというのが唯一無矛盾な結果となるから、誰も妥当な相手に振られていないといえる。Q.E.D.(面倒なので真面目には書かないでおこう)
さて、素敵な定理が出れば素敵な系が出るもの。
系1.1.任意の男mについて、GS(m)=best(m).
証明.定理1より、mから見てGSにおいて振られた相手は全て妥当な相手ではなかったことになり、GS(m)より上の妥当な相手は存在しない。これとGS自体が安定であることから従う。
これは、男各人にとってはGSが最善の結果を出していることを意味する。
系1.2.GSの結果は反応の実行順によらない.
証明.定義より各人に対してbest(m)は1人しかいないから、系1.1より従う。
『GSのマッチングは早い者勝ちになったりしないのか？』という疑問を解消する、実践上とても良い性質。実はここまでの議論ではちゃんと示していなくて、よく見ると今までは『任意にとったGSの結果の一つにおいて、〜である』というかなりややこしい議論をしていたことが分かる。ここまで来てようやっと示せるのかい！とも思えるが、証明が難しい命題でもある。
系1.3.いかなる世界においても、各人の理想は衝突しない.
証明.男同士の理想が衝突しないことは系1.1およびGSが1対1のマッチングであることから自明。女同士の理想が衝突しないことは対称性より従う。(GSにおいて男女の役割を入れ替えることにより全く同様の証明ができる)
これはGSそのものから離れて一般に言えることであり、GSはその証明の補佐に過ぎない。いわばGSによる構成的証明である。
いい話まとめ。
安定マッチングの中でもより良いものを見つけたいというモチベーションを持ってきたが、男各人が(安定という条件下で)それぞれ理想を取っても衝突せずにマッチングが作れるということが分かった。しかもそれを得るアルゴリズムは割と簡単で、適当に順序を入れ替えて実行しても結果が変わらないことが分かった。実際、GSは男各人視点から並列に実行できる。
後編は悪い話をします。乞うご期待。
