Ballmer戦略に依存しないゲームの正の期待値
(gukov.dev)- Steve Ballmerの数字当てパズルは、1〜100の間の数を見つけるゲームで、固定された二分探索は攻略されうるが、混合戦略を使えば相手の選び方に関係なく正の期待値を作れる
- Ballmerは、無作為に選んだ場合でも期待値は負であり、自分が最も時間のかかる数字を選べると考えていたが、John Graham-Cummingは、無作為選択時の期待値は**$0.20**だと反論した
- 固定探索パターンでは、100個の数字のうち少なくとも37個が6回の質問を必要とし、損失を生むため、相手が戦略を知っていれば毎回プレイヤーを負けさせられる
- 解決策は、複数の純粋探索戦略のうち1つを確率的に選ぶゲーム理論の混合戦略であり、数字ごとの勝敗差を平均化して不利な数字をなくす方式である
scipy.linprog()で線形計画問題を解いて見つけた例示戦略では、Ballmerが無作為に選ぶと平均**$0.16**、敵対的に選んでも最悪の場合**$0.14**の期待利益を生む
数字当てパズルと従来の反論
- Ballmerが好んでいたというパズルは、相手が1〜100の間の数字を思い浮かべ、プレイヤーが推測するたびに高いか低いかを知らせるゲームである
- 報酬は、最初の推測で当てれば**$5**、その後は$4、$3、$2、$1、$0、以降はプレイヤーが$1、$2、$3を支払う方式である
- Ballmerは、このゲームをやるべきではないと考えた理由を2つ挙げていた
- 無作為に数字を選んでも損失になる数字が多く、期待値は負だと判断した
- 自分が二分探索で最も時間のかかる数字を戦略的に選べると考えた
- John Graham-Cummingは、“Steve Ballmer’s incorrect binary search interview question”で、Ballmerが無作為に数字を選ぶなら期待値は**$0.20**で正になると反論した
- さらに進んで、Ballmerが戦略的に数字を選ぶ場合でも期待値が正になる戦略を見つけられる
固定二分探索の弱点
- プレイヤーが常に同じ二分探索戦略を使うなら、100個の数字のうち37個は答えを当てるまでに6回の質問が必要になる
- Ballmerがその固定戦略を知っていれば、この37個の「負ける」数字のうち1つを選んで、プレイヤーに損失を強制できる
- この脆弱性は、特定の二分探索1つだけに限られない
- どんな固定探索パターンでも、少なくとも37個の数字は損失を生む
- 相手がその数字を選べば、プレイヤーは毎回損をする
混合戦略による対抗
- 1つの探索パターンに固定せず、複数の探索パターンを用意し、ゲーム開始時にその中から1つを確率的に選んで最後まで維持する
- ゲーム理論では、これを複数の純粋戦略に基づく混合戦略と呼ぶ
- 同じ数字でも、ある探索パターンでは勝てる数字であり、別の探索パターンでは負ける数字であることがある
- 混合戦略の目標は、各数字ごとの期待収益を平均化し、すべての数字で期待値が正になるようにすることである
線形計画で戦略を探す
- 目標は、最悪の場合の期待値を最大化する最適戦略、つまりNash均衡を求めることではなく、すべての数字で勝てる任意の戦略を見つけることである
- 各純粋戦略は、長さ100の勝利ベクトル
V = (v_1, .., v_100)で表せるv_kは、Ballmerが数字kを選んだときの期待収益である- たとえば二分探索は、
v_50 = 5、v_25 = 4、v_0 = -1のような値を持ちうる
- 混合戦略が純粋戦略
V_kを確率p_kで選ぶと、全体の勝利ベクトルはV_mixed = Σ p_i V_iになる - 勝てる戦略を見つけるには、次の条件を満たす線形結合が必要である
- 各要素が正であること
- 係数は確率なので非負であること
- これは典型的な線形計画問題であり、SciPyの
scipy.optimize.linprogで解ける - 複数の二分探索の変種を純粋戦略集合として作り、
scipy.linprog()に投入したコードから勝てる混合戦略が得られた
例示戦略と結果
- 全コードはgukoff/ballmer_puzzleにある
- 初期結果は1ゲームあたり**$0.07**で、Arthur O’Dwyerが新しい純粋戦略を追加して成績を改善した
- 改良された混合戦略の成績は次のとおりである
- Ballmerが無作為に選ぶときの平均利益: $0.16
- Ballmerが敵対的に選ぶときの最悪利益: $0.14
- 例示された混合戦略は、複数の二分探索の変種を小さな確率で混ぜる
- 確率0.4714%: 最初の推測は29、その後は区間の中央を推測し、同点なら左を選ぶ
- 確率0.1691%: 最初の推測は33、その後は中央を推測し、同点なら左を選ぶ
- 確率0.1299%: 最初の推測は36、その後は中央を推測し、同点なら右を選ぶ
- 確率3.3341%: 最初の推測は37、その後は中央を推測し、同点なら右を選ぶ
- 確率1.7818%: 最初の推測は43、その後は最悪計算量を増やさない区間内の最も右の要素を選ぶ
- 確率1.1608%: 最初の推測は44、その後は最悪計算量を増やさない区間内の最も左の要素を選ぶ
- 確率2.1310%: 最初の推測は42、その後は最悪計算量を増やさない区間端の要素を選ぶ
- 完全な戦略は74行あり、省略された全一覧はGitHubのwinning strategyで見られる
- 1ゲームあたり平均14セントの利益がかかる時間に見合うなら、Ballmerがこのゲームを提案してもプレイする価値はある
1件のコメント
Hacker News の意見
最近の関連投稿: Steve Ballmer の誤った 二分探索の面接質問 - https://news.ycombinator.com/item?id=41434637 - 2024年9月、コメント240件
この記事は応用は見事だが、核心を外しているように思う
Ballmer の論点は本質的に テールリスクに関するものだ。生存を重視するなら、期待値は賭けの基準としてまったく良くない。チャンスは一度しかないからだ。ポーカーで「期待値上」勝てる手が来るたびに全財産を賭けるのが筋が通らないのと同じ理由で、数ゲーム以内にほぼ確実に破産することになる
平均が +$0.07 であろうと何であろうと、分布の幅は明らかに 0 を下回ることもあり得る。平均的には勝つ確率が負ける確率より少し高いかもしれないが、実際には結果を一つだけ受け取る。目標が勝つか破滅するかなら、Ballmer に借金をしたいのでない限り、やらないほうがいい
もっと興味深いのは、この戦略を モンテカルロシミュレーションして勝敗分布を見ることだ。そうすれば選択はそれほど明白ではないかもしれない
数兆回くらいゲームをできるなら、もちろん徹底的に搾り取っていい :P
テールリスクの例としてもあまり良くない。明らかな戦略ではテールが極端に厚い
Sam Bankman-Fried は期待値が大好きで、表が出れば世界の「価値」を2倍にするが、裏が出れば世界を破壊するコイン投げをやる、と言ったことで有名だ
要約すると、サンクトペテルブルクのパラドックスはこうだ。公平なコインを表が出るまで投げ、プレイヤーはコインを投げた回数を n とすると $2^n を受け取る。1回目で表なら $2、2回目なら $4、3回目なら $8、10回目なら $1024(2^10) を受け取る、という具合だ。このゲームの期待値が無限大に近づくことは簡単に示せる
したがって、完全に合理的な人なら、このゲームをするために事実上どんな金額でも支払う意思があるはずだ。どんな有限の金額も無限大より小さいので、期待利得は常に正だからだ
しかし、そのゲームをするために数百万ドルを払うという人は、おそらくほとんどいないだろう。SBF は例外かもしれない
これがパラドックスなのは、人々が「合理的」ではないことを示していると考える場合だけだ。実際には、期待値はリスク測定の良い尺度ではなく、誰もがそれを知っているという意味に見える
サンクトペテルブルクのパラドックスに関する非常に網羅的で興味深い記事: https://plato.stanford.edu/entries/paradox-stpetersburg/
ここにいる大半の人と違って、こういう質問は人がどう考えるかを見るにはかなり良い方法だと思う。数学/統計/コンピュータサイエンスのバックグラウンドがあるなら、少なくともこの問題について会話を始められることは期待したい
ただし、前提を隠したり、自分勝手に無意味な制約を追加して罠にするなら、そこから先は納得できない
質問が「このゲームをするか」なら、合理的な数学的翻訳は「期待値が 0 より大きいか 判断せよ」だ。テールリスクを論じたいなら効用関数を明示する必要があり、2人のプレイヤーにとって非対称かもしれない。そしてそれが意図だとはっきり言うべきだ
正直、Steve はこの問題の 数学的な深み をきちんと把握していなかったように思う
ケリー比率より多く賭けると、特に長期的には破産リスクが高まる
https://en.m.wikipedia.org/wiki/Kelly_criterion
元記事の状況に適用されると言っているわけではない。ただ、親コメントには関連があり、投資など多くの状況で非常に有用だ
Ballmer が「敵対的」と言ったとき、こういう戦略を思い浮かべた。実際、彼は最初に固定の数字を選ぶ必要がまったくない。各推測に対して、可能な数字が最も多く残る答えを返せばよく、そうすればどんな戦略でも負けを保証できる
元記事は、どんな敵対者に対しても平均で最低 $0.07 を保証する複雑なランダム戦略を提示している。一方で Ballmer は「選択」を先延ばしにして引き延ばすだけで、毎回 7 回推測させて 1 ドル払わせられる
平均で $0.07 稼げると期待していたら、だまされていると気づくまで何ゲームやるだろうか？
元記事は興味深いが、Ballmer がなお何らかの初期選択にコミットしている、という非常に弱い意味での「敵対的」を仮定している
興味深いことに、Ballmer がコミットメントスキームを使えば、プレイヤーはこの事実を確認できる [1]。たとえばゲーム開始時に Ballmer がランダムなビットを 500 個作り、そこに 1〜100 の範囲から選んだ数字を付け足して、その結果をハッシュし、そのハッシュを送る。ゲームが終わったら彼は 500 個のランダムビットを送り、プレイヤーは公開された選択数字とそのビットを連結してハッシュしたとき、最初に送られたハッシュになるか確認できる。Ballmer が嘘をついて数字を変えるには、別の数字と連結しても元のハッシュになる 500 ビットを見つけなければならず、これは難しい
[1]: https://en.wikipedia.org/wiki/Commitment_scheme
常に最悪のブロックを出す Tetris バリエーション HATERIS の作者が作ったもの
追記: あ、違った。このコメントは間違い。指摘してくれた fgna に感謝
敵対的な Ballmer に勝てる、もっと単純な証明があるように思う。ランダムな Ballmer 相手の二分探索とまったく同じだけの期待結果が出る
私のアルゴリズム名は「ランダムオフセット二分探索」。やり方はこう
offsetと呼ぶoffsetを足し、100 で割った余りを使うこれで終わり。これで Ballmer がこの戦略を知っていても、特定の数字を選んで性能をさらに悪くすることはできない。したがって期待結果は依然として 1 ゲームあたり $0.20 で、記事で提案された戦略より良い
Ballmer が間違っていた多くのことの中でも、これもその一つのようだ
まさにこれこそ、友よ、現代の技術面接プロセスが純粋な狂気である理由を示す完璧な例だ
Ballmer の質問は、彼が期待していた答えの複雑さを考えると公平に見える
面接を受ける人はおそらく数学的には間違った答えを出すだろうが、その過程で思考プロセスを示し、コンピュータサイエンスの原理も少し実演することになる
Ballmer の経歴が長かった点を考える必要がある。彼がこの質問を実際にしたのなら、おそらく 80 年代だったはずで、その当時、記事で説明された複雑な解法を出すことを誰も期待していなかっただろう
正しい答えを提示したなら大したもので、即採用級だっただろう。しかしこの質問が根本的に壊れているとは思わない。賭けるにせよ賭けないにせよ、どちらの答えでもきちんと正当化する必要があるからだ
一般に、どの面接官とも議論があり、単に「候補者が問題に正解したか」だけを見るわけではない。個人的には大手テック企業の面接問題の多くは馬鹿げていると思うが、両側で経験してみると、プロセスは思っていたほど壊れてはいないと思う
この場合なら、二分探索について推論でき、平均利益が 0.20 ドルであることを示せる、という程度のことを見せるもの
それでもおかげで https://aphyr.com/posts/340-reversing-the-technical-intervie... とその続編のような良質なフィクションは得られた
ゲーム全体の数値解を含めてナッシュ均衡をより幅広く分析した記事は、https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...にある
Steve Ballmerの純資産は1,200億ドルなので、ゲーム1回に30秒かかるとすると、全額を勝ち取るには160万年かかる
Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
ゲーム理論の混合戦略を扱う非常に良い本
本に出てくる動機づけの例も素晴らしい
「カードが2枚、エースと2がある。プレイヤーAはそのどちらかをランダムに引き、Bはどのカードが引かれたかを見ることができない。Aがエースを引いた場合、『エースを持っている』と言って相手に1ドルを要求する。Aが2を引いた場合、(A1)『エースを持っている』と言って相手に1ドルを要求するか、(A2) 2を持っていると自白して相手に1ドルを渡すことができる
相手は自発的に1ドルを受け取る場合、受け入れるしかない。しかし1ドルを要求された場合、(B1) Aがエースを持っていると信じて1ドルを支払うか、(B2) 確認を要求してAの発言が本当かどうかを見ることができる。Aが本当にエースを持っていれば、BはAに2ドルを支払わなければならない。逆にAがブラフをかけていて2を持っていた場合、AがBに2ドルを支払う
このゲームを分析し、各プレイヤーの最適戦略と期待利得を求めよ」