コースの割り当て

コース割当とは、大学の授業における学生の席数を割り当てる問題です。多くの大学では、教員が個々の学生に十分な指導を行えるよう、各コースの登録可能人数に上限を設けています。しかし、一部のコースの需要が上限を超えている場合、どの学生を各コースに登録させるべきかという問題が当然生じます。

多くの教育機関では、学生の登録を先着順としています。しかし、これは不公平な結果を招く可能性があります。登録開始時にたまたまコンピューターの近くにいた学生は、最も希望するコースすべてに登録できる一方で、登録が遅すぎた学生は、希望するコースがすべて満席で、あまり希望しないコースしか登録できないという事態に陥る可能性があります。この不公平さを軽減するために、多くの教育機関はより洗練された割り当てメカニズムを採用しています。[1]

ドラフトメカニズム

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

ドラフト手続きの問題点は、戦略性がないことです。学生は、申告された好みを操作することで、より良いコースを受講できる可能性があります。さらに、ドラフト手続きは操作が容易です。学生は、受講希望者の多いコースへの好感度を過大申告し、受講希望者の少ないコースへの好感度を過小申告するはずです。ハーバード大学でのフィールドスタディの結果は、学生が実際に自分の好みを操作していることを示しており、この操作はパレート効率の悪い、社会厚生の低い配分につながることを示しています。[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）というメカニズムが使用されます。Eric Budish がこの理論を開発し、[12] Othman と Sandholm [13]が効率的なコンピューター実装を提供しました。Budish、Cachon、Kessler、および Othman は実装を改良し、CourseMatch と呼ばれる彼らの実装は、ウォートン・ビジネス・スクールで実装され、以前の入札ベースのメカニズムに取って代わりました。[14]これは Cognomos によって商業的に実装されています。[15]最近、ブディッシュ、ガオ、オスマン、ルビンスタイン、チャンは、近似CEEIを見つけるための新しいアルゴリズムを発表しました。このアルゴリズムは、従来のアルゴリズムよりも大幅に高速で、すべての実用的なインスタンスでクリアエラーがゼロになり、優れたインセンティブ特性を備えています。[16]

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

Soumalis、Zamanlooy、Weissteiner、Seuken [19]は、機械学習を使って学生のレポートの誤りを学習し修正する 方法を提示している。

A-CEEI の主な問題は、価格ベクトルの空間を検索する必要があり、各価格ベクトルに対して多くの学生の最適なバンドルを計算する必要があるため、非常に計算負荷が高いことです。

ドラフトと入札を組み合わせる

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

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

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

  • バイナリ- 学生 1 人あたりのコース座席の平均数 (効率性の尺度)、および範囲と標準偏差(公平性の 2 つの尺度)。
  • 序数- 生徒ごとの平均合計順位、範囲、標準偏差。
  • 基数- 生徒 1 人あたりの平均総効用、および範囲と標準偏差。

二項性と順序性の観点から見ると、OCは効率性と公平性の両方において最高のスコアを獲得し、次いでSP-OとTTC-O、ドラフト、SP、TTCの順となり、入札は最も低いスコアを獲得しました。基数性の観点から見ると、OCとBPMが最も効率的でしたが、SP-OとTTC-Oが最も公平でした。ドラフトは非常に非効率的で、BPMは非常に不公平でしたが、SPとTTCは中程度の効率性と中程度の公平性を示しました。

いかなるアルゴリズムも戦略証明は不可能であるため、研究者らは各アルゴリズムにおける戦略的操作のインセンティブ、すなわち操作によって学習者がどれだけの利益を得られるかを研究した。実験の結果、入札メカニズムでは、操作者への利益が最も高く、誠実な学習者への操作による損害も最も高かった。利益と損害の合計が最も低かったのは、TTC-O、SP-O、およびドラフトであった。

両側マッチングに基づくメカニズム

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

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

ディーボルドとビヒラー[23]は、コース割り当て情報の両側マッチングのさまざまなメカニズムを比較しています。

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

その他のメカニズム

コース割り当ての他のメカニズムでは、公平なランダム割り当てが使用されます。[25]

参考文献

  1. ^ ab コミナーズ、スコット・デューク、ルベリー、ジョナサン・ウルマン (2010). 「代理オークションによるコース割り当て」. サベリ、アミン (編).インターネットとネットワーク経済学. コンピュータサイエンス講義ノート. 第6484巻. ベルリン、ハイデルベルク: シュプリンガー. pp.  551– 558. doi :10.1007/978-3-642-17572-5_49. ISBN 978-3-642-17572-5。
  2. ^ ab ブ ディッシュ、エリック;カンティヨン、エステル (2007)。ピーター・クラムトン。ミュラー、ルドルフ。タルドス、エヴァ。テネンホルツ、モーシェ (編)。 「複数単位の割り当て問題における戦略的行動: コース割り当てからの理論と証拠」。計算社会システムとインターネット。ダグシュトゥール セミナー議事録。7271。 Dagstuhl、ドイツ: Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI)、Schloss Dagstuhl、ドイツ: 1. doi : 10.4230/DagSemProc.07271.15。
  3. ^ ab Budish, Eric; Cantillon, Estelle (2012-08-01). 「複数単位割り当て問題：ハーバード大学における授業配分の理論と証拠」アメリカ経済評論. 102 (5): 2237– 2271. doi :10.1257/aer.102.5.2237. hdl :2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/230854. ISSN  0002-8282. S2CID  5132273.
  4. ^ 星野, リチャード; レイブル＝クラーク, カレブ (2014年7月27日). 「クエスト・ドラフト：自動コース割り当てアルゴリズム」. AAAI人工知能会議議事録. AAAI'14. 28 (2). ケベックシティ, ケベック州, カナダ: AAAI Press: 2906– 2913. doi :10.1609/aaai.v28i2.19025. S2CID  14197118.
  5. ^ Li, Mengling (2020年10月1日). 「同点が重要：同点を許容することでコース配分の効率性を向上させる」. Journal of Economic Behavior & Organization . 178 : 354– 384. doi :10.1016/j.jebo.2020.07.030. ISSN  0167-2681. S2CID  225044860.
  6. ^ パパイ、シルビア (2001)。 「戦略性が高く、偉そうなことのない複数の任務」。公共経済理論ジャーナル。3 (3): 257–271。土井:10.1111/1097-3923.00066。ISSN  1467-9779。
  7. ^ エーラーズ、ラース、クラウス、ベッティーナ (2003). 「多重割り当て問題に対する連合的戦略証明と資源単調解」.社会選択と福祉. 21 (2): 265– 280. doi :10.1007/s00355-003-0259-1. ISSN  0176-1714. JSTOR  41106560. S2CID  8455104.
  8. ^ ハットフィールド、ジョン・ウィリアム (2009年9月1日). 「戦略性のない、効率的で、かつ非強引なクォータ配分」.社会選択と福祉. 33 (3): 505– 515. doi :10.1007/s00355-009-0376-6. ISSN  1432-217X. S2CID  7713320.
  9. ^ ab ソンメズ、テイフン;ユンバー、M. ウトゥク (2010)。 「ビジネススクールにおけるコース入札*」。国際経済レビュー。51 (1): 99–123 .土井:10.1111/j.1468-2354.2009.00572.x。ISSN  1468-2354。S2CID  154573224。
  10. ^ 「テルアビブ大学の登録手順（ヘブライ語）」2020年6月15日。
  11. ^ Krishna, Aradhna; Ünver, M. Utku (2008-03-01). 「研究ノート—ビジネススクールにおけるコース入札の効率性向上：フィールド研究と実験室研究」.マーケティング・サイエンス. 27 (2): 262– 282. doi :10.1287/mksc.1070.0297. ISSN  0732-2399.
  12. ^ ab Budish, Eric (2011-12-01). 「組み合わせ割当問題：平等所得からの近似競争均衡」. Journal of Political Economy . 119 (6): 1061– 1103. doi :10.1086/664613. ISSN  0022-3808. S2CID  1161325.
  13. ^ Othman, Abraham; Sandholm, Tuomas; Budish, Eric (2010-05-10). 「近似競争均衡の探索：効率的かつ公正なコース配分」. Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1. AAMAS '10. Toronto, Canada: International Foundation for Autonomous Agents and Multiagent Systems: 873–880 . ISBN 978-0-9826571-1-9。
  14. ^ ab Budish, Eric; Cachon, Gérard P.; Kessler, Judd B.; Othman, Abraham (2016年10月28日). 「コースマッチ：等所得からの近似競争均衡の大規模実装による組み合わせ配分」.オペレーションズ・リサーチ. 65 (2): 314– 336. doi : 10.1287/opre.2016.1544 . ISSN  0030-364X.
  15. ^ 「Course Matchは高等教育における最も公平なコース登録プラットフォームです」www.cognomos.com . 2023年6月14日閲覧。
  16. ^ ブディッシュ、エリック;高、瑞泉。オスマン、アブラハム。ルービンシュタイン、アビアド。張千帆（2023）。 「均衡に基づく公正な分割のための実践的なアルゴリズムと実験的に検証されたインセンティブ（A-CEEI）」。arXiv : 2305.11406 [cs.GT]。
  17. ^ Budish, Eric; Kessler, Judd B. (2016年7月25日). 「市場参加者は（十分に）自分の選好を正確に報告できるか？」ワーキングペーパーシリーズ. doi :10.3386/w22448. {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  18. ^ Budish, Eric B.; Kessler, Judd B. (2017年11月12日). 「エージェントは『自分のタイプを報告』できるか？ ウォートンにおけるコース割り当てメカニズムを変えた実験」. ニューヨーク州ロチェスター. doi :10.2139/ssrn.2579107. S2CID  109825489. SSRN  2579107. {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  19. ^ Soumalias, Ermis; Zamanlooy, Behnoosh; Weissteiner, Jakob; Seuken, Sven (2024). 「機械学習を活用したコース配分」.第25回ACM経済・計算会議論文集. p. 1099. arXiv : 2210.00954 . doi :10.1145/3670865.3673573. ISBN 979-8-4007-0704-9。
  20. ^ Atef Yekta, Hoda; Day, Robert (2020-01-13). 「コース割り当て問題のための最適化ベースのメカニズム」. INFORMS Journal on Computing . 32 (3): 641– 660. doi :10.1287/ijoc.2018.0849. ISSN  1091-9856. S2CID  213466767.
  21. ^ Budish, Eric (2012-12-01). 「マッチング「対」メカニズム設計」. ACM SIGecom Exchanges . 11 (2): 4– 15. doi :10.1145/2509002.2509005. S2CID  5938165.
  22. ^ ディーボルド、フランツ;アジズ、ハリス。ビヒラー、マーティン。マテス、フロリアン。シュナイダー、アレクサンダー (2014-04-01)。 「安定したマッチングによるコース配分」。ビジネスおよび情報システム工学。6 (2): 97–110。土井:10.1007/s12599-014-0316-6。ISSN  1867-0202。S2CID  493430。
  23. ^ Diebold, Franz; Bichler, Martin (2017-07-01). 「無差別条件によるマッチング：コース配分におけるアルゴリズムの比較」. European Journal of Operational Research . 260 (1): 268– 282. doi :10.1016/j.ejor.2016.12.011. ISSN  0377-2217.
  24. ^ Krishna, Aradhna; Ünver, M. Utku (2008年3月). 「研究ノート—ビジネススクールにおけるコース入札の効率性向上：フィールド研究と実験室研究」.マーケティング・サイエンス. 27 (2): 262– 282. doi :10.1287/mksc.1070.0297. ISSN  0732-2399.
  25. ^ Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). 「ランダム配分メカニズムの設計：理論と応用」. American Economic Review . 103 (2): 585– 623. doi :10.1257/aer.103.2.585. ISSN  0002-8282.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Course_allocation&oldid=1321785977"