CODE FESTIVAL 2016 Grand Final D - Dice Game

• 問題
• AC

Petrの純粋戦略は$2$通り:

• 赤を選ぶ
• 青を選ぶ

touristの純粋戦略は$2^6=64$通り:

• どの目が出ても赤と答える。
• 2, 3, …, 6が出たら赤と答え、1が出たら青と答える。
  …
• どの目が出ても青と答える。

これらの混合戦略の中からお互いに最適戦略を取った時にtouristが勝つ確率を知りたい。

$a_{ij} =$ Petrが戦略$i$を取ってtouristが戦略$j$を取った時にtouristが勝つ確率、とすると行列$(a_{ij})$の見た目は

$$\begin{bmatrix} 1 & 1-p_1 & 1-p_2 & 1-(p_1+p_2) & ... & 0 \\ 0 & q_1 & q_2 & q_1+q_2 & ... &1 \end{bmatrix}$$

となっている。touristの混合戦略を$(x_1, ..., x_{64})$で表すとき、touristは$a_{1, 1}x_1 + ... + a_{1, 64}x_{64}$と$a_{2, 1}x_1 + ... + a_{2, 64}x_{64}$の小さいほうを最大化したい。この問題は以下のLPになっている:

• $\textrm{maximize} \ z$
• $a_{1, 1}x_1 + ... + a_{1, 64}x_{64} \ge z$
• $a_{2, 1}x_1 + ... + a_{2, 64}x_{64} \ge z$
• $x_1+ ... + x_{64} = 1$
• $x_1, ... x_{64} \ge 0$

これは単体法などで解けるが、もう少し簡略化する。touristの戦略は「目$i$が出たら$y_i$の確率で赤を選ぶ」という形で表せる。Petrが赤、青を選んだ時にtouristが勝つ確率はそれぞれ$p_1y_1+...+p_6y_6$、$q_1(1-y_1)+...+q_6(1-y_6)$であり、touristはこれらの小さいほうを最大化したい。この問題は以下のように書ける。

• $\textrm{maximize} \ z$
• $p_1y_1+...+p_6y_6 \ge z$
• $q_1(1-y_1)+...+q_6(1-y_6) \ge z$
• $y_1, ..., y_6 \in [0, 1]$

これもLPだけれど、変数が少ないので非基底変数の組み合わせを総当たりするだけでもよさそう。