研究室配属アルゴリズム

アルゴリズムと実行手順

1. 各研究室ごとの順位リストを準備する．
   
   各研究室ごとに，上から下へ順位の良い順に並べている．


2. 各学生の希望を調べる．(表は，第3希望までとった例．)
   


3. 各学生の第1希望を調べる． 順位の高いほうから定員までは仮採用． それ以外は落選．
   
   オレンジ：仮採用． 水色：落選． 灰色：リストから除外．


4. 以降，次の３つのルールで希望者を選定．
   1. 定員を満たすまで無条件に受け入れる．
      A研究室落選の「さる」の第2希望はE研究室． E研究室は定員を満たしていない． したがって，E研究室で「さる」を仮採用する．
   
   
   2. 定員に達していたら，新規希望者と仮採用の学生と比較． 新規希望者の順位が上なら仮採用．仮採用だった学生の最下位は落選．
      A研究室落選の「ひつじ」の第2希望はB研究室． B研究室は定員に達しているが，仮採用中の「いぬ」より 新規希望者の「ひつじ」のほうが順位が上． したがって，B研究室で「ひつじ」を仮採用する． 「いぬ」は落選で，第2希望へ回る．
   
   
   3. 仮採用の学生より新規希望者の順位が下なら落選．
      B研究室落選の「いのしし」の第2希望はE研究室． E研究室は定員で，「いのしし」の順位は仮採用の学生よりも下． したがって「いのしし」は落選で，第3希望へ回る．
   
   
   落選者に関して，これらのルールのもとで選定を繰り返す．


5. 希望研究室をすべて落選なら 「未決定」状態とする．
   黄色：未決定． 「いのしし」は第3希望も落選なので未決定が確定．


6. 全員が「仮採用」か「未決定」になったら仮採用の学生を正式に配属決定として終了．
   ピンク：決定． 黄色：未決定 ⇒第2ラウンドへ．
   第2ラウンドでは，定員を満たしていない研究室から選ぶ．

まとめと補足

• 研究室ごとに上位から定員までの希望者が採用されるので， 必ずしも第1希望の学生だけで定員が埋まってしまうわけではありません． 普段から努力していた人ほど有利になります．
• 学生は，希望研究室の競争率を気にして希望順序を操作する必要は ありません．希望研究室での順位が高ければ第2，第3希望でも採用されますし， 低ければ第1希望でも落選するからです．
• 統一基準により成績順に配属を決定するのとは違って， 研究室ごとに異なる基準で順位をつけられるので， 学生は自分の得意分野の研究室に配属できる可能性が高くなります．
• 2013年は第4希望までとりましたが， 未決定で第2ラウンドに進んだ人はいませんでした．
• このアルゴリズムは，2012年ノーベル経済学賞の安定マッチング理論を 応用したものになっています．