東京大学 新領域創成科学研究科 複雑理工学専攻 2017年8月実施 専門基礎科目 第4問

标签：

• Tokyo-University
• Collision-Probability-of-Discrete-Distributions
• Best-Response-in-One-Shot-Game
• Probability-Simplex-Optimization

Author

之遥, 祭音Myyura

Description

プレイヤーはマシーンと一回のみゲームを行う。$i=1,2,\ldots,n$ とし、プレイヤーが値 $i$ を出す確率を $p_i$、マシーンが値 $i$ を出す確率を $q_i$ とし、

$$\sum_{i=1}^np_i=\sum_{i=1}^nq_i=1$$

とする。プレイヤーとマシーンは、この確率分布に従って1から $n$ までの自然数を出す。両者が一致したとき、プレイヤーの勝ちとする。以下の問に答えよ。

(問1) 全ての $i$ に対して $p_i=1/n$ とする。プレイヤーが勝つ確率を求めよ。

(問2) $p_i=p_1\alpha^{i-1}$、$q_j=q_1\beta^{j-1}$ とする。勝つ確率を $\alpha,\beta,n$ のみを用いて表せ。

(問3) 全ての $i$ に対して $p_i=q_i$ とする。

(a) 勝つ確率の最小値を求めよ。

(b) マシーンが出す値の期待値が $(n+1)/2$ であるとする。このときの勝つ確率の最小値を求めよ。

(問4) $(p_1,\ldots,p_n)$ をプレイヤーの戦略と呼ぶ。次の二つの戦略を考える。

• 戦略 E：$(p_1,\ldots,p_n)=(0,0,\ldots,0,1)$。
• 戦略 R：$(p_1,\ldots,p_n)=(1/n,1/n,\ldots,1/n)$。

$q_1,\ldots,q_n$ のうち $q_n$ が最大であるとする。

(a) 戦略 E は戦略 R より優れていることを示せ。ここで、戦略 A を用いたときの勝率が戦略 B を用いたときの勝率以上なら、A は B より優れていると呼ぶ。

(b) 戦略 E は任意の戦略の中で最も優れていることを示せ。

题目描述

玩家与机器进行一次游戏。双方从 $\{1,\ldots,n\}$ 中按各自的分布出数，玩家出 $i$ 的概率为 $p_i$，机器出 $i$ 的概率为 $q_i$，且

$$\sum_{i=1}^np_i=\sum_{i=1}^nq_i=1.$$

当双方出数相同时玩家获胜。

1. 若 $p_i=1/n$，求玩家胜率。
2. 若 $p_i=p_1\alpha^{i-1}$、$q_j=q_1\beta^{j-1}$，仅用 $\alpha,\beta,n$ 表示胜率。
3. 设 $p_i=q_i$：

(a) 求胜率的最小值。

(b) 再要求机器出数的期望为 $(n+1)/2$，求胜率的最小值。

4. 将概率向量 $(p_1,\ldots,p_n)$ 称为玩家的策略。考虑策略 E：$(0,\ldots,0,1)$，以及策略 R：$(1/n,\ldots,1/n)$，并设 $q_n=\max_iq_i$。

(a) 证明策略 E 优于策略 R。这里“优于”指其胜率不小于另一策略的胜率。

(b) 证明策略 E 在所有策略中最优。

Kai

両者の出す値は独立であり、勝率は $W=\sum_{i=1}^np_iq_i$ である。

問1

$$W=\frac1n\sum_{i=1}^nq_i=\boxed{\frac1n}.$$

問2

$$S_n(r)=\sum_{k=0}^{n-1}r^k =\begin{cases}\dfrac{1-r^n}{1-r}&r\ne1,\\n&r=1\end{cases}$$

とおく。正規化より $p_1=1/S_n(\alpha),\ q_1=1/S_n(\beta)$ だから、

$$\boxed{W=\frac{S_n(\alpha\beta)}{S_n(\alpha)S_n(\beta)}}.$$

特に $\alpha,\beta,\alpha\beta\ne1$ の場合は

$$W=\frac{(1-\alpha)(1-\beta)\{1-(\alpha\beta)^n\}} {(1-\alpha^n)(1-\beta^n)(1-\alpha\beta)}.$$

$S_n$ による式は、いずれかが1の場合にもそのまま使える。

問3

(a) Cauchy–Schwarz の不等式により、

$$W=\sum_{i=1}^np_i^2\ge\frac1n\left(\sum_{i=1}^np_i\right)^2=\frac1n.$$

等号は全ての $p_i=1/n$ のときに成り立つ。よって最小値は $1/n$。

(b) 同じ下界が成り立ち、一様分布は

$$\sum_{i=1}^niq_i=\frac1n\sum_{i=1}^ni=\frac{n+1}2$$

も満たす。したがって、この場合も最小値は $1/n$。

問4

(a) $W_E=q_n$、$W_R=1/n$ であり、

$$q_n\ge\frac1n\sum_{i=1}^nq_i=\frac1n.$$

よって $W_E\ge W_R$。

(b) 任意の戦略について

$$W=\sum_{i=1}^np_iq_i\le q_n\sum_{i=1}^np_i=q_n=W_E.$$

したがって、戦略 E は最適である。