FIT2022（第 21 回情報科学技術フォーラム）CA-002
オンライン割当における最小効用最大化

Online Max-min Fair Allocation
河瀬 康志1）

澄田 範奈2）

Yasushi Kawase Hanna Sumita

1 はじめにアリスとボブが 1 つずつ得られるお菓子を分け合う状
況を考えよう．お菓子が 1 つ得られるごとに，彼らのうち 1 人がお菓子を受け取り食べるとする．各お菓子をよ
り欲しがる方が食べることにすると，表 1 のように不公平な結果になってしまうかもしれない．各お菓子を交互に食べることにすると，表 2 のように非効率なものになってしまうかもしれない．では，どのようなルールならば公平性と効率性を両立することができるだろうか．
表 1 より欲しがる方が食べる場合の結果

1

2

3

4

5

6

⋯

アリスの嬉しさ 0.7
ボブの嬉しさ 0.5

1.0
0.1

0.8
0.7

0.9
0.2

0.7
0.6

0.8 ⋯
0.0 ⋯

表 2 交互に食べる場合の結果

1

2

3

4

5

6

⋯

アリスの嬉しさ 0.7
ボブの嬉しさ 0.5

1.0
0.1

0.8
0.7

0.9
0.2

0.7
0.6

0.8 ⋯
0.0 ⋯

財や資源を複数のエージェントに公平かつ効率的に割り当てる問題は，経済学の分野で基本的な問題のひとつとして研究されている．近年，不可分財の割当アルゴリ
ズムが組合せ最適化やアルゴリズム的ゲーム理論の分野で盛んに研究されている．基本的な問題設定では全ての財の情報が事前に与えられたもとで割当を決定するが，実際には事前に全ての情報が得られるとは限らない．例
えば臓器移植，寄付された食料の割当（フードバンク），
電気自転車の充電ステーションへの割当といった状況では，不可分財が逐次的に与えられ，与えられた財を速やかに割り当てる必要がある．そこで，本稿はこのような状況を動機として，逐次的に財が与えられるというオンライン環境下において，公平かつ効率的に不可分財を割り当てる問題を解析する．
エージェントの集合を 𝑁 = {1, 2, … , 𝑛}, 不可分財の集合を 𝑀 = {𝑒1 , 𝑒2 , … , 𝑒𝑚 } とする．各エージェント 𝑖 ∈ 𝑁
は，加法的価値関数 𝑣𝑖 ∶ 2𝑀 → ℝ+ をもつとする．財𝑒 ∈ 𝑀 に対するエージェントが感じる価値を並べたベク
トル (𝑣1 (𝑒), … , 𝑣𝑛 (𝑒)) を財 𝑒 の価値ベクトルと呼ぶ．割
当 𝐴 = (𝐴1 , … , 𝐴𝑛 ) とは，財集合 𝑀 の分割である．
本稿では，財が逐次的に与えられるもとで，最小効用min𝑖∈𝑁 𝑣𝑖 (𝐴𝑖 ) を最大にする割当 𝐴 を求める問題を扱う．
この min𝑖∈𝑁 𝑣𝑖 (𝐴𝑖 ) という値は，割当 𝐴 の平等主義的効用とも呼ばれる．財がひとつずつ与えられるもとで平等主義的効用を最大にする問題を，オンライン最大最小公

1） 東京大学
2） 東京工業大学

平割当問題 (online max-min fair allocation problem) と呼ぶ．ここで，与えられる財の総数や将来くる財の価値は，事前には未知であるとする．平等主義的効用が最大であるという意味での公平性は，割当の公平性と効率性を測る主要な概念のひとつであり，公平割当の分野で盛んに取り上げられている [3, 8, 10, 12, 14]．そのため，本稿で扱う問題は上で述べた実際の公平割当の問題を自然にモデル化したものであると言える．
本稿の目的は，上記のオンライン最大最小公平割当問
題に対するオンラインアルゴリズムの構築と，その性能を競合比という指標を用いて解析することである．競合比とは，オンラインアルゴリズムによる割当の平等主義
的効用と，財の情報が事前に既知だった場合に達成できる最良の割当での平等主義的効用（オフライン最適値）との比である．競合比には厳密競合比と漸近的競合比の二種類がある．厳密競合比は全ての入力列の中で最悪の状況に着目した指標であり，一方，漸近的競合比はオフ
ライン最適値が十分大きい入力列における最悪の状況に着目する．オフライン最適値が小さいときは，オフライ
ン最適値とアルゴリズムによる割当の平等主義的効用の差も小さいため，両者はほぼ同じと考えられる．そのため，オフライン最適値が十分大きい場合のアルゴリズムの性能が本質的に重要と考えることもでき，漸近的競合
比はその解析のための指標である．正確な定義は 2 節で述べる．

1.1 関連研究
オンライン最大最小公平割当問題において，エージェ
ントの価値関数が全て同じ（𝑣1 = ⋯ = 𝑣𝑛 ）場合は，ス
ケジューリングの分野においてオンライン機械カバー問
題 (online machine covering problem) として研究されてきた．ここで，エージェントは機械に対応し，効用は機械の負荷に対応する．この問題に対して，貪欲に財を割り当てるアルゴリズムは厳密競合比が 1/𝑛 であり決定的
アルゴリズムの中では最良であること [15]，さらに厳密
1競合比が 𝛺() の乱択アルゴリズムが存在するこ√𝑛 log 𝑛とが知られている [4]．
他の公平性や効率性の概念のもとでのオンライン公平
割当問題は近年盛んに研究されている．詳細は，サーベ
イ論文 [1] も参照されたい．例えば，Benade et al. [7] は最大の妬みを最小にする問題に対して，最大妬みが財の数に関して劣線形になる決定的オンラインアルゴリズムを構成した．彼らはまず一様ランダム割当が劣線形妬み
しか発生させないことを示し，ランダム割当を脱乱択化することで主結果を得ている．ただし，我々の設定とは異なり，彼らは財の数が既知としている．
割 当 の 最 小 効 用 最 大 化 問 題（本 稿 の 問 題 の オ フ ラ
イ ン 版）は，組 合 せ 最 適 化 の 分 野 で サ ン タ ク ロ ー ス
問題として知られている．この問題は，1/2 より良い近似比をもつ解を見つけることさえも NP 困難であ9
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）表 3 オンライン最大最小公平割当問題に対する本稿の主結果．各項目は最適オンラインアルゴリズムの競合比を表す．ただし，𝛩̃ は log の多項式を無視した記法である．

厳密競合比
漸近的競合比敵対的 (決定的)敵対的 (乱択)

未知 i.i.d.

0 (定理 7)1/𝑛𝛩(𝑛) (定理 2, 8)

1/𝑒𝛩(𝑛) (定理 2, 9)1/𝑒𝛩(𝑛) (定理 2, 9)

1/𝑛 (定理 3, 5)

1/𝑛 (定理 3, 5)

1 (定理 4)1 (定理 4)る [13]．Bansal and Sviridenko [5] は，各エージェント
𝑖 の各財 𝑒 への価値が 𝑣𝑖 (𝑒) ∈ {0, 𝑣(𝑒)} という場合に対して 𝛺(log log log 𝑛/ log log 𝑛) 近似アルゴリズムを提案した．その後，一般の場合に対する近似アルゴリズムも提案されている [3, 11]．

1.2 主結果
オンライン最大最小公平割当問題は基本的な問題であるが，異なる価値関数をもつエージェントが存在する場合の競合比解析はほとんど知られていなかった．
本研究の主結果は，財の入力モデル二種類に対して最適オンラインアルゴリズムの漸近的競合比を明らかにしたことである．入力モデルは敵対的モデルと未知独立同一分布モデル（i.i.d.）に着目する．敵対的モデルでは次に与えられる財が敵対的に選ばれ，未知独立同一分布モ
デルでは財の価値ベクトルが何らかの確率分布に従って生成される．加えて，最適オンラインアルゴリズムのもつ厳密競合比の解析も行っている．具体的な結果は表 3にまとめる．本研究では最適オンラインアルゴリズムの競合比の上限と下限を示しており，表 3 の各項目はその値を表す．特に，敵対的モデルにおいては最適な漸近的競合比 1/𝑛 をもつアルゴリズムを与える．このアルゴリ
ズムの出力は，各エージェントは全ての財を受け取った
場合の 1/𝑛 以上の利得を得られるという比例性と呼ばれる性質も満たすことも示す．比例性は公平割当の分野で主要な公平性のひとつである．さらに，独立同一分布モ
デルについては漸近的に最適な解を出力するアルゴリズ
ムを与える．以下で主結果の詳細を述べる．

1.2.1 敵対的モデル
敵対的モデルにおける主結果は，漸近的競合比 1/𝑛 をもつ多項式時間決定的アルゴリズムを構成したことである（定理 3）．また，この比は最良である，つまり任意のオンラインアルゴリズムの漸近的競合比は 1/𝑛 以下であることも示す（定理 5）．
こ の 結 果 を 得 る た め に ま ず，各 財 を 各 エ ー ジ ェ
ントに等確率で割り当てるというアルゴリズムに
着 目 す る．こ の ア ル ゴ リ ズ ム を Random と 呼 ぶ．
本 稿 で は，Random の 達 成 す る 平 等 主 義 的 効 用 は
Opt/𝑛 − 𝑂(√Opt log Opt) 以上であり，したがって漸近的競合比は 1/𝑛 以上であることを示す（定理 1）．ただし，Opt はオフライン最適値を表すとする．この結果により，Random と同じ性能保証をもつ決定的アルゴリ
ズムの存在性も成立する [6]．しかし，その決定的アル
ゴリズムの構成は自明ではない．
この決定的アルゴリズムの構成は，理論的に興味深いだけでなく，実用上も意義がある．乱択アルゴリズムにはその性質上，乱数の実現値によっては悪い出力を行
なってしまうという欠点がある．エージェントがリスク回避的な場合には，このような悪い出力が得られる可能̃

既知 i.i.d.
̃

性があることは問題である．Random と同程度の性能をもつ決定的アルゴリズムを構成できれば，常に出力に関する保証が与えられるので，この問題を解決できる．
本 稿 で は，新 し い 脱 乱 択 化 の ア イ デ ア を 用 い て，Random と同じ漸近的競合比をもつ多項式時間決定的
アルゴリズムを提案する（アルゴリズム 1, 定理 3）．単純な決定的アルゴリズムとして貪欲な選択やラウンドロ
ビン（順番に割り当てる方法）に基づくアルゴリズムが挙げられるが，これらは漸近的に性能が良くないことが観察できる．これらの方針の欠点は，割当を個数について極端に平等にする点である．
提案アルゴリズムは，エージェント間での譲り合いを模倣することにより，以下のように財を割り当てる．財が到着したとき，アルゴリズムは高い価値を感じている
エージェントに順番に財をもらう権利を与える．各エー
ジェントは，権利が与えられたとき財をもらうが，これまでの割当を考慮して権利を放棄することもある．これにより，提案アルゴリズムは割当が偏りすぎてしまうことを避けることができる．提案アルゴリズムは，財の総数や価値の上限の情報を用いずに理論的に最良の性能を達成できるという利点をもつ．また，提案アルゴリズムのアイデアはそれ自身興味深く，他の割当問題に対するアルゴリズム設計でも有用な技術となりうる．
加えて，提案アルゴリズムの出力は，すべてのエー
ジェントが各人の価値関数において総価値の 1/𝑛 以上の価値を（漸近的には）受け取るという性質も満たす．つまり，比例性も同時に達成する．
一方，任意の決定的アルゴリズムの厳密競合比は 0 であり（定理 7）
，最適乱択アルゴリズムの厳密競合比は1/𝑛𝛩(𝑛) であることも示す（定理 2, 8）．

1.2.2 未知/既知独立同一分布モデル
独立同一分布モデルに対する主結果は，漸近的にほぼ最適な割当を出力するオンラインアルゴリズムを提案することである．提案アルゴリズムは分布や財の数の情報を用いないシンプルなものである．与えられた財に対する各エージェントの価値を，これまでの割当に応じて指数的に価値を割り引き，この値が最も高いエージェントに財を割り当てる．割引因子の底を (1 − 𝜖/2) としたとき，上記のアルゴリズムが漸近的競合比 (1 − 𝜖) をもつことを示す（定理 4）．
ここで，提案アルゴリズムは Devanur et al. [9] のア
ルゴリズムと似たアイデアに基づくが，彼らの結果を適用して得られるものではないことに注意する．Devanur
et al. [9] は幅広い資源割当問題に適用可能な漸近的競合
比 (1 − 𝜖) のアルゴリズムを与えた．しかし，このアルゴリズムを本稿の設定で適用するためには 2 つの困難性がある．ひとつは，このアルゴリズムは最適値の期待値を推定するために財の数 𝑚 を利用しているが，本稿の設定では 𝑚 は未知であることである．もうひとつは，

10
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）[9] の設定では財の価値ベクトルが有限種類である（すなわち離散分布からサンプルされる）ことを仮定して，線形計画法を用いることによりアルゴリズムを設計していることである．一方，本稿の設定では，無限の種類の価値ベクトルを考慮する必要がある．我々の貢献は，これらの困難性を解決し，アルゴリズムを設計したことである．実際，我々は線形計画をアルゴリズムの設計に用いず，解析にのみ用いる．また，我々のアルゴリズムは
財の数 𝑚 などの情報を用いない．これにより，我々のアルゴリズムはとてもシンプルなものとなる．
加えて，我々のアルゴリズムは，エキスパート問題を解くために使われる乗算型重み更新法 [2] と解釈することもできる．しかしながら，エキスパート問題とオンライン最大最小公平割当問題は異なる目的をもつ問題であり，直接の関係はない．
厳密競合比に関しては，ある分布が存在して，任意のアルゴリズムの厳密競合比はエージェント数 𝑛 に対して指数的に小さくなりうることを示す（定理 9）.

する．漸近的競合比は，最適値が十分に大きい入力に対するアルゴリズムの性能を表していると解釈することができる．競合比の値は高々 1 であり，大きい値をもつアルゴリズムほど良い性能をもつということになる．定義より，ALG の漸近的競合比が少なくとも 𝜌 であるということは，任意の入力列 𝜎 について
𝔼[ALG(𝜎)] ≥ 𝜌 ⋅ OPT(𝜎) − 𝑜(OPT(𝜎)) であることを意味する．
独立同一分布モデルについては，財の数 𝑚 と価値ベ
クトルの分布 𝒟 によって定まる入力列の分布 𝑅(𝑚, 𝒟)を用いる．独立同一分布モデルにおける厳密競合比と漸近的競合比は以下のように定義される：

本稿の構成は以下の通りである．第 2 節では，モデルと競合比の正式な定義を与える．我々の主たるアルゴリ
ズム的な結果は，敵対的モデルに対するものは第 3 節，
独立同一分布モデルに対するものは第 4 節で与える．第5 と 6 節では，我々のアルゴリズムの最適性を示す不可能性を与える．最後に，第 7 節で，まとめと今後の課題について述べる．

3 敵対的モデルに対するアルゴリズム

2 準備

財を「公平」に割り当てる最も単純な方法の 1 つは，各財を一様ランダムに選んだエージェントに割り当てることである．この単純な乱択アルゴリズムを Randomと書くことにする．単純に一様ランダムに割り当てるよりも，高い価値を感じるエージェントに割り当てた方がよい性能をもつように思えるかもしれないが，そのような工夫をすると逆に，最悪のシナリオにおいては Random よりも性能が悪化してしまう．さらに，Random は，敵対的モデルにおいてほとんど最適なア
ルゴリズムであることを示す．
まず，Random の漸近的競合比は少なくとも 1/𝑛 であること示す．チェルノフ限界を用いることにより，より強い次の主張を示すことができる．

エージェントの集合を 𝑁 = {1, 2, … , 𝑛}, 不可分財の集合を 𝑀 = {𝑒1 , 𝑒2 , … , 𝑒𝑚 } とする．各エージェント 𝑖 ∈ 𝑁
は，各財に対する価値を表す関数 𝑣𝑖 ∶ 𝑀 → [0, 1] をもつ．簡単のため，断りがない限り各財の価値は [0, 1]に 正 規 化 さ れ て い る と す る．ま た，各 エ ー ジ ェ ン ト
は 財 に 対 し て 加 法 的 な 効 用 を も つ と す る．つ ま り，
エージェント 𝑖 の財の集合 𝑋 ⊆ 𝑀 に対する効用は，
𝑣𝑖 (𝑋) ≔ ∑𝑒∈𝑋 𝑣𝑖 (𝑒) と表されるとする．財 𝑒 ∈ 𝑀 に対するエージェントが感じる価値を並べたベクトル(𝑣1 (𝑒), … , 𝑣𝑛 (𝑒)) を財 𝑒 の価値ベクトルと呼ぶ．割当𝐴 = (𝐴1 , … , 𝐴𝑛 ) とは，財集合 𝑀 の分割であるとする．
すなわち，相異なる 𝑖, 𝑗 ∈ 𝑁 に対して，⋃𝑖 𝐴𝑖 = 𝑀 かつ
𝐴𝑖 ∩ 𝐴𝑗 = ∅ が成り立つものである．自然数 𝑘 に対して，[𝑘] ≔ {1, 2, … , 𝑘} と定義する．
オンラインアルゴリズムの性能を評価するために，
本稿では厳密競合比と漸近的競合比を用いる．入力列
𝜎 に対し，ALG(𝜎) と OPT(𝜎) をそれぞれオンラインア
ルゴリズム ALG によって得られる割当と最適オフライ
ンアルゴリズム OPT によって得られる割当における平等主義的効用を表すことにする．ここで，ALG が乱択
アルゴリズムの場合は，ALG(𝜎) は確率変数であるとする．このとき，敵対的モデルにおける厳密競合比と漸近的競合比は以下のように定義される：

inf
𝜍

𝔼[ALG(𝜎)],OPT(𝜎)

lim inf

inf

𝑡→∞ 𝜍∶ OPT(𝜍)=𝑡

𝔼[ALG(𝜎)].
OPT(𝜎)

ここで，乱択アルゴリズムに対する競合比は，オブリ
ビアスアドバーサリ1）を用いた定義であることに注意

𝔼𝜍∼𝑅(𝑚,𝒟) [ALG(𝜎)],𝑚,𝒟 𝔼𝜍∼𝑅(𝑚,𝒟) [OPT(𝜎)]inflim inf𝔼𝜍∼𝑅(𝑚,𝒟) [ALG(𝜎)]inf𝑡→∞ 𝑚,𝒟∶ 𝔼𝜍∼𝑅(𝑚,𝒟) [OPT(𝜍)]=𝑡 𝔼𝜍∼𝑅(𝑚,𝒟) [OPT(𝜎)].

本節では，敵対的モデルに対してアルゴリズムを与える．まず，漸近的競合比が 1/𝑛 である乱択アルゴリズム
を 3.1 節で与え，その後同じ競合比をもつ決定的アルゴリズムを 3.2 節で与える．

3.1 乱択アルゴリズム

定理 1 任意のアダプティブアドバーサリに対し，

𝔼[Random(𝜎)] ≥Opt− 𝑂 (√Opt ⋅ log Opt)𝑛

が 成 立 す る．こ こ で，𝜎 は ア ド バ ー サ リ に よ っ て
Random の確率的挙動に依存して選ばれた入力列であり，Opt ≔ 𝔼[OPT(𝜎)] である．
続いて，Random の厳密競合比について記す．厳密
競合比に対して，決定的アルゴリズムではほとんど何も得ることができないが，Random なら最適値の 1/𝑛𝑂(𝑛)を得ることはできる．直感的には，各エージェントが最適値の 𝛺(1/𝑛) の割合を得ることができる確率が 𝛺(1/𝑛)であることから示すことができる．
1） オブリビアスアドバーサリとは，最悪の入力列を乱択アルゴリズ
ムの確率的挙動に依存せずに選択することを意味する．一方，乱択
アルゴリズムの確率的挙動に依存して逐次的に入力列を生成することを許すモデルをアダプティブアドバーサリという．

11
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）定理 2 敵対的モデルにおいて，Random の厳密競合比は少なくとも 1/𝑛𝑂(𝑛) である．

3.2 脱乱択化
アダプティブアドバーサリに対する最適乱択アルゴリ
ズムの競合比は最適決定性アルゴリズムの競合比と等しいことが知られている [6]. この事実により，競合比がRandom と同じであるような決定性アルゴリズムの存在性が導ける．しかし，その証明は構成的ではないた
め，このような決定性アルゴリズムの実体は不明である．さらに，その決定性アルゴリズムの計算量という点には何も示唆していない．
Random を脱乱化する自然な方法はラウンドロビンをもちいることであろう．しかし，この方法は，第 1 節
で示した例（表 2）のような状況ではうまく割り当てているとは言えない．別のアプローチとして，最適値を推定するというものもあるが，これは敵対的モデルにおいては不可能である．
本研究でのアプローチは，財を複数のタイプに分類し，各タイプの財をバランスよくエージェントに割り当てるというものである．正数 𝜖 を固定し，ind(𝑥) = ⌊log1−𝜖 𝑥⌋と定義する．ただし，ind(0) = ∞ とする．財 𝑒 のタイプをベクトル (ind(𝑣1 (𝑒)), … , ind(𝑣𝑛 (𝑒))) によって定義する．ここで，ind(𝑥) が小さいほど価値 𝑥 は大きいことに注意する．エージェント数が 2 であれば，各タイプ毎に，財を評価値の高いエージェントを優先してラウンド
ロビンで割り当てることにより，漸近的競合比 (1 − 𝜖)/2を達成できる．しかし，一般には表 4 に示すように，タ
イプ毎に独立にラウンドロビンを行うと割当結果がとても偏ったものになりうる．そこで，このような偏りを回避するように工夫した方法を提案する．

ら，次はエージェント 𝑛 − 1 にチャンスを与える．エー
ジェント 𝑛 − 1 は，タイプが (𝑤1 , … , 𝑤𝑛−1 , 𝑤𝑛′ ) の形の財
（ただし 𝑤𝑛′ ≥ 𝑤𝑛−1 ）を過去の 𝑛−2 回について全てパスしていた場合 𝑒 を受け取り，そうでない場合はパスをする．ここで，𝑤𝑛′ の値は変動しても良いことに注意する．
例えば，𝑛 = 3 であり，エージェント 2 がタイプ (0, 1, 3)の財を一度パスしている状態で次にタイプ (0, 1, 4) の財が来たとする．評価値が最も低いエージェント 3 が最初に取得のチャンスを得るが，もしこの財をパスした場
合，次にエージェント 2 にチャンスが与えられる．エー
ジェント 2 はタイプ (0, 1, 𝑤3′ ) (𝑤3′ ≥ 1) の財を一度パスしているので，今回は財を受けとる．提案アルゴリズム
は同様の手続きを繰り返す．一般に，もしエージェント𝑛, 𝑛 − 1, … , 𝑖 + 1 がチャンスをパスしたら，アルゴリズ
ムはエージェント 𝑖 に財 𝑒 を得るチャンスを与える．
′
エージェント 𝑖 は，タイプが (𝑤1 , … , 𝑤𝑖 , 𝑤𝑖+1
, … , 𝑤𝑛′ ) の′′形の財（ただし 𝑤𝑖 ≤ 𝑤𝑖+1 ≤ ⋯ ≤ 𝑤𝑛 ）を過去の 𝑖 − 1 回について全てパスしていた場合 𝑒 を受け取り，そうでない場合はパスをする．ここで，財 𝑒 は最終的に誰かには割り当てられることに注意する．実際，エージェント 1
は，財 𝑒 を得るチャンスがもらえれば，必ず受け取る．
表 5 は，我々のアルゴリズムの実行例である．これらの手順をアルゴリズム 1 にまとめる．
アルゴリズム 1: 漸近的競合比 (1 − 𝜖)/𝑛 の決定的
アルゴリズム（敵対的モデル）
1

foreach 𝑒𝑗 ← 𝑒1 , 𝑒2 , … , 𝑒𝑚 do𝜏𝑗 を 𝑣𝜏(1) (𝑒𝑗 ) ≥ 𝑣𝜏(2) (𝑒𝑗 ) ≥ ⋯ ≥ 𝑣𝜏(𝑛) (𝑒𝑗 ) を満たす 𝑁 上の順列とする;

4

各 𝑖 ∈ 𝑁 について 𝑤𝑖 ← ind(𝑣𝜏𝑗(𝑖) (𝑒𝑗 )) とする;

56

表 4 偏りすぎた割当 (𝑛 = 3)

𝑗

1

2

3

4

5

6

⋯

ind(𝑣1 (𝑒𝑗 ))ind(𝑣2 (𝑒𝑗 ))ind(𝑣3 (𝑒𝑗 ))

0
1
2

0
2
1

0
1
3

0
3
1

0
1
4

0
4
1

⋯
⋯
⋯

各 𝑖 ∈ 𝑁 について 𝐴𝑖 ← ∅ とする;

3

2

7
8
9

𝑗

for 𝑖 ← 𝑛, 𝑛 − 1, … , 1 do𝑗𝑗𝑗𝑥(𝜏𝑗 ; 𝑤1 , 𝑤2 , … , 𝑤𝑖 ) を 1 増やす;𝑗𝑗𝑗

if 𝑥(𝜏𝑗 ; 𝑤1 , 𝑤2 , … , 𝑤𝑖 ) = 𝑖 then𝐴𝜏𝑗(𝑖) ← 𝐴𝜏𝑗(𝑖) ∪ {𝑒𝑗 }（𝜏𝑗 (𝑖) に 𝑒𝑗 を割り当て）;𝑗𝑗𝑗𝑥(𝜏𝑗 ; 𝑤1 , 𝑤2 … , 𝑤𝑖 ) ← 0;
Break;

1011

表 5 提案手法での割当 (𝑛 = 3)

𝑗

1

2

3

4

5

6

⋯

ind(𝑣1 (𝑒𝑗 ))ind(𝑣2 (𝑒𝑗 ))ind(𝑣3 (𝑒𝑗 ))

0
1
2

0
2
1

0
1
3

0
3
1

0
1
4

0
4
1

⋯
⋯
⋯

アルゴリズム 1 は多項式時間で動作する．さらに，以下の定理が成立する．

本研究で提案する新しい脱乱化手法の方針を述 べ る．現 在 割 当 を 決 め よ う と し て い る 財 𝑒 の タ
イプが (𝑤1 , 𝑤2 , … , 𝑤𝑛 ) であり，𝑤1 ≤ 𝑤2 ≤ ⋯ ≤ 𝑤𝑛
を 満 た す と 仮 定 す る．す る と ind の 定 義 よ り，
(1 − 𝜖)𝑤𝑖+1 < 𝑣𝑖 (𝑒) ≤ (1 − 𝜖)𝑤𝑖 が成立する．提案アルゴ
リズムは，最初に 𝑒 に対する評価値が最も低いエージェ
ント 𝑛 に対して，𝑒 を取得するチャンスを与える．エー
ジェント 𝑛 は，タイプ (𝑤1 , … , 𝑤𝑛 ) の財を過去の 𝑛−1 回について全てパスしていた場合 𝑒 を受け取り，そうでない場合はパスをする．もしエージェント 𝑛 がパスをした

定理 3 任意の正数 𝜖 < 1 と任意の入力列 𝜎 に対して，
𝜎 によって入力される財の集合を 𝑀 とすると，アルゴ
リズム 1 が出力する割当 𝐴 は，全ての 𝑖 ∈ 𝑁 について
1−𝜖
(𝑛!)2
𝑣𝑖 (𝐴𝑖 ) ≥𝑣𝑖 (𝑀) − 𝑛 を満たす．
𝑛𝜖

各 𝑖 ∈ 𝑁 について 𝑣𝑖 (𝑀) ≥ OPT(𝜎) が成立するため，
この定理からアルゴリズム 1 の漸近的競合比が (1 − 𝜖)/𝑛以上であるといえる．さらに，アルゴリズム 1 の出力は比例性もほとんど満たすことが言える．すなわち，アルゴリズムが出力する割当において，各エージェントは全ての財を得たときの (1 − 𝜖)/𝑛 倍の効用を得られることが保証できる．

12
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）こ の 定 理 を 示 す た め に，財 の 数 に 関 し て ほ ぼ バ
ラ ン ス の 取 れ た 割 当 が 得 ら れ る こ と を 示 す．順
列 𝜏 と添字 𝑘 ∈ [𝑛]，𝑤1 ≤ 𝑤2 ≤ ⋯ ≤ 𝑤𝑘 を満たす
𝑤 = (𝑤1 , 𝑤2 , … , 𝑤𝑘 ) ∈ ℤ𝑘+ について， 𝐸 𝜏,𝑘 (𝑤) = {𝑒𝑗 ∈𝑀 ∣ 𝜏𝑗 = 𝜏 and (𝑤1 , … , 𝑤𝑘 ) = 𝑤} と定義する．ただし，
𝜏𝑗 はアルゴリズム 1 で用いた順列である．各 𝑘 について，{𝐸 𝜏,𝑘 (𝑤)}𝜏,𝑤 は全ての財を分類するものになって
いる．
𝑗

𝑗

補題 1 任意の順列 𝜏 と添字 𝑘 ∈ [𝑛]，𝑤1 ≤ 𝑤2 ≤⋯ ≤ 𝑤𝑘 を満たす 𝑤 = (𝑤1 , 𝑤2 , … , 𝑤𝑘 ) ∈ ℤ𝑘+ について，|𝐴𝜏(𝑘) ∩ 𝐸 𝜏,𝑘 (𝑤)| ≥ |𝐸 𝜏,𝑘 (𝑤)|/𝑛 − 1 が成立する．
定理 3 の証明 エ ー ジ ェ ン ト 𝑖，順 列 𝜏，𝑖 = 𝜏(𝑘) とな る 添 字 𝑘 ∈ [𝑛]，𝑤1 ≤ 𝑤2 ≤ ⋯ ≤ 𝑤𝑘 を 満 た す
𝑤 = (𝑤1 , 𝑤2 , … , 𝑤𝑘 ) ∈ ℤ𝑘+ を固定する．ここで，(1 −𝜖)𝑤𝑘+1 < 𝑣𝑖 (𝑒) ≤ (1 − 𝜖)𝑤𝑘 が全ての 𝑒 ∈ 𝐸 𝜏,𝑘 (𝑤) について成立する．補題 1 より，と な る．こ こ で，最 後 か ら 2 番 目 の 変 形 は，任 意 の
1|𝑟| < 1 を満たす 𝑟 について= (1 + 𝑟 + 𝑟2 + ⋯)𝑛 =𝑛∞∑ℓ=0 (ℓ+𝑛−1
)𝑟ℓ =
𝑛−1

アルゴリズム 1 は，評価値の上限が 1 より大きい場
合にも（上限値の情報なしに）適用可能である．評価
値の上限値の値を 𝜂 = max𝑖′∈𝑁, 𝑒∈𝑀 𝑣𝑖′ (𝑒) と定義する．
𝜂 > 1 のとき，ind(𝜂) は負の整数となる．定理 3 の証明と同様に 𝑤𝑘 ≥ ind(𝜂) (∀𝑘 ∈ [𝑛]) を満たす全てのタイプ
𝑤 ∈ ℤ𝑛 について式 (1) を足し合わせると，各 𝑖 ∈ 𝑁 について

𝑣𝑖 (𝐴𝑖 ) = ∑ 𝑣𝑖 (𝐴𝑖 ∩ 𝐸 𝜏,𝑘 (𝑤))
𝜏,𝑘,𝑤

1−𝜖
∑ 𝑣 (𝐸 𝜏,𝑘 (𝑤))≥𝑛 𝜏,𝑘,𝑤 𝑖∞− ∑∑ (𝑤𝑘 + 1 − ind(𝜂))𝑘−1 (1 − 𝜖)𝑤𝑘+1

𝑤𝑘 +1≥ |𝐴𝑖 ∩ 𝐸 (𝑤)| ⋅ (1 − 𝜖)1
≥ ( |𝐸 𝜏,𝑘 (𝑤)| − 1) ⋅ (1 − 𝜖)𝑤𝑘+1
𝑛1−𝜖=⋅ |𝐸 𝜏,𝑘 (𝑤)|(1 − 𝜖)𝑤𝑘 − (1 − 𝜖)𝑤𝑘+1𝑛1−𝜖≥𝑣 (𝐸𝜏,𝑘 (𝑤)) − (1 − 𝜖)𝑤𝑘+1
(1)
𝑛 𝑖
′
が成立する．不等式 (1) を，𝑤1′ ≤ ⋯ ≤ 𝑤𝑘−1
≤ 𝑤𝑘 を満′′′たす全ての 𝑤 = (𝑤1 , … , 𝑤𝑘−1 , 𝑤𝑘 ) について足し合わせると，∑𝑣𝑖 (𝐴𝑖 ∩ 𝐸 𝜏,𝑘 (𝑤′ ))𝑤′

1−𝜖𝑣 (𝐸 𝜏,𝑘 (𝑤′ )) − (1 − 𝜖)𝑤𝑘+1 )
𝑛 𝑖
𝑤′
1−𝜖
∑ 𝑣 (𝐸𝜏,𝑘 (𝑤′ )) − (𝑤𝑘 + 1)𝑘−1 (1 − 𝜖)𝑤𝑘+1≥
𝑛 𝑤′ 𝑖≥ ∑(が成立する．最後に 𝜏, 𝑘, 𝑤 の全てについて足し合わせると，𝑣𝑖 (𝐴𝑖 ) = ∑ 𝑣𝑖 (𝐴𝑖 ∩ 𝐸 𝜏,𝑘 (𝑤))
𝜏,𝑘,𝑤

1−𝜖
∑ 𝑣 (𝐸 𝜏,𝑘 (𝑤))𝑛 𝜏,𝑘,𝑤 𝑖∞∑∑ (𝑤𝑘 + 1)𝑘−1 (1 − 𝜖)𝑤𝑘+1

𝑘∈[𝑛] 𝜏∶ 𝜏(𝑖)=𝑘 𝑤𝑘 =0∞

1−𝜖≥𝑣 (𝑀) − 𝑛! ⋅ ∑ (ℓ + 1)𝑛−1 (1 − 𝜖)ℓ+1
𝑛 𝑖
ℓ=0
1−𝜖
≥
𝑣 (𝑀)
𝑛 𝑖
∞

− 𝑛! ⋅ ∑ (ℓ + 1)(ℓ + 2) ⋯ (ℓ + 𝑛 − 1)(1 − 𝜖)ℓ+1ℓ=0

1−𝜖
𝑛! ⋅ (𝑛 − 1)!
𝑣 (𝑀) −⋅ (1 − 𝜖)
𝑛 𝑖
𝜖𝑛
2
1−𝜖
(𝑛!)
≥
𝑣 (𝑀) − 𝑛
𝑛 𝑖
𝜖
=

∑

𝑘∈[𝑛] 𝜏∶ 𝜏(𝑖)=𝑘 𝑤𝑘 =ind(𝜂)

𝜏,𝑘

− ∑

(𝑛−1)!

(1−𝑟)∞⋅∑ℓ=0 (ℓ+1)(ℓ+2) ⋯ (ℓ+𝑛−1)𝑟ℓという事実を用いている．

𝑣𝑖 (𝐴𝑖 ∩ 𝐸 𝜏,𝑘 (𝑤))

≥

1

≥

1−𝜖
𝑣 (𝑀)
𝑛 𝑖
∞

− 𝑛! ⋅ ∑ (ℓ + 1)𝑛−1 (1 − 𝜖)ℓ ⋅ (1 − 𝜖)ind(𝜂)+1
ℓ=0

1−𝜖
(𝑛!)2
≥
𝑣𝑖 (𝑀) − 𝑛 ⋅ 𝜂𝑛𝜖が成立する．この評価は 𝜂 ≤ 1 の場合にも定理 3 よりも良い性能保証を与えるため，有用である．

4 独立同一分布モデルに対するアルゴ
リズム
本節では，各財の価値ベクトル 𝑣 が独立に未知確率分
布 𝒟 に従って決まるという未知独立同一分布モデルを扱う．ここで，分布 𝒟 と財の数 𝑚 の情報はどちらも未知とする．敵対的モデルにおける定理 2 より，独立同一分布モデルにおいても Random が少なくとも 1/𝑛𝑂(𝑛)の厳密競合比をもつ．以下では，漸近的競合比に着目す
る．本研究では，このモデルに対して漸近的にほぼ最適でシンプルなアルゴリズムを与える．
ここでも，ラウンドロビンでは本研究の結果を得ることが難しい．エージェント数は 𝑛 = 2 であり，財の価値ベクトルは確率 1 で (1, 1/2) であるとする．財の数が𝑚 = 6ℓ （ℓ は正の整数）のとき，財をエージェント 2 に
4ℓ 個割り当てることにより最適値 2ℓ を達成出来るが，ラウンドロビンではそれぞれのエージェントに 3ℓ 個割
り当てることになるため平等主義的効用は 3ℓ/2 にしかならない．
一方，本研究の提案アルゴリズムは以下のように割当を決定する．𝜖 を十分小さい正の数とする．新たな財 𝑒𝑗 が与えられた時，提案アルゴリズムは各エージェ
ント 𝑖 にとっての価値 𝑣𝑖 (𝑒𝑗 ) を仮想的に (1 − 𝜖)𝑣𝑖(𝐴𝑖) 倍に割り引く．ここで，𝐴𝑖 は，エージェント 𝑖 にこれまで割り当てられた財の集合を表すとする．アルゴ
リズムは財 𝑒𝑗 を割引後の価値が最大のエージェント
𝑖(𝑗) ∈ arg max𝑖 (1 − 𝜖)𝑣𝑖(𝐴𝑖) 𝑣𝑖 (𝑒𝑗 ) に割り当てる．この割引

13
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）により，現在得ている効用が少ないエージェントの優先度を高めることができる．詳しくはアルゴリズム 2 にまとめる．

用は min𝑖∈𝑁 ∑𝑗=1 𝑋𝑖,𝑗 となる．ブールの不等式とマルコ𝑚フの不等式を用いると，𝑚

Pr [min ∑ 𝑋𝑖,𝑗 ≤ (1 − 𝜖)Opt]

アルゴリズム 2: 漸近的競合比 (1 − 2𝜖) の決定的
アルゴリズム（未知独立同一分布モデル）
1

𝑖∈𝑁

𝑗=1
𝑚

≤ ∑ Pr [ ∑ 𝑋𝑖,𝑗 ≤ (1 − 𝜖)Opt]

各 𝑖 ∈ 𝑁 について 𝐴𝑖 ← ∅ とする;

𝑖∈𝑁

foreach 𝑒𝑗 ← 𝑒1 , 𝑒2 , … , 𝑒𝑚 do
3𝑖(𝑗) ∈ arg max𝑖 ((1 − 𝜖)𝑣𝑖(𝐴𝑖) ⋅ 𝑣𝑖 (𝑒𝑗 )) を選択;

𝑗=1

2

4

𝑚

= ∑ Pr [(1 − 𝜖)∑𝑗=1 𝑋𝑖,𝑗≥ (1 − 𝜖)(1−𝜖)Opt ]𝑖∈𝑁𝐴𝑖(𝑗) ← 𝐴𝑖(𝑗) ∪ {𝑒𝑗 } （𝑖(𝑗) に 𝑒𝑗 を割り当て）;𝑚≤ ∑ 𝔼 [(1 − 𝜖)∑𝑗=1 𝑋𝑖,𝑗] /(1 − 𝜖)(1−𝜖)Opt

(2)

𝑖∈𝑁

定理 4 任意の正数 𝜖 < 1 と，期待最適値が少なくとも
2𝑛log である任意の 𝑚, 𝒟 に対し，アルゴリズム 2 の2𝜖が成立する．定理 4 を示すには，式 (2) の最右辺の値が十分小さいことを示す．各 𝑠 = 0, 1, … , 𝑚 に対し，ポテ
ンシャル 𝛷(𝑠) を以下のように定義する：

𝜖

出力の期待平等主義的効用は期待最適値の (1 − 2𝜖) 倍以上である．

𝜖Opt 𝑚−𝑠.
)𝑚𝑠𝛷(𝑠) ≔ ∑ 𝔼 [(1 − 𝜖)∑𝑗=1 𝑋𝑖,𝑗] ⋅ (1 −𝑖∈𝑁

入力の実現列が 𝜎 であるとき，最適値 OPT(𝜎) は次の
整数計画問題の最適値となる：

max 𝜆
𝑚
𝜍
s.t. 𝜆 ≤ ∑𝑗=1 𝑣𝑖𝑗⋅ 𝑥𝑖𝑗 (∀𝑖 ∈ 𝑁),(IP𝜍 )(∀𝑗 ∈ [𝑚]),∑𝑖∈𝑁 𝑥𝑖𝑗 = 1
𝑥𝑖𝑗 ∈ {0, 1}(∀𝑖 ∈ 𝑁, ∀𝑗 ∈ [𝑚]).
𝜍𝜍
ここで，𝑣𝑗𝜍 = (𝑣1𝑗
, … , 𝑣𝑛𝑗
) は入力列 𝜎 の 𝑗 番目の財に対する価値ベクトルを表し，変数 𝑥𝑖𝑗 は，エージェント 𝑖
が 𝑗 番目の財を受け取るかどうかを表す．以後，期待最適値 𝔼[OPT(𝜎)] を Opt で表すことにする．Opt = 0 であれば任意のアルゴリズムは最適値 0 を達成できるので，一般性を失わず，Opt > 0 を仮定する．
定理 4 の証明では，分布 𝒟 が有限個の価値ベクトル上の離散分布である場合に定理を示し，その証明を一般の場合に拡張する．分布 𝒟 に対して，supp(𝒟) を正の確率をもつ価値ベクトルの集合と定義する．まず，| supp(𝒟)| が有限とする．全てが期待値に従って発生するような「期待問題例」についての線形計画問題

max 𝜆s.t. 𝜆 ≤ ∑ 𝑚 ⋅ Pr [𝑈 = 𝑢]𝑢𝑖 𝑥𝑖ᵆᵆ∈supp(𝒟)𝑈∼𝒟

ここで，(2) の最右辺は 𝛷(𝑚)/(1 − 𝜖)(1−𝜖)Opt に等しい．
このとき，以下の 2 つの補題が導ける．
補題 3 𝛷(𝑠) は 𝑠 に関して単調減少である．
補題 4 𝛷(0)/(1 − 𝜖)(1−𝜖)Opt ≤ 𝑛 ⋅ 𝑒

𝜖2
Opt
2

.

定理 4 の証明 まず 𝒟 が有限の価値ベクトル上の離散確率分布の場合に着目する．補題 3, 4 を式 (2) に適用す𝑚
ることにより，確率 Pr[min𝑖∈𝑁 ∑𝑗=1 𝑋𝑖,𝑗 ≤ (1 − 𝜖)Opt]
は高々

𝛷(𝑚)
(1 − 𝜖)(1−𝜖)Opt≤

𝛷(0)(1 − 𝜖)(1−𝜖)Opt

≤𝑛⋅𝑒

−

𝜖2
Opt
2

であることが言える．さらに補題 2 より，平等主義的効𝑚
用の期待値 𝔼[min𝑖∈𝑁 ∑𝑗=1 𝑋𝑖,𝑗 ] は少なくとも(1−𝜖)⋅(1−𝑛⋅𝑒

−

𝜖2
Opt
2

)⋅Opt ≥ (1−𝜖)⋅(1−𝑛⋅𝑒である．よって，Opt ≥(∀𝑖 ∈ 𝑁),

2
𝜖2

log

𝑛
𝜖

𝔼[min ∑ 𝑋𝑖,𝑗 ] ≥ (1 − 𝜖) ⋅ (1 − 𝑛 ⋅ 𝑒
𝑖∈𝑁

−

𝜖2
Opt
2

)⋅Opt

の仮定より，𝑚(LP)∑𝑖∈𝑁 𝑥𝑖ᵆ = 1 (∀𝑢 ∈ supp(𝒟)),𝑥𝑖ᵆ ≥ 0 (∀𝑖 ∈ 𝑁, ∀𝑢 ∈ supp(𝒟))の最適値を Opt で表す．| supp(𝒟)| が有限なので，この線形計画問題は有限個の変数と有限個の制約から構成される．(IP𝜍 ) の最適解の期待値から (LP) の実行可能解を構成することで Opt は Opt 以上であることを示せる．

−

−

𝜖2
Opt
2

) ⋅ Opt

𝑗=1≥ (1 − 𝜖) ⋅ (1 − 𝜖)Opt ≥ (1 − 2𝜖)Optが得られる．
以後，この証明を一般の場合に拡張する．𝛿 を 1 より小さい正の値とする．実数 𝑥 ∈ [0, 1] に対し，⌈log1−𝛿 𝑥⌉ if 𝑥 ≥ 𝛿 ⋅ Opt/𝑚,
𝜅(𝑥) = {∞if 𝑥 < 𝛿 ⋅ Opt/𝑚

補題 2 Opt ≥ Opt.
正数 𝜖 > 0 を固定する．アルゴリズム 2 において，エージェント 𝑖 が 𝑗 番目の財から得る利得を表す確率変数を，𝑋𝑖,𝑗 とする． すなわち，𝑖 が 𝑗 番目の財 𝑒𝑗 を受け取れば 𝑋𝑖,𝑗 = 𝑣𝑖 (𝑒𝑗 ) であり，そうでない場合は 𝑋𝑖,𝑗 = 0
である．アルゴリズム 2 によって得られる平等主義的効と定義する．ここで，𝜅(𝑥) は有限集合 {0, 1, … , ⌈log1−𝛿 (𝛿⋅Opt/𝑚)⌉} ∪ {∞} の要素であり，

14
第 1 分冊𝑥 ≥ (1 − 𝛿)𝜅(𝑥) ≥ (1 − 𝛿)𝑥 ≥ (1 − 𝛿)𝑥 − 𝛿 ⋅

Opt
(3)
𝑚

Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）を満たす．分布 𝒟 (𝛿) を，𝒟 において各価値ベクトル
𝑢 を ((1 − 𝛿)𝜅(ᵆ𝑖) )𝑖∈𝑁 に修正したものとする．ここで，supp(𝒟(𝛿) ) のサイズは高々 (⌈log1−𝛿 (𝛿Opt/𝑚)⌉ + 2)𝑛 と有限である．分布 𝒟 (𝛿) に対する線形計画問題 (LP) の最(𝛿)

適値を Opt とする．
上で述べた，supp(𝒟) のサイズが有限である場合の証明と同様の議論により，𝑚

𝔼 [min ∑ 𝑋𝑖,𝑗 ] ≥ (1 − 𝜖) ⋅ (1 − 𝑛 ⋅ 𝑒
𝑖∈𝑁

−

(𝛿)
𝜖2
Opt
2

(𝛿)

)Opt

(4)

𝑗=1
(𝛿)

が 導 け る．さ ら に，式 (3) と 補 題 2 よ り，Opt≥(1 − 𝛿)Opt − 𝛿 ⋅ Opt ≥ (1 − 2𝛿)Opt が成立する．
不等式 (4) は任意の整数 𝛿 (< 1) に対して成立するため，𝛿 → 0 の極限を考えると，𝑚

𝔼 [min ∑ 𝑋𝑖,𝑗 ] ≥ (1 − 𝜖) ⋅ (1 − 𝑛 ⋅ 𝑒
𝑖∈𝑁

−

𝜖2
Opt
2

) ⋅ Opt𝑗=1

定理 5 敵対的モデルに対して，任意の乱択オンライン
アルゴリズムの漸近的競合比は 1/𝑛 以下である．
決定性オンラインアルゴリズムについては，より強い不可能性を示すことができる．この不可能性により，任意の正数 𝜖 (< 1/10) に対しある入力列 𝜎 が存在し，ALG(𝜎) ≤1𝑛1

OPT(𝜎) − 𝛺((OPT(𝜎)) 2−𝜖) となることが示

せる．証明では，Benade et al. [7] によるアイデアを応用することにより敵対的な入力列を構築する．この入力列の構成法により，過度にバランスした割当を求めるア
ルゴリズムでは，漸近的競合比が 1/𝑛 よりも悪くなってしまうことも示唆される．
定理 6 エージェント数 𝑛 は 2 以上であると仮定す
る．敵 対 的 モ デ ル に お い て，任 意 の 決 定 性 ア ル ゴ リ
ズム ALG，実数 𝑐 > 0，実数 𝑟 ∈ (1/2, 1) について，
ある入力列 𝜎 が存在し，ALG(𝜎) ≤ OPT(𝜎)/𝑛 − 𝑐 とOPT(𝜎) = 𝑂(𝑐3−𝑟 ) が成立する．

≥ (1 − 𝜖) ⋅ (1 − 𝜖)Opt

5.2 厳密競合比≥ (1 − 2𝜖)Optが満たされる．したがって，定理は示された．
補 足 と し て，ア ル ゴ リ ズ ム 2 は，財 の 価 値 が 1以下という仮定がなくても動作可能であることを
述 べ る．財 の 価 値 の 上 界 を 𝜂 と し，各 エ ー ジ ェ ン
ト 𝑖 ∈ 𝑁 と財 𝑒 ∈ 𝑀 に対し 𝑣𝑖̂ (𝑒) = 𝑣𝑖 (𝑒)/𝜂 と定義する．すると，(1 − 𝜖)̂ = (1 − 𝜖)𝜂 を満たすような正数𝜖 ̂ を考えることにより，アルゴリズム 2 は各財 𝑒𝑗 を
(𝑗−1)

arg max𝑖∈𝑁 (1 − 𝜖)̂ 𝑣𝑖̂ (𝐴𝑖 ) ⋅ 𝑣𝑖̂ (𝑒𝑗 ) に含まれるエージェン
トに割り当てるものだと解釈できる．よって，期待最適2𝑛値が少なくとも 𝜂 ⋅ 2 log である時，アルゴリズム 2 の𝜖̂𝜖̂

出力の期待平等主義的効用は期待最適値の (1 − 2𝜖)̂ 倍以上となる．この議論を 𝜂 < 1 の場合に用いると，定理 4
より良い性能保証を与えることもできる．
また，期待最適値 Opt の値があらかじめ与えられるセ
ミオンライン設定では，𝜖 = 2

log Optと設定することに√ Optより，アルゴリズム 2 で達成される期待平等主義的効用𝑚
は 𝔼[min𝑖 ∑𝑗=1 𝑋𝑖,𝑗 ] = Opt − 𝑂(√Opt log Opt) であることを保証できる．また，財の数 𝑚 があらかじめ与えられているならば，Opt ≤ 𝑚/𝑛 であることから，𝜖 = 2√

log 𝑚
𝑚

と設定したアルゴリズム 2 で達成される期待平等主義的𝑚
効用は 𝔼[min𝑖 ∑𝑗=1 𝑋𝑖,𝑗 ] = Opt − 𝑂(√𝑚 log 𝑚) となることを保証できる．

5 敵対的モデルにおける不可能性
この節では，敵対的モデルにおける競合比の上界を与える．

5.1 漸近的競合比
敵対的モデルにおける漸近的競合比の上界は 1/𝑛 であり，Random は漸近的競合比の意味で最適なアルゴリ
ズムであることを簡単に示すことができる．

続いて，厳密競合比の上界を議論する．まず，どの決定性アルゴリズムを用いても厳密競合比が 0 になることが言える．
定理 7 敵対的モデルにおいてエージェント数 𝑛 が 2 以上の場合，任意の決定性アルゴリズムの厳密競合比は 0である．
証明

任 意 の 決 定 性 ア ル ゴ リ ズ ム ALG に つ い て，ALG(𝜎) = 0 かつ OPT(𝜎) > 0 となる入力列 𝜎 が存在することを示す．
1 つ目の財 𝑒1 は，どのエージェントにとっても価値が 1 であるとし，ALG はエージェント 𝑘 ∈ 𝑁 に 𝑒1 を割り当てたとする．一般性を失わず，𝑘 ≠ 1 と仮定する．
続く 𝑛 − 1 個の各財 𝑒𝑗 (𝑗 = 2, 3, … , 𝑛) について，エージェント 𝑗 にとって価値は 1 であり，その他のエージェ
ントにとっては価値が 0 であるとする．すると，この𝑛 個の財からなる入力列 𝜎 について，ALG(𝜎) = 0 かつ
OPT(𝜎) = 1 となるので，厳密競合比は 0 となる．
乱択アルゴリズムを用いると正の厳密競合比を達成することができるが，エージェント数に対し指数的に小さい値（1/𝑛! = 1/𝑛𝛩(𝑛) ）しか達成できないことが言える．証明には Yao の原理を用いる．この上界により，Random は厳密競合比の意味でほぼ最適であると言える．
定理 8 敵対的モデルにおいて，任意の乱択アルゴリズ
ムの厳密競合比は高々 1/𝑛! である．

6 独立同一分布モデルにおける不可能性
独立同一分布モデルにおける競合比の上界を与える．
4 節において漸近的競合比 (1 − 𝑂(𝜖)) をもつ（つまりほぼ最適な割当を出力する）アルゴリズムを与えたため，

15
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）厳密競合比のみ解析する．アルゴリズムが入力の分布と財の数があらかじめ与えられていたとしても，厳密競合
比はエージェント数 𝑛 に対して指数的に小さくなる．
定理 9 価値ベクトルのある分布と財の数から定まる独立同一分布モデルの入力に対し，任意のアルゴリズムの厳密競合比は高々 1/𝑒𝛺(𝑛) である．
証明では，財の数 𝑚 が 𝑛 に等しく，入力される価値ベクトルが以下の分布に従う問題例を用いる：• 各 𝑖 ∈ [𝑛] について，𝜒𝑖 である確率が

2
3𝑛

，

• 各 𝑘 ∈ [𝑛/2] について，𝜒2𝑘−1 + 𝜒2𝑘 である確率が2．
3𝑛ただし，𝜒𝑖 は第 𝑖 成分が 1 であるような単位ベクトルである．

7 まとめと今後の課題
本稿では，オンライン最大最小公平割当問題について
敵対的モデルと独立同一分布モデルそれぞれの厳密競合
比及び漸近的競合比を解析した．特に，敵対的モデルに1−𝜖
おいては，漸近的競合比がとなる決定性アルゴリズ
𝑛ムを与えた．また，独立同一分布モデルにおいては，任意の正数 𝜖 に対し漸近的競合比が 1 − 𝜖 となる決定性ア
ルゴリズムを構築した．
本研究のモデルでは財が与えられた時点で（割当前に）各エージェントにとっての価値が分かるが，実際には割当後に価値が明らかになるモデルも考えられる．
しかし，この設定は制限が強い．実際，独立同一分布
モデルにおいて，各 𝑖 ∈ 𝑁 に対して確率 1/𝑛 で第 𝑖 成
分にのみ 1 をもつ単位ベクトル 𝜒𝑖 をとる場合は漸近的競合比は高々 1/𝑛 となる．さらに，敵対的モデルでは，エージェント 𝑖 に割り当てた財 𝑒 の価値ベクトルが1 − (1 − 𝜖)𝜒𝑖 （ただし 𝜖 > 0）となる場合，漸近的競合比
は高々 𝜖 となる．
最後に，今後の研究の方向性について議論する．本研
究の提案アルゴリズムは漸近的競合比の意味では最適であるが，定数項部分を改善できるかは今後の課題である．また，他の入力モデルであるランダム順序モデルに対するアルゴリズムの設計が挙げられる．さらに，敵対的モデルと独立同一分布モデルの両方に対して同時に良い競合比をもつアルゴリズムの設計も重要な課題である．
謝辞
本研究は以下の助成を受けたものである．株式会社
メルカリとインクルーシブ工学連携研究機構との共同研究である価値交換工学，JSPS 科研費 20K19739， JST
さきがけ JP-MJPR2122 （河瀬）．JSPS 科研費 17K12646,
21K17708 （澄田）．

参考文献[1]Martin Aleksandrov and Toby Walsh. Online Fair Division: A Survey. In Proceedings of the AAAI Con-

ference on Artificial Intelligence, volume 34, pages
13557–13562, 2020.
[2]Sanjeev Arora, Elad Hazan, and Satyen Kale. The
multiplicative weights update method: a meta algorithm and applications. Theory of Computing, 8(1):121–164, 2012.
[3]Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing, 39(7):2970–2989, 2010.
[4]Yossi Azar and Leah Epstein. On-line machine covering. Journal of Scheduling, 1(2):67–77, 1998.
[5]Nikhil Bansal and Maxim Sviridenko. The Santa
Claus problem. In Proceedings of Aannual ACM symposium on Theory of Computing, pages 31–40, 2006.
[6]S Ben-David, A Borodin, R Karp, G Tardos, andA Wigderson. On the power of randomization in online algorithms. Algorithmica, 11(1):2–14, 1994.
[7]Gerdus Benade, Aleksandr M Kazachkov, Ariel D
Procaccia, and Christos-Alexandros Psomas. How
to Make Envy Vanish Over Time. In Proceedingsof ACM Conference on Economics and Computation,
pages 593–610, 2018.
[8]Sylvain Bouveret, Yann Chevaleyre, and Nicolas
Maudet. Fair allocation of indivisible goods. In Felix
Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang,and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 12, page 284 –310.
Cambridge University Press, 2016.
[9]Nikhil R Devanur, Kamal Jain, BalasubramanianSivan, and Christopher A Wilkens. Near optimal
online algorithms and fast approximation algorithms
for resource allocation problems. Journal of the ACM,
66(1), 2019.
[10]Daniel Golovin. Max-min fair allocation of indivisible goods. Technical Report CMU-CS-05-144,
Carnegie Mellon University, June 2005.
[11]Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of the Lovász local
lemma. Journal of the ACM, 58(6):28:1–28:28, 2011.
[12]Yasushi Kawase and Hanna Sumita. On the max-min
fair stochastic allocation of indivisible goods. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2070–2078, 2020.
[13]Jan Karel Lenstra, David B Shmoys, and Éva Tardos.
Approximation algorithms for scheduling unrelatedparallel machines. Mathematical programming, 46(1):259–271, 1990.
[14]Yunpeng Li, Changjie He, Yichuan Jiang, Weiwei
Wu, Jiuchuan Jiang, Wei Zhang, and Hui Fan. Maxmin fair allocation for resources with hybrid divisibilities. Expert Systems with Applications, 124:325–340,
2019.
[15]Gerhard J. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters,
20(4):149–154, may 1997.

16
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.