第3章 協力ゲームの古典理論 - econ.keio.ac.jp

allFIN : 2011/4/4(18:34)
第 3 章 協力ゲームの古典理論
3.1
凸集合と凹関数
凸性についてはこれまでにも言及してきたが，ここでは本書で使う
範囲の基礎的用語などについてまとめておこう．
集合 X ⊆ n が凸集合 (convex set) であるとは，
x, y ∈ X, λ ∈ [0, 1] =⇒ λx + (1 − λ)y ∈ X
となることをいう．ここに，[0, 1] := {λ ∈ | 0 ≤ λ ≤ 1} である．
線分や三角形，球などは身近な凸集合である．また，１点のみから
なる集合や全空間，さらには空集合も自明な凸集合である．
２点 x, y ∈ n と λ ∈ [0, 1] に対し，λx + (1 − λ)y を２点 x, y の凸
結合（convex combination）という．λ = 0, 1 であるときは真の凸結
合という．
凸集合 X の端点 (extreme point) とは，X の異なる２点の真の凸
結合としてあらわすことが出来ない点 x ∈ X をいう．集合 X の端点
の集合を ext X と書く．
119
allFIN : 2011/4/4(18:34)
第 3 章 協力ゲームの古典理論
集合 Y を含む最小の凸集合を Y の凸包 (convex hull) といい，ch Y
と書く．すると，クライン−ミルマン (Krein-Milman) の定理とは
Y が n のコンパクト凸集合ならば， Y = ch ext Y
であることを述べている1 ．この定理は，後で凸ゲームのコアを特徴
付けるときに用いられる．
関数 u : n → が凹関数（concave function）であるとは，任意
の x, y ∈ n と任意の λ ∈ [0, 1] に対して
u(λx + (1 − λ)y) ≥ λu(x) + (1 − λ)u(y)
となることである．
凹関数の和は凹関数であることは定義から明らかである．
凸集合 X ⊆ n で定義された凹関数は定義域の内点で連続である2 ．
n
それゆえ，非負象限 n
+ で定義された凹関数は正象限 ++ におけ
る連続関数である．定義域の境界で連続であるとは限らないことは，
u(0) = 0，u(x) = 1 − x2 , x > 0 をみたす関数 u : + → は凹であ
るが原点で不連続であることからわかる．
−u が凹関数であるとき，u は凸関数（convex function）であると
いう．
関数 u : n → が準凹関数（quasiconcave function）であるとは，
任意の x, y ∈ n と任意の λ ∈ [0, 1] に対して
u(x) ≥ u(y)
1 証明はたとえば
=⇒
u(λx + (1 − λ)y) ≥ u(y)
Ichiishi [17, 1983] など参照のこと．
2 証明はたとえば Mangasarian [22, 1969] など参照のこと．
120
allFIN : 2011/4/4(18:34)
3.1. 凸集合と凹関数
であることをいう．
凹関数は準凹関数であることも定義から直ちにしたがう．
正象限での２変数関数 f (x, y) = xy は準凹関数であるが凹関数で
はない．凹でないことは，２点 (1, 1) と (2, 2)，λ =
1
2
をとれば確か
められる．準凹であることは，たとえば 相加平均 ≥ 相乗平均 で
あることを使って定義から直接に示すことができる．
準凹関数の和は準凹関数であるとは限らない．たとえば関数 h(x, y) =
2
x + y 2 は 2+ で準凹ではないが，関数 x2 + 0y 2 と 0x2 + y 2 は 2+ で
いずれも準凹であることを確かめることができる．
次の不等式はジャンセンの不等式 (Jensen’s inequality) と呼ば
れるもので，市場ゲームのところで必要となる．
関数 f : n → が凹関数 ⇐⇒ 任意有限 m 個
m
m
の xi ∈ n の凸結合
p i xi
ただし
pi = 1, pi ≥
i=1
i=1
0, i = 1, . . . , m に対して，
f
m
i=1
m
pi xi ≥
pi f (xi ).
i=1
証明. 十分性は定義より明らか．逆は数学的帰納法によ
る．m = 2 ならば凹関数の定義からしたがう．m > 2 で
成立するならば m + 1 でも成立することは以下のように
確かめられる．
121
allFIN : 2011/4/4(18:34)
第 3 章 協力ゲームの古典理論
f
m+1
i=1
=f
pi xi
m
pi xi + pm+1 xm+1
i=1
m
pi
= f [1 − pm+1 ]
xi + pm+1 xm+1
1 − pm+1
i=1
m
pi
≥ [1 − pm+1 ]f
xi
1 − pm+1
i=1
+ pm+1 f (xm+1 )
≥ [1 − pm+1 ]
m
i=1
pi
f (xi )
1 − pm+1
+ pm+1 f (xm+1 )
=
m
pi f (xi ) + pm+1 f (xm+1 )
i=1
=
m+1
pi f (xi ).
i=1
3.2
3.2.1
シャープレイ値とポテンシャル
シャープレイ値
ゲーム (N, v) のシャープレイ値は，各 i ∈ N の利得が
1 φ(v)i =
|S|!(n − |S| − 1)![v(S ∪ {i}) − v(S)]
n!
S⊆N \{i}
122
(3.1)
allFIN : 2011/4/4(18:34)
3.2. シャープレイ値とポテンシャル
で与えられる利得ベクトル φ(v) である．ここでは，オーマン（Aumann
[1, 1989]）による公理系からの導出とともに，ハート＝マスコレル
(Hart and Mas-Colell [15, 1989]) のポテンシャル関数からの導出を紹
介し，また，ハルサニー値 (Harsanyi [14, 1977]) としての特徴付けに
も触れる．
/S か
定義 3.1. プレイヤー i, j ∈ N が互いに交代可能であるとは i ∈
つj∈
/ S であるようなすべての S ⊆ N に対して,
v(S ∪ {i}) = v(S ∪ {j})
となることをいう．
/ S である
また，プレイヤー i ∈ N が無為プレイヤーであるとは i ∈
ようなすべての S ⊆ N に対して
v(S ∪ {i}) = v(S)
となることをいう．
v(S ∪ {i}) = v(S) + v({i}) をみたすプレイヤー i を一般に駄身
（dummy) というが，無為プレイヤー i とは v({i}) = 0 である駄身
のことである．
定義 3.2. GN ⊆ 2
n
−1
をすべてのゲーム v の集合とするとき，以
下の条件をみたす関数 φ : GN → n を GN 上のシャープレイ値
(Shapley value) またはたんに値 (the value ) という.
対称性 ゲーム v におけるすべての互いに交代可能なプレイヤー i と
j に対して, φ(v)i = φ(v)j .
無為プレイヤー ゲーム v のすべての無為プレイヤー i に対して φ(v)i =
0.
効率性
i∈N
φ(v)i = v(N ).
123