最適戦略は？

質問

次のような２人でやるゲームを考えます。
（１）Aは100ドルを自由に２つに分けます。例えば72ドルと28ドルのように。100ドルと0ドルでもかまいません。
（２）BはAが分けた後、一方を自分(B)のもの、他方を相手(A)のものと決めることができます。
これが1回のゲームです。A,Bとも多く手に入れようと最善を尽くします。
このゲームをｎ回するとします。A,Bの役割は変わりません。このときの両者の最適戦略は
A:毎回50,50に分ける。　B:どっちとっても同じ。　しかありません。ちっとも面白くないゲームです。
なので、ルールをちょい変えます。
（３）Bはｎ回のうち1回は選択権をAに譲らないといけません。どの回に譲るかは、その回にＡが分けた結果を見てＢが決めます。
このときＡは最善をつくすとＢより多く手に入れることができます。
例　n=2
1回目：Aは75ドル、25ドルに分けます。　
　ここで、Bの行動は２つに分かれます。
　分岐1：Bが選択権を行使して、B=75、A=25ゲット
　分岐2：Bが選択権をAに譲る。A=75、B=25ゲット
分岐1後の2回目の場合：Aは100ドル、0ドルに分けます。
　Bは選択権を譲らないといけません。（1回は譲る必要があるので）　なのでA=100、B=0ゲット
分岐2後の2回目の場合：Aは50ドル、50ドルに分けます。
　Bは選択権を行使し、B=50、A=50ゲット
どちらの場合も、A=計125ドル、B=計75ドルとなります。
これ、何となくnの式で表すことができそうなのですが、なかなかうまく導き出せません。お知恵拝借いたしたく。

回答No.1

nag0720 · ベストアンサー

n回のゲームでAが最善をつくしたときに獲得できる金額をS(n)とすると、
S(1)=100
S(2)=125
までは考察の通りでいいでしょう。

n+1回のゲームで、１回目をa(≧50)ドルと100-aドルに分けたとします。

もしBが選択権をAに譲ったとしたら、Aはaドルを自分のものにして、２回目以降は50ドル、50ドルに分ければ、Aは合計でa+50nドル手に入れることができます。

もしBが選択権を行使してaドルをBのものにしたら、２回目以降は最善をつくしてS(n)ドル手にいれれば、合計S(n)+100-aドル手に入れることができます。

１回目の最善手は、この２つの金額が同じになるようにすればよいので、
S(n+1)=a+50n=S(n)+100-a
つまり、
S(n+1)=S(n)/2+50+25n
これを解くと、
S(n)=50n+100/2^n
で、１回目の最善手は、
50+50/2^nドルと50-50/2^nドルに分ければいいことになります。

まとめると、

n回のゲームでのk回目の最善手は、
Bが選択権をAに譲るまでは、50+100/2^(n-k+1)ドルと50-100/2^(n-k+1)ドルに分ける。
Bが選択権をAに譲ったあとは、50ドル、50ドルに分ける。

ということになります。
ただし実際には、100ドルを1/32とか1/64とかに分けることはできないので、それも考慮するとすればかなり複雑になるでしょう。

お礼

回答ありがとうございます。
なるほど、総収入S(n)で漸化式をたてれば簡単ですね。aについて直接漸化式をたてようとして迷路にはまってしまいました。