雛学生論文賞受賞論文

要約機

東工大の学科所属方式における学生の申告の安定性について
宮岸宏明(薪許謀議草壁語学科)指導教官森雅夫

ここで，学生がお互いに他の学生の本当の志望や成績1. はじめにを知っているとし、う仮定をおくと，各学生は他の学生が本論文では，成績と学生の提出した志望という 2 種類のデータから，学生をいくつかの定員の決まっている学科に所属させようとする状況を考えている.

どのような申告をするかを考えることが可能である.
そこでどの学生も自分が所属できる最も高い学科に所属しようとすると仮定する.すると，と、の学生について東工大の学科所属の場合，全学生の満足度の総和を最も，自分だけがこれ以上申告を変えても所属できる学科大とする，などの目標が数量的にはっきりと表わされては良くならないと考える申告は，全学生が[この結果ないないので，線形計画法などの方法を使用できない.まらば良いだろう jた，東工大の場合，定員がある幅を持った範囲で示さの申告を集めたものを安定な申告と定義する.学生 z のれ，どの学科も所属する学生数がその範囲内でなければ学科 j に対する真の志望順位を Gi (j) とすると，安定ならないという特別な制約がある.したがって，学科所な申告 (Xl* ， … ， X n *) は次のように表わされる.

属の方法はアルゴリズムの形で与えられている.その方

Vi , VXi , Gi(Fi(Xl* , …, X iJ …, X n*) )三三 G i (F i (Xl* ， … ， Xiぺ ...， X n *))法では，一度別の学科に所属が決まった学生を下限不足の学科へ移す，はぎとりと呼ばれる手続きが入札多少複雑になっている.と考えた申告である.このとき各学生

3. 安定な申告を求めるアルゴリズム

そこで，この論文では学生がお互いに他の学生の本当安定な申告を求めるためには，学生の申告の全体をの志望や成績を知っていると L 、う仮定のもとで，東工大

X=(Xh...， Xn)t とすると，定義より次のようなアルゴの学科所属の方法について，どの学生も納得できるようリズムをとれば良い.

な結果になり，各学生がこのように申告すると予想でき

Step1 成績が l 番の学生から順に学生 i についてん

る申告を安定な申告として定義し，その特徴を調べてい=F;(X) を求める.

る.

科んよりも順位が上の学科 j のうち，本当の志望において学第 l 志望を学科 J と申告を変更することで j に所属できるかを調べ2. 安定な申告n 人の学生が ，そして，る.

m 学科に所属する場合を考える.東工

Step2 Step1 の条件を最初に満たす学生の申告を第大の学科所属方法は，基本的には志望を成績よりも優先

1 志望を学科 J と変更し，新たな申告 X' について，している.つまり，成績が最下位の学生の第 1 志望が，再び Step 1, 2 を繰り返す.

成績が 1 番の学生の第 2 志望よりも優先して扱われる.

Step3 Step1 の条件を満たす学生が L 、なくなったとすると，場合によっては自分の本当の志望を書くよりもきの申告が安定な申告.

嘘の申告をした方がよい結果が得られることがある.

しかし，東工大の学科所属では，学生は希望学科に所

そこで成績が i 番目の学生の第 J 志望の申告を Xi jJ

属できない場合，留年を希望することができる.このとこれをまとめて Xi=(Xib Xi2 , ..', Xim) としたとき，東き上記の考え方で安定な申告を求めることができない場

工大が行なっている学科所属の結果，学生 i が所属する合がある.

学科を Fi(Xh ...， X n )46と，定義する.

ところで安定な申告について学科所属を行なった結果© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

は，成績の良い方の学生から順に所属学科を決定する学

以下の成績の学生から所属学科の期待値は，急激に増大

科所属の決定方法によって各学生の本当の志望からえたする.

給果と同じになる.これを利用して，安定な申告を求めまた，人気が特にある学科，人気のある学科，不人気る第 2 のアルゴリズムを考えた.

学科に分けられるときは，人気学科・不人気学科と二分

Step0 学科 h の所属学生数 n(k) を O とする.

されたノミターンを 2 つ重ね合わせたものとして表現でき成績が 1 番の学生から順に Step 1, 2 を繰り返す.

Step1 学生 i について ，n(k) く(学科 h の下限)を満ることがわかった.

さらに安定な申告と本当の志望をそのまま表現するとたし所属可能な学科の中で，もっとも所属を希望してきの結果の差異について調べると，人気が人気学科・不いる学科 h を学生 i の第 1 志望の申告とする.

人気学科と二分されたパターンの場合は期待値にそれほStep2 n(ktl= 叫ん )+1とする.

ど差が出なかったが，人気が特にある学科・人気のある

このアルゴリズムは次の性質を持つことが証明でき

学科・不人気学科に分けられるときは，期待値に差が大きく出て，安定な申告を申告するときは，ある程度以下る.

1) 希望留年の申告を認める場合と認めない場合のどの成績の学生は希望した学科に入りにくくなっている.

ちらについても実行できる.

また期待値に対する分散をとったところ，一般に安定な2) 実行すると有限回で終了する.

申告の方が分散が小さく，比較的確実に期待される志望

このアルゴリズムの実行結果を X* とすると，順位の学科に入れることがわかった.

3) X* は2 掌で定義した安定な申告の性質をもっている.

これらのことから，安定な申告をすると，各学科への人気度のパターンと成績によってどのくらいの志望の学

4) 希望留年の申告を認めない場合，任意の学生 z について Fi(X*) は唯ーである.

科へ所属できるかが予想できる.このとき成績の良い学

生ほとe 志望順位の高い学科に入りやすくなっていて，優先される.

4. 計算機実験
3 章の安定な申告を求めるアルゴリズムをもとに，プ5.

結論

ログラムを作成した.それをもとに，人気学科が l つだ

本論文では，学生がお互いに他の学生の本当の志望やけ存在するときとか，不人気学科が l つだけ存在すると成績を知っていると L 、う仮定のもとで，安定な申告といきといった，学科問の人気度のパターンを与えてみたとう特別な申告を定義し，その存在性を証明し，計算機実き，安定な申告を行なうと，ある成績の学生が何番目の験によって特徴を調べた.その結果，この安定な申告は志望学科に所属できると期待できるかについて調べた.

東工大の学科所属の方法において，成績の良 L 、学生の志さらに各学生が安定な申告をしているときと，全学生が望を優先する形となっていることがわかった.しかし，本当の志望をそのまま申告するときで，所属する学科の現実には学生が得られる情報はそれほど多くなく，不確志望順位の期待値にどんな違いが生じるのかを調べてみ実である.したがって，そのような状況では安定な申告た.のような特別な申告が存在するのか，存在するならばそ

その結果，人気度のパターンによって期待値と成績順位のグラフを描いたところ，それぞれ異なる特徴をもっの申告による結果は学生にどのような影響を与えるのか，と L 、う問題が課題として残っている.

たグラフとなった.たとえば，相対的に人気のない学科

参芳文献

が 1 つある場合，大部分の学生がこの学科に対してもっている志望順位は低いものと推測できるので，他の人気[1] 今野浩・朱最適クラス編成問題東京工業大のある学科に所属で、きなかった成績の低い学生が人気の学におけるケーススタディー，東京工業大学人文社ない学科に集中する.したがって，グラフではある程度

会群レポート，1992 年 1 月号

IHSS90‑22 (1990).

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

41