進振りにも使われているG.S.アルゴリズムをわかりやすく解説

はじめに

　東京大学では進学選択(いわゆる『進振り』)が2年の夏休みに行われる。それにより、ほとんどの2年生は3年生から所属する学部学科が決まる。

　さて、その進振りには第一から第三までの段階が存在する。第一段階は各自1つの学部学科しか志望できず、点数順に決まっていく。残念ながらそこで決まらなかった人は、第二段階に進むことになる。

　その第二段階では志望順をつけて複数の学部学科を志望することができる。勘のいい人であればこの時点で気づくかもしれないが、第二段階は第一段階のように、単純に点数順で決まるわけではない。つまり、第二段階は単純に点数だけでなく、各々の志望順も反映されるのだ。

　では、第二段階ではどのような採用方法を用いているのだろうか？　もちろん、適当に採用しているわけではない。公平を期すために、決まったアルゴリズムを採用している。

　そして現在、そのアルゴリズムにはどうやらG.S.アルゴリズムというものが応用されているようだ。このことは、私が1Sで受講した主題科目『数理工学のすすめ』で、計数工学科の教員が言っていたことなので間違いないと思われる。また、第二段階のアルゴリズムについてネットで調べてみると、『DAアルゴリズム』あるいは『受入保留アルゴリズム』が使われている、と出てくるだろう。DAアルゴリズムも受入保留アルゴリズムもG.S.アルゴリズムの別名である。

　ちなみに、初年次ゼミナールや、英語中級・英語上級の講座の決定にもこのアルゴリズムは使用されている。また、東大に限らず、会社における配属分けなどにもこのアルゴリズムが使われているようだ。

　このことを以前Xにポストしたところ、かなりの反響があったので、本記事ではそんなG.S.アルゴリズムについて、できるだけわかりやすく解説する。なるべく正確な内容を書くよう心がけるが、私は講義でちょろっと習っただけの初学者なので、もしかしたら誤ったことを書いてしまうかもしれない。そのため、もっと知りたい人やより正確に知りたい人は、自分で調べることをお勧めする。

G.S.アルゴリズムの概要

　G.S.アルゴリズム(Gale-Shapleyアルゴリズム)とは、安定結婚問題における安定マッチングのうち1つ(あるいは2つ)を求めるアルゴリズムである。

　まず、安定結婚問題とは、次のような問題である。

　例えば、図1のようにA〜Eという5人の男と、1〜5という5人の女がいて、各々は、図1のような選好リストを持っているとする。

　この10人で男女1人ずつのペアを5つ作ることを考える。このとき、現在組んでいる相手よりも好きであるペアがないような組み合わせ(安定マッチング)になるようにする。

　例えば、以下の図2のような組み合わせを作るとする。ここで、Cと5に着目してみよう。

　Cは現在第5希望の3とペアを作っているが、5は第1希望である。一方、5は現在第5希望のEとペアを作っているが、Cは第1志望である。つまり、互いに現在組んでいる相手よりも好きであるペアが存在する(Cと5)ことになるので、このマッチングは安定マッチングとはいえない。このとき、Cと5のようなペアを不安定対と呼ぶ。

　つまり、このような不安定対が1つもないような組み合わせ(安定マッチング)を作れるかというのが安定結婚問題である。
　例えば、図3は安定マッチングである。

　このような安定マッチングは、各々の状況において少なくとも1つ必ず存在する(証明は各自で調べてほしい)。そして、この安定マッチングを1つ(あるいは2つ)発見できるようなアルゴリズムこそが、G.S.アルゴリズムである。

　G.S.アルゴリズムは、David GaleとLloyd Stowell Shapleyという2人のアメリカ人数学者により考案された。ちなみに、Shapleyは2012年にノーベル経済学賞を受賞している。

G.S.アルゴリズムのやり方(1対1対応の場合)

　先の例のように、1対1対応の場合、G.S.アルゴリズムのルールは至ってシンプルで、以下の通りである。

1. 全員がペアを作っていない状態で始める。

2. 片方のサイドに注目する。

3. ペアを作っていない人Xは、まだ断られていない相手のうち、自分の選好リストの最上位の人Yにプロポーズする。

   1. Yに相手がいないならば、とりあえずXとペアを作る。

   2. Yに相手がいる(つまり他の人X'とペアを作っている場合)ならば以下のように対処する。

      1. Yの選好リストにおいて、XがX'より上位なら、YはX'とペアを解消し、Xとペアを作る。

      2. Yの選好リストにおいて、X'がXより上位なら、YはXのプロポーズを断り、X'とのペアを継続する。

4. これを繰り返し、全員がペアを作り終えたら終了する。

　では、実際に先の例にG.S.アルゴリズムを適用してみよう。

　ここでは、左の男サイドから、またAから順にプロポーズしていくことにする。まずAが1に、Bが2にCが5にそれぞれプロポーズする。ここまではプロポーズ先が被っていないので、素直にそのまま結べばよい。すると、図4のようになる。

　次に、Dが5にプロポーズするが、5はすでにCとペアを作っている。ここで、5の選好リストを見ると、Dが3番目なのに対して、Cは1番目である。よって、5はDのプロポーズを断ることになる(図5)。

　そこで、Dは選好リストの2番目の2にプロポーズする。2はすでにBとペアを作っているので、選好リストを参照する。すると、Dは1番目、Bは4番目なので、2はBとペアを解消し、Dと新たにペアを形成する(図6)。

　同様に、Bは選好リストの2番目の1にプロポーズする。1はすでにAとペアを作っているので、選好リストを参照する。すると、Aは5番目、Bは4番目なので、1はAとペアを解消し、Bと新たにペアを形成する(図7)。

　相手がいなくなったAは選好リストを参照し、2番目の3にプロポーズする。3には相手がいないので、Aのプロポーズを受け入れてペアを作る(図8)。

　最後にEが1にプロポーズするが、1はすでにBとペアを作っている。そのため、1は選好リストを参照する。すると、Eは1番目、Bは4番目なので、1はBとペアを解消し、Eとペアを作る(図9)。

　最後に、相手がいなくなったBは選好リストを参照し、3番目の4にプロポーズする。相手の4は相手がいないので、Bのプロポーズを受け入れてペアを作る(図3)。以上ですべてのペアが完成し、これは安定マッチングとなる。

　いくつか補足をする。

　まず、今回はAから順にプロポーズをしたが、プロポーズする順番を変えても出来上がる安定マッチングは同じである。気になる人は自分で確かめてみよう。

　また、女性側からプロポーズをしても安定マッチングを出力することができる。一般に、男性側からプロポーズした場合に出る結果と女性側からプロポーズした場合に出る結果は異なるが、今回の例の場合では同じになる(図3)。

　ちなみに、男性側からプロポーズして得た安定マッチングを男性最良安定マッチング、女性側からプロポーズして得た安定マッチングを女性最良安定マッチングと呼ぶ。
　男性最良安定マッチングは男性の希望が最大限に反映された安定マッチングで、女性最良安定マッチングは女性の希望が最大限に反映された安定マッチングである。

G.S.アルゴリズムのやり方(1対1対応でない場合)

　これまで1対1対応の場合を見てきたが、ここからは1対1対応でない場合を考えてみる。

　例として、図10のような状況を考えてみよう。
　A~Eの5人の学生が、X~Zの3つの学科に進学したいと考えている。A~Eはそれぞれの成績と選好リストを持っており、X~Zは点数の高い学生順に選択していく。また、Xの定員は3人、Yの定員は1人、Zの定員は1人とする。

　先ほどの例とはかなり状況が異なるが、アルゴリズムの中身自体はほとんど同じで、以下の通りとなる。

1. 全員が進学していない状態で始める。

2. 生徒サイドに注目する。

3. 進学していない人Pは、まだ断られていない学科のうち、自分の選好リストの最上位であるQ学科に進学しようとする。

   1. Qが定員に満たなければ、とりあえずPを受け入れる。

   2. Qが定員いっぱいならば以下のように対処する。

      1. Qの選好リストにおいて、Pが現在入っている人のうち最下位であるP'より上位なら、QはP'を追い出し、Pを入れる。

      2. Qの選好リストにおいて、P'がPより上位なら、QはPの進学を断る。

4. これを繰り返し、できなくなったら終了する。

　では、実際に先の例にアルゴリズムを使用してみよう。

　まず、AがX、BがY、CがZ、DがXに入ろうとする(図11)。X~Zはまだ定員に満たないので、全員を受け入れる。

　次にEはYに進学しようとする。しかし、Yは定員1名であり、すでにBが入っている。ここでEとBの成績を比べると、Eの方がBより成績が良いため、BはYを追い出され、代わりにEが入ることになる(図12)。

　次に、Bは選好リストに従いZに進学しようとする。ただし、Zは定員1名であり、すでにCが入っている。ここで、BとCの成績を比べると、Cの方がBより成績が良いため、BはZに入れない(図13)。

　Bはもう選好リストが残っていないので、ここでマッチングは終了となる。少々物足りない感じがするが、完成した組み合わせ(図14)を見てみると、安定マッチングになっていることがわかる。

　もう気づいた人も多いかと思うが、この例は進振りの第二段階のシステムとほとんど同じである。この例では、Bは第二段階で内定せず、第三段階へと進み、X学科は第三段階で枠を設けることになるだろう。

　ただし、実際の進振りでは、学部学科ごとに使う点数が異なったり、工学部の場合は志望理由書が考慮されたりなど、これ以外にさまざまな要素がある。そのため完全な同一視はできないことに注意したい。

　さて、この例では学生側からアプローチをしていた。そのため、1対1のときの例で述べたように、これは学生側の希望が最大限配慮された安定マッチングである。つまり、もし進振りの第二段階に進んだときには、自分の志望順を正直に、志望する可能性のある学科をすべて書くことが最適であるということだ(ちなみに、このことは第二段階を選ぶときUTASに注意書きとして表示されるので、学生側からマッチングをするのは確実だと思われる)。

　実際、私も第一段階の底点が84点台だった理学部情報科学科に、第二段階の第一志望で書いたところ、77点台で(奇跡的に)通ったので、変に考えを巡らせることなく、正直に書くのが良いと思う。

おわりに

　ここまでG.S.アルゴリズムについて解説してきたが、もっと詳しく知りたいという人は、以下に示す参考サイトを見たり、自分で調べたりしてほしい。また、本記事の内容に誤りがあれば、下部のコメント欄やXのポストに反応してほしい。

G.S.アルゴリズムについての他の記事(参考サイト)