ゲーム理論の問題

$x,y\in {\mathbb{R}}^n$ に対し $x^{\top }Ay=\sum _{i=1}^n\sum _{j=1}^n|i-j|x_i{y}_j$ である。また $e_k$ で、$k$ 番目の成分だけが $1$ で他が $0$ のベクトルを表す。$e_k\in \Delta$ である。$v_0=\frac{n-1}{2}$ とおく。

補題. $c\in {\mathbb{R}}^n$ に対し $\underset{y\in \Delta }{\max }\sum _j{c}_j{y}_j=\underset{j}{\max }{c}_j$ である。

（証明）$y\in \Delta$ なら $y_j\ge 0$ なので ${\sum }_j{c}_j{y}_j\le \left({\max }_k{c}_k\right){\sum }_j{y}_j={\max }_k{c}_k$。一方、$c_{k_0}={\max }_k{c}_k$ となる $k_0$ をとると $y=e_{k_0}\in \Delta$ で等号が成り立つ。（終）

ステップ 1: $\underline{v}\ge v_0$。 $x^0=\frac{1}{2}(e_1+e_n)\in \Delta$ とおく。任意の $y\in \Delta$ に対し、$1\le j\le n$ より $|1-j|+|n-j|=(j-1)+(n-j)=n-1$ なので
$$x^{0\top }Ay=\sum _{j=1}^n\frac{|1-j|+|n-j|}{2}{y}_j=\frac{n-1}{2}\sum _j{y}_j=v_0$$
である。よって ${\min }_{y\in \Delta }{x}^{0\top }Ay=v_0$ であり、$\underline{v}$ は $x\in \Delta$ についての最大値なので $\underline{v}\ge v_0$。

ステップ 2: 各 $y\in \Delta$ について ${\max }_{x\in \Delta }{x}^{\top }Ay$ を求める。 $y\in \Delta$ を固定し、$g(i)=\sum _{j=1}^n|i-j|y_j$（$i=1,\dots ,n$）、$\mu =\sum _{j=1}^{n}j{y}_j$ とおく。$x^{\top }Ay={\sum }_{i}g(i)x_i$ なので、補題より ${\max }_{x\in \Delta }{x}^{\top }Ay={\max }_{i}g(i)$ である。

まず $g(1)={\sum }_j(j-1)y_j=\mu -1$、$g(n)={\sum }_j(n-j)y_j=n-\mu$ である。次に $1\le i\le n$ に対し $t=\frac{i-1}{n-1}\in [0,1]$ とおくと $i=(1-t)\cdot 1+t\cdot n$ なので、各 $j$ について $i-j=(1-t)(1-j)+t(n-j)$ であり、三角不等式と $1-t\ge 0$, $t\ge 0$ から
$$|i-j|\le (1-t)|1-j|+t|n-j|$$
が成り立つ。両辺に $y_j\ge 0$ を掛けて $j$ について足すと
$$g(i)\le (1-t)g(1)+tg(n)\le \max \{g(1),g(n)\}$$
となる。$i=1,n$ では等号なので
$$\underset{x\in \Delta }{\max }{x}^{\top }Ay=\max \{\mu -1,n-\mu \}$$
である。$(\mu -1)+(n-\mu )=n-1$ なので、2 数のうち大きい方は平均 $v_0$ 以上であり、
$$\max \{\mu -1,n-\mu \}\ge v_0,\text{等号は }\mu -1=n-\mu \text{、すなわち }\mu =\frac{n+1}{2}\text{ のときに限る}$$
が成り立つ。

ステップ 3: $\overline{v}=v_0$。 ステップ 2 より、すべての $y\in \Delta$ で ${\max }_x{x}^{\top }Ay\ge v_0$ なので $\overline{v}\ge v_0$。一方、$p=\lfloor \frac{n+1}{2}\rfloor$, $q=n+1-p$ とおくと $1\le p\le q\le n$, $q-p\in \{0,1\}$ であり、$y^{\ast }=\frac{1}{2}(e_p+e_q)\in \Delta$ は ${\sum }_{j}j{y}_j^{\ast }=\frac{p+q}{2}=\frac{n+1}{2}$ をみたすので、ステップ 2 より ${\max }_x{x}^{\top }A{y}^{\ast }=v_0$。よって $\overline{v}\le v_0$ で、$\overline{v}=v_0$ である。

ステップ 4: ゲームの値。 任意の $x^{\prime }\in \Delta$, $y^{\prime }\in \Delta$ に対し、最小値・最大値の定義から
$$\underset{y\in \Delta }{\min }{x}^{\prime \top }Ay\le x^{\prime \top }A{y}^{\prime }\le \underset{x\in \Delta }{\max }{x}^{\top }A{y}^{\prime }$$
である。左辺は $y^{\prime }$ によらず、右辺は $x^{\prime }$ によらないので、左辺を $x^{\prime }$ について最大化し、右辺を $y^{\prime }$ について最小化して $\underline{v}\le \overline{v}$ を得る。ステップ 1, 3 と合わせて $v_0\le \underline{v}\le \overline{v}=v_0$ なので $\underline{v}=\overline{v}=v_0$ であり、ゲームの値が存在して $\frac{n-1}{2}$ に等しい。

ステップ 5: プレイヤー 2 の最適戦略。 $\overline{v}=v_0$ なので、$y\in \Delta$ が最適戦略であることは ${\max }_x{x}^{\top }Ay=v_0$ と同値であり、ステップ 2 の等号条件より、これは ${\sum }_{j}j{y}_j=\frac{n+1}{2}$ と同値である。

ステップ 6: プレイヤー 1 の最適戦略。 ステップ 1 と $\underline{v}=v_0$ より $x^0$ は最適戦略である。逆に $x\in \Delta$ を最適戦略とすると、${\min }_y{x}^{\top }Ay=v_0$ なので、すべての $y\in \Delta$ で $x^{\top }Ay\ge v_0$ である。

(a) 内側の成分が $0$ であること。ステップ 3 の $y^{\ast }$ について $f(i)={\sum }_j|i-j|y_j^{\ast }=\frac{|i-p|+|i-q|}{2}$ とおく。$i\le p$ なら $f(i)=\frac{(p-i)+(q-i)}{2}=\frac{n+1-2i}{2}$、$i\ge q$ なら $f(i)=\frac{2i-n-1}{2}$ であり、$q-p\le 1$ より $p<i<q$ となる整数 $i$ はないので、すべての $i$ はこのどちらかに入る。したがって $f(i)\le v_0$ で、等号は $i=1$ または $i=n$ のときに限る（$i\le p$ の場合は $i=1$、$i\ge q$ の場合は $i=n$ のときだけ等号）。すると
$$0\le x^{\top }A{y}^{\ast }-v_0=\sum _{i=1}^n{x}_i(f(i)-v_0)$$
で、右辺の各項は $x_i\ge 0$, $f(i)-v_0\le 0$ より $0$ 以下なので、すべての項が $0$ である。$1<i<n$ では $f(i)-v_0<0$ なので $x_i=0$ である（$n=2$ ならこの主張は空である）。よって $x_1+x_n=1$。

(b) 両端の成分。$y=e_1$ とすると $x^{\top }A{e}_1={\sum }_i|i-1|x_i=(n-1)x_n\ge v_0$ より $x_n\ge \frac{1}{2}$。$y=e_n$ とすると $x^{\top }A{e}_n={\sum }_i|i-n|x_i=(n-1)x_1\ge v_0$ より $x_1\ge \frac{1}{2}$（(a) より内側の成分は $0$ である）。$x_1+x_n=1$ と合わせて $x_1=x_n=\frac{1}{2}$、すなわち $x=x^0$ である。

以上より、このゲームの値は $\frac{n-1}{2}$ であり、プレイヤー 1 の最適戦略は $x_1=x_n=\frac{1}{2}$（他の成分は $0$）のものただ 1 つ、プレイヤー 2 の最適戦略は ${\sum }_{j}j{y}_j=\frac{n+1}{2}$ をみたす $y\in \Delta$ 全体である。