협력 게임

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

협력 게임은 플레이어들이 연합을 형성하여 서로 협력하고 구속력 있는 계약을 체결하는 게임을 연구하는 게임 이론의 한 분야이다. 이는 수학적 정의, 부분 게임, 특성 함수의 성질, 비협력 게임과의 관계, 해결 개념 등을 포함하며, 안정 집합, 핵심, 섀플리 값, 커널, 하르사니 배당, 핵, 볼록 협력 게임 등의 개념을 통해 분석된다. 협력 게임 이론은 기업 간 합병, 자원 분배, 투표, 국제 협약 등 현실 세계 문제 분석에 활용되며, 한국 사회 문제 해결과 더불어민주당의 정책 수립 및 집권 전략에도 시사점을 제공할 수 있다.

더 읽어볼만한 페이지

협동 - 업무 연속성 계획
업무 연속성 계획은 예기치 못한 상황 발생 시 조직의 핵심 업무를 지속하고 빠르게 복구하기 위한 사전 계획으로, 회복탄력성을 높이고 사업을 안정적으로 유지하며 이해관계자에게 미치는 영향을 최소화하는 데 목적을 둔다.
협동 - 델파이 기법
델파이 기법은 전문가들의 의견을 반복적인 피드백을 통해 수렴하여 문제를 해결하는 하향식 의견 도출 방법으로, 익명성, 정보 흐름의 구조화, 정기적인 피드백을 특징으로 하며 다양한 분야에서 활용된다.
게임 이론 - 대연정
대연정은 의원내각제 또는 이원집정부제 국가에서 대립하는 거대 정당들이 국가적 위기 극복, 정치적 봉쇄, 또는 비례대표제 하의 연립 내각 구성의 필요에 따라 연합하는 정부 형태로, 정치적 안정과 국민 통합에 기여할 수 있지만 유권자 선택권 제한 및 소수 정당 약진의 우려도 있다.
게임 이론 - 완전 정보
완전 정보 게임은 게임 이론에서 모든 플레이어가 게임의 모든 정보를 공유하는 게임을 의미하며, 체스, 틱택토, 오목 등이 이에 해당한다.
수학 - 회귀 분석
회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다.
수학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.

협력 게임

2. 협력 게임의 정의

협력 게임은 여러 플레이어들이 서로 협력하여 연합을 만들고, 이를 통해 얻는 집단적 보상을 어떻게 나눌 것인가를 다루는 게임 이론의 한 분야이다.^[4]

협력 게임은 보통 다음 두 가지 요소로 구성된다.

플레이어들의 집합 $N$
각 플레이어 연합(결합)에 대한 보상을 나타내는 특성 함수 $v$

여기서 특성 함수

v

는

N

의 모든 부분집합에 대해 특정 값을 부여한다.

v(S)

는 연합

S

에 속한 플레이어들이 얻을 수 있는 최상의 값을 의미하며, '결합 값'이라고도 한다. 일반적으로 아무도 참여하지 않는 연합의 보상은 0으로 가정한다(

v(\emptyset) = 0

).

협력 게임은 보상 대신 비용 함수(

C

)를 사용해서 나타낼 수도 있는데, 이를 비용 게임이라고 한다. 비용 게임에서 각 연합의 비용은 비용 함수를 통해 계산된다.

2. 1. 수학적 정의

협력 게임은 플레이어들의 집합과 각 플레이어 연합(결합)에 대한 특성 함수로 정의된다.^[4] 플레이어들의 집합

N

과 모든 가능한 연합에 대한 보상을 나타내는 특성 함수

v : 2^N \to \mathbb{R}

로 구성되며,

v( \emptyset ) = 0

을 만족한다. 즉, 아무도 참여하지 않는 연합의 보상은 0이다.

특성 함수

v

는 각 연합

S

가 얻을 수 있는 최상의 값, 즉 연합의 보상을 나타낸다. 이를 '결합 값'이라고도 한다. 협력 게임은 플레이어 집합

N

과 특성 함수

v

의 쌍

(N,v)

으로 표시되며, 특성 함수는 게임 분석에 자주 사용된다.

협력 게임은 보상 대신 비용 함수

C: 2^N \to \mathbb{R}

를 사용하여 표현할 수도 있다. 이를 비용 게임이라고 하며, 각 연합의 비용을 나타낸다.

보상 게임의 특성 함수

v

에 대해, 쌍대 게임인 비용 게임의 특성 함수

v^*

는 다음과 같이 정의된다.

:

v^*(S) = v(N) - v( N \setminus S ), \forall~ S \subseteq N.\,

이는 전체 연합

N

에 참여하지 않음으로써 발생하는 연합

S

의 기회 비용을 나타낸다.

비용 게임

C

의 쌍대 보상 게임

C^*

도 마찬가지로 정의할 수 있다. 협력 게임과 그 쌍대 게임은 여러 면에서 동등하며, 많은 성질을 공유한다. 예를 들어, 어떤 게임과 그 쌍대 게임의 코어는 같다.

2. 2. 협력 게임 이론의 정의

협력 게임 이론은 플레이어들이 연합을 형성하고 서로 협력하며 구속력 있는 계약을 체결할 수 있는 게임을 연구하는 게임 이론의 한 분야이다. 이 이론은 두 명 이상의 플레이어가 다른 플레이어의 안녕에 영향을 미치는 선택을 해야 하는 시나리오를 분석하는 수학적 방법을 제공한다.^[5]

협력 게임에서 플레이어들은 특정 목표나 결과를 달성하는 데 공통적인 관심을 공유한다. 플레이어들은 협력의 기초를 마련하기 위해 공통의 관심사를 식별하고 이에 동의해야 하며, 이를 통해 함께 목표를 달성하기 위해 노력할 수 있다.

협력은 플레이어 간의 의사 소통과 정보 교환을 필요로 한다. 플레이어는 상호 이익을 위한 기회를 식별하기 위해 선호도, 자원 및 제약 조건에 대한 정보를 공유해야 한다. 정보를 공유함으로써 서로의 목표를 더 잘 이해하고 함께 목표 달성을 위해 노력할 수 있다.

협력 게임에서 플레이어는 자발적으로 모여 연합을 형성하고 합의를 한다. 플레이어는 연합의 동등한 파트너여야 하며, 모든 합의는 상호 이익이 되어야 한다. 협력은 모든 당사자가 혜택의 공정한 분배를 받고 있다고 느끼는 경우에만 지속 가능하다.

협력 게임에서 플레이어 간의 합의는 구속력이 있고 의무적이다. 플레이어는 특정 행동 방침에 동의하면 이를 따를 의무가 있다. 플레이어는 서로의 약속을 지킬 것이라고 믿어야 하며, 합의를 시행할 메커니즘이 마련되어 있어야 한다. 합의를 구속력 있고 의무적으로 만듦으로써 플레이어는 공유된 목표를 달성할 수 있다.

협력 게임은 모든 N의 부분 집합 S(결합)에 값을 특정하여 주어진다. 수학적으로, 이 게임 (결합 게임)은 유한한 플레이어 집합

N

과 함수

v : 2^N \to \mathbb{R}

에 의해 정의된다. 이 함수는 특성 함수라고도 불린다. 협력 게임은 플레이어 집합 N과 특성 함수 v의 쌍

(N,v)

에 의해 표시된다. 협력 게임의 표현 및 분석에는 특성 함수가 자주 사용되며, v를 게임이라고 부르기도 한다.

함수

v

는

N

에서의 각 결합에 보상을 대응시키는 것으로 해석된다. 어떤 결합 S에 대한 특성 함수의 값 v(S)는 S의 플레이어가 획득할 수 있는 최상의 값을 나타내며,

v(S)

를 '결합 값'이라고 부른다. 일반적으로는

v(\emptyset) = 0

(아무도 참가하지 않는 결합에 대한 보상을 주지 않는 것)을 가정한다.

또한, 결합 게임에서의 보상과는 반대로,

N

에서의 각 결합에서의 비용을 대응시키는 비용 함수 (cost function)

C: 2^N \to \mathbb{R}

을 사용하여 기술하는 방법도 있다. 이를 비용 게임 (cost game)이라고 부른다. 비용 함수에 의해 얻어지는 값은 결합한 플레이어들이 지불하는 비용을 나타낸다. 결합 게임에서의 개념은 비용 게임에서의 개념으로 쉽게 바꿀 수 있다.

3. 부분 게임

부분 게임은 원래 게임에서 특정 연합에 속하는 플레이어들에게만 초점을 맞춘, 더 작은 규모의 게임이다.^[1] 부분 게임은 전체 연합에 대한 해결 개념을 더 작은 연합에 적용하여 분석하는 데 유용하다.^[1]

어떤 협력 게임 $(N,v)$ 에서 $S \subsetneq N$ 을 공집합이 아닌 플레이어 집합이라고 하자.^[1] $S$ 에서의 부분 게임 $v_S : 2^S \to \mathbb{R}$ 는 다음과 같이 정의된다.^[1]

: $v_S(T) = v(T), \forall~ T \subseteq S.\,$

즉, $S$ 에 포함된 연합에만 집중한다.^[1]

A와 B가 두 개의 비교환( $A\cap B = \emptyset$ ) 연합인 경우, A와 B의 대연합 값은 단독 값의 합 이상이 된다.^[1] 즉,

: $v (A \cup B) \; \ge \; v (A) \; + \; v (B)$ if $A\cap B = \emptyset$ .

4. 특성 함수의 성질

협력 게임은 모든 연합에 대한 값을 지정하여 제공된다. 형식적으로 연합 게임은 "대연합"이라고 불리는 유한한 플레이어 집합 $N$ 과, 모든 가능한 플레이어 연합의 집합에서 $v( \emptyset ) = 0$ 을 만족하는 지불 집합으로의 "특성 함수" $v : 2^N \to \mathbb{R}$ 으로 구성된다.^[4] 이 함수는 플레이어 집합이 연합을 형성함으로써 얼마나 많은 집단적 보상을 얻을 수 있는지를 설명한다.

특성 함수는 협력이 클수록 보상도 커지는 성질을 갖는다. 이는 $A \subseteq B \Rightarrow v (A) \le v (B)$ 로 표현된다.

4. 1. 초가법성 (Superadditivity)

상호 배타적인 연합들의 결합 가치가 각 연합의 개별 가치의 합보다 작지 않다는 초가법성은 다음과 같이 표현된다.

:

v ( S \cup T ) \geq v (S) + v (T)

이며, 여기서

S, T \subseteq N

은

S \cap T = \emptyset

을 만족한다.

이는 더 큰 연합이 더 많은 것을 얻는다는 것을 의미한다.

:

S \subseteq T \Rightarrow v (S) \le v (T)

.

이는 초가법성에서 파생된다. 즉, 지불금이 단일 연합이 0의 가치를 갖도록 정규화된 경우를 말한다.

4. 2. 단조성 (Monotonicity)

더 큰 연합이 더 많은 것을 얻는다는 성질이다. 이는 초가법성에서 파생된다. 즉, 더 많은 플레이어가 참여할수록 더 큰 이익을 얻을 수 있음을 의미하며, 지불금이 단일 연합이 0의 가치를 갖도록 정규화된 경우를 말한다.^[1]

4. 3. 단순 게임의 성질

연합 게임에서 보상이 1(승리) 또는 0(패배)으로만 주어지는 경우를 단순 게임이라고 한다.^[6] 단순 게임은 투표 게임이라고도 불리며, 다음과 같은 성질을 가진다.

단조성: 어떤 연합이 승리하면, 그 연합을 포함하는 더 큰 연합도 반드시 승리한다.
적절성: 어떤 연합이 승리하면, 그 연합의 여집합(나머지)은 패배한다.
강력성: 어떤 연합이 패배하면, 그 연합의 여집합은 승리한다.
적절성과 강력성: 어떤 연합이 승리하는 것과 그 여집합이 패배하는 것은 같다.
거부권자: 모든 승리 연합에 속하는 플레이어. 거부권자가 있으면, 그를 포함하지 않는 연합은 패배한다.
약한 게임: 거부권자가 존재하는 게임. 즉, 모든 승리 연합의 교집합이 공집합이 아니다.
독재자: 독재자를 포함하는 모든 연합이 승리하는 거부권자. 독재자는 패배 연합에 속하지 않는다.
운반체: 모든 연합 S에 대해, S가 승리하는 것과 S와 운반체의 교집합이 승리하는 것이 같은 집합 T. 운반체에 속하지 않는 플레이어는 무시된다.
나카무라 수: 교집합이 빈 ''승리 연합''의 최소 개수. 나카무라 정리에 따르면, 이 수는 합리성의 정도를 측정하며, 집계 규칙이 얼마나 잘 정의된 선택을 산출할 수 있는지를 나타낸다.

단순 게임의 성질들 사이에는 다음과 같은 관계가 있다.^[7]

약한 게임은 적절하다.
강하고 약한 게임은 독재자를 가진다.

단순 게임의 종류는 다음 표와 같이 나타낼 수 있다.^[10]

단순 게임의 존재^[21]
타입	유한 비계산 가능	유한 계산 가능	무한 비계산 가능	무한 계산 가능
1111	no	yes	yes	yes
1110	no	yes	no	no
1101	no	yes	yes	yes
1100	no	yes	yes	yes
1011	no	yes	yes	yes
1010	no	no	no	no
1001	no	yes	yes	yes
1000	no	no	no	no
0111	no	yes	yes	yes
0110	no	no	no	no
0101	no	yes	yes	yes
0100	no	yes	yes	yes
0011	no	yes	yes	yes
0010	no	no	no	no
0001	no	yes	yes	yes
0000	no	no	no	no

거부권자가 없는 계산 가능한 단순 게임은, ''적절''하고 ''강력하지 않은'' 경우에만 3보다 큰 나카무라 수를 갖는다.^[11]

5. 비협력 게임과의 관계

협력 게임은 비협력 게임에서 플레이어들이 협력할 수 있다고 가정할 때, 비협력 게임을 통해 표현될 수 있다.^[12] ''G''를 전략적(비협력적) 게임이라고 할 때, 연합이 조율된 행동을 강제할 수 있다고 가정하면, ''G''와 관련된 여러 협력 게임이 존재한다. 이러한 게임들은 종종 ''G의 표현''이라고 불린다.^[12]

α-유효 게임과 β-유효 게임 등의 개념을 통해 비협력 게임을 협력 게임으로 변환할 수 있다. α-유효 게임은 각 연합에 그 구성원들이 힘을 합쳐 '보장'할 수 있는 이득의 합을 연관시킨다. '보장'한다는 것은 최대-최소, 즉 반대 세력의 전략에 대해 최소값을 취한 것의 최대값을 의미한다. β-유효 게임은 각 연합에 그 구성원들이 힘을 합쳐 '전략적으로 보장'할 수 있는 이득의 합을 연관시킨다. '전략적으로 보장'한다는 것은 최소-최대, 즉 반대 세력의 전략에 대해 최대값을 취한 것의 최소값을 의미한다.^[12]

$v$ 를 보상 게임의 함수로 할 때, $v$ 의 ''쌍대 게임''(dual game)인 비용 게임의 함수 $v^*$ 의 값은 다음과 같이 정의된다.

: $v^*(S) = v(N) - v( N \setminus S ), \forall~ S \subseteq N.\,$

직관적으로, 쌍대 게임은 전체 연합 N에 참여하지 않음으로써 발생하는 연합 $S$ 의 기회 비용을 표현한다고 생각할 수 있다.

보상 게임 $C^*$ 는 마찬가지로, 비용 게임 $C$ 의 쌍대 보상 게임으로 결정된다. 협력 게임과 그 쌍대 게임은 몇 가지 의미에서 등가이며, 그들은 많은 성질을 공유한다. 예를 들어, 어떤 게임과 그 쌍대 게임에서 그 코어는 같다.

6. 해결 개념

협력 게임 이론에서 해결 개념은 플레이어들에게 보상을 공정하게 분배하는 방법을 제시한다. 여러 해결 개념들은 각기 다른 공정성 기준을 기반으로 한다. 협력 게임은 제휴에 대한 보상을 기술하며, 플레이어는 제휴에 참여하는 것이 참여하지 않는 경우보다 이득을 얻을 경우에만 제휴에 참여한다.

협력 게임의 중심 가정은 전체 제휴 N이 형성된다는 것이다. 이때, 전체 제휴에서 얻어진 v(N)을 플레이어들에게 공정한 방법으로 분배해야 한다. 이를 위해 다양한 해결 개념이 제시되었으며, 각 해결 개념은 서로 다른 공정성 기준을 기반으로 한다.

6. 1. 해결 개념의 성질

협력 게임 이론에서 "솔루션 개념"은 각 플레이어에게 할당되는 보상 벡터(또는 벡터 집합)를 의미한다. 연구자들은 다양한 공정성 개념을 바탕으로 여러 솔루션 개념을 제안했으며, 이러한 솔루션 개념은 다음과 같은 성질들을 가질 수 있다.^[13]

성질	설명
효율성(Efficiency)	보상 벡터는 전체 가치를 정확하게 분할한다. 즉, 모든 플레이어의 보상 합은 전체 연합의 가치와 같다.
개인 합리성 (Individual rationality)	어떤 플레이어도 혼자 얻을 수 있는 것보다 적은 보상을 받지 않는다.
존재성(Existence)	솔루션 개념은 모든 게임에 대해 존재한다.
유일성(Uniqueness)	솔루션 개념은 모든 게임에 대해 유일하다.
한계성(Marginality)	플레이어의 보상은 이 플레이어의 한계 기여도에만 의존한다. 즉, 두 개의 다른 게임에서 한계 기여도가 동일하다면 보상도 동일하다.
단조성(Monotonicity)	플레이어의 한계 기여도가 증가하면 플레이어의 보상도 증가한다.
계산 용이성(Computational ease)	솔루션 개념은 (플레이어 수에 대해) 다항 시간 내에 효율적으로 계산할 수 있다.
대칭성(Symmetry)	솔루션 개념은 대칭 플레이어들에게 동일한 보상을 할당한다. 두 플레이어는 그들 중 하나만 포함하는 모든 연합에서 서로 교환되어도 보상이 변하지 않으면 대칭적이다.
가산성(Additivity)	두 게임의 합에서 플레이어에게 할당된 보상은 각 개별 게임에서 플레이어에게 할당된 보상의 합과 같다.
무효 플레이어에 대한 영 할당(Null player property)	무효 플레이어(어떤 연합에 추가되어도 그 연합의 가치를 변화시키지 않는 플레이어)에 대한 할당은 0이다.

효율적인 보상 벡터는 '사전-대입'이라고 하며, 개별적으로 합리적인 사전-대입은 대입이라고 한다. 대부분의 솔루션 개념은 대입이다.

6. 2. 안정 집합 (Stable Set)

'''안정 집합'''(Stable Set)은 폰 노이만-모겐슈테른 해라고도 불리며, 2명 이상의 플레이어가 참여하는 게임에 대해 처음으로 제안된 해법이다. 안정 집합은 다음 두 가지 속성을 만족하는 대안 (또는 배분)들의 집합이다.^[1]

내부 안정성: 안정 집합 내의 어떤 지불 벡터도 집합 내의 다른 벡터에 의해 지배되지 않는다.
외부 안정성: 집합 밖의 모든 지불 벡터는 집합 내의 적어도 하나의 벡터에 의해 지배된다.

폰 노이만과 모르겐슈테른은 안정 집합을 사회에서 허용 가능한 행동들의 집합으로 보았다. 즉, 다른 행동보다 분명히 선호되는 행동은 없지만, 허용되지 않는 각 행동에 대해 선호되는 대안이 있다는 것이다.^[1]

안정 집합은 존재하지 않거나 유일하지 않을 수 있으며, 찾기 어려운 경우가 많다. 이러한 어려움과 기타 문제점으로 인해 많은 다른 해법 개념이 개발되었다.^[1]

v

를 게임,

x

와

y

를

v

의 두 대안이라고 할 때, 어떤 연합

S \neq \emptyset

가 다음 두 조건을 만족하면

x

는

y

를 ''지배''한다.^[1]

$x_i > y _i, \forall~ i \in S$
$\sum_{ i \in S } x_i \leq v(S)$

즉,

S

의 플레이어들은

y

에서 얻는 것보다

x

에서 얻는 지불금을 선호하며, 자체적으로 얻는 지불금이

x

에서 받는 할당 이상이므로

y

가 사용될 경우 대연합에서 탈퇴하겠다고 위협할 수 있다.^[1]

6. 3. 핵심 (Core)

게임 이론에서 '''핵심'''(핵심)은 어떤 연합도 구성원들의 보상 합보다 큰 가치를 갖지 않는 보상 벡터의 집합을 의미한다. 즉, 모든 연합은 전체 연합을 떠나 더 큰 보상을 받을 유인이 없다.

핵심은 다음 조건을 만족하는 보상 벡터

x

의 집합으로 정의된다.

:

C(v) = \left\{ x \in \mathbb{R}^

: \sum_{i \in N} x_i = v(N); \quad \sum_{i \in S} x_i \geq v(S), \forall~ S \subseteq N \right\}.\,

효율성: 모든 플레이어의 보상 합은 전체 연합의 가치와 같다.
전략적 안정성: 어떤 연합도 전체 연합에서 이탈하여 더 큰 이득을 얻을 수 없다.

핵심은 비어 있을 수 있으며(본다레바-샤플리 정리 참조), 비어 있지 않은 경우에도 유일한 벡터를 포함하지 않을 수 있다. 핵심은 모든 안정 집합에 포함되며, 핵심이 안정적이면 유일한 안정 집합이다.

단순 게임의 경우, 선호 프로파일에 대한 핵심 개념이 추가로 정의될 수 있다. 선호 프로파일

p

에 대한 단순 게임

v

의 핵심

C(v, p)

는 지배 관계

\succ^p_v

에 의해 지배되지 않는 대안 집합이다.

단순 게임의 나카무라 수는 교집합이 없는 승리 연합의 최소 수이다. 나카무라 정리에 따르면, 특정 조건을 만족할 때 핵심

C(v,p)

가 비어 있지 않다.

6. 4. 강한 ε-핵심 (Strong Epsilon-Core)

Strong Epsilon-Core^영어은 핵심이 비어 있을 수 있기 때문에 도입된 일반화된 개념이다. 어떤 숫자

\varepsilon \in \mathbb{R}

에 대한 ''강한

\varepsilon

-핵심''은 다음과 같은 지불 벡터의 집합이다.

:

C_\varepsilon(v) = \left\{ x \in \mathbb{R}^N: \sum_{i \in N} x_i = v(N); \quad \sum_{i \in S} x_i \geq v(S) - \varepsilon, \forall~ S \subseteq N \right\}.

경제학적 관점에서 강한

\varepsilon

-핵심은 어떤 연합이 대연합을 떠날 때

\varepsilon

의 벌금을 지불해야 한다면, 지불을 개선할 수 없는 사전 귀속의 집합이다.

\varepsilon

는 음수가 될 수 있으며, 이 경우 대연합을 떠나는 것에 대한 보너스를 나타낸다. 핵심이 비어 있는지 여부에 관계없이 강한

\varepsilon

-핵심은

\varepsilon

의 충분히 큰 값에 대해 비어 있지 않으며, 충분히 작은 값(음수일 수도 있음)에 대해 비어 있게 된다. 이러한 추론에 따라, ''최소 핵심''은 모든 비어 있지 않은 강한

\varepsilon

-핵심의 교집합이다. 또한, 집합을 비어 있지 않게 만드는

\varepsilon

의 가장 작은 값에 대한 강한

\varepsilon

-핵심으로 볼 수도 있다.

6. 5. 섀플리 값 (Shapley Value)

로이드 섀플리가 1953년에 소개한 섀플리 값은 효율성, 대칭성, 단조성을 만족하는 유일한 지불 벡터이다.^[14] 섀플리 값은 효율적이고, 대칭적이며, 가산적이고, 더미 플레이어에게 0의 지불을 할당하는 고유한 지불 벡터임을 보였다. 초가산적 게임의 섀플리 값은 개별적으로 합리적이지만, 일반적으로는 그렇지 않다.

존 하르사니가 1963년에 섀플리 가치를 일반화하기 위해 사용한 하르사니 배당은 협력 게임에서 플레이어들의 연합에 의해 생성되는 잉여를 식별한다.^[15] 이 잉여를 명시하기 위해, 이 연합의 가치는 하위 연합에 의해 이미 생성된 잉여에 의해 보정된다. 게임

v

에서 연합

S

의 배당

d_v(S)

는 다음과 같이 재귀적으로 결정된다.

\begin{align}d_v(\{i\})&= v(\{i\}) \\d_v(\{i,j\})&= v(\{i,j\})-d_v(\{i\})-d_v(\{j\}) \\d_v(\{i,j,k\})&= v(\{i,j,k\})-d_v(\{i,j\})-d_v(\{i,k\})-d_v(\{j,k\})-d_v(\{i\})-d_v(\{j\})-d_v(\{k\})\\&\vdots \\d_v(S) &= v(S) - \sum_{T\subsetneq S }d_v(T)\end{align}

배당에 대한 명시적인 공식은

d_v(S)=\sum_{T\subseteq S }(-1)^

v(T)로 주어진다. 함수

d_v:2^N \to \mathbb{R}

는

v:2^N \to \mathbb{R}

의 뫼비우스 역변환으로도 알려져 있다.^[16] 공식

v(S) = d_v(S) + \sum_{T\subsetneq S }d_v(T)

를 사용하여

d_v

로부터

v

를 복구할 수 있다.

하르사니 배당은 게임과 해법 개념 모두를 분석하는 데 유용하며, 예를 들어 섀플리 가치는 각 연합의 배당을 그 구성원에게 분배하여 얻어진다. 게임

v

에서 플레이어

i

의 섀플리 가치

\phi_i(v)

는 그녀가 속한 모든 연합의 배당 중 플레이어의 몫을 합산하여 얻어진다.

\phi_i(v)=\sum_{S\subset N: i \in S }{d_v(S)}/

.

6. 6. 커널 (Kernel)

게임

v : 2^N \to \mathbb{R}

가 주어지고,

x \in \mathbb{R}^N

이 효율적인 지불 벡터라고 할 때, 플레이어 ''i''가 플레이어 ''j''에 대해 ''x''를 기준으로 가지는 "최대 잉여"는 다음과 같이 정의된다.

:

s_{ij}^v(x) = \max \left\{ v(S) - \sum_{ k \in S } x_k : S \subseteq N \setminus \{ j \}, i \in S \right\}

이는 지불 벡터 ''x'' 하에서 전체 연합 ''N''에서 탈퇴함으로써 플레이어 ''j''의 협력 없이 플레이어 ''i''가 얻을 수 있는 최대 이득의 양을 의미한다. 이때, ''i''의 탈퇴 연합에 속한 다른 플레이어들은 ''x''에 따른 그들의 지불에 만족한다고 가정한다. 최대 잉여는 한 플레이어가 다른 플레이어에 대해 가지는 교섭력을 측정하는 한 방법이다.

v

의 ''커널''은 다음을 만족하는 보수 ''x''의 집합이다.

모든 플레이어 쌍 ''i''와 ''j''에 대해, $( s_{ij}^v(x) - s_{ji}^v(x) ) \times ( x_j - v(j) ) \leq 0$
모든 플레이어 쌍 ''i''와 ''j''에 대해, $( s_{ji}^v(x) - s_{ij}^v(x) ) \times ( x_i - v(i) ) \leq 0$

직관적으로, 플레이어 ''i''는

s_{ij}^v(x) > s_{ji}^v(x)

이면 보수 ''x''에 대해 플레이어 ''j''보다 더 많은 교섭력을 갖는다. 그러나

x_j = v(j)

이면 플레이어 ''j''는 플레이어 ''i''의 위협에 면역이 되는데, 이는 혼자서도 이 지불을 얻을 수 있기 때문이다. 커널은 어떤 플레이어도 다른 플레이어에 대해 이러한 교섭력을 갖지 않는 모든 보수를 포함한다.

커널은 보상을 할당하는 벡터 중에서 다음을 만족한다.

효율성
개별 합리성

이 해결 개념은 1965년 데이비스(Davis)와 마쉴러(Maschler)에 의해 처음 소개되었다.^[1]

6. 7. 하르사니 배당 (Harsanyi Dividend)

존 하르사니의 이름을 따서 명명된 하르사니 배당은 협력 게임에서 플레이어들의 연합에 의해 생성되는 잉여를 식별한다.^[15] 이 잉여를 명시하기 위해, 이 연합의 가치는 하위 연합에 의해 이미 생성된 잉여에 의해 보정된다. 이를 위해, 게임

v

에서 연합

S

의 배당

d_v(S)

는 다음과 같이 재귀적으로 결정된다.

\begin{align}d_v(\{i\})&= v(\{i\}) \\d_v(\{i,j\})&= v(\{i,j\})-d_v(\{i\})-d_v(\{j\}) \\d_v(\{i,j,k\})&= v(\{i,j,k\})-d_v(\{i,j\})-d_v(\{i,k\})-d_v(\{j,k\})-d_v(\{i\})-d_v(\{j\})-d_v(\{k\})\\&\vdots \\d_v(S) &= v(S) - \sum_{T\subsetneq S }d_v(T)\end{align}

배당에 대한 명시적인 공식은

d_v(S)=\sum_{T\subseteq S }(-1)^

v(T)로 주어진다. 함수

d_v:2^N \to \mathbb{R}

는

v:2^N \to \mathbb{R}

의 뫼비우스 역변환으로도 알려져 있다.^[16] 실제로,

v(S) = d_v(S) + \sum_{T\subsetneq S }d_v(T)

공식을 사용하여

d_v

로부터

v

를 복구할 수 있다.

하르사니 배당은 게임과 해법 개념 모두를 분석하는 데 유용하며, 예를 들어 섀플리 값은 각 연합의 배당을 그 구성원에게 분배하여 얻어진다. 즉, 게임

v

에서 플레이어

i

의 섀플리 가치

\phi_i(v)

는 그녀가 속한 모든 연합의 배당 중 플레이어의 몫을 합산하여 얻어진다.

\phi_i(v)=\sum_{S\subset N: i \in S }{d_v(S)}/

.

6. 8. 핵 (Nucleolus)

v : 2^N \to \mathbb{R}

를 게임이라고 하고,

x \in \mathbb{R}^N

를 보수 벡터라고 하자. 연합

S \subseteq N

에 대한 ''과잉''은

v(S) - \sum_{i \in S} x_i

이며, 이는 보수

x

하에서 연합

N

에서 탈퇴하고 대신 보수

v(S)

를 취할 경우 연합

S

의 플레이어가 얻을 수 있는 이득을 의미한다.

v

의 ''핵''은 모든 연합의 과잉 벡터(

\mathbb{R}^{2^N}

의 벡터)가 렉시민 순서에서 가장 작은 임퓨테이션이다.

핵의 좀 더 직관적인 설명은 다음과 같다. 최소 코어부터 시작하여

C_\varepsilon(v)

의 정의에서 부등식의 우변을 집합을 비우지 않고 더 이상 줄일 수 없는 연합을 기록한다. 집합을 비우지 않고 줄일 수 없을 때까지 나머지 연합에 대해 우변을 계속 줄인다. 등식에서 부등식이 성립하는 새로운 연합 집합을 기록한다. 나머지 연합의 우변을 계속 줄이고 모든 연합이 기록될 때까지 필요한 만큼 이 과정을 반복한다. 결과적인 보수 벡터가 핵이다.

정의에서 명시적으로 언급하고 있지는 않지만, 핵자(nucleolus)는 항상 유일하다.
핵심(core)이 비어있지 않은 경우, 핵자는 핵심에 속한다.
핵자는 항상 커널(kernel)에 속하며, 커널은 협상 집합(bargaining set)에 포함되므로 항상 협상 집합에 속한다.^[1]

7. 볼록 협력 게임 (Convex Cooperative Games)

섀플리가 소개한 볼록 협력 게임은 일부 게임이 갖는 "눈덩이 효과"라는 직관적인 속성을 가진다. 특징 함수 $v$ 가 슈퍼모듈러인 경우 게임은 ''볼록''하다고 정의된다.

: $v( S \cup T ) + v( S \cap T ) \geq v(S) + v(T), \forall~ S, T \subseteq N.$

$v$ 의 슈퍼모듈러성은 다음 식과 동일하다.

: $v( S \cup \{ i \} ) - v(S) \leq v( T \cup \{ i \} ) - v(T), \forall~ S \subseteq T \subseteq N \setminus \{ i \}, \forall~ i \in N;$

즉, "연합에 가입하려는 인센티브는 연합이 커짐에 따라 증가"하며, 이는 눈덩이 효과를 유발한다. 비용 게임의 경우, 부등호가 반대로 되어 특징 함수가 서브모듈러인 경우 비용 게임은 ''볼록''하다고 한다.

볼록 협력 게임은 다음과 같은 여러 좋은 속성을 갖는다.

초모듈성은 초가산성을 의미한다.
볼록 게임은 ''완전 균형''을 이룬다. 볼록 게임의 핵심은 비어 있지 않으며, 볼록 게임의 모든 부분 게임이 볼록이므로 모든 부분 게임의 핵심도 비어 있지 않다.
볼록 게임은 핵심과 일치하는 고유한 안정 집합을 갖는다.
볼록 게임의 Shapley 값은 핵심의 무게 중심이다.
극점 (정점)은 탐욕 알고리즘을 사용하여 다항 시간 내에 핵심에서 찾을 수 있다. $\pi: N \to N$ 을 플레이어의 순열이라고 하고, $S_i = \{ j \in N: \pi(j) \leq i \}$ 을 $1$ 부터 $i$ 까지 정렬된 플레이어 집합이라고 하자. $\pi$ 에서, $i = 0, \ldots, n$ 에 대해, $S_0 = \emptyset$ 이다. 그런 다음 $x \in \mathbb{R}^N$ 에 의해 정의된 $x_i = v( S_{\pi(i)} ) - v( S_{\pi(i) - 1} ), \forall~ i \in N$ 페이오프는 $v$ 의 핵심의 정점이다. 핵심의 모든 정점은 적절한 순열 $\pi$ 을 선택하여 이러한 방식으로 구성할 수 있다.

서브모듈러 집합 함수와 수퍼모듈러 집합 함수는 조합 최적화에서도 연구된다. 볼록 비용 게임의 코어는 ''기저 다면체''라고 불리는데, 그 이유는 코어의 요소가 매트로이드의 기저 속성을 일반화하기 때문이다.

하지만 최적화 커뮤니티는 일반적으로 서브모듈러 함수를 볼록 함수의 이산적 유사물로 간주하는데, 그 이유는 두 종류의 함수 모두 최소화가 계산적으로 다루기 쉽기 때문이다. 이는 섀플리가 원래 정의한 수퍼모듈러 함수를 "볼록"이라고 정의한 것과 직접적으로 충돌한다.

8. 현실 세계에의 응용 및 한국 사회에 대한 시사점

협력 게임 이론은 기업 간의 합병, 자원 분배, 투표, 국제 협약 등 다양한 현실 세계 문제를 분석하는 데 사용될 수 있다. 특히 기업의 전략적 결정은 협력 게임 이론을 통해 가치를 창출하고 발전시킬 수 있으며, 이는 협력 게임 이론이 기업의 전략 이론이 될 수 있음을 의미한다.^[17]

여러 기업 A, B, C의 공동 사업을 예로 들어보자. 각 기업의 이익은 다음과 같이 정의할 수 있다.

기업	이익
A	3USD
B	6USD
C	5USD
A, B	10USD
A, C	10USD
B, C	12USD
A, B, C	18USD

여기서 v({A,B})는 기업 A, B가 협력했을 때의 이익을 나타낸다. 이 경우, 기업들이 제휴하는 쪽이 전체 이득은 커진다. 하지만, 개별 기업에게 제휴 여부는 이득의 분배에 따라 달라진다.

3사가 공동으로 사업을 진행했을 때 기업 A, B, C의 이득을 각각 x_A, x_B, x_C라고 하자.

예를 들어, 이득이 x_A = 4USD, x_B = 4USD, x_C = 10USD인 경우, x_A + x_B = 8USD < v({A,B}) = 10USD이 되므로, 기업 A, B는 2사만 제휴하여 이득 (x_A = 5USD, x_B = 5USD)를 얻는 것이 유리하다. 따라서 이 조건에서는 기업 A, B는 C를 포함한 3사의 제휴를 거부할 것이다. 이러한 상태를 제휴 (AB)에 관해서, 분배 (x_A = 5USD, x_B = 5USD)가 분배 (x_A = 4USD, x_B = 4USD, x_C = 10USD)을 지배한다고 한다.

한편, 분배 (x_A = 5USD, x_B = 7USD, x_C = 6USD)의 경우, 어느 두 기업의 제휴에 의해서도 그 제휴에 참가한 모든 기업의 이득을 증가시킬 수 없다. 이러한 분배만이 코어에 속한다.

참조

_[1] 웹사이트 Non-Cooperative Game - Game Theory .net http://www.gametheor[...] 2016-09-15
_[2] 웹사이트 Cooperative Game Theory http://www.utdallas.[...]
_[3] 웹사이트 Cooperative Game Theory: Characteristic Functions, Allocations, Marginal Contribution http://www.uib.cat/d[...]
_[4] 문서 " $2^N$ denotes the [[power set]] of $N$ ."
_[5] 서적 Cooperative Game Theory Tools in Coalitional Control Networks Springer Cham
_[6] 서적 Computational Aspects of Cooperative Game Theory https://books.google[...] Morgan & Claypool Publishers 2011-10-25
_[7] 서적 Handbook of Social Choice and Welfare Volume 1
_[8] 문서 "See\n[[Rice's theorem#An analogue of Rice's theorem for recursive sets|a section for Rice's theorem]]\nfor the definition of a computable simple game. In particular, all finite games are computable."
_[9] 간행물 Computability of simple games: A complete investigation of the sixty-four possibilities http://mpra.ub.uni-m[...]
_[10] 문서 "Modified from Table 1 in Kumabe and Mihara (2011).\nThe sixteen types are defined by the four conventional axioms (monotonicity, properness, strongness, and non-weakness).\nFor example, type {{mono|1110}} indicates monotonic (1), proper (1), strong (1), weak (0, because not nonweak) games.\nAmong type {{mono|1110}} games, there exist no finite non-computable ones, there exist finite computable ones, there exist no infinite non-computable ones, and there exist no infinite computable ones.\nObserve that except for type {{mono|1110}}, the last three columns are identical."
_[11] 간행물 The Nakamura numbers for computable simple games http://econpapers.re[...]
_[12] 문서 'Aumann, Robert J. "[http://www.ma.huji.ac.il/~raumann/pdf/The%20Core%20of%20a%20Cooperative.pdf The core of a cooperative game without side payments]." Transactions of the American Mathematical Society (1961): 539-552.'
_[13] 서적 Game theory: a multi-leveled approach https://archive.org/[...] Springer 2008
_[14] 간행물 Monotonic solutions of cooperative games 1985-06-01
_[15] 서적 Papers in Game Theory Springer, Dordrecht 1982
_[16] 서적 Set Functions, Games and Capacities in Decision Making {{!}} Michel Grabisch {{!}} Springer https://www.springer[...] Springer
_[17] 간행물 Using cooperative game theory to contribute to strategy research 2018-08-01
_[18] 간행물 Chapter 8 Game-theoretic analysis of voting in committees
_[19] 문서 単純ゲームが
_[20] 간행물 Computability of simple games: A complete investigation of the sixty-four possibilities
_[21] 문서 "Kumabe and Mihara (2011) の Table 1 を修正。\n16個ある '''Type''' は伝統的な４つの性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか) で決まる。\nたとえば type 1110 とは単調 (1) でプロパー (1) で強く (1) 拒否権プレーヤーあり (0) の単純ゲームたちを指す。\nその行は type 1110 ゲームのなかに、有限かつ計算不能なものが不在であり、有限かつ計算可能なものが存在し、無限かつ計算不能なのものが不在であり、無限かつ計算可能なものが不在であることをしめす。"
_[22] 간행물 The Nakamura numbers for computable simple games

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com