[2Yin-A] ポスター3

[2Yin-A-15] オンライン施設配置問題における最大累積コストの近似

〇太田 英佑¹、東藤 大樹¹ (1. 九州大学)

キーワード：

マルチエージェント、施設配置、メカニズムデザイン

施設配置問題は，すべての選択肢が単一の線分または区間に分布する静的なマルチエージェント意思決定の数理モデルである．
しかし，実際の状況では，このような意思決定は動的に行われ，エージェントの選好は時間とともに変化する可能性がある．本論文では，各エージェントが時間の経過とともに累積コストを最小化しようとする新しい状況を考慮し，すべてのエージェント間で最大累積コストを近似することに焦点を当てる．まず，オンラインアルゴリズムを提案し，2つの期間と3つのエージェントが存在する場合にオンライン最適であることを示す．次に，戦略的操作不可能性を満足するオンラインアルゴリズムを提案し，その最悪ケースのパフォーマンスを分析する．