イベント / EVENT

2019年度 第1回 リポート

2019年度市民講座「情報学最前線」スタート!

第1回は横井助教がマッチング理論について講義

 国立情報学研究所の研究者らが、最先端の情報学研究について一般の方向けに分かりやすく解説する市民講座「情報学最前線」の2019年度の講座がスタートしました。今年度は4回にわたり、コンピュータビジョンや理論計算機科学などさまざまなテーマで講義を行います。

https://www.nii.ac.jp/event/shimin/

 第1回は、7月2日(火)に開催し、情報学プリンシプル研究系 横井 優 助教が「みんなHappy!? マッチングの数理と計算-かしこい割り当ての決め方-」と題し講義しました。

report_2019-1-1.jpg

 研修医の病院への配属や学生の研究室への配属、寮でのルームメイト決め、保育園の割り当てなど、社会には望ましい組み合わせや割り当て=マッチングを考える場面が数多くあります。横井助教は、そのような場面で、各参加者の希望を考慮しつつ、誰も理不尽な思いをしない公平なマッチング方法を考えるマッチング理論の研究を行っています。

 講義では、理論、応用ともに発展しているトピックとして、二つのグループのメンバー同士をマッチさせる「二部マッチングモデル」を紹介しました。横井助教は、各参加者がどんな希望順序を持っているときでも安定マッチング(誰もが納得しうる公平性の高いマッチング)を見つけることができる「Gale-Shapleyアルゴリズム」について説明。このアルゴリズムやその改良版が、実際に日本やアメリカで研修医の病院への配属や学生の研究室配属に応用されており、アルゴリズムの導入や改善によって、マッチ率や参加者の満足度が向上していると話しました。

 続いて、人々が各自の所有物を交換する「物々交換モデル」について説明しました。横井助教は、このモデルのアルゴリズムとして、各参加者がどんな希望順位を持っているときでも安定な割り当て(コア配分)を見つけることができる「Top Trading Cycle(TTC)アルゴリズム」を挙げ、物々交換の理論がアメリカやイギリスでの腎移植ネットワークに応用されていることを紹介しました。

 しかし、現実社会には「医師の専門性を考慮してバランス良く配置したい」「都市部への医師の集約を防ぎたい」「割り当て人数に下限を設けたい」などさまざまな制約があり、これまでの理論やモデルでは対処しきれない問題がたくさんあります。そこで、横井助教は、これまでのマッチング理論を発展させ、このような制約の入った問題を解く研究に取り組んでいます。横井助教は自身の研究成果として、制約が、ある種の良い性質を持つときには高速に計算ができることや、安定マッチングが存在しない場合には、安定性の条件を緩和することで公平性の高いマッチングが可能になり得ることを説明しました。

また、就職活動マッチングのように、各参加者が逐次的に意志決定を迫られる動的で無統制なマッチングモデルがあります。これに対し横井助教は、「参加者がどのような選好順序を持つときも、均衡マッチング(全求職者が最適戦略に従った際に得られるマッチング)が安定マッチングとなるようなオファー順を効率的に設計できる」という自身の研究成果を紹介しました。しかしこれは現実の要素を抜いて抽象化したモデルであり、まだ応用には遠いため、「今後はよりリアリティのある問題設定に広げていく必要がある」と話し、講義を締めくくりました。

参加者からは、「マッチングにアルゴリズムがあるということに驚いた」「マッチングアルゴリズムが実際の社会に活用されていると知って面白かった」「実際の業務に活用できそうだと思った」などの感想が寄せられました。

次回は、9月10日(火)18時30分から、「驚き!3Dセンシング-進化するコンピュータの眼-」と題して、コンテンツ科学研究系 池畑 諭 助教が講義します。最先端の3Dセンシング技術にご注目ください。

詳細、お申し込みは、下記ページをご覧ください。
https://www.nii.ac.jp/event/shimin/
多くの方々のご参加をお待ちしております!

report_2019-1-2.jpgreport_2019-1-3.jpg

shimin 2019-report_1 page3808

注目コンテンツ / SPECIAL