Extension of Additive Valuations to General Valuations on the Existence of EFX

概要

論文内容の要約
論文題目: Extension of Additive Valuations to General

Valuations on the Existence of EFX∗
(EFX 配分の存在に関する非加法的評価関数への拡張)
馬原 凌河

古典的な公平配分理論では，金銭や土地などに代表される可分財についての研究が中心であっ
た．しかし，現実の問題においては，財の可分性が仮定できない場合が自然に生じうる．実際，美
術品の相続，公的宿舎の割当，講義の座席割当など多数の応用例があり，不可分財の公平配分問
題は基礎的かつ重要性の高い研究課題である．本論文では，エージェント集合 N = {1, 2, . . . , n},
不可分財集合 (アイテム集合) M = {g1 , g2 , . . . , gm }, 各エージェント i の評価関数 vi : 2M → R≥0
が与えられたときの不可分財の公平配分問題について考察している．ここで，各評価関数 vi に
ついて，(i) vi (∅) = 0 および (ii) 任意の S, T ⊆ M に対して，S ⊆ T ⇒ vi (S) ≤ vi (T ) を仮
定する．公平配分問題の目標は「公平な」配分 X = (X1 , X2 , . . . , Xn ) を求めることである．こ
こで，X1 , X2 , . . . , Xn は M の分割であり，アイテム集合 Xi はエージェント i への配分を意
味する．各アイテムは不可分であるため，ひとつのアイテムを分割して複数のエージェントへ配
分することはできない点に注意する．無羨望性 (envy-freeness) は代表的な公平性の指標のひ
とつである．配分 X = (X1 , X2 , . . . , Xn ) が無羨望配分であるとは，任意の i, j ∈ N に対して，

vi (Xi ) ≥ vi (Xj ) が成り立つことを言う．不可分財の公平配分問題においては，無羨望配分の存
在は必ずしも保証されない．そこで，近似的な無羨望性を保証する研究がさかんに行われている．
その中でも EFX(envy-free up to any item) は最も説得力のある近似的な無羨望性として特
に重要視されている．しかしながら，EFX 配分が常に存在するかどうかはかなり限定された場合
を除いて未解決である．配分 X = (X1 , X2 , . . . , Xn ) が EFX 配分であるとは，任意の i, j ∈ N
と任意の g ∈ Xj に対して，vi (Xi ) ≥ vi (Xj \ {g}) が成り立つことを言う．既存研究では，以下
のそれぞれの場合において EFX 配分が常に存在することが知られている．

• n = 2 の場合
• 各エージェントの評価関数が等しい場合
• 高々 n − 1 個の不可分財を未割当 (どのエージェントにも割り当てない) としてよい場合
本論文では，上記の結果を拡張した以下のそれぞれの場合において，EFX 配分が常に存在するこ
とを示した．
∗

本論文の国際会議版は ESA 2021 に掲載されている [3].

1

(1) 2 つの評価関数 vα , vβ が与えられており，各エージェントの評価関数が vα または vβ であ
る場合

(2) m ≤ n + 3 である場合
(3) 高々 n − 2 個の不可分財を未割当 (どのエージェントにも割り当てない) としてよい場合
証明はいずれも構成的であり，EFX 配分を求めるアルゴリズムを与えている．また，(1) は自身
の過去の結果である，2 種類の加法的な評価関数の場合についての結果 [2] の一般化となってい
る．EFX 配分の存在を示す手法では，所望の条件を満たしていない限り，EFX 部分配分を保持
しながら，何らかのポテンシャルを改善するアプローチが標準的である．ここで，部分配分とは
未割当のアイテムを許す配分のことである．Chaudhury らは n = 3 かつ，各エージェントの評価
関数が加法的1 である場合に，辞書式ポテンシャルを用いて EFX 配分が常に存在することを示し
た [1]．本論文では，(2) および (3) において，辞書式ポテンシャルを用いた．また，辞書式ポテ
ンシャルに加えて，(1) において分割辞書式最小ポテンシャルを新たに導入した．これらのポテン
シャルを用いる点の困難は，現在の EFX 部分配分 X から新たな EFX 配分 X ′ を構成する際に，
あるエージェント i について，vi (Xi′ ) < vi (Xi ) となりうることである．これによって，配分 X ′
において，エージェント i が EFX の条件を違反して他のエージェントを羨望しうることが主要な
問題となる．そのような障害を克服するために，あらかじめ新たな EFX 配分 X ′ で出現しうるア
イテム集合をすべてリストアップし，その中で i にとって最も良いアイテム集合を i へ配分する
ことによって，i がどのエージェントも羨望しないようにするという操作が鍵となるアイデアで
ある．また，一度の変換ではポテンシャルは改善しない場合があり，そのような場合はさらに複
数回配分を変換して，ポテンシャルを改善させることも必要となる．このような工夫により，新
たに得られた配分が EFX の条件を満たし，かつポテンシャルを改善していることが保証される．
また，本論文では上記の肯定的な結果に加えて，n = 3 かつ m = 7 の場合でさえ，既存の辞書
式ポテンシャルを用いるアプローチがうまくいかない例を示している．この結果は，ある意味で
辞書式ポテンシャルを用いるアプローチの限界を示しており，より一般の場合について EFX 配分
の存在を示すためには，新たなポテンシャルを用いるか，全く別の手法が必要となることが示唆
される．

参考文献
[1] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents. In
Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 1–19,
2020.
[2] Ryoga Mahara.

Existence of EFX for two additive valuations.

arXiv preprint

arXiv:2008.08798, 2020.
[3] Ryoga Mahara. Extension of additive valuations to general valuations on the existence of
EFX. In 29th Annual European Symposium on Algorithms (ESA), 2021.
1

評価関数 vi が加法的であるとは，任意の S ⊆ M に対して vi (S) =

2

∑
g∈S

vi ({g}) が成り立つことを言う. ...