제1장 공조적 2인 게임

(1)

1

제1장 공조적 2인 게임

(2-person cooperative Game)

4. Nucleolus (중핵)

(2)

2/25

4. Nucleolus (중핵)



Core는 전에 언급한 것과 같이 개인의 합리성(Individual Rationality)과 단체의 합리성(Group Rationality)의 교집 합임.



이를 식으로 한번에 표시하면,



여기서 S는 가능한 연합(coalition, 수학적으로는 가능한 부분집합), x는 분배를 나타냄. 즉, 어떤 분배가 core이 기 위해서는 각 연합이 성취할 수 있는 최소(확보된) 금 액보다 분배된 금액이 각 연합에 있어서 모두 크거나 같 아야 함.







S i

x

i

S

v ( )

(3)

3/25

4. Nucleolus (중핵)



2인 게임의 경우를 그림으로 나타내면, 오른쪽과 같음.



여기서 X

₁

, X

₂

는 분배를 나타냄.

이중 특정분배(x

₁

, x

₂

)가 core이 기 위해서는 다음을 만족해야 함



즉, 단체합리성은 다음 식(click)



개인합리성은 다음식들로 표현

됨.(click)

성취가능한 분배[v(1,2)]

단체합리성 초기 분배

개인합리성 CORE!

X

₁

X

₂

2

)

1

2 , 1

( x x

v  

2 1

) 2 (

) 1 (

x v



(x₁

, x

₂)

v(1) v(2)

v(1,2)

(4)

4/25

4. Nucleolus (중핵)

 여러 가지 core의 예

A

B C

A의 보상이 어떻게 되던지 관계없이, B와 C의 공조로 창출 수 있는 효용공간 (utility space)

B의 보상이 어떻게 되던지 관계없이, A와 C의 공조로 창출 수 있는 효용공간

A,B,C가 공조하는 경우 측면

측면

(5)

5/25

4. Nucleolus (중핵)

 여러 가지 core의 예(계속)

A

B C

유일한(unique) Core 빈(Empty) Core=

Core가 없는 경우 측면

측면

(6)

4. Nucleolus (중핵)

 Core는 앞에서도 보았듯이 유일한 해를 가져오기 어 려움.

 따라서 이러한 커다란 해의 집합을 줄이려는 노력의 하나가 중핵(中核, 핵소체;Nucleolus) 임.

 일전의 부동산거래 게임을 약간 변형하여 예를 들도 록 함.

 3인의 선수가 있으므로 3각시장(Three-Cornered

Market)게임이라고 부르기로 함. 나중에 왜 이렇게

부르는지 이해가 될 것임.

(7)

7/25

4. Nucleolus (중핵)

 농부(F: farmer)가 1억원짜리 땅을 보유. 즉, 자신이 농경지로 쓰려면 1억원의 가치가 있음. 1억원 이하 로는 팔려하지 않음.

 공장부지를 필요로 하는 사업가(M; Manufacturer)는 공장부지로 쓰기위하여 2억원까지 지불할 용의가 있 음.

 땅투기회사(S; Subdivider)는 이 땅을 구입하여 여러 개로 나누어 팔아 3억원의 이익을 챙길 수 있음. 따 라서 3억원 이상으로는 사지 않음.

 이를 특성함수로 나타내면 다음과 같음.

(8)

4. Nucleolus (중핵)

Coalitions (K)

F M S FM FS MS FMS

V(K) 1 0 0 2 3 0 3

 예를 들어, 농부(F)가 사업가(M)에게 땅을 p에 판다 면, F는 p를, M은 2-p의 잉여를 가져감.

 초기의 보상벡터는 (v(F), v(M), v(S)) = (1,0,0) 임.

 모든 거래가능성 및 가능한 보상을 그림으로 나타내

면 다음과 같음.

(9)

9/25

4. Nucleolus (중핵)

거래이전,

최초의 보상벡터 (F,M,S)=(1,0,0).

이점 이하로 갈 수는 없음.

왜냐하면 1억원 이하로 팔 지는 않을 것이므로.

따라서, (click) 3인 부동산 거래 게임의 보상 공간

F M

S

3인 공조시

(10)

4. Nucleolus (중핵)

F의 경우 최상의 거래는 3억원을 받고 기획사

에게 파는 것, 보상벡터는 (F,M,S)=(3,0,0)이 됨. (click)

F M

S

S의 경우 최상의 거래는 1 억원을 주고 농부로 부터 사는 것, (F,M,S)=(1,0,2) 가 됨. (click)

M의 경우 최상의 거래는 1 억원을 주고 F에게서 사는 것, 3억원에 다시 팔 수도 있는 땅을 1억원 주었 으니까 보상은 2억원. 즉.

(1,2,0)가 됨. (click)

왜 (F,M,S)= (1,1,0) 이 아닐까? 이는 FM만 의 공조만으로도

성취할 수 있는 보상임.

FMS가 공조를 한다면, M이 1에 사고, 다시 S 에게 3에 팔 경우, 보 상은 2가 됨 (1,2,0).

(1,1,0)

FM만이 공조하는 경우

(11)

11/25

4. Nucleolus (중핵)

F M

S 이외의 3인 공조시 모든 거래가격

(1억원이상)을 고려하면 거래가능한 구역은 삼각형이 됨 (click).

(1,2,0)

(3,0,0)

(1,0,2) FM은 둘만의 공조만으로도 이 수준의 보상((2,0,0): F가 M에 게 2억원에 파는 경우)을 확보 할 수 있음. 하지만, S와 공조한 다면 이 이상을 받으려 할 것임.

이선을 수직으로 삼각형에 투사 하면(click),

이 선과 같이 삼각형 표면을 지나감.

(2,0,1)

(1,1,0): F가 M에게 1억원에 팔고 F가 공장을 짓는 경우

3인 공조시

성취가능한 효용

녹색삼각형

(12)

4. Nucleolus (중핵)

F M

S

2. 연두색 삼각형 위에서 Coalition MS는 공조할 경우 보상이 (0,0)이고 따라서 삼각형 표면 어디로 이동하던지

움직이면 됨. 즉 적색점선이 왼쪽으로 이동하면 OK.

(1,2,0)

(F,M,S)=(3,0,0) (1,0,2)

3. Coalition FS는 M과의 공조 없이도 이 파란 점선의 보상을 보장 받음. 오른쪽으로는 이동 할 수 없고, 왼쪽으로 이동시에는 오히려 보상이 줄어 들게 되므로 이 파란점선 위에서 움직이는 것 만을 허용할 것임.

1. Coalition FM는 이 자주색 점선 보다 보상을 더 가져다 주는 경우에만 S와 공조할 것 임. 따라서 FMS 셋의 공조시 최고 보상을 나타내는 연두색 삼각형에서는 이 점선 아래쪽 만이 core의 조건을 만족함.

아래쪽에서만이 FMS가 FM을 block 함.

(2,0,1)

(13)

13/25

4. Nucleolus (중핵)

• 정리하면, FM limit 선은 아래로만, MS limit선은 북서쪽 으로만, FS limit선위에서만 움직여야 block당하지 않음.

• 각 각 2인 공조 보다 나은 보상을 가져다 주는 따라서

봉쇄당하지 않는 3인 공조 부분은 파란실선 임. 그렇다면 core는?

FS Limit MS Limit FM Limit

(1,2,0) (3,0,0) (1,0,2)

(2,0,1)

여기가 바로 CORE!!!

S=0

*삼각형이므로 3각시장(Three-Cornered Market) 게임이라고 부르기로 함.

(14)

4. Nucleolus (중핵)



하지만 아직 Core는 여러 개(선, 무한이 많은 Core) 임.



줄이는 방법이 없을까?  Nucleolus!



Nucleolus(중핵)의 착안점: 가장 불만족스럽게 생각하는 연합을 우선적으로 불만을 줄임. 예를 들어, 전 그림에서

(F,M,S)=(3,0,0)일 경우, F가 3을 가져가고 나머지는 0을 가져감.

따라서 M과 S는 불만. 따라서 F의 보상을 줄이면서 M과 S의 보 상을 늘리면 덜 불만스럽게 생각할 것임.



이러한 불만족의 수준을 나타내기 위하여 과잉(excess)을 정의

해 봄.

(15)

15/25

4. Nucleolus (중핵)



과잉은 연합의 가치(v(K); 연합을 통하여 보장받는 최소 의 보상; 연합 K의 특성함수값)와 실제 분배된 각 선수들 의 보상( α

_i

)의 합과의 차이 임.



예를 들어, F혼자서는 1의 보상을 보장받으나(v(F)=1)), 실제로 3의 보상을 받는다면? F가 2만큼 더 받았다고 생 각할 수 있음. 잉여(surplus)와 유사한 개념임. 즉,









K i

K

i

v K

e ( ,  ) ( ) 

2 3

1 1

) ( )

,

(         

 F

K i

F i

v F

e   

(16)

4. Nucleolus (중핵)



따라서 Core는 이러한 과잉이 0보다 작거나 같은 보상의 집합임. 즉,



또는, core 는 다음을 만족하는 보상( α

_i

)의 집합임.

(chapter1-3.ppt, slide 20 참조)

0 )

( )

,

(    

iK

K

i

v K

e  

 



K i

v ( ) 

(17)

17/25

4. Nucleolus (중핵)

 Nucleolus는 이러한 과잉(excess;불만족)이 가장 큰 것을 최소한으로 만드는 보상의 집합 을 말함.

 Schmeidler(1967)가 고안해 냄.

 이전의 3각시장게임을 다시 보도록 함. 우선

여기서 과잉을 계산해 보면 다음과 같음.

(18)

4. Nucleolus (중핵)



예를 들어, β=(β

_{F ,}

β

_{M ,}

β

_S

)

=(3,0,0)에서는

0 ) 0 0 3 ( 3 ) (

) (

) , (

0 ) 0 0 ( 0 ) (

) ( ) , (

0 ) 0 3 ( 3 ) (

) ( ) , (

1 )

0 3 ( 2 ) (

) (

) , (

0 0 0 )

( ) , (

0 0 0 )

( ) , (

2 3

1 )

( ) , (



















































































S M

F S M

S F

M F

S M F

FMS v

FMS e

MS v MS

e

FS v FS

e

FM v FM

e

S v S

e

M v M

e

F v F

e



(1,2,0)

β=(3,0,0)

(1,0,2)

α=(2,0,1)

S=0

(19)

19/25

4. Nucleolus (중핵)



α=(α

_F

α

_M

α

_S

) =(2,0,1)에서는

(3,0,0) 0

) 1 0 2 ( 3 ) (

) (

) , (

1 )

1 0 ( 0 ) (

) ( )

, (

0 ) 1 2 ( 3 ) (

) ( )

, (

0 ) 0 2 ( 2 ) (

) (

) , (

1 1

0 )

( )

, (

0 0 0 )

( )

, (

1 2

1 )

( )

, (























































































S M

F S M

S F

M F

S M F

FMS v

FMS e

MS v MS

e

FS v FS

e

FM v

FM e

S v S

e

M v M

e

F v F

e



(1,2,0)

(1,0,2)

α=(2,0,1)

S=0

(20)

20/25

4. Nucleolus (중핵)



δ=(δ

_{F ,}

δ

_{M ,}

δ

_S

) =(2.5,0,0.5)에 서는



τ 와 ρ 에서는?(click)

δ =(2.5,0,0.5)

0 ) 5 . 0 0 5 . 2 ( 3 ) (

) (

) , (

5 . 0 )

5 . 0 0 ( 0 ) (

) ( ) , (

0 ) 5 . 0 5 . 2 ( 3 ) (

) ( ) , (

5 . 0 )

0 5 . 2 ( 2 ) (

) (

) , (

5 . 0 5

. 0 0 )

( ) , (

0 0 0 )

( ) , (

5 . 1 5

. 2 1 )

( ) , (



























































































S M

F S M

S F

M F

S M F

FMS v

FMS e

MS v MS

e

FS v FS

e

FM v FM

e

S v S

e

M v M

e

F v F

e



(1,2,0) β=(3,0,0)

(1,0,2)

α=(2,0,1)

S=0

τ= (2.25,0,0.75) ρ =(2.75,0,0.25)

(21)

21/25

4. Nucleolus (중핵)



τ 에서는,



ρ 에서는,

0 ) 75 . 0 0 25 . 2 ( 3 ) (

) (

) , (

75 . 0 ) 75 . 0 0 ( 0 ) (

) ( ) , (

0 ) 75 . 0 25 . 2 ( 3 ) (

) ( ) , (

25 . 0 ) 0 25 . 2 ( 2 ) (

) ( ) , (

75 . 0 75 . 0 0 )

( ) , (

0 0 0 )

( ) , (

25 . 1 25 . 2 1 )

( ) , (



























































































S M F

S M

S F

M F S

M F

FMS v

FMS e

MS v MS

e

FS v FS

e

FM v FM

e

S v S

e

M v M

e

F v F

e



0 ) 25 . 0 0 75 . 2 ( 3 ) (

) (

) , (

25 . 0 )

25 . 0 0 ( 0 ) (

) ( ) , (

0 ) 25 . 0 75 . 2 ( 3 ) (

) ( ) , (

75 . 0 )

0 75 . 2 ( 2 ) (

) ( ) , (

25 . 0 25

. 0 0 )

( ) , (

0 0 0 )

( ) , (

75 . 1 75

. 2 1 )

( ) , (



























































































S M

F S M

S F

M F

S M F

FMS v

FMS e

MS v MS

e

FS v FS

e

FM v FM

e

S v S

e

M v M

e

F v F

e



(22)

4. Nucleolus (중핵)



이러한 각 점에서의 과잉 (excess)를 표로 정리하면 다음과 같음.



잉여 중 극대를 표시하 면?(click 4번)



불만을 줄이려면 어느 쪽으 로 움직여야 할까?(click)

점/

연합

α τ σ ρ β F

_-1 _-1.25 _-1.5 _-1.75 _-2

M

₀ ₀ ₀ ₀ ₀

S

_-1 _-0.75 _-0.5 _-0.25 ₀

FM

₀ _-0.25 _-0.5 _-0.75 _-1

FS

₀ ₀ ₀ ₀ ₀

MS

_-1 _-0.75 _-0.5 _-0.25 ₀

FMS

₀ ₀ ₀ ₀ ₀

β=(3, 0, 0) α=(2, 0, 1)

ρ =(2.75, 0, 0.25) δ =(2.5, 0, 0.5)

τ= (2.25, 0, 0.75)

(23)

23/25

4. Nucleolus (중핵)

 만일 똑같은 속도(rate, 0.25씩)로 불만(과잉의 절대값)을 줄여나간다면 어느 점에서 멈추어야 각 연합에 대한 불만이 가장 작아지게 될

까?(click)

 바로 이러한 보상집합 (vector)를 중핵

(nucleolus)라고 함.

점/

연합

α τ δ ρ β F

_-1 _-1.25 _-1.5 _-1.75 _-2

M

₀ ₀ ₀ ₀ ₀

S

_-1 _-0.75 _-0.5 _-0.25 ₀

FM

₀ _-0.25 _-0.5 _-0.75 _-1

FS

₀ ₀ ₀ ₀ ₀

MS

_-1 _-0.75 _-0.5 _-0.25 ₀

FMS

₀ ₀ ₀ ₀ ₀

(24)

4. Nucleolus (중핵)

 중핵을 구하기 위하여 이러한 복잡한 계산이 항상 필 요할까? NO.

 중핵은 core의 겉의 벽들(한계선, 한계점)을 안쪽으 로 밀면서, core 가 없어지기 직전에 멈추면, 그 남 은 것이 nucleolus임.

 다시 말해서, 중핵은 core의 median(중앙, center)

또는 위치(location)라고 할 수 있으며, core가 없을

때에는 특성함수값이 일정한 비율로 조정될 때 가장

먼저 나타날 core의 부분, 즉, 잠재적인 위치를 나타

냄.

(25)

25/25

4. Nucleolus (중핵)

 3각시장게임의 예에서는 다음과 같이 중핵을 구할 수 있음.

β=(3, 0, 0)

α=(2, 0, 1) (2+3)/2=2.5, (0+0)/2=0, (1+0)/2=0.5

즉, δ = (2.5, 0, 0.5)

• Core가 1차원(선)인 경우는 산술평균.

• Core가 2차원(면)인 경우? Nucleolus는 산술평균이 아니라 기하평균임.

예) 2와 3의 산술평균=2.5, 2와 3의 기하평균= 23  6 2.45

(26)

26/25

4. Nucleolus (중핵)

 이러한 중핵은 정부가 세금을 과하거나 보조를 할 때 사회구성원의 불만을 최소화하는데 이용될 수 있음.

 또한, 전술한 바와 같이 중핵은 core의 median(중 앙=기하평균, core가 선이면 기하평균과 산술평균이 같아짐)이라고 할 수 있음.

 하지만, 중핵은 core의 mean(산술평균)은 아님.

 이러한 core의 평균개념을 도입하여 만들어진 해가

바로 Shapley Value임.

(27)

27/25

4. Shapley Value?

F M

S

(1,2,0)

(3,0,0) (1,0,2)

SV=(1+7/6, 1/6, 4/6)

1/6 4/6

1+7/6

0 1 2 3 2

1

F S

1.4142

2.5

0.7071

Core

Nucleolus 9-21-12