ケーキの分配法？

ケーキが１つあります。これを２人で上手く分けるには、まず１人が同じ大きさになるように２つに切ります。次にもう１人が好きな方を取ります。こうすると、切った方は同じ大きさになるように切ったのですから、どちらを取られても文句は言えないわけです。
それでは、これが３人の場合やそれ以上の場合、どのようにすればいいのでしょうか？以前、解法を聞いたことがあるのですが忘れてしまいました。どなたか教えて下さい。

No.14 回答者： nozomi500 回答日時： 2001/03/09 11:38

stomachmanさんの考察はいつの感心します。

ただ、ケーキは理論的に文句が出なければいいだけで、満足度については、分けた後で交渉すればいいものでしょう。双方の満足、なんていう考えは、２人でグルになって１人をいじめるのが好きな（？）人には似合わない。
いちご１個はケーキ何gに匹敵するか。ポーカーフェイスを装って、ほんとうはいちごがきらいなんだけれど、いちごをほしそうにして、多めにケーキを切らせよう、なんている戦略があります。どっちにしても、とるほうは、２つの内の両方が半分未満になることはないはずだから、少なくとも損はしないですね。

No.13 回答者： stomachman 回答日時： 2001/03/08 02:12

nozomi500さん＜２人でケーキを分ける場合でも、切る方があれこれ考えなきゃならない分だけ、労力の損。

選ぶ側の方が楽。
　これは昔から気になってた非対称性の問題なんですが、このスレッドを機会に改めて考えてみています。質問のご主旨から少し逸脱してはいますが...（回答#5の末尾をご参照下さい。）

　たしかに両者の価値観が同じなら、どっちが切っても同じ事ですから、切るだけ手間損ですね。
　しかし、それぞれの価値基準が異なっている場合にはどうでしょうか。「満足度」を数値化できたとして、切り方によって二人の満足度の和が異なることがあります。たとえば
A：苺ほしい。B：チョコ欲しい。
という状態の時に、苺もチョコも半分ずつになるように切るのは「満足度の和が最大」という意味で最適ではない。双方にとってもっと嬉しい切り方がある訳で、ちょっと比喩的にゲーム理論でいう「パレート最適」という言い方をしました。
　自分が切ればいろんな戦略が選べます。Aが切るなら
1：チョコが乗ってる小さいピースと、苺が乗ってる大きいピース。きっとBはチョコを選ぶだろう。どこまで小さくしても大丈夫だろうか？
2：チョコが乗ってる大きいピースと、苺が乗ってる小さいピース。Bの好みは分からないが、ともかくできるだけ確実に苺を全部取りたい。
3：チョコも苺も半分ずつ。ケーキ本体も半分ずつ。Bの好みは分からん。どっちでも半分満足でいいや。利益は半分だけどリスクはゼロ。
4：チョコまるごとと苺半分の小さいピースと、チョコなし苺半分の大きいピース。Bがどっちを取っても苺は半分確実に貰える。あとはBが大きさをとるかチョコを取るか。
などなど.....
　それに対して、選ぶ側は「もっと旨く切ってよー」と思っても、先に選ばせて貰う以上文句は言えない。
　
　このような場合、お互いに好みを「定量的に」表明して交渉するのが最適になります。そして切る前に、「どこをどう切って、どっちがどのピースを取るか」が既に合意出来ているなら誰が切ろうが同じ。でも、双方が譲らない場合に、初めてご質問の手順の出番です。ところが今度はどっちが切るかでにらみ合い。
　自分が切るか選ぶかについて双方の選択が同じであると、膠着状態になる。これはまだ解決できていません。（国際紛争なんてだいたいこんな構図じゃないでしょうか。）

　という訳で「切る作業」を手間と考えるか権利と考えるか、によって話は違ってくる。しかも現実の問題ではケーキは必ずしも１個じゃない（次もある）訳でして、平均として得をするための戦略や、何度か相手の価値観を測る戦略もある。もとのご質問とは関係なくなってしまうけれど、一般に協力ゲームの問題として定式化できないものか、と思っています。

　なお、某国が企業に油田試掘権を売るとき、２セットの油井を準備させて、その好きな方を国が取るんだ、という話を聞いたことがあります。やっぱり選ぶだけの方が楽ちんではあるけれど、細かいところまで調査をやることは難しい。一方、企業側はいろいろな要因（埋蔵量、採掘コスト、品質、付属設備、付帯条件etc）を調整して、博打に出たり、安全な戦略を取ったり、好きに画策をやれます。

　なんだかまとまりがなくなってしまいましたが、とりあえず観点だけ提出しておきます。

No.12 回答者： nozomi500 回答日時： 2001/03/07 22:36

　忘れられてなくて（質問者はわすれているのかなあ）ありがたいです。

（なんで私がありがたがるんでしょうね）
　順番をきめる問題がありましたね。しかし、最初のケーキ２等分のとき、どっちが切るか、はどうやって決めるんでしょう。
　切るほうは絶対に得をしないうえに、切る手間をとられる。誰だってしたくないですが。

No.11 回答者： stomachman 回答日時： 2001/03/07 00:57

nozomi500さん＜忘れてませんてば。

ただ、６つに切ったは良いけど、そのうち２つづつを誰がどうやって選ぶのか、そこを決めなくちゃいけません。

「文句が言えない」というだけなら、実用的には

答案３
ママに分けて貰う。黙って喰わない奴はケーキ没収。

いや、これじゃ食べ終わったあとで喧嘩するかも知れません。やはり「各人の判断が一貫性を持っている限り、不満が生じないように」と考えなくちゃいかんでしょう。しかも有限回の手順でケーキが腐る前に分け終えなくちゃ。さらにnozomi500さんの指摘の通り、欲しいかどうかの判断は実際に切った後でなきゃまずいですね。くじ引きもダメとなったら...

答案４
Aが3つに切ります。徹底的に調節して宜しい。乗っかってる苺やチョコを細切れにして再分配しても構いません。そして、どれを貰っても良いと宣言します。
(1)他の二人の内の少なくともひとりBが「Aの分け方は確かにフェアだ」と同意した場合：Cは好きなのを選ぶ。AとBは残りのどっちを取っても文句無しです。（終)
(2)B, Cにとって、それぞれ一番欲しい一切れ、欲しくない一切れが出来た場合：さらに場合分けが必要です。
(2-1)一番欲しいやつがB, Cで一致しない場合：CとBがそれぞれ欲しいのを取って、残りがA。これで文句無しです。（終)
(2-2)一番欲しいやつがB, Cで一致する場合：BとCは一番欲しくないやつを表明します。
(2-2-1)一番欲しくないやつがB,Cで一致する場合：この一番欲しくないのをAにあげて、残りをくっつけちゃう。これで２人で分ける場合に帰着です。（終)
(2-2-2)一番欲しくないやつがB,Cで違ってる場合：ケーキのピースをa,b,cと名付けましょう。
Aはa=b=cどれでもフェアであると既に宣言しています。
Bはa>b>cの順に好む。
Cはa>c>bの順に好む。
だからaが誰に行ってもBかCから文句が出ます。そこでBが一番欲しいやつaを削って二番目に欲しい奴bにくっつけ、どちらを貰っても良いと宣言します。その結果をa', b'とすると、誰が見てもa>a', b'>bですから
Bはa'=b'>cの順で好み、a'かb'が貰えれば文句はないと宣言しました。
Aはb'>c>a'の順で好み、しかもcならフェアだと言ったんですから、b'かcが貰えれば文句はない。（b'ならラッキー！です。）
そこでCが好きなのを選びます。Cが取ったのが
(2-2-2-1)a'なら、A:c, B:b', C:a'。（終)
(2-2-2-2)b'なら、A:c, B:a', C:b'。（終)
(2-2-2-3)cなら、A:b', B:a', C:c。（終)
これで如何でしょう。

　さて答案４において、２人が組んで誰かをはめられるか。まずAが標的だとするとどうでしょう。(2-2-2)以外の場合はAは自分の切った通りのピースを受け取れますから満足します。そこでBとCが(2-2-2)を成立させ、Bがわざと不均等に調節したとします。するとAから見てb'>c>a'になり、Aは必ずb'かcを受け取れるのでやはり満足します。だからAを嵌めることはできない。
　ではAと誰かが組む場合。Aがわざと不均等に切る。(1)は組んだ相手がAに同意すれば成立しますが、すると標的が最初に好きなのを選べるから失敗。故に(2)しかありません。
　Bが標的だとしましょう。(2-1)だとBは好きなのを取れるからダメ。(2-2-1)ではAだけが損をしてB,Cはフェアなのでこれも失敗。(2-2-2)ではBは一番小さいピースを無視して、合わせて少なくとも2/3以上の価値のあるケーキを等分できるので、Bは満足します。だからBを嵌めることはできない。
　Cが標的だとしましょう。(2-1)だとCは好きなのを取れるからダメ。(2-2-1)ではAだけが損をしてB,Cはフェアなのでこれも失敗。(2-2-2)ではCが最初に選択権を持つ。つまりCも嵌めることはできません。
以上から、２人が組んで誰かを嵌めることは不可能です。

No.10 回答者： nozomi500 回答日時： 2001/03/06 10:57

　たぶん質問者より私のほうが気にしている（質問者自信はわすれていたりして）みたいですが、この方法というのは、「いかに切るか」でなく、「切ったのに文句を出させない」ことが目的なんでしょうね。

　すると、「ここで切っていい？」と聞きながら切るのは外道といえるかもしれません。「ここで切るよ」といって切ったところが垂直に切れていないと文句が出ることもありますね。
　
　「丸いケーキ」のドラフト方式は、たとえば、最初の人が１２時から６時の方向に切って、次の人が２時から８時に切って、最後に４時から１０時、ということで３分の１ずつ切るのでしょうね。２番目が４等分だと、３時から９時の方向になり、あとどうやって６分の１にできるのか・・。
　たぶん、これが一番すっきりしそうですが、stomachmanさんのつっこみがないと不安ですね。でも、忘れられているんでしょうね。

No.9 回答者： nozomi500 回答日時： 2001/03/02 22:41

　回答じゃないのですが、yun nekoさんの丸いケーキで「４等分」されたケーキは、１個が「0.25」（にちかい）に切られているはずなんですが、どうやって、「0.25」のケーキを約「0.17」にできるんでしょう。

　最初の人が「0.5」に切ったケーキ２つから、「0.17」ずつ切らないと無理じゃないですか。それなら、丸くても長くても同じか・・・

　なんで私は、この手の答えが気になってしかたないんだろう、と、自分でもおかしいですが。

No.8 回答者： yun_neko 回答日時： 2001/03/02 12:18

nozomi500さん

＞yun nekoさんの方法で、４等分したあとで６等分は無理だから、２番目の人は、２つの部分をそれぞれ３分の１ずつ切り取ることになるのでしょうか。

丸いケーキなら可能です。

No.7 回答者： nozomi500 回答日時： 2001/03/01 22:35

　benjaminさんの方法について、読み間違いしていました。

すみません。３人ともが３分の１だと思う場所を指して、そのうちで一番すくないのを選んだ人が取るんだったのですね。このほうが、グルをされにくいですね。

yun nekoさんの方法で、４等分したあとで６等分は無理だから、２番目の人は、２つの部分をそれぞれ３分の１ずつ切り取ることになるのでしょうか。

No.6 回答者： nozomi500 回答日時： 2001/03/01 09:33

　いやあ、私はもとが善人なもんで、２人がグルになるなんてことを思ってもみませんでした。

（笑）

　yun nekoさんの方法は、いわゆるプロ野球のドラフト会議でやっている方法ですね。ケーキとちがって、選手はなかなかうまくわけられない。そもそも、うまくわけるのはいやだ、うちのチームが0.65ほしい、という人がいたりするから。ははは。

No.5 回答者： stomachman 回答日時： 2001/03/01 00:51

●nozomi500さんのご回答は：

Aが最初の一切れを切る。B,Cのうちこれが欲しい人は何人か？
　0人-> Aがこの一切れを取る。残りを２人で分ける。
　1人-> 欲しい人がこの一切れ取る。残りを2人で分ける。
　2人-> Bが残りのケーキを切る。AはBが切った２つのうちから選ぶ（最初の一切れを選ぶのは禁止）。Cは残った２切れの大きさを調節する。Bが好きな方を取る。Cが残りを取る。

ということでしょうか。なるほど。
　しかし、AとBが組んでCを「はめる」ことができちゃう。（法律問題まで関係しているとなると、考えすぎとも言い切れない？）

＊Aがいささか大きく切る(0.35)とCは欲しがる。しかしBも手を挙げて「2人->」 の場合を成立させる。Bは残りのケーキを不均等(0.01と0.64)に切る。Aはその大きい方(0.64)を取る。Cは残り(0.01と0.35)の大きさを調節してBと半分ずつ(0.18と0.18)になるようにするのが最善の策。
　Aは得をし、BはCの泣き顔が見たい。後でこっそりAから分け前を貰うのかも知れない。なんて可哀想なC。
（「2人->」 の後、２度目に切ったり、調節したり、選んだりのパターンを幾つか調べてみた中では、少なくともこういう「共謀によるいじめ」はどの場合にも可能でした。）

●答案１：オークションはどうでしょうか。
最初に誰が切るかは問題ではない。ともかくナイフを構える。そして一切れの大きさが小さくなる方向へじわじわとナイフを移動して行きます。三人のうち二人が「それだったらいらない」と意思表示したところで切ります。
二人がいらないと言ったんだから、意思表示しなかった一人が受け取って、残りは「二人で公平に」の問題に帰着。

　しかし、例えば三人とも欲しい・いらないの判断が完全に一致しちゃったらどうするか。その場合、ちょうど境目があるはずで、そこで切れば良さそうですが、さてナイフがその位置に収束するのに有限時間でできるか？多分、早く食べたいひとが妥協することになりますが、妥協するタイミングまで３人が一致したら困りますね。

●答案２：そこで、「a: 欲しい」＞「b: ま、よろしんじゃないでしょうか」＞「c: いらない」の３値でやってみてはどうでしょう。aからc、cからaへの意思変更はダメで、一瞬でもbを経由しなくちゃいけない。
（abc)でそれぞれの人数を示しますと、初め(300)[＝３人ともa]からスタート。ナイフを移動していきます。
・(300)か(210)か(201)->まだまだ。ナイフの移動を続けます。
・(120)か(111)か(102)->切って、欲しい人が取る。残りを二人で分ける。
ここまではまあ問題ないでしょう。また
・(030)->切って、くじびきで取る人を決める。残りを二人で分ける。
ちょっと苦しいけど、全員「ま、よろしんじゃないでしょうか」ですから。くじで最初の一切れが当たった人は、ひょっとしたらもっと良いのを手に入れられるかもしれない可能性を失う訳ですが....（でもそれを言ったら、ケーキを二人で分ける問題においても、切る側より選ぶ側の方が微妙にチャンスが多い気がしますよね。）ともあれ、これで状態(012)は生じ得ないことになります。
　さらにやっかいなのは状態が次のように遷移する場合：
(300)→(210)→(021)→(003)
あるいは
(300)→(210)→(201)→(021)→(003)
です。だから(021)になったら、もうそこで切っちゃうしかない。
・(021)->切る。そうすると、bの意思表示をしている二人のうち、どっちがその最初の一切れを取りどっちが残りのケーキを切るかが問題です。「b: ま、よろしんじゃないでしょうか。」と言っている手前、二人でくじびきして貰う。（もし残りのケーキを切る役をcの人にやって貰ったら、後の二人共が「こんな切り方だったら最初の一切れはいらない」と言い出すかもしれないのでダメ。）
　以上で、(003)[=３人ともc]に行きつく以前に必ずケーキを切ることが保証されます。

●これでもまだ文句が出ないとも限らない。ケーキが非対称の場合、どっちからどっちへナイフを動かすかが問題になる。動かし方によって３人の「満足度」の合計が違ってきます。「あそこに乗ってるチョコさえ貰えれば...」「あの苺が絶対欲しい」「毒々しい緑色のクリームが好き」と、それぞれ違う価値観を持っている３人。この場合は相談した方がよい。ゲーム理論で言うパレート最適戦略があるかも知れません。

　いやはや、本気で取り組むと、いろんな定式化ができる問題のようです。面白いですね。