山分けの方法（２）
少し補足。備忘録として、n人の場合の等分保証な山分けの方法をメモ。
- 1番目の人が 1/n を全体から取り分ける。
- 2番目の人はそれが 1/n より多いと思ったら、多い分を全体に返す。思わなければ何もしない。
- 3番目からn番目の人も同様。
- 最後に多い分を全体に返した人（誰も返さなかったら1番目の人）が取り分けた分をもらう。
- 残ったものを n-1 人の等分保証な山分けで取り分ける。
他にも方法はあるだろうけど、帰納的に定義されているのでわかりやすい。ただし、これは恨みっこなしの山分けの方法ではない。恨みっこなしの方法については 山分けの方法 - tkenichiの日記 で紹介した本を見てください。
問題としては手順を考えるのが有名なんだろうけど、趣旨を少し変えて全員の満足度が一番高くなるような分配を求める問題を考えてみる。
山分けの対象（ケーキとか）が1種類の場合には、1/n 等分するのがこの問題の答えなので、特に面白くはない。問題として面白いのは、山分けの対象が多種類あって、n 人の評価がそれぞれ異なるときである（ケーキの例で言うと、イチゴが好きな人とクリームが好きな人がいるということ）。n = 2 (A,B) として、山分けの対象も2種類、それぞれ x_0、y_0 単位あるとする。単位あたりの A、B のそれぞれの評価が
| 1つめ | 2つ目 | |
| A | a | b |
| B | c | d |
| 合計 | x_0 | y_0 |
の表で与えられているとすると、A にそれぞれ (x,y) 単位与えるとすると、B には (x_0-x,y_0-y) 単位与えることなって、
- 0 ≦ x ≦ x_0
- 0 ≦ y ≦ y_0
および恨みっこなし条件から
- a(x_0-x) + b(y_0-y) ≦ ax + by （Aの評価基準ではAの分け前のほうがよい）
- cx + dy ≦ c(x_0-x) + d(y_0-y) （Bの評価基準ではBの分け前のほうがよい）
となって、この場合の
- ax + by + c(x_0-x) + d(y_0-y)
の最大化問題になる。明らかにこれは線形計画法。n が増えても、種類が増えても事情は同じ。ちょっと厄介なのは、原点が可能解じゃないので、シンプレックス法を行うにしても初期解を求めるのが面倒かもしれない。
元の、手順を求める問題と、この線形計画法の可能解を求めるアルゴリズムの問題が関係していないかな、と思ったのだけれど、どうでしょう？手順を求める問題は、山分けの対象が何種類かとか評価の値がわからなくてもよい、というのがポイントだと思うから関係ないかな？
