情報処理学会 第88回全国大会

4D-06
最適輸送から見た譲渡可能効用マッチングの分析
○石川和磨,岩﨑 敦(電通大)
譲渡可能効用マッチング(または割当問題)とは、お互いにマッチすることで得られる余剰を金銭などを通じて分け合える状況を扱う枠組みである。この枠組みでは、誰と誰をマッチさせるかという組み合わせの決定と、余剰をどのように分けるかという決定を同時に行う。例えば、労働者をどの企業にいくらの給与でマッチさせるか、広告をどのウェブサイトにいくらで掲載するかなどの例がある。この譲渡可能効用マッチングは最適輸送の枠組みに帰着できることが知られており、実証研究への応用がいくつか行われている。本研究では、最適輸送の基本であるエントロピー正則化付き割当問題と、譲渡可能効用割当問題の解との関係を分析する。