ゲーム理論新版が難しすぎたので、ゲーム理論・入門新版--人間社会の理解のために (有斐閣アルマ) から読むことにした。

作者:岡田章
出版社/メーカー: 有斐閣
発売日: 2014/09/18
メディア: 単行本（ソフトカバー）

09章交渉ゲームでは 2 人のプレイヤーの交渉問題を考えたが、この章では、3 人以上のプレイヤーの交渉問題と、このゲームにおける解概念としてコアやシャープレイ値を説明する。

3 人以上の交渉問題の定式化
- 例1: 起業ゲーム
協力ゲーム理論によるアプローチ
- コア
  - 例1: 起業ゲーム
  - 例2: 多数決ゲーム
- シャープレイ値
  - 例1: 起業ゲーム
非協力ゲーム理論によるアプローチ (戦略的アプローチ)
- 例3: 3人対称ゲーム
市場ゲーム
- 例4: 1人の売り手と2人の買い手

3 人以上の交渉問題の定式化

3 人以上の交渉問題において、協力を目的として作られるプレイヤーのグループを提携という。
ある提携 $S$ に対して提携の価値 $v(S)$ を対応させる関数 $v$ を特性関数という。
プレイヤーの集合 $N$ と特性関数 $v$ の組 $(N, v)$ で表されるゲームを、提携形 $n$ 人ゲームまたは特性関数形 $n$ 人ゲームという。
互いに交わらない2つのどんな提携 $S$ と提携 $T$ に対しても $S$ と $T$ の価値の合計より $S$ と $T$ を合併した提携 $S \cup T$ の価値の方が大きいか等しい時、すなわち $v(S) + v(T) \leq v(S \cup T)$ であるとき、特性関数は優加法的であるという。また、優加法的な特性関数を持つゲームを、単に優加法的ゲームという。

例1: 起業ゲーム

プレイヤーA, B, C ( $N = {A, B, C}$ ) が共同で起業しようとしている。
プレイヤーが可能な提携は全部で7通り。
- $1$ 人提携: $\{A\}, \{B\}, \{C\}$
- $2$ 人提携: $\{A, B\}, \{B, C\}, \{C, A\}$
- $3$ 人提携: $\{A, B, C\}$
各提携に対する収益は下記の通り。
- $v(\{A\}) = 60, \: v(\{B\}) = 40, \: v(\{C\}) = 20$
- $v(\{A, B\}) = 200, \: v(\{B, C\}) = 100, \: v(\{C, A\}) = 150$
- $v(\{A, B, C\}) = 240$
優加法性の確認。
- どの2人も1人だけで起業したときの2人の収益の和より、2人共同で起業した時の収益の方が大きい。
  - $v(\{A\}) + v(\{B\}) = 100 \lt v(\{A, B\}) = 200$
  - $v(\{B\}) + v(\{C\}) = 60 \lt v(\{B, C\}) = 100$
  - $v(\{C\}) + v(\{A\}) = 80 \lt v(\{C, A\}) = 150$
- 2人で起業した時の収益と残りの1人が単独で起業した時の収益の和よりも、3人共同で起業した時の収益の方が大きい。
  - $v(\{A, B\}) + v(\{C\}) = 220 \lt v(\{A, B, C\}) = 240$
  - $v(\{B, C\}) + v(\{A\}) = 160 \lt v(\{A, B, C\}) = 240$
  - $v(\{C, A\}) + v(\{B\}) = 190 \lt v(\{A, B, C\}) = 240$

2 人の交渉問題の分析と同じ様に、提携形 $n$ 人ゲームの分析には、協力ゲーム理論によるアプローチと非協力ゲーム理論によるアプローチ (戦略的アプローチ) がある。

協力ゲーム理論によるアプローチ

2人の交渉問題の解と同様、協力ゲーム理論の基本的な公理としてパレート最適性と個人合理性がある。
協力ゲーム理論では、パレート最適性と個人合理性の2つの性質を満たす利得ベクトルを、ゲームの配分という。
優加法的なゲームにおいて、プレイヤーの利得ベクトル $x = (x_1, \cdots, x_n)$ が $x_1 + \cdots + x_n \leq v(N)$ を満たす時、 $x$ は ( $N$ に関して) 実現可能であるという。
パレート最適
- 実現可能な2つの利得ベクトル $x = (x_1, \cdots, x_n)$ と $y = (y_1, \cdots, y_n)$ に対して、 $x$ が $y$ よりパレート優位である ( $x$ が $y$ を支配する) とは、全ての $i \in N$ に対して $x_i \gt y_i$ が成り立つことをいう。
- 提携形 $n$ 人ゲームの実現可能な利得ベクトル $x$ がパレート最適であるとは、 $x$ よりパレート優位な他の実現可能な利得ベクトル $y$ が存在しないことである。
- また、優加法的ゲームにおいてパレート最適であるとは、 $x_1 + \cdots + x_n = v(N)$ ということである。
個人合理性
- 提携形 $n$ 人ゲームの実現可能な利得ベクトル $x$ が個人合理性を満たすとは、全ての $i \in N$ に対して $x_i \geq v(\{i\})$ が成り立つ時をいう。
- 右辺の $v(\{i\})$ は、プレイヤーが他の誰とも協力しない時の利得。左辺の $x_i$ は他のプレイヤーと何らかの協力をして得られる利得。つまり、全てのプレイヤーにとって、単独でいるよりも、何らかの協力をした方が、同等かより大きな利得が得られるということを示している。
図形的には、を満たす3人ゲームの配分は高さの正三角形で表される。

コア

協力ゲームの代表的な解がコアである。
また、提携合理性とは、個人合理性の考え方を提携レベルに拡張し、もし利得ベクトル $x$ において、ある提携 $S$ の全メンバーの利得の合計が提携 $S$ だけで獲得可能な総利得 $v(S)$ より小さいならば、提携 $S$ (もしくはそのメンバー) は利得ベクトル $x$ に合意しないという考え方である。
定義 10.3
提携形 $n$ 人ゲームの実現可能な利得ベクトル $x$ が提携合理性を満たすとは、 $N$ の全ての提携 $S$ に対して、 $\displaystyle{\sum_{i \in S} x_i \geq v (S)}$ が成り立つ時をいう。
定義 10.4
提携形 $n$ 人ゲームのコアとは、提携合理性を満たす配分の集合である。
定理 10.1
優加法的ゲームでは、コアは他の配分に支配されない配分の集合と等しい。

例1: 起業ゲーム

起業ゲームのコアを計算する。

コアは次の等式および不等式を満たす。

$x_A + x_B + x_C = 240$
$x_A + x_B \geq 200$
$x_B + x_C \geq 100$
$x_C + x_A \geq 150$
$x_A \geq 60$
$x_B \geq 40$
$x_C \geq 20$

これを、1人提携の利得の値が0になるように、 $y_A = x_A - 60$ 、 $y_B = x_B - 40$ 、 $y_C = x_C - 20$ と変数変換をすると、下記の様になる。このような変換をゼロ正規化と呼ぶ。

$y_A + y_B + y_C = 120$
$y_A + y_B \geq 100$
$y_B + y_C \geq 40$
$y_C + y_A \geq 70$
$y_A \geq 0$
$y_B \geq 0$
$y_C \geq 0$

これを解くと、

$y_A + y_B + y_C = 120$
$0 \leq y_A \leq 80$
$0 \leq y_A \leq 80$
$0 \leq y_A \leq 80$

となる。これがこのゲームのコアである。図形で表すと下記三角形内の濃いブルー部分となる。

また、ゼロ正規化前の変数で表すと、

$x_A + x_B + x_C = 240$
$60 \leq x_A \leq 140$
$40 \leq x_B \leq 90$
$20 \leq x_C \leq 40$

となる。これは何を意味しているかと言うと、例えば

コアの範囲外の配分 $x_1 = (100, 80, 60)$ だと、AとBだけで起業した場合200万円得られるはずなので、AとBはこの配分に納得しない。
コアの範囲内の配分 $x_2 = (110, 90, 40)$ だと、全てのメンバーにとって3人で起業することが最適となるので、この配分に納得する。

つまり、コアとは、どのプレイヤーも不満を持たない配分の集合である。

例2: 多数決ゲーム

コアを持たないゲームの例として多数決ゲームを考える。

3人での多数決ゲームは次の様に定式化できる。

$v(\{1\}) = v(\{2\}) = v(\{2\}) = 0$
$v(\{1, 2\}) = v(\{2, 3\}) = v(\{3, 1\}) = 1$
$v(\{1, 2, 3\}) = 1$

このゲームの提携合理性を満たす配分の条件は、

$x_1 + x_2 + x_3 = 1$
$x_1 + x_2 \geq 1$
$x_2 + x_3 \geq 1$
$x_3 + x_1 \geq 1$
$x_1 \geq 0$
$x_2 \geq 0$
$x_3 \geq 0$

である。ここで、2〜4番目の式の両辺を足すと $x_1 + x_2 + x_3 \geq \frac{3}{2}$ となり、1番目の式に矛盾するので、提携合理性を満たす配分の集合は空集合であり、コアは存在しない。つまり、どんな配分であれ常に誰かが不満を持つ。

定理 10.2
ゼロ正規化された3人ゲームのコアが存在するための必要かつ十分条件は、
$v(\{1, 2\}) + v(\{2, 3\}) + v(\{3, 1\}) \leq 2v(\{1, 2, 3\})$
が成り立つことである。

シャープレイ値

コアとともに代表的な協力解にシャープレイ値がある。シャープレイ値はコアとは異なり、常にただ一つだけ存在する。

例1: 起業ゲーム

シャープレイ値の計算方法を起業ゲームの例で見ていく。

特性関数を再掲する。

$v(\{A\}) = 60, \: v(\{B\}) = 40, \: v(\{C\}) = 20$
$v(\{A, B\}) = 200, \: v(\{B, C\}) = 100, \: v(\{C, A\}) = 150$
$v(\{A, B, C\}) = 240$

シャープレイ値は、3人が順に起業に参加するとして、各プレイヤーが参加すると、どれだけ収益を増やすか (限界貢献度) に注目する。起業に参加する順番によって各プレイヤーの限界貢献度は変わってくるが、各順序は同じ確率で実現すると想定して、各順序の限界貢献度の平均値を算出する。この値をシャープレイ値という。

参加順序	Aの限界貢献度	Bの限界貢献度	Cの限界貢献度
A -> B -> C	60	140	40
A -> C -> B	60	90	90
B -> A -> C	160	40	40
B -> C -> A	140	40	60
C -> A -> B	130	90	20
C -> B -> A	140	80	20
平均値	115	80	45

シャープレイは、パレート最適性、ナルプレイヤー、対称性、加法性という4つの公理を満たす唯一の配分がシャープレイ値として導かれることを証明した。

ナルプレイヤーの公理: どんな提携に対する限界貢献度も0であるプレイヤー (ナルプレイヤー) のシャープレイ値は0である。
対称性の公理: 全ての提携に対する限界貢献度が等しい2人のプレイヤー (対称なプレイヤー) のシャープレイ値は等しい。
加法性の公理: 2つのゲーム $u$ と $v$ の和として定式化されるゲーム $u + v$ のシャープレイ値は、それぞれのゲームのシャープレイ値の和である。

非協力ゲーム理論によるアプローチ (戦略的アプローチ)

9章と同様に、交渉のプロセスをダイナミックなゲームとして定式化し、協力ゲーム理論による協力解が非協力ゲーム理論による均衡点 (ナッシュ均衡点や部分ゲーム完全均衡点) によって実現できるかどうかを考える。特に、コアやシャープレイ値が公理として前提とするパレート最適性が交渉ゲームの均衡として実現できるかどうかに注目する。尚、優加法的ゲームでは、パレート最適性は全体提携の形成を意味する。

例3: 3人対称ゲーム

ゲームの状況

プレイヤー集合は $N = \{1, 2, 3\}$
特性関数は、
- $v(\{1\}) = v(\{2\}) = v(\{3\}) = 0$
- $v(\{1, 2\}) = v(\{2, 3\}) = v(\{3, 1\}) = a$ (但し、 $0 \lt a \lt 1$ )
- $v(\{1, 2, 3\}) = 1$

つまり、「3人が協力すると全体で利得1が得られる。2人だけの協力では1より小さい利得aが得られる。協力しない時の利得は0。この時、どの様な提携が形成され、利得はどの様に分配されるだろうか？」という問題を考える。

ダイナミックなゲームとして定式化

このゲーム状況は、交互提案ゲームとして定式化できる。
誰が提案者になるかは交渉に大きな影響を持つので、提案者はランダムに選ばれるものとする。
交渉のルール
1. 提案者がランダムに選ばれる。
2. 選ばれた提案者は、提携とその利得分配を提案する。
3. 提携の他のメンバーが順次、提案を受け入れるかどうかを選択する。
4. もし全員が提案を受け入れるならばゲームは終了。もし誰かが提案を拒否すれば、1に戻る。
将来利得に対する割引因子を $\delta$ とする。
この交渉ルールはランダムな提案者ルールと呼ばれている。

部分ゲーム完全均衡点

ここでは、どの交渉ラウンドでもプレイヤーは同じ戦略を採用する定常部分ゲーム完全均衡点に注目して、全員提携が形成される条件を求める。

プレイヤーの期待利得の条件
- 被提案プレイヤーは、 $\delta v_i$ 以上の利得を提案されたらそれを受け入れるのが合理的である。なぜなら、交渉を拒否すれば、交渉は次のラウンドに進み、プレイヤー $i$ の割引期待利得は $\delta v_i$ となるからである。
- 従って、もしプレイヤー1が提案者に選ばれた場合は、3人提携の利得分配として $(1 - \delta v_2 - \delta v_3, \delta v_2, \delta v_3)$ を提案し、プレイヤー2と3はこれを受け入れる。
- これにより、プレイヤー1の期待利得は $v_1 = \frac{1}{3} (1 - \delta v_2 - \delta v_3) + \frac{2}{3} \delta v_1$ となる。右辺第1項は、提案者の時の利得、第2項は被提案者のときの利得を示している。
- この式を変形し、プレイヤー2と3に関しても同様に考えると、下記が成り立つ。
  - $(3 - 2 \delta ) v_1 + \delta v_2 + \delta v_3 = 1$
  - $\delta v_1 + (3 - 2 \delta ) v_2 + \delta v_3 = 1$
  - $\delta v_1 + \delta v_2 + (3 - 2 \delta ) v_3 = 1$
- これを解くと、 $v_1 = v_2 = v_3 = \frac{1}{3}$ となる。
a の条件
- また、全員提携が2人提携よりも最適な提案であるためには、 $1 - \frac{2}{3} \delta \geq a - \frac{1}{3} \delta$ である必要がある。ここで左辺は、全員提携を提案する時の提案者の利得であり、右辺は2人提携を提案する時の利得である。
- これを解くと、 $1 - \frac{1}{3} \delta \geq a$ となる。
- そして、割引因子 $\delta$ が限りなく1に近い、つまりプレイヤーが忍耐強いとき、 $a \leq \frac{2}{3}$ が成り立つ。
- 定理 10.2 (ゼロ正規化された3人ゲームのコアが存在するための必要かつ十分条件は、 $v(\{1, 2\}) + v(\{2, 3\}) + v(\{3, 1\}) \leq 2v(\{1, 2, 3\})$ が成り立つことである) より、これは、3人対称ゲームのコアが存在するための必要かつ十分条件である。

以上をまとめると、割引因子が限りなく1に近い時、ランダムな提案者ルールをもつ交渉ゲームの定常部分ゲーム完全均衡点において、3人対称ゲームの全員提携が形成されるための必要かつ十分条件は、ゲームのコアが存在することである。この時、プレイヤーの均衡期待利得は $\frac{1}{3}$ であり、提携内の分配は均等分配 $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ となる。