Round-Robin アルゴリズム

資源分配問題に於けるRound-Robin アルゴリズムを説明し、このアルゴリズムの出力が、Envy-Freeness up to one goodを実現することを説明する。

$n$人のエージェントに$m$個のアイテムを分配する問題を考える。

$N=\{1,2,...,n\}$をエージェントの集合、$M=\{1,2,...,m\}$をアイテムの集合とする。そして、各エージェント$i$はアイテム$j$に対して$v_i(j)$という効用を持つ。
また、全ての$i,j$について、$v_i(j)\geq 0$とする。さらに、$M$の部分集合$S$に対するエージェント$i$の効用は、$v_i(S)=\sum_{j \in S} v_i(j)$で与えられるものとする。

エージェント$i$が$m$個のアイテムのうち受け取る分を$S_i \subseteq M$と書くことにする。$M$の$n$分割をallocationといい、$(S_1,S_2,...,S_n)$と書く。

このallocationに関して、エージェント間の「平等性」を保証する為に、数理的な性質を満たしているかどうかを議論する。ここでは、Envy-freenessとEnvy-freeness up to one goodの二つを紹介する。

次に、今回メインで紹介するアルゴリズムを説明する。

Round-Robin アルゴリズム

[STEP 1] 全ての$i \in N$について$S_i = \emptyset$とする。

[STEP 2]$1$から$n$までのエージェントに適当に番号をつける。

[STEP 3]
[WHILE] まだ分配されていないアイテムがあるなら、
[DO]$1$から$n$までのエージェントがその順番に一番欲しいitemを取っていき、アイテムが残っている限り、その操作を何周も行う。

証明

agent $i \neq j$について、$v_i(S_j)-v_i(S_i)$を上から評価する。まず、もし$j$が$i$より番号が後ろだった場合、$i$は$j$を羨むことはない。よって、$j$を$i$より番号が早いものとする。

アルゴリズムは$l = \lceil m/n \rceil$回のroundを行う。あるround $k$において、$r_k$,$r_k'$をそれぞれ$j$,$i$に分配されるitemとする。そうすると、

$$v_i(S_j)-v_i(S_i) = (v_i(r_1)+v_i(r_2)+ \cdots + v_i(r_l))-(v_i(r_1')+v_i(r_2')+ \cdots + v_i(r_l'))$$

であり、書き換えると、

$$v_i(S_j)-v_i(S_i) = v_i(r_1)+(v_i(r_2)-v_i(r_1'))+(v_i(r_3)-v_i(r_2'))+ \cdots + (v_i(r_{l})-v_i(r_{l-1}')) + v_i(r_l')$$

になる。アルゴリズムより、$k=2,3,...,l-1$で$v_i(r_k') \geq v_i(r_{k+1})$が成立する。これより、$k=2,3,...,l-1$で$v_i(r_{k+1})-v_i(r_k') \leq 0$であるから、

$$v_i(S_j)-v_i(S_i) \leq v_i(r_1) - v_i(r_l') \leq v_i(r_1)$$

が成立する。故に、$S_j$から$r_1$を取り除くと、$i$の$j$に対する妬みは消える。これは全ての$i,j$で言えるので、今得られたallocationは、Envy-free up to one goodである。