第Ⅱ部 協力ゲームの理論
第10章 コア
2008/07/01(火)
ゲーム理論合宿
内容
• 配分の支配
– 配分間の支配関係
– 提携合理性と支配関係
• コア
– コアの定義
– コアの存在
• 非分割財市場のコア
• 負の公共財~ごみ処理ゲーム
• 凸ゲーム
– 凸ゲーム
– 凸ゲームのコアとシャープレイ値
1
1.配分の支配
• ベンチャー企業をプログラマー1,2と営業3で起こす
平均プログラマ1 敏腕プログラマ2
シャープレイ値は
営業3
 (v)  (30,40,50)
いま、3人で提携することを考えたときに、利益の配分はどのようになるかを考える
(提携形3人ゲームの配分の集合を図示することを考える)
一般に3人ゲーム(N={1, 2, 3},v)の配分は次のように表される
2
1.配分の支配
3次元の利得ベクトルで書くと(a)
高さv(N)の正三角形で表すと(b)
3
1.配分の支配
1
配分(120,0,0)
配分(0,120,0)
配分(0,0,120)
配分(30,40,50)
配分(20,45,55)
50
40
30
2
3
4
1.配分の支配
シャープレイ値的に(30,40,50)という配分にしましょう!
ふざけんな!オレら二人だけで組むと100稼げるんだ!
せめて(20,45,55)はもらわないと!
・・・・。(涙目)
配分a(30,40,50)は提携{2,3}に関して
配分b(20,45,55)に支配されているという
5
1.配分の支配
定義1.配分間の支配
ゲーム(N,v)において、2つの配分x,yについて、提携Sに関して
(i)選好条件
(ii)実現可能条件
xi  yi i  S
x
i
iS
 v(S )
の2つの条件が成立するとき、提携Sに関して、配分xは配分y
を支配するといい、次のように書く
x dom y
S
選好条件:提携Sのすべてのメンバーにとって、配分xが配分yより大きい利得が
得られるため、yよりもxを選好する
実現可能条件:そのような配分xを提携Sだけで実現可能である
6
1.配分の支配
優加法的提携形n人ゲームにおける2つの配分をx,yとすると
y dom x x dom y
が可能なのはn≧5のとき。
●提携合理性について
ゲーム(N,v)において、利得ベクトルxがすべての提携にとって
x
i
 v( S )
iS
をみたすとき、この利得ベクトルは提携合理的であるという
7
2.コアの理論
支配される配分はその提携によって拒否され、実現されること
は難しい。そこで、コアという解を定義する
●コアの定義(支配関係による定義)
ゲーム(N,v)において、いかなる配分にも支配されない配分の
集合をコアとよぶ
●コアの定義(提携合理性による定義)
ゲーム(N,v,A)が弱優加法的であるならば、コアは提携合理的
配分の集合である。すなわち、コアをC(v)とすると


C (v)   x  A :  xi  v(S ) S  N 
iS


である
8
2.コアの理論
コアは一次不等式の組の解として与えられ、n次元ベクトル
空間の有界閉集合である
コアはシャープレイ値と異なり、配分の集合として定義された解
ただ一つの配分を指定する解ではない
コアが空集合でないゲームはプレイヤー全体が共同で行動し
た方が部分的な提携で行動するより、大きな利得が得られ、全
体としての協力関係が安定的であることを意味する
コアが空集合のゲームは全体提携の値に対して、部分提携の
値が相対的に大きく、全体的な協力関係が不安定であることを
意味する
9
2.コアの理論
3人ゲームの例
提携合理性の条件は
全体合理性の条件は
これらの条件から図示したのが次頁
10
2.コアの理論
提携合理性の条件を
コアの制約条件という
制約条件は
基本三角形上に図示でき、
三角形DEFがコアを示す
11
2.コアの理論
別の例
この場合、
コアは空である
12
2.コアの理論
• 3人ゲームでコアが空でない条件
プレイヤーの集合をN={1,2,3}としたとき、優加法的提携形
3人ゲームのコアが存在するための必要十分条件は次の
不等式を満たすことである。
2v(123)  v(12)  v(13)  v(23)
13
3.非分割財市場のコア
非分割財:文字通り分割できない財。家、車など。
供給者1:a円以上なら売ってもいい
需要者2:b円以下なら買ってもいい
需要者3:c円以下なら買ってもいい
ここではa<b<cとする
価格
c
価格Pは需要曲線と供給曲線の
交点として定まるから、b≦p≦c
となる
b
実際、どこに決まるかは交渉による
ので、提携形ゲームとして表現
a
数量
1
2
14
3.非分割財市場のコア
売らなくてもプレイヤー1はaの価値をもった家を持ってるので、
v(1)  a, v(2)  0, v(3)  0
ここで、提携は売買と考えられるので、
v(12)  b, v(13)  c, v(23)  0
三人で交渉され、もっとも高い価格で売買がなされると
v(123)  c
このゲームのコアは
または
と表現され、コアを求めることによって、市場における取引の結果
として、各プレイヤーが受け取る価値と価格の範囲を求めること
ができる
15
3.非分割市場財のコア
具体的な数値例としてa=30, b=80, c=120とすると
シャープレイ値は
Φ(v)=(80,10,30)で コ
アに属さない。これは提
携{1,2}が満たされる状
況も考えているため。
実際に提携される構造
は{1,3}{2}となる
16
4.凸ゲーム
• ゲーム(N,v)において、提携Sにプレイヤーiが参加し
たときの限界貢献度v(S∪{i})-v(S)が提携の規模が
大きくなるにつれて、常に増加するとき。すなわち、
• 任意のi∈Nと任意のS⊂T⊂N-{i}について
v(S {i})  v(S )  v(T {i})  v(T )
のとき、このゲームを凸ゲームという
17
4.凸ゲーム
• 凸ゲームの性質
• N人凸ゲームにおいてコアは空でなく、かつその範囲が広く、
任意のiについて境界xi=v(i)と共通部分をもつ
• 凸ゲームのシャープレイ値はコアに含まれる
18
ダウンロード

game10