「命懸けで宝石を分け合う問題」について

前置き

下記のつぶやきで紹介されていた問題に関するお話。

（埋め込み画像が表示されないっぽいので、問題設定については後述。）元々の問題設定では宝石の数は100個だったのだが、

という意見を目にしたので、色々と考えてみた。

問題設定

問題設定は以下の通り（説明の都合上、内容を保ったまま表現や表記を変えた部分があるので注意）。

全部でN人の人たちが、C個の宝石の分配方法を相談する。
N番の人、N-1番の人、…、1番の人、の順に、その時点で生存している各人に宝石を何個渡すかを提案して、多数決で賛否を問う。
多数決で過半数の賛成が得られれば提案通りに宝石を分配し終了、そうでなければ提案者は死亡して次の番の人の提案に移る（賛成と反対が同数のときは死亡することに注意）。
各人は、できるだけ多くの宝石の獲得を目指す。ただし、
- 自分が死亡するよりは、宝石が貰えない（0個獲得）としても生存することを望む。
- 結果的に自分の取り分が変わらないならば、最終的に生存者数がより少なくなることを望む。
以上の条件の下で、各人は自身にとって最善の結果を目指して合理的な判断を行う*1。その際、他の人も全員が合理的な判断を行うという前提で判断する。

大元の問題では「C = 100、N = 5のときに、5番の人は宝石を何個獲得できるか」だけが問われているが、NやCの値を色々と変えたらどうなるかを考えてみるのが今回の話である。

定義などの準備

まず、いくつか定義を導入しておく。

【定義】

N番の生存提案とは、1番からN番の人たちへの宝石の分配の方法のうち、それを提案すればN番の人が多数決で過半数の賛成を得られるものを指す。
N番の生存提案が存在する場合、N番の最適生存提案とは、N番の生存提案のうちN番の人の宝石獲得数が最も多くなるものを指す。

一般に、N番の生存提案が存在する場合、最適生存提案は複数存在することもある（後述）。これを踏まえて、各人の判断基準についてさらに詳しい仮定と定義を導入する。

【仮定と定義】

各人は楽観的であるかまたは悲観的であるものとする。N番の人が楽観的であるとき、M番の人（MはN以上）の提案におけるN番の想定利得を以下のように定義する：

N番からM番までの少なくとも一人が生存提案を持つとき：その中で番号が最大の人をL番の人とする。このとき、M番の人の提案におけるN番の想定利得を、L番の最適生存提案（複数存在するかもしれない）におけるN番の人の宝石獲得数の最大値と定義する。

N番からM番までの人が誰も生存提案を持たないとき、M番の人の提案におけるN番の想定利得を「死亡」と定義する。

N番の人が悲観的であるとき、M番の人（MはN以上）の提案におけるN番の想定利得を以下のように定義する：

N番からM番までの少なくとも一人が生存提案を持つとき：その中で番号が最大の人をL番の人とする。このとき、M番の人の提案におけるN番の想定利得を、L番の最適生存提案（複数存在するかもしれない）におけるN番の人の宝石獲得数の最小値と定義する。

N番からM番までの人が誰も生存提案を持たないとき、M番の人の提案におけるN番の想定利得を「死亡」と定義する。

上記の想定利得は、一般には他の人たちがそれぞれ楽観的であるか悲観的であるかによって変わり得ることを注意しておく。これらの定義の下、他の人の提案に対する各人の合理的な判断とは何であるかを以下のように明確にしておく。

【定義】 MをN以上の数とするとき、M番の生存提案に対するN番の人の賛否を以下のように定める。

M = Nのとき、N番の人は常に「賛成」するものとする。

NがMより小さいとき、その提案におけるN番の人の宝石獲得数が、M-1番の人の提案におけるN番の想定利得よりも真に望ましいならば「賛成」、そうでなければ「反対」するものとする。

考察

用語の準備が終わったので、各人の合理的な判断や想定利得について考察していく。なお、以下ではC = 0の場合（つまり、分配すべき宝石が存在しないにもかかわらず、死の危険を冒してまで「宝石の分配方法」を相談するという猟奇的な状況）も考察の対象に含めるものとする。
まず、次の事実は単純明快であるが、以下の議論においてかなり役に立つ。
【補題１】 MがNより大きいとき、M番のある生存提案について、

（１）M-1番の人の提案におけるN番の想定利得が「死亡」ならば、N番の人は常に賛成する。

（２）そうでないとき、

（２−１）この提案におけるN番の人の宝石獲得数が0個ならば、N番の人は常に反対する。

（２−２）M-1番の人の提案におけるN番の想定利得がC個ならば、N番の人は常に反対する。

【証明】（１）については、「死亡するよりは宝石獲得数が0個でも生存を優先する」という前提による。
（２−１）と（２−２）については、N番の人はこの後の提案において自身が死なないことをわかっているので、「自分の取り分が同じならば、生存者数がより少なくなることを優先する」という前提による。（証明終）

これを用いると、人数が少ない場合についての解析は難しくない。なお、以下では「1番からN番の人にそれぞれa[1]個、…、a[N]個の宝石を配る」という提案を(a[1],…,a[N])で表すことがある。
【命題１】

（１）N = 1のとき、1番の最適生存提案は(C)、つまり宝石を自身が総取りすることである。

（２）N = 2のとき、2番の生存提案は存在しない。

（３）N = 3のとき、3番の最適生存提案は(0,0,C)、つまり宝石を自身が総取りすることである。

（４）N = 4のとき、Cが1以下であれば4番の生存提案は存在しない。一方、Cが2以上であれば、4番の最適生存提案は(1,1,0,C-2)である。

【証明】（１）は明らか。
（２）については、補題１の（２−２）により2番の提案に対して1番の人は常に反対するので2番の人は過半数の賛成を取れない。
（３）については、上の議論より2番の人の提案における1番と2番の人の想定利得は(2個、死亡)なので、補題１の（２−１）と（２−２）により3番の提案に対して1番と2番の人の応答は常に(反対、賛成)である。よって3番は自分が賛成することで常に過半数の賛成を得られるので、自身に宝石をすべて割り当てるのが最善の選択である。
（４）については、上の議論より3番の人の提案における各人の想定利得は(0,0,C)であるので、4番の人の提案において、補題１の（２−２）より3番の人は常に反対する。よって、4番の人自身は賛成するとして、過半数を取るには1番と2番にともに賛成させる必要がある。補題１の（２−１）により、そのためには1番と2番の人の両方に少なくとも1個の宝石を配る必要がある。また逆にそうすれば実際に過半数の賛成を得ることができる。よって、4番の人の最適生存提案は(1,1,0,C-2)となるが、Cが1以下であればこの提案は不可能なので、その場合には生存提案は存在しない。（証明終）

また、人数を多くしていったときに、次の性質が成り立つ。
【命題２】 Cの値を固定してNの値を増やしていくとき、N番の人が生存提案を持つようなNの値も生存提案を持たないようなNの値も無限に存在する。より詳しくは、

（１）N番の人が生存提案を持つならば、N+1番から2N+1番までの少なくとも一人は生存提案を持つ。

（２）Nを2Cより大きな数とし、N番の人が生存提案を持つとすると、N+1番から2N-2C番までの人は誰も生存提案を持たない。

【証明】（１）については、もしN+1番から2N番までの人が誰も生存提案を持たないとすると、補題１の（１）より2N+1番の人の提案に対してN+1番から2N番までのN人は全員常に賛成するので、2N+1番の人自身が賛成することで過半数（少なくともN+1人）の賛成が得られる。
（２）については、それらの人のいずれか（M番の人とする）について、N+1番からM-1番までの人が生存提案を持たないと仮定すると、M-1番の人の提案における1番からN番までの人の想定利得は少なくとも「死亡」ではない。ここで宝石はC個しかないので、補題１の（２−１）により、これらの人のうちM番の人の提案に賛成するのは高々C人であり、常に少なくともN-C人は反対する。すると、賛成票は多くてC + (M - N)票、反対票は少なくともN - C票であり、Mは2N-2C以下なのでC + (M - N)はN - C以下である。よってM番の人は過半数の賛成を獲得することはできない。（証明終）

C = 0の場合：

命題２により、たとえ宝石が一つもない状況であっても自力で生存可能な人が無限にいることがわかるが、これは個人的には少々驚きであった。以下、この状況（C = 0の場合）について各人の最適生存提案と想定利得を決定する。と言っても、可能な提案は「全員に宝石を0個配る」しか無いので、問題は各人が生存できるかどうかだけである。
【結果：C = 0の場合】
生存提案を持つ人の番号を順に $a_1, a_2, \cdots$ とすると、 $a_k = 2^k-1$ が成り立つ。
【証明】k = 1およびk = 2については命題１より正しい。以下、 $a_k$ 番の人が生存提案を持つとすると、命題２の（２）より $a_k+1, \cdots, 2a_k$ 番の人は生存提案を持たず、これと命題２の（１）を合わせると $2a_k + 1$ 番の人は生存提案を持つ。よって $a_{k+1} = 2a_k + 1$ であり、 $a_k = 2^k - 1$ だとすると $a_{k+1} = 2(2^k - 1) + 1 = 2^{k+1} - 1$ となり、再帰的に主張が示される。（証明終）

C = 1の場合：

C = 0の場合の結果には、各人が楽観的であるか悲観的であるかは関係しなかった。一方、C = 1の場合には楽観的であるか悲観的であるかが影響してくる。以下では、話をややこしくし過ぎないために、「全員が楽観的」あるいは「全員が悲観的」のいずれかの場合だけ考えることにする。
【結果：C = 1の場合】
数列 $a_k$ と $b_k$ を、 $a_1 = 1, a_2 = 3, a_k = 2a_{k-1} - 1$ （ $k \geq 3$ ）および $b_0 = 0, b_1 = 2, b_2 = 5, b_k = 2b_{k-1} - 1$ （ $k \geq 3$ ）で定める。このとき、

（１）全員が悲観的な場合、N番の人が生存提案を持つことはNが数列 $a_k$ に現れることと同値である。また、 $N = a_k$ （ $k \geq 3$ ）のとき、N番の人の最適生存提案は「1番から $b_{k-2}$ 番までの誰か一人に宝石を1個、それ以外の全員に宝石を0個配る」ことである。

（２）全員が楽観的な場合、N番の人が生存提案を持つことはNが数列 $a_k$ に現れることと同値である。また、 $N = a_k$ （ $k \geq 3$ ）のとき、N番の人の最適生存提案は、

kが奇数であれば「 $b_0 + 1$ 番〜 $b_1$ 番、 $b_2 + 1$ 番〜 $b_3$ 番、…、 $b_{k-3} + 1$ 番〜 $b_{k-2}$ 番、の誰か一人に宝石を1個、それ以外の全員に宝石を0個配る」ことであり、

kが偶数であれば「 $b_1 + 1$ 番〜 $b_2$ 番、 $b_3 + 1$ 番〜 $b_4$ 番、…、 $b_{k-3} + 1$ 番〜 $b_{k-2}$ 番、の誰か一人に宝石を1個、それ以外の全員に宝石を0個配る」ことである。

【証明】Nが4までの場合については命題１より（１）が成り立つ。また、4番の人の提案における1番から4番の人の想定利得は(0個,0個,1個,死亡)である。
N = 5のとき、上の議論と補題１により、5番の人の提案において3番の人は常に反対、4番の人と5番の人は常に賛成する。このことから、生存提案は「1番か2番の人に宝石を1個配る」ことである。よって、 $a_3 = 5$ であることに注意すると、 $N \leq a_3$ については主張がすべて成り立つことが確かめられた。
以下、 $k \geq 3$ とし、 $N \leq a_k$ については主張がすべて成り立つと仮定する。このとき命題２の（２）より、 $a_k+1$ 番から $2a_k - 2 = a_{k+1} - 1$ 番までの人は誰も生存提案を持たない。次に $a_{k+1} = 2a_k - 1$ 番の人の提案について、上の議論と補題１より $a_k+1$ 番から $2a_k - 2$ 番までの計 $a_k - 2$ 人と自分自身は常に賛成するので、過半数である $a_k$ 票の賛成を得るには残りの $a_k$ 人のうち誰か一人の賛成を得ることが必要かつ充分である。補題１より、このためには $a_k$ 番の人の提案における想定利得が0個である人の誰か一人に宝石を1個配ることが必要かつ充分である。
ここで、全員が悲観的な場合、仮定により1番から $a_k$ 番の全員について件の想定利得は0個であるので、これらの誰かに宝石を1個配ればよい。 $k \geq 3$ なので定義より $a_k = b_{k-1} = b_{(k+1)-2}$ であるから、この場合にも主張が成り立つ。一方、全員が楽観的な場合、

k+1が奇数、すなわちkが偶数のとき、仮定により件の想定利得が0個であるのは $b_0 + 1$ 番〜 $b_1$ 番、 $b_2 + 1$ 番〜 $b_3$ 番、…、 $b_{k-4} + 1$ 番〜 $b_{k-3}$ 番、 $b_{k-2} + 1$ 番〜 $b_{k-1}$ 番の人である（ $b_{k-1} = a_k$ に注意）。よってこれらの誰かに宝石を1個配ればよい。 $k-1 = (k+1)-2$ であるから、この場合にも主張が成り立つ。

k+1が偶数、すなわちkが奇数のとき、仮定により件の想定利得が0個であるのは $b_1 + 1$ 番〜 $b_2$ 番、 $b_3 + 1$ 番〜 $b_4$ 番、…、 $b_{k-2} + 1$ 番〜 $b_{k-1}$ 番の人である（ $b_{k-1} = a_k$ に注意）。よってこれらの誰かに宝石を1個配ればよい。 $k-1 = (k+1)-2$ であるから、この場合にも主張が成り立つ。

以上より再帰的に、すべてのNについて主張が成り立つことが示される。（証明終）

C = 1の場合には、全員が悲観的な状況と全員が楽観的な状況とで自力で生存できる人の集合は変わらないものの、前者の状況では宝石を貰える可能性があった人が後者の状況では宝石を貰えなくなる場合が存在するのがちょっと面白い点であろうか。

N = 5の場合

命題１によりNが4までの場合には結果がすべて決定できているが、大元の問題がN = 5（かつC = 100）の場合を考えているので、N = 5の場合にどうなるかも考えてみる。Cが1以下の場合には上記のように決定できているので、ここからはCが2以上の場合を考える。このとき命題１により、4番の人の提案における各人の想定利得は(a[1],a[2],a[3],a[4]) := (1,1,0,C-2)である。
5番の人の提案において、自分自身は賛成するので、過半数を得るためにはあと二人から賛成を得られればよい。ここで、L番の人（L = 1,…,4）から賛成を得るためには、最低限a[L] + 1個の宝石を配れば充分である。よって、a[1]からa[4]のうち小さい方から二つの値をa[L']およびa[L'']とすると、5番の人の最適生存提案は、L'番とL''番の人に宝石をそれぞれa[L'] + 1個およびa[L''] + 1個配り、残るC - a[L'] - a[L''] - 2個の宝石を自分自身へ配ることである。具体的には、

C = 2のとき、L' = 3およびL'' = 4となるので、5番の人の最適生存提案は(0,0,1,1,0)である。

C = 3のとき、L' = 3であり、L''は1,2,4のいずれかとなるので、5番の人の最適生存提案は(2,0,1,0,0)、(0,2,1,0,0)および(0,0,1,2,0)である。

Cが4以上のとき、L' = 3であり、L''は1か2のいずれかとなるので、5番の人の最適生存提案は(2,0,1,0,C-3)および(0,2,1,0,C-3)である。

Cが3以上のとき、命題１よりN = 4までの場合には最適生存提案が（存在するかどうかも含めて）ただ一通りに決定されるが、N = 5の場合には上記の通り複数の最適生存提案が存在する。そのため、6番の人の最適生存提案を考えるためには、他の人がそれら複数の可能性のどれを想定するか、つまり本稿の言葉では「楽観的」であるか「悲観的」であるか、を定める必要がある。逆に言うと、大元の問題で設定されたN = 5という値は、そうした複数の可能性を考慮せずに済ませられる範囲で最大の人数だったのである。

発展

前述のような複数の最適生存提案のうちどれを想定するかという点について、確率的な選択を考慮したり、参加者間の相談や交渉を可能としたり、ゲーム理論でいうところの繰り返しゲームの状況における最適な戦略*2を考察したり、といった発展形も考えられるかもしれないが、それらはここでは触れないものとする*3。

*1:「最終的に生存者数がより少なくなることを望む」のが合理的な判断なのかという点は措いておく

*2:この場合、参加者が「死亡」するという設定を変える必要がありそうである

*3:あと、没ネタとして、従来のように死ぬくらいなら0個の宝石獲得を優先する「凡夫」という参加者と、0個の宝石獲得で終わるくらいなら死を選ぶ「狂気の沙汰ほど面白い」参加者の二通りを考えるというアイデアもある。~~ざわ・・・ざわ・・・したい~~興味のある方は考えてみてはどうだろうか