読者です 読者をやめる 読者になる 読者になる

合コンアプリ: 安定結婚問題とGale-Shapleyアルゴリズム

計算機

安定結婚問題というゲーム理論の問題がある。2つの異なる種類のもの(例えば男女)が組を作る際に最も満足度の高い組み合わせを求めるにはどうすればよいかという問題である。ここでの満足度の高い組み合わせ(これを安定な組み合わせと呼ぶ)とは、互いに今のペアより好ましい相手と共になれるような組が存在しないような組み合わせのことである。つまり、「今の女よりお前の方が実は好きやってん」「え、私も###」というような悲劇が起きないような組み合わせが、安定な組み合わせである。

この組み合わせを求めるのに、Gale-Shapleyアルゴリズムというのが知られている。Shapleyはこれでノーベル賞を受賞している。

知人にこの話をしたら、「そりゃ全員の好みが分かっていたらどっかに最適解はあるやろ?それでノーベル賞ってなんなん!?」と驚いていた。確かに、GSアルゴリズム自体は下らない。でも、こういうのはあとからどれだけワラワラと似たようなのが出てくるかが重要だ。それに、ShapleyはGSアルゴリズム以外でも有名だし。

安定な組み合わせを求めるには、全員の好みの順位が分かっていなければならない。全員の好みが開示されていれば、そもそもこんな問題解く必要もない。むき出しの欲望が交錯する世界だ。(そういう世界が安定になるとは思えない。この事実については別に考察が必要と思われるがそれは別の機会に)

上位の調停者にならば、自分の好みを教えることならありうるだろう。上位の調停者に相当すべきなのがコンピュータである。人間がアルゴリズムによって調整されている世界が、私が目下目指している世界である。

そういうわけで、安定結婚問題を解く合コン用アプリを作った。一応Playストアに公開している。

StableMatching - Google Play の Android アプリ

f:id:fjkz:20140606224209p:plain:w150

随分前に作ったものだが、正直ゴミアプリなのでこれは全然使えません。

ひとつの理由は、仮にこれが使える状況であっても、こんなのを使わずに各々が一番いいと思うところにぶっこむのが、おそらく最も合理的な解だということ。まじめに解析したことはないが、多分囚人のジレンマゲームみたいなのになる。全体としての利益は小さくなるが、全員が協力せずに個別に利益を求めると、このアプリを使わないというのが均衡解になると思う(予想)。

ふたつ目の理由は、このアプリを使える状況に持っていければ、つまり全員が好みを入力してくれるような関係性が作れれば、もう問題の99%は解決しているということ。そこまで持っていけるスキルのあるグループが、あえてこのアプリを使う動機が全くない。

そういう理由で、このアプリは使えない、むしろ使うべきでないのだが、これを使えるものにしていくには2つのアプローチがある。それを次回述べたい。

という、前振りの投稿でした。

- - - -

次回:


究極の出会い系サイトを作る方法: 好みを推測するアプローチ - 超ウィザード級ハッカーのたのしみ