コース割り当て

履修科目割り当てとは、大学の授業における学生の席数を割り当てる問題である。多くの大学では、教員が各学生に十分な注意を払えるよう、各授業の履修登録者数に上限を設けている。一部の授業では、登録希望者が上限を超える場合があるため、どの学生をどの授業に登録させるべきかという疑問が生じる。

多くの教育機関では、先着順で学生の登録を受け付けています。しかし、これは不公平な結果を招く可能性があります。登録開始時にたまたまコンピューターの近くにいた学生は、最も人気のあるコースすべてに登録できる一方、遅れて来た学生は、希望するコースがすべて満席で、あまり人気のないコースにしか登録できない可能性があります。このような不公平を軽減するために、多くの教育機関はより高度な割り当てメカニズムを使用しています。^{[ 1 ]}

ドラフト方式（ラウンドロビンとも呼ばれる）では、学生は空席のあるコースのセットから順番にコースを選択します。選択順序は最初のラウンドではランダムで、その後のラウンドでは逆になります。実際には、学生はラウンドごとに選択する必要はなく、個々のコースに対する好みをコンピュータに報告するだけで、コンピュータが一度に1つずつコースを選択します。この手順は、たとえば1990年代半ばからハーバード・ビジネス・スクールで使用されています。 ^{[ 2 ]}ドラフト方式の重要な利点は、すべての学生がt番目のコースを取得する前に、どの学生も( t +1)番目のコースを取得することはないという意味で、比較的公平であることです。

ドラフト方式の問題点の1つは、戦略耐性がないことです。学生は、報告した好みを操作することで、より良いコースを取得できる可能性があります。さらに、ドラフト方式は操作しやすいです。学生は、より希望するコースの好みを過大に報告し、あまり希望しないコースの好みを過小に報告する必要があります。ハーバード大学でのフィールド調査の結果は、学生が実際に好みを操作していることを示しており、この操作はパレート効率的ではなく、社会的厚生が低い配分につながります。^{[ 2 ]}

操作による非効率性を軽減できる可能性のあるドラフトの変種として、プロキシドラフトがある。このメカニズムでは、学生は依然としてコンピュータに好みを報告するが、今回はコンピュータが学生の代わりに最適な方法で好みを操作し、元のドラフトを実行する。この手順により、操作のミスや選択順序における位置の知識不足による厚生損失が軽減される。^{[ 3 ]： 5}その他の変種としては、クエストドラフト^{[ 4 ]}やパレート改善ドラフト^{[ 5 ]}がある。

ドラフト方式のもう一つの問題点は、学生の順位付けのみを考慮し、基数的な評価を無視している点です。これは非効率性を招く可能性があります。例えば、ランダムな順序で最初の学生がコースAをコースBよりわずかに好むのに対し、2番目の学生はAをBより強く好むとします。ドラフト方式では最初の学生にAが割り当てられますが、（少なくとも功利主義的な観点からは）2番目の学生にAを割り当てる方が効率的だったでしょう。

経済理論家は、ランダム連続独裁制（RSD）が事後的にパレート効率的であり、他のいくつかの自然な特性を満たす唯一の戦略耐性メカニズムであることを証明しました。この理論的事実に基づいて、彼らはそれをコース割り当てに実際に使用することを提案しました。^{[ 6 ] [ 7 ] [ 8 ]}

しかし、実地実験では、RSDは、第一希望のコースを受講できた学生数や学生一人当たりの平均コース順位といった自然な指標において、操作可能なドラフト制度よりも劣ることが示されている。^{[ 3 ]： 5}

入札方式では、各学生に一定額の架空のお金が与えられ、その「お金」を受講したいコースに割り当てます。すべてのコースに対するすべての学生の入札は、高い順から低い順に並べられ、1つずつ処理されます。各入札は、学生がスケジュールを埋めておらず、かつコースに空席がある場合にのみ有効になります。同様の方式は、ロス・スクール・オブ・ビジネス、コロンビア・ビジネス・スクール、ハース・スクール・オブ・ビジネス、ケロッグ・スクール・オブ・マネジメント、プリンストン大学、イェール・スクール・オブ・マネジメント^{[ 9 ]}、テルアビブ大学^{[ 10 ]}で使用されています。

入札メカニズムにはいくつかの欠点があります。まず、第一価格オークションと同様に、戦略耐性がありません。そのため、学生は他の学生がこれらのコースにいくら入札するかを推測して、各コースにいくら入札するかを決めるのに多くの労力を費やす可能性があります。第二に、結果が非​​効率的になる可能性があります。学生の入札には、学生の好みを推測することと、座席に対するより大きな権利を持つ人を決定することという2つの役割があります。これら2つの役割は相反する可能性があり、非効率的な結果につながる可能性があります。^{[ 11 ]}第三に、入札メカニズムの結果は非常に不公平になる可能性があります。一部の学生は希望するコースを全く受けられない一方で、他の学生は希望するすべてのコースを受ける可能性があります。^{[ 12 ]}

Kominers、Rubbery、Ullman ^{[ 1 ]}は、各学生に代わって質の高い操作を計算することを目的とした代理入札メカニズムを導入した。彼らのシミュレーションによると、このメカニズムは操作を行うインセンティブを減少させ、したがって効率性を向上させる可能性がある。

均衡メカニズムでは、各学生は実行可能なすべてのコーススケジュール（つまり、2 つのコースが時間的に重複せず、2 つのコースが異なる時間に同じ教材を教えない、コースのすべての部分集合）に順位を付けることができます。次に、コンピュータはこの市場で均等な収入からの競争均衡を見つけます。正確な競争均衡は存在しない可能性があるため、実際によく使用されるメカニズムは、均等な収入からの近似競争均衡（A-CEEI）です。エリック・ブディッシュがこの理論を開発しました。^{[ 12 ]}オスマンとサンドホルム^{[ 13 ]}は効率的なコンピュータ実装を提供しました。ブディッシュ、カション、ケスラー、オスマンは実装を改善しました。彼らの実装は CourseMatch と呼ばれ、ウォートン・ビジネススクールで実装され、以前の入札ベースのメカニズムに取って代わりました。^{[ 14 ]}これは Cognomos によって商用実装されています。^{[ 15 ]}最近、Budish、Gao、Othman、Rubinstein、Zhang らは、近似 CEEI を見つけるための新しいアルゴリズムを発表しました。これは、以前のアルゴリズムよりも大幅に高速で、すべての実用的なインスタンスでゼロのクリアリング エラーを達成し、インセンティブ特性も優れています。^{[ 16 ]}

スケジュールのランキングを報告する必要性は、実行可能なスケジュールの数が非常に多くなる可能性があるため、このようなアルゴリズムを実装する上で大きな課題となります。^{[ 17 ] [ 18 ]}この課題を克服するには、学生が妥当な時間内に好みを記述できるようなシンプルな言語を設計する必要があります。ウォートンで開発された言語では、学生は各コースの効用と、コースのペアごとの「調整値」を指定できます。各ペアの効用は、個々のコースの効用の合計に調整値を加えたものです。ゼロ/正/負の調整値は、それぞれ独立財/補完財/代替財であるコースに対応します。さらに、特定のコースの組み合わせ（たとえば、同じ時間に開講されるコースや同じ内容のコース）は明示的に禁止されています。この言語ではスケジュール上のすべての可能なランキングを表現できるわけではありませんが、実際には十分です。^{[ 14 ]}

Soumalis、Zamanlooy、Weissteiner、Seuken ^{[ 19 ]}は、機械学習を使用して学生のレポートのエラーを学習して修正する方法を提示しています。

A-CEEIの大きな問題点は、価格ベクトル空間を探索する必要があり、各価格ベクトルに対して多数の学生の最適な組み合わせを計算する必要があるため、計算負荷が非常に高いことである。

Atef-YektaとDay ^{[ 20 ]}は、公平性を高めるラウンドごとの構造を維持しつつ、入札の要素を取り入れることでドラフトメカニズムの効率性を向上させることを目指している。彼らはいくつかのヒューリスティックアルゴリズムを提示している。

• TTCアルゴリズム：トップトレーディングサイクルにヒントを得たアルゴリズムです。各学生は1000ポイントをコースに割り当てます。各ラウンドで、各学生は残りの受講可能なコースの中から、最も価値の高いコースを選択します。各コースは定員に応じて最高額の入札者を受け入れ、最低額の入札者を拒否します。拒否された学生は、新たに最も価値の高いコースを選択し、すべての学生が1つのコースを受講するまでこのプロセスを繰り返します。その後、アルゴリズムは次のラウンドに進みます。このアルゴリズムの目的は、入札の効率性とドラフトの公平性を両立させることです。
• SPアルゴリズム：セカンドプライスオークションにヒントを得たアルゴリズムです。マルチラウンドTTCに似ていますが、1つの違いがあります。定員qの各コースについて、合格した学生は全員( q +1)番目の「価格」（ポイント）を支払い、残りのポイント（入札額から価格を引いたもの）は、残りのコースの中で最も良いコースに移動され、次のラウンドでそのコースを獲得できる可能性が高まります。
• TTC-OおよびSP-O：TTCおよびSPの最適化バージョン。整数線形計画法を用いてグローバル最適福祉を計算する。
• OCアルゴリズム：このアルゴリズムはラウンドごとの最適化ではなく、順序ランクのグローバル最適化を行い、それに基づいて基数効用の合計のグローバル最適化を行います。最適化は整数線形計画法を用いて行われます。このメカニズムは、順序ランクに関してパレート効率的です。

彼らは、それぞれ900人の学生と6つのコースの定員を持つ100のサンプル市場において、5つのアルゴリズムを入札およびドラフトメカニズムと比較した。コースセクションは112あり、一部は同じコースに属し、一部は重複している（そのため一緒に受講できない）。コースの定員は、離散的な一様分布からランダムに抽出された。これらの特徴は、ハーバード・ビジネス・スクールのものと類似している。彼らは、いくつかの指標を用いてアルゴリズムを評価した。

• 二値変数- 学生一人当たりの平均受講者数（効率性の指標）、およびその範囲と標準偏差（公平性の2つの指標）。
• 順序尺度- 生徒一人当たりの平均合計順位、範囲、および標準偏差。
• カーディナル- 学生一人当たりの平均総効用、範囲、および標準偏差。

二値的および順序的側面では、効率性と公平性の両方でOCが最高得点を獲得し、次いでSP-OとTTC-O、そしてDraft、SP、TTCの順となり、Biddingが最低得点でした。基数的側面では、OCとBPMが最も効率的でしたが、SP-OとTTC-Oが最も公平でした。Draftは非常に非効率的で、BPMは非常に不公平であり、SPとTTCは中程度の効率性と中程度の公平性でした。

戦略に耐性のあるアルゴリズムは存在しないため、研究者らは各アルゴリズムにおける戦略的操作のインセンティブ、つまり学生が操作によってどれだけの利益を得られるかを研究した。実験の結果、入札メカニズムでは操作者の利益が最も高く、正直な学生に対する操作による損害も最も高いことが分かった。利益と損害の合計が最も低かったのは、TTC-O、SP-O、およびドラフトであった。

ほとんどの研究では、学生のみがコースに対する好みを持ち、コースには好みがないと仮定しています。つまり、市場は片面市場です。しかし、コースにも好みがある可能性があり、したがって市場は両面市場であると仮定する研究もあります。^{[ 21 ]} 両面市場の主な目標は安定したマッチングを見つけることであり、主なアルゴリズムはゲイル・シャプレーアルゴリズム（遅延受諾、DA）です。

Diebold、Aziz、Bichler、Matthes、Schneider ^{[ 22 ]}は、学生にとって最適なDAと効率調整済みDAという2つのメカニズムを比較しています。また、個々のコースではなく、コースのスケジュール割り当てに関する最近の拡張についても調査しています。彼らは、安定したマッチングメカニズムの利点を示すフィールド実験について報告しています。

DieboldとBichler ^{[ 23 ]}は、コース割り当て情報に基づく双方向マッチングのさまざまなメカニズムを比較している。

Krishna と Unver ^{[ 24 ]}および Sonmez と Unver ^{[ 9 ]}は片面市場を考察しているが、それでも双方向マッチングの使用を提案している。彼らの根拠は、既存のメカニズムでは学生の入札には 2 つの異なる役割があるということである。1 つは各コースの席に対するより大きな権利を誰が持っているかを決定するために使用され (この役割では戦略的ツールとして使用される)、もう 1 つは学生の好みを推測するために使用される。彼らはこれら 2 つの役割を分離することを提案している。各学生が各コースの基数値とコースの順序付けの両方を報告できるようにする。これら 2 つの報告は一致している必要はない。DA を実行すると、学生の好みは順序付けによって決定され、コースの好みは学生の基数値によって決定される。実際には、コースはそれをより強く望む学生を受け入れることを「優先」する。DA アルゴリズムと同様に、各学生は自分の順序付けで最も高いランクのコースに「提案」する。需要の高いコースでは、学生をその基数値に基づいて順位付けし、最も低い値を持つ学生を拒否します。理論と実地実験に基づくと、この方式は割り当ての効率性を向上させると報告されています。しかし、矛盾する2つの選好セットを報告すると、インセンティブの問題が増加する可能性があります。さらに、このアルゴリズムには公平性の保証がありません。

コース割り当ての他のメカニズムでは、公平なランダム割り当てが用いられている。^{[ 25 ]}