| 大会名称 |
|---|
| 2022年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2022 |
| 発行日 |
| 2022-08-30 |
| セッション番号 |
| 1a |
| セッション名 |
| アルゴリズム [選奨セッション] |
| 講演日 |
| 2022/09/13 |
| 講演場所(会議室等) |
| 12棟-101教室 |
| 講演番号 |
| CA-002 |
| タイトル |
| オンライン割当における最小効用最大化 |
| 著者名 |
| 河瀬康志, 澄田範奈, |
| キーワード |
| 公平割当, オンライン最適化 |
| 抄録 |
| 逐次的に与えられる財をn人のエージェントに公平に割り当てる問題をオンライン公平割当問題という．本発表では，エージェント達の最小効用がなるべく大きな割当を求める公平割当問題を扱う．各エージェントは財に対して加法的な効用をもつとする．財の与えられ方として，独立同一分布モデルと敵対的モデルを扱い，それぞれのモデルでの漸近的競合比を明らかにする．独立同一分布モデルに対しては，漸近的にほぼ最適な割当を分布の情報なしに得ることができるアルゴリズムを提案する．敵対的モデルに対しては，漸近的競合比1/nをもつ多項式時間決定的オンラインアルゴリズムを構築し，この競合比は乱択を許しても最適であることも示す． |
| 本文pdf |
| PDF download (356.2KB) |