修士論文 要旨

Asymptotic Existence of Envy-Free Fair Allocations
for Groups of Agents(エージェントのグループに対する無羨望性を満たす公平な分配の漸近的な存在性)
数理情報学専攻

48206239 横山 智彦
指導教員 岩田 覚 教授

1. はじめに資源分配問題は，経済学と計算機科学の橋渡しであるアルゴリズム的ゲーム理論で古くから研究されてきた．

OXS(0, 1)-OXS
マトロイドランク

本修士論文では資源分配の公正性の基準の一つである無加法的羨望性に着目する．分配が無羨望であるとは，全てのエージェントが他のエージェントを羨まないような分配劣モジュラのことである．しかし，不可分財に対する無羨望な分配の存在判定問題は NP 完全であることが知られている．
では，どのような状況であれば無羨望な資源分配が存在しやすいのだろうか．エージェントがアイテムに対し

図 1: 様々な評価関数クラスの関係．OXS とは割当評価関数のこと，(0, 1)-OXS とは二値割当評価関数のこと，マトロイドランクとはマトロイドのランク関数のこと．

確率的な効用値を持ち，さらに加法的評価を持つとき，Dickerson ら [2] や Manurangsi と Suksompong [3] は無羨望な分配の漸近的存在性を示している．表 1 を参照せよ．パレート最適性とは，少なくとも 1 人のエージェントの効用を下げないと，より良い別の資源分配が存在しないことである．
加法的評価以外にも劣モジュラ評価などの非加法的評価は応用上重要である．我々の知るところでは，非加法的な評価関数に対する無羨望な分配の漸近的な存在の研究はなされていない．本修士論文では，重要な非加法的な評価関数である割当評価関数 (OXS 評価関数)に焦点を当てる．割当評価は Shaplay [4] に定義され，Benabbou ら [1] によって公平性の研究が進められた．
他の評価関数との関係を図 1 に記す．
ここでは，エージェントはグループに分けられているとする．今回我々は，エージェントのグループが割当評価を持つとき，無羨望な分配の漸近的な存在性に関し初めて証明を与えた．既存の研究と本研究を簡単にまとめたものを表 1 に記す．
2. 定義
M = [m] をアイテム集合，N = [n] をエージェント集合とする．任意のエージェント i ∈ N は任意のアイ
テム j ∈ M に対し効用値 ui (j) ∈ [0, 1] を持つとする．
エージェントが加法的評価を持つとは，任意のアイテム∑
部分集合 M ′ ⊆ M に対し ui (M ′ ) = j∈M ′ ui (j) が成立すること．今，N は N1 , N2 , ..., Nk と分けられ，Npはタイプ p の集合とする．分配 (M1 , M2 , ..., Mk ) とは，アイテムの部分集合の列で任意の相異なる p, q ∈ [k] に対し Mp ∩ Mq = ∅ を満たすものをいう．分配に従って
タイプ p はアイテム部分集合 Mp ⊆ M を得る．

評価関数
加法的(0,1)-OXS
OXS

表 1: 既存研究と本研究の比較．
漸近的な無羨望性
漸近的な無羨望性+ 無駄がない+ パレート最適)(m=Ωn log nlog log n[3]m = Ω(n log n) [2]

本研究 (定理 1)
本研究 (定理 2 と 3)

本研究 (定理 1)
未解決

定義 1 (割当評価). アイテム部分集合 M ′ ⊆ M に対する，タイプ p の割当評価 vp (M ′ ) とは， Np 内のエー
ジェントと M ′ 内のアイテムによって作られる二部グラフの最大重みマッチングの重みとして定義される．
定義 2 (タイプ毎の無羨望性). 分配 (M1 , M2 , ..., Mk )がタイプ毎で無羨望であるとは，任意の 2 つのタイプp, q ∈ [k] について vp (Mp ) ≥ vp (Mq ) が成立すること．
タイプ p と M ′ ⊆ M に対するアイテム j ∈ M の周
辺効用 ∆p (M ′ ; j) は次のように定義される：
 v (M ′ ∪ {j}) − v (M ′ ) (j ∈/ M ′ ),pp∆p (M ′ ; j) =
 vp (M ′ ) − vp (M ′ \ {j}) (j ∈ M ′ ).
定義 3 (無駄のない分配). アイテム j ∈ M がある分配において無駄であるとは， あるタイプ p について

∆p (Mp ; j) > 0 であるが，そのアイテム j は誰にも配られていない，もしくは，他のタイプ q ̸= p についてj ∈ Mq かつ ∆q (Mq ; j) = 0 が成立していること．さらに，分配に無駄がないとは，その分配に対してどのアイテムも無駄になっていないこと．
先に説明したパレート最適性を満たす分配は無駄のない分配であることはすぐに分かる．

Asymptotic Existence of Envy-Free Fair Allocations for Groups of Agents(エージェントのグループに対する無羨望性を満たす公平な分配の漸近的な存在性) (横山 智彦)のマッチングの最小重み Cn,m,r の期待値は，アルゴリズム 1 割当評価に対するラウンドロビンベースなア
ルゴリズム
1: M1 , M2 , ..., Mk = ∅, M ′ = M , r = 1．
2: タイプをエージェント数が小さい順に並べ，順序を1, 2, ..., k とする．
3: while M ′ ̸= ∅ かつ ∆p (Mp ; j) > 0, ∃j ∈ M ′ , ∃p ∈ [k]do4:for p = 1, 2, ..., k do
5:
if ∆p (Mp ; j) > 0 を満たす j ∈ M ′ が存在する
then6:
Np と Mp ∪ M ′ の作る二部グラフから辺数 r の最大重みマッチングを作る．マッチングに繋がる
M ′ のアイテムを jpr とする．
7:
Mp = Mp ∪ {jpr }, M ′ = M ′ \ {jpr }8:
end if
9:end for10:
r =r+111: end while
12: return M1 , M2 , ..., Mk

3. 二値割当評価
ui (j) が独立に確率 p で 1 を取り，確率 1 − p で 0 を取るとする．また，事象 E が高い確率で起こるとは，ある定数 c > 0 があって Pr[E] ≥ 1 − n−c が成立することである．このとき，マッチングベースなアルゴリズムを考えることにより次の存在性を示すことができる．
定理 1. n ≤ m かつ，ある十分大きな定数 c ≥ 2 について p ≥ c log n/n が成立するとき，タイプ毎に無羨望でパレート最適な分配が高い確率で存在する．

4. 割当評価
一般の割当評価に関する無羨望性の存在性を述べる．
今，ui (j) は独立に [0, 1] 上の一様分布に従って得られるものとする．
4.1. エージェント数が多い場合
まず，各タイプ内のエージェント数が多いときを考える．np はタイプ p のエージェント数とする．このとき，
事象 E が高い確率で起こるとは，全ての p ∈ [k] についてある定数 cp > 0 があって Pr[E] ≥ 1 − np −cp が成立することと定義する．このとき次の定理を示した．

補題 1. アルゴリズム 1 の出力を (M1 , M2 , ..., Mk ) とする．このとき，nq ≥ np のとき，)(np1,E[vp (Mp )] − E[vp (Mq )] ≥ 1 − − o(1)k2nq
また，nq < np のとき，π2.
6定理 3. n ≤ m かつ任意のタイプ p で np ≥ 2 のとき，タイプ毎に無羨望かつ無駄のない分配が，タイプ数が多いとき高い確率で存在する．

5. おわりに本研究では割当評価に対し，異なるグループ間の無羨性を満たすような分配の漸近的な存在性を示した．さらに，この分配は無駄がない分配であることを示すことができた．無羨望かつパレート最適な分配の漸近的な存在性を調べることは，今後の研究課題である．
参考文献
[1]

N. Benabbou, M. Chakraborty, E. Elkind, and Y.
Zick. Fairness towards groups of agents in the allocation of indivisible items. In Proceedings of the 28th
International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 95–101, 2019 (cited on page 1).

[2]

J. P. Dickerson, J. Goldman, J. Karp, A. D. Procaccia,and T. Sandholm. The computational rise and fall offairness. In Proceedings of the 32nd AAAI Conferenceon Artiﬁcial Intelligence (AAAI), pages 1405–1411,
2014 (cited on page 1).

[3]

P. Manurangsi and W. Suksompong. Closing gaps inasymptotic fair division. SIAM Journal on Discrete
Mathematics, 35(2):668–706, 2021 (cited on page 1).

[4]

L. S. Shapley. Complements and substitutes in the
optimal assignment problem. Naval Research Logistics Quarterly, 9(1):45–48, 1962 (cited on page 1).

[5]

J. Wästlund. An easy proof of the ζ(2) limit in
the random assignment problem. Electronic Communications in Probability, 14:261–269, 2009 (cited onpage 2).

確率で存在する．

ルゴリズムにより分配が得られる．証明のテクニックは

Wästlund によるランダム割当問題に関する研究 [5] を参考にした．完全二部グラフ Kn,m 上の辺重みが各辺独立に母数 1 の指数分布に従うとする．このとき，辺数 r)4.2. タイプ数が多い場合
次に，エージェントの数ではなく，タイプの数が多い場合を考える．このとき事象 E がタイプ数が多いとき高い確率で起こるとは，ある定数 c > 0 があって Pr[E] ≥1 − k −c が成立することとする．このとき次が証明される．

いてある定数 c, c′ ≥ 0 があって cnq ≤ np ≤ c′ nq を満

アルゴリズム 1 に示したラウンドロビンベースなア(1E[vp (Mp )]−E[vp (Mq )] ≥ (np −nq )+ 1 − − o(1)k定理 2. k · maxp np ≤ m かつ，任意の p, q ∈ [k] につたすとき，タイプ毎に無羨望かつ無駄のない分配が高い

r−1n∑
1∑

1r
m−jr=1
j=0∑n 1で与えられる．さらに，E[Cn,n,n ] =r=1 r2 = (1 −π2o(1)) 6 である．今，辺数 np のマッチングの最大重みの期待値として与えられる割当評価値 E[vp (Mp )] やE[vp (Mq )] に関して次の補題を得る.

E[Cn,m,r ] =