情報の欠如した公平分割問題に対するアルゴリズム

本研究の目的は，不可分財を複数のエージェントに公平に割り当てるという公平分割問題において，財に対する効用（うれしさ）の情報が厳密には分からない状況にも対応できるアルゴリズム理論を構築することである．公平分割問題は社会の様々なところに現れるが，実用上は財や効用の情報が厳密には分からないことも多々あるため，本研究では情報が欠如した状況に対応するための理論を整備する．2022年度は主に，エージェントの財の価値の数値は分からないが価値の順序（選好）は分かる，という設定において，できるだけ公平な割当を求める問題に取り組んだ．特に，確率的な割当（財の集合の確率分布，くじのようなもの）に着目する．数値情報がわかっていても不可分財の割当では公平性と効率性（無駄がないこと）を両立することは一般に難しく，財を確率的に割り当てることは対応策のひとつである．既存研究では，割り当てに制約がない場合に，公平かつ効率的な割当を求めるメカニズムが提案されている．しかし，授業科目割当やシフト割当などを考えると，一般には各エージェントに割り当てられる財の集合に制約がありうる．既存研究のメカニズムを制約がある状況に適用しても，望ましい割当が求められるとは限らない．そこで本研究では制約のある場合に着目する．主結果は，(1) エージェントの人数，(2) 制約がマトロイドかどうか，(3) 制約がエージェント間で同じかどうか，(4) 選好が同じかどうか，について場合分けし，公平・効率的な割当が必ず存在するかどうかを解析したことである．また，望ましい割当が存在するケースに対しては，その割当を求めるメカニズムも提案した．この成果はプレプリントとして公開済みであり，国際会議でも採択されている．また，他にも公平分割問題に関する研究を行い，国際会議で発表予定である．さらに，前年度に行った研究を国際会議と国内学会で発表した．

本研究の目的は，不可分財を複数のエージェントに公平に割り当てるという公平分割問題において，財に対する効用（うれしさ）の情報が厳密には分からない状況にも対応できるアルゴリズム理論を構築することである．公平分割問題は社会の様々なところに現れるが，実用上は財や効用の情報が厳密には分からないことも多々あるため，本研究では情報が欠如した状況に対応するための理論を整備する．2022年度は主に，エージェントの財の価値の数値は分からないが価値の順序（選好）は分かる，という設定において，できるだけ公平な割当を求める問題に取り組んだ．特に，確率的な割当（財の集合の確率分布，くじのようなもの）に着目する．数値情報がわかっていても不可分財の割当では公平性と効率性（無駄がないこと）を両立することは一般に難しく，財を確率的に割り当てることは対応策のひとつである．既存研究では，割り当てに制約がない場合に，公平かつ効率的な割当を求めるメカニズムが提案されている．しかし，授業科目割当やシフト割当などを考えると，一般には各エージェントに割り当てられる財の集合に制約がありうる．既存研究のメカニズムを制約がある状況に適用しても，望ましい割当が求められるとは限らない．そこで本研究では制約のある場合に着目する．主結果は，(1) エージェントの人数，(2) 制約がマトロイドかどうか，(3) 制約がエージェント間で同じかどうか，(4) 選好が同じかどうか，について場合分けし，公平・効率的な割当が必ず存在するかどうかを解析したことである．また，望ましい割当が存在するケースに対しては，その割当を求めるメカニズムも提案した．この成果はプレプリントとして公開済みであり，国際会議でも採択されている．また，他にも公平分割問題に関する研究を行い，国際会議で発表予定である．さらに，前年度に行った研究を国際会議と国内学会で発表した．