ゲーム理論の問題

$4$ つの航空会社 $1,2,3,4$ が、共同で $1$ 本の滑走路を建設する。会社 $i$ が使う機体に必要な長さの滑走路を単独で建設すると、その費用は $c_i$（単位：億円）で、
$$c_1=8,c_2=20,c_3=32,c_4=50$$
である。長い滑走路は短い滑走路の用途も兼ねる。そのため、会社の集合 $S\subseteq N=\{1,2,3,4\}$ が共同で建設するときの費用は
$$C(S)=\underset{i\in S}{\max }{c}_i(S\ne \varnothing ),C(\varnothing )=0$$
とする。

この費用ゲーム $(N,C)$ のシャープレイ値 $({\phi }_1,{\phi }_2,{\phi }_3,{\phi }_4)$ を求めよ。ただし、各会社 $i$ のシャープレイ値は
$${\phi }_i=\sum _{S\subseteq N\setminus \{i\}}\frac{|S|!(4-|S|-1)!}{4!}(C(S\cup \{i\})-C(S))$$
で定める（各会社の費用負担額を表す）。答えは $({\phi }_1,{\phi }_2,{\phi }_3,{\phi }_4)$ の順の組で答えよ。

プレイヤー集合 $N=\{1,2,3,4,5\}$ の提携形ゲーム（特性関数形ゲーム）を考える。プレイヤー $1,2$ はそれぞれ左手用の手袋を $1$ 枚ずつ、プレイヤー $3,4,5$ はそれぞれ右手用の手袋を $1$ 枚ずつ持っており、左右 $1$ 枚ずつの組が $1$ つできるごとに価値 $1$ が生まれる。すなわち提携 $S\subseteq N$ に対し、$S$ に含まれる $\{1,2\}$ のプレイヤーの人数を $\ell (S)$、$\{3,4,5\}$ のプレイヤーの人数を $r(S)$ として
$$v(S)=\min \{\ell (S),r(S)\}$$
と定める（$v(\varnothing )=0$）。

配分 $x=(x_1,\dots ,x_5)\in {\mathbb{R}}^5$ のうち、${\sum }_{i\in N}{x}_i=v(N)$ かつすべての提携 $S\subseteq N$ について ${\sum }_{i\in S}{x}_i\ge v(S)$ を満たすもの全体をコアという。このゲームのコアはただ 1 点からなる。そのコアの点の第 1 成分を $c_1$、プレイヤー $1$ のシャープレイ値を ${\phi }_1$ とするとき、$c_1-{\phi }_1$ を求めよ。

プレイヤー全体の集合を $N=\{1,2,3,4\}$ とする提携形（特性関数形）ゲーム $(N,v)$ を考える。$t$ は $0\le t\le 12$ を満たす実数の定数とする。$j,k$ は $2,3,4$ のうちの互いに異なるものを表し、特性関数 $v$ は次で与えられる。

• $v(\varnothing )=0$、$v(\{i\})=0(i=1,2,3,4)$
• $v(\{1,j\})=6$、$v(\{j,k\})=0$
• $v(\{1,j,k\})=9$、$v(\{2,3,4\})=t$
• $v(N)=12$

このゲームのコア $C(v)$ を、
$$\sum _{i\in N}{x}_i=v(N)$$
を満たし、かつすべての提携 $S\subseteq N$ について
$$\sum _{i\in S}{x}_i\ge v(S)$$
を満たす $x=(x_1,x_2,x_3,x_4)\in {\mathbb{R}}^4$ 全体の集合と定める。

コア $C(v)$ が空でないような $t$ の最大値を $t_1$、シャープレイ値 $({\varphi }_1,{\varphi }_2,{\varphi }_3,{\varphi }_4)$ が $C(v)$ に属するような $t$ の最大値を $t_2$ とする。$t_1,t_2$ をこの順に組 $(t_1,t_2)$ で求めよ。

$n$ を $2$ 以上の整数とし、$A$ を $(i,j)$ 成分が $|i-j|$（$i,j=1,\dots ,n$）の $n$ 次正方行列とする。プレイヤー 1 が行 $i$、プレイヤー 2 が列 $j$ を選んだとき、プレイヤー 2 がプレイヤー 1 に $A$ の $(i,j)$ 成分 $|i-j|$ を支払う 2 人ゼロ和ゲームを考える（直線上の地点 $1,\dots ,n$ のどれかを互いに選び、離れているほどプレイヤー 1 が得をするゲームである）。

混合戦略の集合を $\Delta =\{x\in {\mathbb{R}}^n\mid x_k\ge 0(k=1,\dots ,n),x_1+\cdots +x_n=1\}$ とし、プレイヤー 1 が $x\in \Delta$、プレイヤー 2 が $y\in \Delta$ を独立に用いるときのプレイヤー 1 の期待利得を $x^{\top }Ay$ とする。
$$\underline{v}=\underset{x\in \Delta }{\max }\underset{y\in \Delta }{\min }{x}^{\top }Ay,\overline{v}=\underset{y\in \Delta }{\min }\underset{x\in \Delta }{\max }{x}^{\top }Ay$$
とおき（これらの最大値・最小値が存在することは用いてよい）、$\underline{v}=\overline{v}$ のときこの共通の値をゲームの値という。また、${\min }_{y\in \Delta }{x}^{\top }Ay=\underline{v}$ をみたす $x\in \Delta$ をプレイヤー 1 の最適戦略、${\max }_{x\in \Delta }{x}^{\top }Ay=\overline{v}$ をみたす $y\in \Delta$ をプレイヤー 2 の最適戦略という。

次の 3 つがすべて成り立つことを証明せよ。
- このゲームの値が存在して $\frac{n-1}{2}$ に等しい。
- プレイヤー 1 の最適戦略は、$x_1=x_n=\frac{1}{2}$、それ以外の成分が $0$ である $x$ ただ 1 つである。
- $y\in \Delta$ がプレイヤー 2 の最適戦略であるための必要十分条件は $\sum _{j=1}^{n}j{y}_j=\frac{n+1}{2}$ である。

売り手のプレイヤー $1$ が品物を $1$ 個だけ持っており、プレイヤー $1$ 自身にとってこの品物の価値は $0$ である。買い手のプレイヤー $2,3,4$ はそれぞれこの品物を高々 $1$ 個欲しがっており、品物を手に入れたときの価値はそれぞれ $4,7,10$ である。この状況を、プレイヤー集合 $N=\{1,2,3,4\}$ の提携形ゲーム（特性関数形ゲーム）$v$ として次のように表す。各提携 $S\subseteq N$ に対し、 $$v(S)=\{\begin{array}{ll}\max \{b_j\mid j\in S,j\ne 1\}& (1\in S\text{ かつ }S\ne \{1\})\\ 0& (\text{それ以外})\end{array}$$ とする。ここで $b_2=4,b_3=7,b_4=10$ である（$v(\varnothing )=0$）。このゲームのシャープレイ値を $({\phi }_1,{\phi }_2,{\phi }_3,{\phi }_4)$ とするとき、この組を求めよ。