研究室配属アルゴリズムの解析
渡辺 梨沙

1

はじめに

1.1

研究室配属アルゴリズムとは(指導教員：工藤 和恵)合のシミュレーションを行う。研究室の順位リストはどちらの場合も完全にランダムである。偏りのある学生の希望リストは、各学生に関して希望研究室 i に数値 i + rL (r は [0, 1] の一様乱数) を割り当てて、その数値の小さい順に希望研究室を並べ替えて作成する。

2013 年度の情報科学科の研究室配属を決めるために作られ、実践されたアルゴリズムで、2012 年のノーベ
ル経済学賞の理論ゲイル＝シャプレイのアルゴリズム[1] に基づいている。この研究室配属アルゴリズムは、2013 年度の研究室配属において、とてもよい結果が得られた。
1.23

結果と考察

3.1

ランダムリスト時の比較研究室配属アルゴリズム概要

10.95
rate

1. 各研究室ごとの順位リストと学生の希望リストをを作る

0.9T-Uni
Ocha

0.85

2. 次のルールに基づいて各研究室の希望者を選抜する

0.8024(a) 定員になるまでは無条件に受け入れる(b) 既に定員なら仮採用の学生と比較する→順位が上の学生を仮採用にする

6capacity

81012

図 1: ランダムリスト時の決定率。横軸 (capacity) は定員、縦軸 (rate) は第 4 希望までで決まったときの決(c) 仮採用の学生より新たな希望者の方が順位が下なら落選とする定率を表す。

satisfuction

3. 希望研究室を全て落選なら「未決定」とする
4. 全員が仮採用か未決定になったら終了

2

アルゴリズムの解析

2.1

本研究の目的

T-Uni
Ocha0

研究室配属アルゴリズムは、お茶の水女子大学理学部情報科学科においては良好な結果を出すことができた。しかし、大規模な大学の学科配属、研究室配属にも対応できるかは不明である。そのような大規模な集団に対するこのアルゴリズムの有効性を確認するため、人数の多少での変化をみる。また、研究室によって人気の差があるので、人気の偏りがどのように配属結果に影響するのかを調べる。

246capacity810

図 2: ランダムリスト時の平均満足度。横軸 (capacity)
は定員、縦軸 (satisfuction) 平均満足度を表す。

0.9

用語説明

ratio

2.21
0.980.960.940.92
0.9

決定率 第４希望までで決まった学生の総学生数に対する割合

T-Uni
Ocha

0.6
0.300

満足度 実行結果にどれだけ満足しているかという数
値で第 n 希望の研究室に配属されたときの満足度を (L − n + 1)/L と定義する。(L: 研究室数)

2.3

0.4
0.6
satisfuction

0.81

図 3: ランダムリスト時の満足度分布。横軸 (satisfuc-

大規模大学の設定tion) は満足度、縦軸 (ratio) は総学生数に対する比率

お茶の水女子大学理学部情報科学科 13 研究室に対し、大規模大学は、250 研究室とする。定員を変数として、学生数は次の関係式から決める。
(学生数) × 1.05 = (定員) × (研究室数)

2.40.2を表す。
学生の希望リストがランダムな場合に、大規模大学(T-Uni) とお茶大情報科学科 (Ocha) の決定率 (図 1)、平均満足度 (図 2)、満足度分布 (図 3) を比較する。定員および学生数が増えると決定率、満足度とも数値が上がる。満足度分布図からもほぼ全ての学生が満足していることがわかる。

シミュレーションの設定

学生の希望リスト・研究室の順位リストともにランダムの場合と、学生の希望リストに偏りを持たせた場

67

3.2

ランダムと偏りありの場合の比較

0.01
0.008

10.8

Ocha-R
Ocha-P

0.6

ratio

rate

T-Uni-L1
T-Uni-L2
T-Uni-D
Ocha

0.4

0.006
0.004

0246
capacity

8100.0020

図 4: お茶大の決定率の比較。横軸 (capacity) は定員、0縦軸 (rate) は第 4 希望までで決まったときの決定率を0.2

0.40.6
satisfuction0.81表す。Ocha-R はランダムリスト時、Ocha-P は偏りの
図 8: 満足度分布の比較。横軸 (satisfuction) は満足ある場合のデータ。

rate

度、縦軸 (ratio) は総学生数に対する比率を表す。T10.8
0.60.40.20Uni-L1 は研究室数 250・定員 5 人、T-Uni-L2 は研究室数 250・定員 1 人、T-Uni-D は学科数 25・定員 10人、Ocha は研究室数 13・定員 5 人のデータ。

T-Uni-R
T-Uni-P

0246capacity8のが図 4〜図 7 である。決定率・満足度ともにランダムリスト時と比べて偏りのある場合の方が結果が悪くなっている。また、お茶大よりも大規模大学の方が、ランダムの場合と偏りのある場合の差が大きくなり、とくに決定率は偏りのある場合、大規模大学の方がお茶大より低い値になっている。
図 8 の T-Uni-L1、T-Uni-L2 と T-Uni-D およびOcha は明らかに性質が違う。この性質の違いは、研究室数の差からきていると考えられる。研究室数が多いと満足度が高い方に分布が偏り、より多くの人が満足する。これは、研究室数が多くなると希望する研究室の選択肢が多くなるため、研究室数が少ないときよりも、希望にばらつきが大きく、その中で高い方の希望から叶えられることが原因だと考えられる。また、T-Uni-L1 と T-Uni-L2 の比較から、定員が増えると曲線が滑らかになることがわかる。

10

図 5: 大規模大学の決定率の比較。T-Uni-R はランダ
ムリスト時、T-Uni-P は偏りのある場合のデータ。

satisfuction

10.9
Ocha-R
Ocha-P

0.80.70.60246capacity8104

図 6: お茶大の平均満足度の比較。横軸 (capacity) は定シミュレーションの結果から、大人数でもある程度希望がばらけていれば問題なく機能するということがわかる。また偏りをつけると、人数が少ないときでも決定率が下がる。今回は偏りのつけ方を一通りしか試していないので違う偏りのつけ方をするとまた違う結果が得られることが予想される。今後ほかの偏りでシミュレートし、どのような結果が得られるか実験していきたい。

員、縦軸 (satisfuction) 平均満足度を表す。Ocha-R はsatisfuction

ランダムリスト時、Ocha-P は偏りのある場合のデータ。

1T-Uni-R
T-Uni-P

0.8
0.6
0246
capacity

8

まとめ

参考文献

10[1] D.Gale, L.S.Shapley, ”College Admissions andthe Stability of Marriage”, Amer. Math. Monthly,
69, PP. 9–15 (1962)

図 7: 大規模大学の平均満足度の比較。T-Uni-R はランダムリスト時、T-Uni-P は偏りのある場合のデータ。

[2] 宮崎修一, ”安定マッチング問題”, 情報処理, 54,
PP. 1064–1071 (2013)

お茶大 (Ocha) と大規模大学 (T-Uni) のそれぞれに関して、学生の希望リストがランダムの場合 (R) と偏りのある場合 (P) の決定率と平均満足度を比較したも68