@Lawasintegrity
前書き
そんなに難しい話題ではないです．本当はイメージ図をふんだんに入れる予定だったのですが，図の入れ方が分かりませんでした...
今回の話題はケーキカット問題です．関係する公平性の話や簡単なアルゴリズムを具体的に考えていきたいと思います．
準備
ケーキを分割する問題を考えます．ケーキは長さ$1$で，それを縦に切って分割して$n$人の分配したいです．つまり，ケーキを$[0,1]$とみなします．プレイヤーの集合を$N:=\{ 1,2,...,n\}$とします．
ケーキを分割して$X \subseteq [0,1]$のピースを作るとします．異なる2つのピースは交わらないです．つまり，$X_1 \cap X_2 = \emptyset$です．
各プレイヤーは$[0,1]$上に正の実数の値を取る利得関数$V_i$を持っているとします．利得関数は次の性質を満たすとします．
(1) $X_1 \cap X_2 = \emptyset$なら、$V_i(X_1)+V_i(X_2)=V_i(X_1 \cup X_2)$.
(2) 任意の$i$について$V_i([0,1])=1$.
(3) 任意の$\lambda \in [0,1]$で，$I \subseteq [0,1]$を分割できる．つまり、ある$I' \subseteq I$があって，$V_i(I') = \lambda V_i(I)$になる．
さて，ある分配$X=(X_1,X_2,...,X_n)$に関する性質として次のものたちを考えます．
(Proportionality) $\forall i \in N$について，$V_i(X_i) \geq \frac{1}{n}$.
(Envy-freeness) $\forall i,j \in N$について，$V_i(X_i) \geq V_i(X_j)$.
(Equitability) $\forall i,j \in N$について，$V_i(X_i) = V_j(X_j)$.
(Proportionality)とは全員，均等な分配よりは貰える価値が大きいとことです．(Envy-freeness)は$i$さんが他の人の分配を羨むことはないということです．(Equitability)は価値の意味で真に平等であるということです．
これら3つの性質の関係を簡単に見てみましょう．
まず，(Envy-freeness)$\Rightarrow$(Proportionality) です．なぜなら，$\sum_{i \in N}V_i(X_j)=1$より，少なくとも1つの$j$では$V_i(X_j) \geq \frac{1}{n}$が成立しています．(Envy-freeness)の性質から，$V_i(X_i) \geq V_i(X_j) \geq \frac{1}{n}$となります．つまり，(Proportionality)が成立しています．
一般的に，(Proportionality)$\nRightarrow$(Envy-freeness) です．しかし，$n=2$のときに限って，(Proportionality)$\Rightarrow$(Envy-freeness) です．なぜなら，$V_1(X_1)+V_1(X_2)=1$より，$V_1(X_1) \geq \frac{1}{2}$なら，$V_1(X_1) \geq V_1(X_2)$です．
また，(Equitability) は厳しい条件で他の2つから導かれるものではありません．
ここからは具体的に分配を構成するアルゴリズムに関する話をします．
昔から知られている有名な手法はいくつもあります．しかし，実効性という観点からの計算論的な研究は比較的新しいです．
Cut and Choose アルゴリズム($n=2$におけるEnvy-freeness/Proportionality)
これは恐らく一番有名です．$2$人で平等に分ける為にはどうすれば良いか？それは，相手に分け方を決めさせて，自分がどちらか片方を選ぶという手法です．$n=2$では(Proportionality)も(Envy-freeness)も同じことで，この手法作られた分配はこれらの性質を満たします．ちゃんと書くと次のようになります．
(1) Agent 1は$[0,1]$を$V_1(X_1)=V_1(X_2)=\frac{1}{2}$となるように，$X_1,X_2$に分ける．
(2) Agent 2は$X_1,X_2$のうち良い方を選ぶ．
ここで逸脱行為はしないとします．そういう場合に関する研究もあると思います．
Dubins and Spanierのアルゴリズム(1961) (一般の$n$におけるProportionality)
これは，一般の$n$人のときの，(Proportionality)を実現する分配のアルゴリズムです．注意して欲しいのは，(Envy-freeness)は全く満たさないことです．手順は次のようなものです．
(1) 各プレイヤー$i \in N$について，$V_i([0,x_i])=\frac{1}{n}$を満たす$x_i$を計算する．このような$x_i$は$V_i$の性質から存在する．
(2) $x_i$が一番小さい$i$を選び$i^*$とする．つまり，$i^* \in \argmin_{i \in N} x_i$とする．そして，$i^*$さんに分配する分を$X_{i^*}:=[0,x_{i^*}]$とする．
(3) 残りのケーキ$[0,1] \setminus X_{i^*}$で，上の(1),(2)と同じことを$i^*$を除いた残りの人たちで繰り返す．全員の分配が決定したら終了．
これは(Proportionality)を満たします．最後の一人以外は全員，$V_i(X_i)=\frac{1}{n}$の分配を与えられます．最後の一人$j$さんについて，任意の$i \in N \setminus \{ j \}$について$V_j(X_i) \leq \frac{1}{n}$が成立します．もし成立していないとすると，$j$さんが最後に残ることはありません．よって，
$$V_j(X_j) \geq 1-\sum_{i=1}^{n-1} \frac{1}{n} =1-\frac{n-1}{n} = \frac{1}{n}$$が成立するので，(Proportionality)を満たします．
一般の$n$人について(Proportionality)を満たすアルゴリズムとして，他にEven and Pazのアルゴリズム (1984)が知られています．ここでは割愛しますが，Even and Pazの方がDubins and Spanierのより計算量的に効率的です．
因みにこれらのアルゴリズムは(Envy-freeness)を満たしません．
Selfridge and Conwayのアルゴリズム($n=3$におけるEnvy-freeness)
これまで，$n=2$のときの(Envy-freeness)と，一般の$n$の(Proportionality)に関するアルゴリズムを紹介しました．次に，$3$人のときの(Envy-freeness)を満たすアルゴリズムであるSelfridge and Conwayのアルゴリズムを紹介します．手順を簡単に説明すると，ケーキ全体から部分をくり抜いて，その部分と残りを別々に分割します．
[初期化]
(1) Agent 1 が$V_1(X_1)=V_1(X_2)=V_1(X_3)=1/3$になるように$[0,1]$の分割$(X_1,X_2,X_3)$を作る．
(2) Agent 2 が$X_1,X_2,X_3$の中で一番良いものを選ぶ．今，それを$X_1$とする．さらに，$V_2(X_1) > V_2(X_2) \geq V_2(X_3)$とする．ここで，$X_1$の中で，$V_2(X_1\setminus X')=V_2(X_2)$となっているような$X' \subset X_1$を考える．
(3) 元のケーキ$[0,1]$から$X'$を取り除く．
ここで残った部分$(X_1\setminus X') \cup X_2 \cup X_3$をケーキ2と呼ぶ．
[ケーキ2の分割]
(4) Agent 3 が$X_1\setminus X' , X_2 , X_3$の中で一番良いものを選ぶ．
(5) もし，Agent 3 が$X_1\setminus X'$を選んだら，Agent 2 は$X_2$を選ぶことにする．そうでないなら，つまり，Agent 3 が$X_2$か$X_3$を選んだら，Agent 2 は$X_1\setminus X'$を選ぶことにする．まとめると，$X_1\setminus X'$はAgent 2か3のどちらかに選ばれることにする．$X_1\setminus X'$を選んだ方をAgent $T \in \{2,3\}$と呼ぶ．
(6) Agent 1 は余ったものを与えられる．
[$X'$の分割]
(7) Agent $\{2,3\} \setminus T$が$X'$を自分の基準で平等に等分する．
(8) Agent $T$，$1$，$\{2,3\} \setminus T$がこの順番で，(7)で作られた3つのピースを選ぶ．
さて，このアルゴリズムの出力は本当に(Envy-freeness)になっているのでしょうか？
まず，ケーキ2の分割だけみると，それは(Envy-freeness)になっています．Agent 1 は$X_2$か$X_3$を受け取りますが，どれも価値は$1/3$です．Agent 2 は$X_1\setminus X'$か$X_2$を受け取りますが，どちらも価値は等しく，$V_2(X_3)$以上です．Agent 3 は一番良いものを選べるので良いです．
次に$X'$の分割です．Agent $T$は一番良いものを選びます．また，Agent $\{2,3\} \setminus T$は自分で等分したので他のものを羨むことはないです．あとは，Agent 1 がAgent $T$の与えられたものを羨むかどうかですが，仮にAgent $T$が$X'$全部を貰ったとしても，ケーキ2と$X'$の分割を合わせてトータルでみると，Agent 1 はAgent $T$を羨むことはありません．Agent $T$は$X_1\setminus X'$を受け取り，さらに$X'$全てを受け取ったとしても$X_1$にしかなりません．Agent 1 にとっては$X_1,X_2,X_3$はどれも等しく$1/3$の価値なので，Agent $T$を羨むことはないという理由です．
よって，ケーキ2と$X'$の分割を合わせても(Envy-freeness)になっていることが分かります．
$n\geq4$におけるEnvy-freeness
Brams and Taylor (1995)が一般の$n$人についてのEnvy-freenessなケーキカットを与えるアルゴリズムを与えました．これは実行時間を有限で抑えられる保証がなく，一般の$n$人についてのEnvy-freenessはまだまだ難しい問題になっています．
ケーキカットの計算量(Robertson-Webb model)
ここで少しだけ，アルゴリズムの計算量をどうやって評価するのかを説明します．$V$は連続的な関数を想定してよく，演算をどう与えるのか，実はあまり統一的ではないように思います．一番主流なものとして，演算のモデルである，Robertson-Webb model (1997)を紹介します．これは次の2つのクエリの呼び出し回数で計算量を評価するものです．2つのクエリとは
(クエリ1) $eval_i(x,y)$ : $i$さんに区間$[x,y]$の価値を聞く操作．
(クエリ2) $cut_i(x,\alpha)$ : $i$さんに$x$からスタートして価値が$\alpha$になる場所を聞く操作．
のことです．
ここで，$eval_i(x,y)の値=V_i(x,y)$で，$V_i(x,cut_i(x,\alpha)の値)=\alpha$です．このモデルを用いると先に紹介したアルゴリズムの計算量を評価することができます．
実は
(Envy-freeness)のアルゴリズムの結果は公平であるように思えますが，実際はプレイヤーごとに役割が異なっていて，公平であるか怪しいところです．例えば，Cut and Chooseに関しては，Agent 2 になった方が得である可能性が高いです．つまり，分割する者ではなく，選択する方が有利になっているわけです．他人の得たものに対して羨むことはしなくても，獲得する利得の絶対量は異なることを注意したいです．
参考文献
L.E. Dubins and E. H. Spanier. How To Cut a Cake Fairly. $\textit{American Mathematical Monthly}$, 68(1), 1-17, 1961.
S. J. Brams and A. D. Taylor. An Envy-Free Cake Division Protocol. $\textit{American Mathematical Monthly}$, 102(1), 9-18, 1995.
J. M. Robertson and W. A. Webb. $\textit{Cake Cutting Algorithms: Be Fair If You Can.}$ Natick, MA: A. K. Peters, 1998.
