仁の求め方についての補足 - NABENAVI.net

第 12 章「協力ゲームの理論」における仁についての補足
渡辺隆裕
April 30, 2014
1
協力ゲームの正規化
協力ゲームにおけるほとんどの解（コア，仁，シャープレイ値）は，特性関数の正の 1 次変換に
対して影響を受けないことが知られている．
3 人ゲームで説明すると，プレイヤーを A,B,C とし，ある正の数 r とある 3 つの実数（正でも
負でも良い）sA ，sB ，sC に対して，特性関数 v を以下のような特性関数 w に変換したとしよう．
w(A) = rv(A) + sA ,
w(B) = rv(B) + sB ,
w(C) = rv(C) + sC ,
w(AB) = rv(AB) + (sA + sB ), w(BC) = rv(BC) + (sB + sC ), w(AC) = rv(AC) + (sA + sC ),
w(ABC) = rv(ABC) + (sA + sB + sC ).
このとき新しい特性関数 w で求めた仁やシャープレイ値を (y1 , y2 , y3 ) とし，元の特性関数 v の
仁やシャープレイ値を (x1 , x2 , x3 ) とすると，
yi = rxi + si i = A, B, C,
となることが知られている．また xi が特性関数 v のコアの配分であることと，yi が特性関数 w の
コアの配分になることも同値である．
ここで r = 1，sA = −v(A)，sB = −v(B)，sC = −v(C) とすると，w(A) = w(B) = w(C) = 0
となり，ゲームの解の計算が容易になる．これをゼロ正規化と呼ぶ．仁の計算などはゼロ正規化
して行うと簡単になる．ゼロ正規化されたゲームの仁を (yA , yB , yC ) とすると
xi = yi + v(i) i = A, B, C,
とすれば，元のゲームの仁を (xA , xB , xC ) を得ることができる．
1
例 1. テキストの P462，モデル 45 をゼロ正規化してみよう．モデル 45 における特性関数は
v(A) = 6,
v(B) = 4,
v(C) = 0,
v(AB) = 18, v(BC) = 18, v(AC) = 16,
v(ABC) = 48,
であった．これをゼロ正規化すると
w(A) = v(A) − 6 = 0,
w(B) = v(B) − 4 = 0,
w(C) = v(C) − 0 = 0,
w(AB) = v(AB) − (6 + 4) = 8, w(BC) = v(BC) − (4 + 0) = 14, w(AC) = v(AC) − (6 + 0) = 10,
w(ABC) = v(ABC) − (6 + 4 + 0) = 38,
となる．このゼロ正規化されたゲームの仁を (yA , yB , yC ) として計算すると，
yA = 12, yB = 13, yC = 13,
となる．これと
xA = yA + v(A), xB = yB + v(B), xC = yC + v(C),
を使うと，元のゲームの仁 (18, 17, 13) が計算できる．
3 人ゲームの仁を求める
2
2.1
線形計画問題への帰着
一般には，仁は線形計画問題を繰り返して解くことによって得られることが知られている．こ
こでは 3 人ゲームの場合に，その線形計画問題の作り方を示し，それを用いてテキストに書かれ
ている仁の求め方について再検討する．
3 人ゲームのプレイヤーを A,B,C とし，特性関数が与えられているとする．ゼロ正規化すれば，
計算は簡単であるが，テキストと合わせるためにゼロ正規化せずに話を進める．
配分 (xA , xB , xC ) が与えられた時に，各提携の不満を表にすると以下のようになる．
提携
A
B
C
不満
v(A) − xA
v(B) − xB
vC − x(c)
AB
BC
v(AB) − (xA + xB ) v(BC) − (xB + xC )
2
AC
v(AC) − (xA + xC )
テキストの（モデル 45 の）例だと，この表は
提携
A
B
不満 6 − xA 4 − xB
C
AB
BC
AC
−x(c) 18 − (xA + xB ) 18 − (xB + xC ) 16 − (xA + xC )
である (テキストの表 12.2).
仁を求めるには，まず xA , xB , xC を xA + xB + xC = v(ABC) を満たすように動かして，表の
中の最大である不満が最小になるような xA , xB , xC を求める必要がある．表の中のどこが最大不
満になるかは分からないが，その最大不満を M とすると，すべての不満は M より小さくなって
いる．つまり M と xA , xB , xC は次の式を満たすはずである．
v(A) − xA ≤ M,
v(B) − xB ≤ M,
v(C) − xC ≤ M,
v(AB) − (xA + xB ) ≤ M, v(BC) − (xB + xC ) ≤ M, v(AC) − (xA + xC ) ≤ M,
xA + xB + xC = v(ABC).
この最大不満である M を最小化するには，以下の線形計画問題を解けば良い．
最小化 M
制約
v(A) − xA ≤ M,
v(B) − xB ≤ M, ≤
v(C) − xC ≤ M,
v(AB) − (xA + xB ) ≤ M, v(BC) − (xB + xC ) ≤ M, v(AC) − (xA + xC ) ≤ M,
xA + xB + xC = v(ABC).
(1)
テキストの例だと
最小化 M
制約
6 − xA ≤ M,
4 − xB ≤ M,
−xC ≤ M,
(2)
18 − (xA + xB ) ≤ M, 18 − (xB + xC ) ≤ M, 16 − (xA + xC ) ≤ M,
xA + xB + xC = 48
となる．
2.2
簡便な解法
この問題は，変数が xA ，xB ，xC ，M と 4 個ある（4 次元の）線形計画問題であり，図などで
解くことは一般的には難しい．そこでテキストでは，以下のように考えている．
3
1 番目の式から xA ≥ v(A) − M となる．一方，xB + xC = v(ABC) − xA を 5 番目の式 v(BC) −
(xB +xC ) ≤ M に代入し，v(BC)−(v(ABC)−xA ) ≤ M を得る．これを変形して xA ≤ v(ABC)−
v(BC) + M を得る．2 つの式を合わせると v(A) − M ≤ xA ≤ v(ABC) − v(BC) + M となる．同
様に 2 番目と 6 番目の式から，xB の範囲として v(B) − M ≤ xB ≤ v(ABC) − v(AC) + M を得
て，3 番目と 4 番目の式から v(C) − M ≤ xC ≤ v(ABC) − v(AB) + M を得る．まとめると
v(A) − M ≤ xA ≤ v(ABC) − v(BC) + M
(3)
v(B) − M ≤ xB ≤ v(ABC) − v(AC) + M
(4)
v(C) − M ≤ xC
(5)
≤ v(ABC) − v(AB) + M
(3) は，例えばテキストだと 6 − M ≤ xA ≤ 30 + M となる．(3) において M をできる限り小
さくしようとすると，一番左の項は値が大きくなり，一番右の項は値が小さくなる．したがって，
M をできる限り小さくしようとすると，xA が存在する範囲は小さくなる．
どこまで M を小さくできるか考えてみると，もし v(A) − M > v(ABC) − v(BC) + M となれば，
このような xA は存在しないことになる．したがって xA が存在する範囲で M が最小になるのは
v(A)−M = v(ABC)−v(BC)+M の時のはずである．すなわち M = 21 (v(A)+v(BC)−v(ABC))
である．テキストの例だと M = −24/2 = −12 である．またこのとき xA は，xA = v(A) − M (=
v(ABC) − v(BC) + M ) となって値は決まる．
同様に，xB が存在する範囲で M が最小になるのは M = 21 (v(B) + v(AC) − v(ABC)) であリ，
xC が存在する範囲で M が最小になるのは M = 12 (v(C) + v(AB) − v(ABC)) である．テキスト
の例だと，それぞれ M = −14，M = −15 である．
xA ，xB ，xC がすべて存在するためには，M は上記の中で一番大きい値より大きくなくてはな
らない．そこで
1
1
1
M = max{ (v(A)+v(BC)−v(ABC)), (v(B)+v(AC)−v(ABC)), (v(C)+v(AB)−v(ABC))}
2
2
2
(6)
とすれば良い．もし，第 1 項が最大値を与えるならば xA = v(A) − M (= v(ABC) − v(BC) + M )
となり，最大の不満を最小化するために A に対する配分が決まる．そしてこのときの最大の不満
は A と BC になっているはずである．
同じように第 2 項が最大値ならば，xB = v(B) − M となり，このときの最大の不満は B と AC ．
4
第 3 項が最大値ならば，xC = v(C) − M となり，このときの最大の不満は C と AB である．
テキストでは M = −12 であり xA = 18 が決まる，このときの最大の不満を持つ提携は A と BC
であり，ともに −12 である．
このように最大の不満を最小化し，1 人のプレイヤーの配分を決めることができれば，その配分
を先の問題に代入して変数を 1 つ減らし，さらに残りの不満の中の最大の不満を最小にするよう
に配分を決めてゆく．
テキストの例だと提携の不満が以下のように表せる．
提携
A
B
C
不満 6 − 18 4 − xB
AB
−xC
BC
AC
18 − (18 + xB ) 18 − (xB + xC ) 16 − (18 + xC )
さらに xA + xB + xC = 48 から，xB + xC = 48 − xA = 30 なので，これを使って xB だけの式に
直すと，
提携
A
B
不満 −12 4 − xB
C
AB
BC
AC
xB − 30 −xB −12 −32 − xB
これらの不満の最大値をまた改めて M と置いて，同様に考えると解が求められる．これがテキ
ストの解法である．
2.3
簡便な解法では失敗する場合
しかし，このようなテキストの方法では失敗する場合がある．次の例を考えてみよう．
v(A) = 0
v(B) = 0
v(C) = 0
v(AB) = 4 v(BC) = 6 v(AC) = 5
v(ABC) = 10
(6) に従って計算をすると，
1
2 (v(A)
+ v(BC) − v(ABC)) = 12 (0 + 6 − 10) = −2,
1
2 (v(B)
+ v(AC) − v(ABC)) = 12 (0 + 5 − 10) = − 25 ,
1
2 (v(C)
+ v(AB) − v(ABC)) = 12 (0 + 4 − 6) = −3
となるので M = −2 となる．xA = 2 であり，A と BC の不満は共に M = −2 で，それは全ての
提携で最大の不満となっていなければならない．
5
ここで xA + xB + xC = 10 に xA = 2 を代入して，xB + xC = 8 を得る．ここで AB の不満を
計算すると，
v(AB) − (xA + xB ) = 4 − (2 + xB ) = 2 − xB
となる．A と BC の不満が −2 で，それが最大の不満となるためには，2 − xB ≤ −2 でなければ
ならない．これより xB ≥ 4 でなければならない．
次に AC の不満を計算すると，
v(AC) − (xA + xC ) = v(AC) − (v(ABC) − xB ) = 5 − (10 − xB ) = −5 + xB
となる．xB ≥ 4 から，AC の不満は −1 以上でなければならない．しかし，これは提携の不満は
A と BC が最大であり，その値が −2 であることに矛盾してしまう．xA = 2 では最大の不満は A
と BC ではなく，AB か BC になってしまう．
このようにテキストの簡便な方法では，最大の不満を最小化することに失敗することがあり，仁
がうまく求められないことがある．最大の不満を最小化するには，やはり (1) の線形計画問題を正
確に解かなければならないのである．
3
演習問題 12.5 の解
テキスト 484 ページの演習 12.5 も同様に，テキストの簡便な方法が失敗する場合である．テキ
ストの方法で問題を解くと xA = 3000，xB = 1000，xC = 1000 となるため，当初の解答は，この
ように掲載していた（第 8 刷まで）．しかし，この解よりも xA = 1000，xB = 1000，xC = 3000
の方が最大の不満を最小にできると，ゼミ生や読者から指摘された．
実際，xA = 3000，xB = 1000，xC = 1000 における不満を計算してみる．提携の不満は
提携
A
B
C
AB
BC
AC
(7)
不満 −xA −xB
−xC
2000 − (xA + xB ) 3000 − (xB + xC ) 3000 − (xA + xC )
であるから，
提携
A
B
C
AB
BC
AC
(8)
不満 −3000 −1000 −1000 −2000 1000 −1000
6
となり，最大不満は提携 BC の 1000 である．一方，xA = 1000，xB = 1000，xC = 3000 だと，
提携
A
B
C
AB
BC
AC
(9)
不満 −1000 −1000 −3000
0
−1000 −1000
となり，最大不満は提携 AB の 0 である．(8) より (9) の方が最大不満が小さくなっており，明ら
かに xA = 3000，xB = 1000，xC = 1000 は仁ではないと分かる．
このように演習 12.5 はテキストの方法で解くと誤りであることが分かる．しかしながらこの問
題は，プレイヤー A,B に注目することで，問題を解くことができる．以下にそれを示そう．
プレイヤーと A と B は，共に自分だけの特性関数は 0 で，C と協力した時の特性関数は 3000
である．つまりプレイヤー A と B は，全く同じ立場にあり，区別がない．このようなプレイヤー
は対称的であるという．
一般に 3 人ゲームにける 2 人のプレイヤー i と j が，v(i) = v(j) であり，i, j 以外のもう一人の
プレイヤー k に対して，v(ik) = v(jk) となっているとき，プレイヤー i と j は対称的であると言
う．そして，対称的なプレイヤーは，仁やシャープレイ値では同じ配分となることが知られている．
演習 12.5 の場合，A と B が対称的であることから，仁の配分では xA = xB となる．またこれ
より仁の配分では xC = v(ABC) − (xA + xB ) = 5000 − 2xA である．したがって，これを (7) に
代入することで，すべての提携の不満を xA を用いて，以下のように表すことができる．
提携
A
B
C
AB
BC
AC
不満 −xA −xA 2xA − 5000 2000 − 2xA xA − 2000 xA − 2000
ここで xA を 0 ≤ xA ≤ 5000 の間で変化させ，最大の不満を最小化する xA を考える．各不満のグ
ラフは図 3 で与えられ，これより最大の不満が最小化するのは 2000 − 2xA = xA − 2000 のとき，
すなわち xA =
4000
3
4000 7000
である．したがって仁は ( 4000
3 , 3 , 3 ) である．
この時の不満は，以下の表になる．
提携
A
B
C
AB
BC
AC
不満
− 4000
3
− 4000
3
− 7000
3
− 2000
3
− 2000
3
− 2000
3
(10)
(9) より，(10) の方がさらに最大不満が小さくなっていることが分かる．
7
୙‶
5000
3000
2000
0
5000
-5000
-5000
図 1: 演習 12.5：xA = xB としたときの各提携の不満
8

Download Report