[2H4-GS-13] AI応用: データ解析と探索

[2H4-GS-13-04] 部分的選好下における学校選択問題のスケジューリング

〇和田 凌司¹、八尋 健太郎¹、東藤 大樹^1,2、横尾 真^1,2 (1. 九州大学、2. 理化学研究所 革新知能統合研究センター AIP)

キーワード：マッチング理論、学校選択制、部分的選好

学校選択問題に代表されるマッチング問題に関する既存研究の多くは，学生や学校の持つ選好が厳密に順序付けられている問題を前提としている．しかしながら，学生や学校が数多く存在する現実的な仮定の下で，互いの正確な情報を得ることは困難である．そこで本論文では，各エージェントの選好の一部が順序付けられていない，部分的な選好下における学校選択問題を考察する．学生と学校は期間毎に回数の定められたインタビューを行うことにより，互いに自分が潜在的に持つ選好を明確にしていく．しかしながら，インタビューにはコストが生じると仮定するのが一般的である．そこで，必要最小限の期間でインタビューを行い，各エージェントの潜在的な選好を解明しつつ，望ましい割当を求めることが望まれる．インタビューを行う回数の最小化の観点では，学生最適性を満たす割当を求めるメカニズムが存在する．そこで本論文では，インタビューを行う期間に関する一種の最小性を満たしつつ，学生最適性を満たす割当を出力するInterview Scheduling Gale-Shapleyを提案する．