【クリスマス2021】ケーキの切り分けと称した資源配分問題
メリークリスマス！ この記事は 物工/計数 Advent Calendar 2021 - Adventar の第25日目（最終日）の記事です。
前提知識
途中までは特に何の知識もなく読めます。後半は、ラグランジュの未定乗数法、および数理計画法の「相補性条件」の知識*1を前提とします。（一か所を認めれば、これを知らなくても読むことができます）
やや唐突な問題設定
クリスマスなのであなたはケーキを焼きました。ケーキを $r$ 個に切り分け、$n$ 人の子供たちに配ります。子供 $i~(1 \leq i \leq n)~$がケーキを $x$ 個貰った時の満足度を $f_i(x)$ で表しましょう。$f_i$ は0以上の整数から実数への関数です。どんな配分をすれば、満足度の和を最大にできるでしょうか？すなわち、$\sum_{i=1}^n x_i=r,x_i \geq 0$という条件のもとで、$ \sum_i {f_i(x_i)}$を最大化するようなアルゴリズムを考えてください。
この問題を資源配分問題と呼びます。
【資源配分問題】
$\sum_{i=1}^n x_i=r,x_i \geq 0,x_i \in \mathbb{Z}$という条件のもとで、$ \sum_i {f_i(x_i)}$を最大化せよ。
クリスマスケーキはこじつけです。
関数fの制約
関数$f_i$に何の制約も与えないと、効率的なアルゴリズムを作るのは難しそうです。そこで、任意の$t \geq 0$に対して $f_i(t+2)-f_i(t+1) \leq f_i(t+1)-f_i(t)$ という制約を考えましょう。これは、「$t$ が大きくなるほど$f_i$の上がり幅が減る」ことを表しています。例えば、ケーキを1個ももらえないのは明らかに激烈に不満なので、$f(1)-f(0)$はとても大きいでしょう。ケーキをもらいすぎると、もらえる数が増えても嬉しさはたいして増えないでしょう。この辺りの直感を単純化したのが上記の制約です。
実はこの制約を加えると、次のような貪欲法でこの問題を解くことができます。少し帰納的なアルゴリズムの書き方なのでご注意ください。
アルゴリズム1．
$k$番目までのケーキを配り終えたと仮定する：各子供に、$x^*(k)_1, \cdots, x^*(k)_n$個配ったとする。$k+1$番目のケーキを誰に配るかを次のように決める：「$k+1$番目のケーキを配ったときに、嬉しさの上がり幅が最も上がる人に配る」。すなわち、$f_i(x^*(k)_i+1)-f(x^*(k)_i)$が最大になる$i$を考え、子供$i$にケーキを配る。
既視感
実はこの問題は、昔このブログで扱った*2問題を一般化したものです。それはこれです。
shib-e-ngineering.hatenablog.com
この証明と同様に今回の貪欲法の正当性も証明できます。今回は正当性証明は本題ではないですが、一応略証を書いておきましょう。
【アルゴリズム1の正当性の略証】
1番目のケーキを、$f_i(x(1)_i+1)-f(x(1)_i)$が最大となる$i$（これを$i*$とする）以外の子供$j$に配ったとする。「1番目に$i*$に配ることでより悪くない配り方を作れる」ことを示す。2番目以降、子供$i*$にケーキを配ることがあるのなら、ケーキを配る順番を入れ替えて、1番目に子供$i*$に配っても満足度は変わらない。2番目以降、子供$i*$にケーキを配ることがないのなら、「1番目に子供$j$ではなく子供$i*$に配る」という点のみを変えた配り方は、$f_i(t+2)-f_i(t+1) \leq f_i(t+1)-f_i(t)$ という制約ゆえ、元の変え方よりも満足度の和が高い。
ゆえに、1番目のケーキは子供$i*$に配ったとしていい。これを帰納的に繰り返せば、アルゴリズム1で与えられる配り方が最適であることがわかる。■
詳細は省きますが、プライオリティキューというものを使うことでこのアルゴリズムを$O(r \log n)$の計算量で実装することができます。
fの凸性と連続緩和アルゴリズム
このままだと前の記事の使い回しも使い回しなのですが、今回やりたいのはここからです。$f$の制約$f_i(t+2)-f_i(t+1) \geq f_i(t+1)-f_i(t)$ を見直してみると、「増分が増えない」ことから、これが「上に凸」っぽい条件であることがわかります。実際、（整数でないところは線分で結んで）$f(t)$の定義域を実数全体に拡張したグラフは上に凸です。ここからは$f$を$-f$に置き換え「下に凸」っぽい関数とし、最大化問題を最小化問題に置き換えましょう。
さらに簡単のため、$g(t)=f(t) (t \in \mathbb{Z})$をみたし、微分可能で下に凸である関数$g$が存在するとします。*3
こうすると元の問題で$x$の範囲を整数ではなく非負実数にした連続緩和問題を考えることができます。
【連続緩和問題】
$\sum_{i=1}^n y_i=r,y_i \geq 0,y_i \in \mathbb{R}$という条件のもとで、$ \sum_i {g_i(y_i)}$を最小化せよ。
ラグランジュの未定乗数法と相補性条件より、実数$\lambda$が存在して任意の$i$について「$z_i=0 \implies g'_i(z_i)- \lambda \geq 0$かつ$z_i>0 \implies g'_i(z_i)- \lambda = 0$（★）」が成り立つことと$\{z_i\}$が上の問題の最適解であることは同値です。相補性条件をご存知でない場合はこの（★）を認めて先に進んでください。最適解を$z_i$で表します。
ここで、次のように整数ベクトル$\{x_i\}$を構成しましょう。
・$z_i$が整数のとき、$x_i=z_i$
そうでないとき、
・$g_i(\lfloor z_i\rfloor+1)-g_i(\lfloor z_i\rfloor) < \lambda$のとき、$x_i= \lceil z_i \rceil$
・$g_i(\lfloor z_i\rfloor+1)-g_i(\lfloor z_i\rfloor) \geq \lambda$のとき、$x_i= \lfloor z_i \rfloor$
まず、★と平均値の定理より任意の$z_i$に関して$g_i(z_i+1)-g_i(z_i) \geq \lambda$です。さらにgの凸性より、$g_i(\lceil z_i\rceil+1)-g_i(\lceil z_i\rceil) \geq \lambda$も従いますから、任意の$i$に対して$g_i(x_i+1)-g_i(x_i) \geq \lambda$が従います。さらに、$z_i \geq 1 \implies g_i(\lfloor z_i\rfloor)-g_i(\lfloor z_i\rfloor-1) \leq \lambda$も成り立ちます。これをまとめると
「・任意の$i$に対して$g_i(x_i+1)-g_i(x_i) \geq \lambda$
・$x_i >0$ならば$g_i(x_i)-g_i(x_i-1) \leq \lambda$」（♡）
となりますが、実はこのとき、$\{x_i\}$は$r' := \sum_{i=1}^n x_i$とした場合の資源配分問題の（$r$に$r'$を代入したときの）最適解になっています。
このことを示しましょう。実はそのために必要な議論はさっきの貪欲法の正当性証明とよく似ています。最大化問題を最小化問題に変えたことに注意してください。
【（♡）を満たす$\{x_i\}$が最適である証明】
（♡）を満たす$\{x_i\}$をとり、$\sum_i y_i =\sum_i x_i$だが$\{x_i\}$とは異なる$\{y_i\}$を任意にとる。この$y_i$が$x_i$よりも「良くない」ことを示せばよい。$\{x_i\}$と$\{y_i\}$が異なるが目的関数（$\sum_i f_i(x_i)$）が一定なので、$x_i<y_i$かつ$x_j>y_j$となる$i,j$の組が存在する。ここで$\{z_i\}$を、「$z_i=y_i-1,z_j=y_j+1$」とし、他は$\{y_i\}$と同じにした列で定める。この時、$\sum_i |x_i-z_i|$は$\sum_i |x_i-y_i|$よりも小さいことに注意しよう。さらに、$y_i$から$z_i$に変えたとき目的関数は
$g_i(z_i+1)-g_i(z_i) - ( g_i(z_i)-g_i(z_i-1) ) \leq g_i(x_i+1)-g_i(x_i) - ( g_i(x_i)-g_i(x_i-1) )$
だけ下がる（この値が非負かはまだわからない）。この不等式には$g$の凸性と$x_i \leq z_i$かつ$x_j \geq z_j$用いた。さらに（♡）よりこの右辺は$\lambda - \lambda =0$
以上である。したがって$\{z_i\}$の方が目的関数を小さくできる。$\sum_i |x_i-z_i|<\sum_i |x_i-y_i|$であり、同じことを繰り返せば最終的に$\sum_i |x_i-z_i|=0$とでき、この時$x_i=z_i$であるから、$\sum_i f_i(x_i) \leq \sum_i f_i(y_i)$がいえる。
いかにも貪欲法っぽく、「交換しても悪くならない」をうまく使った証明であるといえます。さて、$\sum_i x_i =r'$は$r$と等しいとは限りませんので、このままでは元の資源配分問題を解けたとは言えません。
しかしながら、例えば$r'<r$のとき、求まった$\{x_i\}$は資源配分問題の$r'$での最適解ですから、ケーキの例で言うなら「ケーキを$r'$個まで配る途中の配り方」までは追えたことになります。アルゴリズム1の性質上、残りの$r-r'$個をアルゴリズム1と同じように配れば事がすみます。そして、$r'-r \leq \sum_i |x_i-z_i| \leq n$なので、この「残りの部分」は$O(n \log n)$で終了します。
もしも$r>>n$であり、連続緩和問題の最適解を効率的に求められるのであれば、*4連続緩和問題を先に解く方が効率的な解法が求まるというわけです。なお、$r'>r$だった場合にもやはり$O(n \log n)$で$r$での最適解にたどり着けることを理論的に示せますが、そのことはここでは省略します。
まとめ
いかがだったでしょうか。アドベントカレンダーの最終日に遅刻するのは忍びなさすぎるのですが、今なんと23時52分です。本当にギリギリで申し訳ありません。
このように、離散的なアルゴリズムにおいても「凸性のようなもの」をうまく活用して、効率的なアルゴリズムを考えることができます。そして、「交換しても悪くならない」という貪欲法の正当性証明の常套手段は、この「凸性のようなもの」と極めて相性がいいことがわかっています。この辺りを一般化したのが離散凸解析のM凸関数などの概念です。
最大化問題を最小化問題にすげ替えたせいでいつの間にかケーキの話は消滅していますし、クリスマスなのにクリスマスっぽい感じを出せなかったのが悲しいですが、物工・計数アドベントカレンダーのほかの記事もお楽しみいただければと思います。（改めて貼っておきましょう）
物工/計数 Advent Calendar 2021 - Adventar
今年もお疲れさまでした。
