研究背景・目的
学生の進学コースの割当てや研修医の病院への配属など、多数の参加者の希望に基づきマッチングを求めたい場面は社会に数多く見受けられます（図1）。その多くに、参加者が提出する希望順位リストを入力データとしてマッチングを計算するコンピュータシステムが用いられています（図2）。私はその計算を支えるアルゴリズムの理論研究を行っています。適切なアルゴリズムを設計することによって、一部の参加者に理不尽な思いをさせたり、虚偽のデータ申告を誘発したりすることのないような公平な仕組みづくりを目指します。社会の変化に伴い現れる多様な問題に対処するための柔軟な理論づくりが求められています。
研究内容
マッチングシステムを必要とする個々の問題では、その運営機関の制度や問題意識に由来するさまざまな要望があります。例えば、割当て先の組織がダイバーシティに関する制約を持っていたり、一定数以上の割当ての保証を求めていたりする状況が考えられます。そのような多種多様な問題に対処するため、マッチング理論を拡張する研究を行っています。一見似たように見える問題でも、その背後にある数学的構造の違いにより、問題の難しさや然るべきアプローチ方法が大きく異なることがあります。問題の本質的構造を見抜き、組合せ最適化理論などを活用しながら、高速に公平なマッチングを求めるアルゴリズムを設計しています。
産業応用の可能性
マッチング理論は、人や組織の間のマッチングを求める様々な場面で役立ちます。中でも、特に大きな貢献を見せる場面として、公共性が高く規模の大きいシステムの開発・改良があげられます。制度の透明化やアルゴリズムの公開が求められる公共性の高いシステムにおいては、参加者に納得してシステムを利用してもらうために、計算結果の正当性が理論的に保証されていることが必要不可欠です。加えて、大規模な問題を扱う際には、実用可能な速度で必ず出力が得られることを保証する必要があるため、アルゴリズムの計算量の改善が欠かせません。
連絡先
横井 優［情報学プリンシプル研究系 助教］
yokoi[at]nii.ac.jp ※[at]を@に変換してください
