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

标签：

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

Author

之遥

Description

プレイヤーはマシーンと一回のみゲームを行う。 $i = 1, 2, \dots, n$ とし、プレイヤーが値 $i$ を出す確率を $p_i$ とし、 $\sum_{i=1}^n p_i = 1$ とする。 $j = 1, 2, \dots, n$ とし、マシーンが値 $j$ を出す確率を $q_j$ とし、 $\sum_{j=1}^n q_j = 1$ とする。プレイヤーとマシーンは、$1$ から $n$ までの自然数を、この確率分布に従い出すものとする。プレイヤーとマシーンが同じ数を出したとき、プレイヤーの勝ちとする。このとき、以下の問いに答えよ。

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

(問2) $i = 1, 2, \dots, n$ に対して、 $p_i = p_1 \alpha^{i-1}$ とし、 $j = 1, 2, \dots, n$ に対して、 $q_j = q_1 \beta^{j-1}$ とする。プレイヤーが勝つ確率を、 $\alpha, \beta, n$ のみを用いて表せ。

(問3) $i = 1, 2, \dots, n$ に対して、 $p_i = q_i$ とする。

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

(問4) $(p_1, p_2, \dots, p_n)$ をプレイヤーの戦略と呼ぶことにする。以下の二つの戦略を考える。

• 戦略 $E$: $(p_1, p_2, \dots, p_{n-1}, p_n) = (0, 0, \dots, 0, 1)$
• 戦略 $R$: $(p_1, p_2, \dots, p_n) = (1/n, 1/n, \dots, 1/n)$

ここで、 $q_1, q_2, \dots, q_n$ のうち、 $q_n$ が最大であるとする。

• (a) 戦略 $E$ は、戦略 $R$ より優れていることを示せ。ここで、戦略 $A, B$ に対して、戦略 $A$ を用いたときのプレイヤーが勝つ確率が、戦略 $B$ を用いた時のプレイヤーが勝つ確率以上のとき、戦略 $A$ は戦略 $B$ より優れているという。
• (b) 戦略 $E$ は、任意の戦略の中で最も優れていることを示せ。

Kai

(問1)

$$P(\text{Player wins}) = \sum_{1}^{n}p_iq_i = \frac{1}{n}\sum_{1}^{n}q_i = \frac{1}{n}$$

(問2)

$$\left\{ \begin{aligned} &1 = \sum_{1}^{n}p_i = \sum_{1}^{n}p_1\alpha^{i-1} = p_1\frac{1 - \alpha^n}{1 - \alpha} \\ &1 = \sum_{1}^{n}q_j = \sum_{1}^{n}q_1\beta^{j-1} = q_1\frac{1 - \beta^n}{1 - \beta} \end{aligned} \right. ,\qquad \left\{ \begin{aligned} &p_1 = \frac{1 - \alpha}{1 - \alpha^n} \\ &q_1 = \frac{1 - \beta}{1 - \beta^n} \end{aligned} \right.$$

$$\begin{aligned} &P(\text{Player wins}) = \sum_{1}^{n}p_iq_i = \sum_{1}^{n}p_1q_1(\alpha\beta)^{i-1} = p_1q_1\frac{1 - (\alpha\beta)^n}{1 - \alpha\beta} \\ &= \frac{1 - \alpha}{1 - \alpha^n}\frac{1 - \beta}{1 - \beta^n}\frac{1 - (\alpha\beta)^n}{1 - \alpha\beta} \end{aligned}$$

(問3)

(a)

$$P(\text{Player wins}) = \sum_{1}^{n}p_iq_i = \sum_{1}^{n}p_i^2 = n\Big(\sqrt{\frac{\sum_{1}^{n}p_i^2}{n}}\Big)^2 \ge n\Big(\frac{\sum_{1}^n p_i}{n}\Big)^2 = \frac{1}{n}$$

When $p_i = \frac{1}{n}(i = 1,2,\dots,n)$, $P(\text{Player wins})$ obtains its minimum $\frac{1}{n}$.

(b)

When $p_i = \frac{1}{n}(i = 1,2,\dots,n)$, $E[\text{Machine's output}] = \sum_{1}^{n}\frac{i}{n} = \frac{n + 1}{2}$ satisfies the condition. So it can obtain its minimum in (問3).(a) , which is $\frac{1}{n}$.

(問4)

(a)

$$\begin{aligned} &P_{E}(\text{Player wins}) = \sum_{1}^{n}p_iq_i = q_n \\ &P_{R}(\text{Player wins}) = \sum_{1}^{n}p_iq_i = \frac{\sum_{1}^{n}q_i}{n} = \frac{1}{n} \\ &\because q_n \ge q_1,q_2,\cdots,q_{n-1} \\ &\therefore 1 = q_1 + q_2 + \cdots + q_{n - 1} + q_n \le q_n + q_n + \cdots + q_n + q_n = nq_n \\ &q_n \ge \frac{1}{n} \\ &\therefore P_{E}(\text{Player wins}) \ge P_{R}(\text{Player wins}) , \text{ which means that the strategy E is superior to the strategy R}. \end{aligned}$$

(b)

Sulution 1

$$P_{\text{any}}(\text{Player wins}) = \sum_{1}^{n}p_iq_i \le \sum_{1}^{n}p_iq_n = q_n\sum_{1}^{n}p_i = q_n = P_{E}(\text{Player wins})$$

So the strategy E is superior to any strategies.

---

Solution 2

For any strategy $A$ , let $p_1 = \Delta_1 ,p_2 = \Delta_2 \cdots p_{n-1} = \Delta_{n-1},p_n = 1 - \sum_{1}^{n-1}\Delta_i$ , where $0 \le \Delta_i \le 1(i=1,2,\dots,n-1)$.

$$\begin{aligned} &\quad P_{E}(\text{Player wins}) - P_{A}(\text{Player wins}) \\ &= (0 - \Delta_1)q_1 + (0 - \Delta_2)q_2 + \cdots + (0 - \Delta_{n-1})q_{n-1} + \sum_{1}^{n}\Delta_{i}q_n \\ &= \Delta_1(q_n - q_1) + \Delta_2(q_n - q_2) + \cdots + \Delta_{n-1}(q_n - q_{n-1}) \ge 0 \\ &\therefore P_{E}(\text{Player wins}) \ge P_{A}(\text{Player wins}) \end{aligned}$$

So the strategy E is superior to any strategies.