01. 志望順に基づくクラス編成 志望順に基づくクラス編成 -金色の嘘-

クラス編成を行う場合,各学生にクラスの志望順を提出してもらうことが,一般的には多いと思います.

例えば6人の学生を3つのクラス(クラスA, B, C)に所属させる場合を考えましょう.

ここでは,各クラスの定員は2名とし,各学生の志望順は,下記の表のようだったとしましょう. また,学生は成績の良い順にa, b, c, d, e, fと並んでいるとしましょう.

  第1志望 第2志望 第3志望
学生a A B C
学生b A B C
学生c A B C
学生d B A C
学生e A C B
学生f B A C

このとき,学生の配属の決め方として,すぐに考え付くものに以下の2つがあるでしょう.

方法1(成績優先)
成績の良い学生から順に,可能な(まだ定員に空きのある)クラスの中で最も志望するクラスに配属する.

これは,表を上から各横行毎に見る方法とも言えますね.上記の表では次のようになります.

学生aは第1志望のクラスAへ.
学生bも第1志望のクラスAへ.
学生cはクラスAが定員一杯なので第2志望のクラスBへ.
学生dは第1志望のクラスBへ.
学生eはクラスAが定員一杯なので,第2志望のクラスCへ.
学生fはクラスAとクラスBが定員一杯なので第3志望のクラスCへ.

方法2(志望優先)
第1志望の列を上から順に見て,学生をクラスに割り当てる.ただし,定員一杯だったクラスを志望している学生については,クラスを割り当てずに保留する.次に第2志望の列を上から順に見て,保留中の学生を,同じように割り当ててゆく.以下第3志望列についても,同様に繰り返す.

これは,表を左から各縦列毎に見る方法とも言えますね.見易いように上記の表をもう一度書いておきましょう.

  第1志望 第2志望 第3志望
学生a A B C
学生b A B C
学生c A(保留) B(保留) C
学生d B A C
学生e A(保留) C B
学生f B A C

この表では以下のようになります.

まず第1志望の列を上から見る.

学生aは第1志望のクラスAへ.
学生bも第1志望のクラスAへ.
学生cはクラスAが定員一杯なので保留.
学生dは第1志望のクラスBへ.
学生eはクラスAが定員一杯なので保留.
学生fは第1志望のクラスBへ

次に第2志望の列を上から見て,保留されている学生cと学生eを割り当てる.

学生cはクラスBが定員一杯なので保留.
学生eはクラスCへ.

最後に第3志望の列を上から見て,保留されている学生cを割り当てる.

学生cはクラスCへ.

方法1と2のどちらが「良い」方法なのかは,意見の分かれるところでしょう.
大きな違いとして方法2は「嘘をつくと良くなることがある」という性質を持ちます.
例えば,上記の表で学生cの志望順位を(ABC)の順から(BAC)の順に変えてみましょう.
この表に方法2を使うと, 以下のようになります.

  第1志望 第2志望 第3志望
学生a A B C
学生b A B C
学生c B A C
学生d B A C
学生e A(保留) C B
学生f B(保留) A(保留) C

まず第1志望の列を上から見る.

学生aは第1志望のクラスAへ.
学生bも第1志望のクラスAへ.
学生cは第1志望のクラスBへ.
学生dは第1志望のクラスBへ.
学生eはクラスAが定員一杯なので保留.
学生fはクラスBが定員一杯なので保留.

次に第2志望の列を上から見て,保留されている学生eと学生fを割り当てる.

学生eはクラスCへ.
学生fはクラスAが定員一杯なので保留.

最後に第3志望の列を上から見て,保留されている学生fを割り当てる.
学生fはクラスCへ.

学生cは,方法2では本来の志望順位(ABC)において第3志望のクラスCにしか行けないのですが,自分の志望順位を(BAC)と嘘をついて提出することにより,本来の志望順位で第2志望のクラスBに所属することができるようになります.
(そのせいで, 学生fは第1志望のBから、第3志望のCにおいやられてしまうわけです.)

いつでもこんな事ができる訳ではありませんが,このような事が生じる可能性が,方法2にはあります.ですから方法2を使うと,学生達は他人の志望によっては得する可能性があるので,互いの志望を探り合うようになるかもしれませんね. また,提出された志望順は,クラスの人気と関係ないものになっているかもしれません.

ちなみに方法1では,嘘をついて得する事は決してありません.(何故だか分りますか?)

ですから方法1を使うと,学生は他人の志望を知って得することは無く,自分の本当の志望をそのまま提出することが予想されます.このため,提出された志望順は,クラスの人気を反映したものになっている可能性が大きいと予想されます.

参考文献:久保幹雄, 松井知己, 組合せ最適化[短編集], 朝倉書店, 1999年1月.