Ballmer戦略に左右されないゲームの正の期待値

Steve Ballmerは間違っていた

数日前、John Graham-Cummingが「Steve Ballmerの間違った二分探索インタビュー問題」について投稿し、HackerNewsで大きな注目を集めた。Ballmerのお気に入りの頭の体操は次のとおり。

私は1から100までの数字を1つ思い浮かべています。あなたは推測でき、推測のたびに私が高いか低いかを教えます。最初の推測で当てれば5ドルを払います。4ドル、3ドル、2ドル、1ドル、0ドル、そしてあなたは私に1ドル、2ドル、3ドルを支払わなければなりません。

このゲームをプレイしますか？

Steve BallmerはこのYouTubeインタビューで、このゲームをプレイすべきでない理由を2つ挙げている。

1. 1から100までの数字のうち多くは損失をもたらすため、数字をランダムに選んだとしても期待値は負になる。
2. 彼は二分探索を使って見つけるのに最も時間がかかる数字を戦略的に選べる。

しかしJohnは、Ballmerが数字をランダムに選ぶならゲームの期待値は実際には $0.20 で正であることを示し、1点目を反論している。

私は2点目に反論し、Ballmerの戦略に関係なくこのゲームの期待値が正であることを証明する。

Ballmerが敵対的に数字を選べる方法

常に二分探索戦略を使って数字を見つけると仮定しよう。100個の数字のうち37個は、当てるまでに6回の質問が必要になる。Ballmerがあなたの戦略を知っていれば、常にこうした「負け」数字のどれかを選び、毎回のゲームで損失を発生させられる。これは固定された探索パターンに対して常に成り立つ。少なくとも37個の数字が損失をもたらし、Ballmerはその中から1つを選べる。

どう対抗できるか？

ここで私たちはゲーム理論の領域に入る。1つの固定探索パターンの代わりに、複数の探索パターンの集合を用意できる。そしてゲーム開始時に、それらのパターンの1つを確率的に選び、ゲーム中はそれを使い続ける。

ゲーム理論では、これを混合戦略と呼び、複数の純粋戦略からなる戦略集合に基づく。

同じ数字でも、ある探索パターンでは「勝ち」になり、別の探索パターンでは「負け」になることがあるため、こうした混合戦略は各数字の期待収益を「平準化」できる。理論上は、混合戦略によってすべての数字を「勝ち」にできる、つまり各数字に対して正の期待収益を持たせられる可能性がある。これこそが私たちの探しているものだ。

勝てる混合戦略を見つける方法

注: 私たちはすべての数字で勝てる 何らかの 戦略を見つけたいのであって、最悪ケースで最大の期待値を持つ 最良の 勝利戦略（ナッシュ均衡）を求めているわけではない。

ナッシュ均衡に興味があるなら、Arthur O’Dwyerが5個までの数字のゲームについて閉形式解を調べており、Bo Waggonerが100個の数字のゲームの均衡値を無後悔オンライン学習を使って近似している。

すべての数字で勝てる混合戦略を見つけることは、数学的最適化問題として捉えられる。各戦略は「勝利」ベクトル V=(v1,..,v100) で表せる。ここで vk は、Ballmerが数字 k を選んだときの期待利益である。たとえば二分探索は、v50=5、v25=4、v0=−1 のようなベクトルに対応しうる。

純粋戦略 V1, V2, ..., Vn があり、混合戦略が確率 pk で戦略 Vk を選ぶとしよう。すると混合戦略の「勝利」ベクトルは単なる線形結合になる: Vmixed=∑i=1npiVi.

この見方では、勝利戦略を見つけるとは、次の2つの制約を満たす線形結合を見つけることになる:

• 線形結合の各要素が正であること（各数字に対して平均的にお金を稼げる）。
• この線形結合の係数が非負であること（確率に対応する）。

これは典型的な線形計画問題であり、scipy にはそのための効率的な解法がある。混合戦略を見つけるために、いくつもの純粋戦略（さまざまな二分探索）を考案して scipy.linprog() に入力すると、voilà、解が勝利戦略を示してくれる。

勝利戦略の例

完全なコードは gukoff/ballmer_puzzle にある。 注: 初期結果の $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で確認してほしい。

結論

1ゲームあたり平均14セント稼げるなら、次にSteve Ballmerがこのゲームを持ちかけてきたときは、ぜひ参加すべきだ。

GN⁺の要約

• この記事は、Steve Ballmerの二分探索ゲームをめぐる議論を扱っている。
• ゲーム理論を使って、Ballmerの戦略に関係なく勝てる混合戦略を見つける方法を説明している。
• この記事は、ゲーム理論や最適化問題に関心のある人にとって有益かもしれない。
• 類似のものとして、さまざまなゲーム理論関連の研究や論文がある。

[GN⁺]

Hacker Newsの意見

• Ballmerの主張はテールリスクに関するもの

  • 生存を重視するなら、期待値は良い賭け方ではない
  • ポーカーで期待値が高いからといって毎回オールインしないのと同じ
  • 平均的には勝てる可能性が高くても、得られる結果は一度きり
  • 目標が勝利なら、Ballmerに金を借りないほうがよい
  • モンテカルロシミュレーションでこの戦略の勝敗分布を見るほうが面白そう

• Ballmerが「敵対的」と言ったとき、固定された数字を選ぶ必要がないことを考慮している

  • 各推測に対して、可能な数字の個数が最大になる答えを返せば、戦略に関係なく敗北を保証できる

• 「ランダムオフセット二分探索」というアルゴリズムを提案

  • 0〜100の間でランダムな数字を選び、これを「オフセット」と呼ぶ
  • 二分探索アルゴリズムを実行するが、各段階で値に「オフセット」を加え、100でモジュロ演算を行う
  • Ballmerがこの戦略を知っていても、特定の数字を選んで性能を落とすことはできない
  • したがって、期待結果は依然として1ゲームあたり$0.20

• Ballmerが間違っている多くのことの一つ

• 『Little Mathematics Library – Elements of Game Theory』を勧めている

  • ゲーム理論の混合戦略を扱う良書
  • 本では動機付けの例として2枚のカードゲームを紹介している
    • Aプレイヤーがエースを引いたら、相手に1ドルを要求する
    • デュースを引いたら、相手に1ドルを要求するか、1ドルを支払う
    • 相手は自発的に1ドルを受け取るか、エースかどうかの確認を要求できる
    • エースなら2ドルを支払い、ブラフなら2ドルを受け取る
    • ゲームを分析し、各プレイヤーの最適戦略と期待報酬を求める

• ナッシュ均衡のより広範な分析と、ゲーム全体の数値的解法を示すリンクを共有している

• 現代の技術面接プロセスは純粋に狂っている一例

• 「これが正しそう、よくやった！」というコメントを探していたが、なかったので自分で書いた

  • これが正しそう、よくやった

• Steve Ballmerの純資産は1200億ドル

  • 各ゲームに30秒かかると仮定すると、全財産を勝ち取るのに160万年かかる