賢いマッチングアルゴリズムの話

飽き性

私はその時々ハマっている音楽をひたすらリピートで聴くタイプなので、満足する臨界点まできてしまうと一時的な「飽き」状態になりその曲はしばらく寝かせることになる。

何が言いたいかというと、ここ数ヶ月ハマっていた曲が一通り「飽き」状態になりSpotifyで聴きたい曲が一時的に無くなってしまったので、最近はポッドキャストをよく聴いているのです。

テック系のポッドキャストをよく聴くのですが、

Turing Complete FMは私が最近よく聴くポッドキャストの1つです。

どんな番組かというと、紹介文によるところ

”プログラミングとコンピュータサイエンスについてのディープな話をするポッドキャスト”

といった感じです。

私にとってはディープすぎるテーマをよく触れられているのですが、ホストのRui Ueyamaさんが平易でわかりやすい説明をしてくださるので、いつも楽しく拝聴しています。

そんな Turing Complete FM の何気なく聴いていた第23回の放送で登場した廉略投票を行わなくてよいマッチングのアルゴリズムが「なるほど!」って感じだったので紹介したいと思います。

安定結婚問題

安定結婚問題という、1962年にデイヴィッド・ゲールとロイド・シャプレーが提唱した問題がある。

簡単に説明すると、ある人数の男女が自分の好みに基づき結婚相手を決める状況で、全異性と自分自身(結婚しないことを意味する)のなかでランキングをつける。この時にどうすれば全員が合理性のある(全員が独身より望ましい相手と結婚&現在組んでいる人よりも相思相愛なペアが存在しない)マッチングをとることができるか。というのが安定結婚問題であり、この時に安定なマッチングを得るのが Gale-Shapleyアルゴリズムである。

要するに最大数の幸せなマッチングを求めるためのアルゴリズムです。

どんなところで使えるかというと、僕の身の回りだと大学のラボ決めとか社交ダンスのカップル決めとかかなあ。

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

結婚安定化問題は1対1のペアを作る問題ですが、学生の研究室配属のマッチングのような1対n(複数名が1つのラボに配属される)のマッチングにも適応させることができます。

早速例を出しながらどんなアルゴリズムか見ていきましょう。

学生とラボのマッチングを例にとります。

  • 学生が入りたいラボの順番をつける。
  • (1巡目)学生たちの第一希望を元に、各研究室の判断基準により欲しい学生を選び、研究室の定員の数だけの学生に、一時的に合格の印をつける。
  • (2巡目)各研究室の選考から省かれた学生の第二希望を一時的に合格の印をもらった学生と合わせて、その中から研究室の判断基準により学生を選び合格の印を付け直す。つまり第一希望の回で合格をもらった学生よりも第二希望の回の学生で、研究室として欲しい学生がきたら、その第二希望の学生が合格の印をもらうことができる。
  • (3巡目)二巡目の選考の結果、合格をもらえなかった学生の次の希望(第二希望or第三希望)を合格の印をもらっている学生と合わせて、再び選考を行う。
  • これを全学生が配属されるまで繰り返すと研究室と学生にとって最大安定な組み合わせを得ることができる。

このアルゴリズムの特徴は、最大幸福なペアを作れることと、自分に素直であることが自分にとって一番よい結果をもたらす、というところです。

つまり、Aさんが一番人気そうだからBさんを第一指名にしようといった戦略を考えない方が結果が良くなるということです。

非常に実践的なアルゴリズムだし、必ず安定したマッチングを作れるといったところが「おれのかんがえたさいきょうのあるごりずむ」感があってとてもよいです。

思い出

書いていて思い出したのですが、弊大学弊学部弊学科の2年次の専攻コース決めは、希望コースを順番づけしたものと、興味のあるテーマ(半導体、電気エネルギーなど)をチェックボックス形式で埋めたものを提出し、学務のブラックボックスを経由して配属を決めます。

あいにく1つだけ学生から人気のないコースがあり(弊学科と少し解離した専攻内容であることが原因)、その人気のない専攻に関するテーマをチェックボックスで選んでしまうと、どんな希望コース順にしてもその人気のないコースに配属されると噂されており、当時「チェックボックスゲー」などと揶揄されていましたが、実はしっかりこのようなアルゴリズムが機能していたのかもしれなかったりして(あるいはチェックボックスが本当に地雷として作用していたかもしれないが)。

このアルゴリズムの発見によってロイド・シャプレーは2012年にノーベル経済学賞をもらったそうなのですが、牌の奪い合いを解決できる、世界が平和になるアルゴリズムだなあと思ったので平和賞でもいいと思いました(小並感)。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です