협동 게임 이론

게임이론에서 협동게임(또는 연합게임)은 협동행동의 외부적 집행 가능성(예: 계약법을 통한)으로 인해 플레이어 그룹간 경쟁("연합")이 있는 게임이다. 이들은 동맹을 맺을 가능성이 없거나 모든 협정이 (예: 신뢰할 수 있는 위협을 통한) 자기강제적일 필요가 있는 비협조적인 게임에 반대한다.^[1]

협동게임은 어떤 연합이 형성될 것인가, 집단이 취하는 공동행동, 그에 따른 집단보상을 예측하는 데 초점을 맞춘 협동게임 이론의 틀을 통해 분석되는 경우가 많다. 선수 개개인의 행동과 성과를 예측하고 내쉬 평형도를 분석하는 데 초점을 맞춘 전통적인 비협조 게임 이론과는 반대되는 것이다.^[2][3]

협동 게임 이론은 연합의 구조, 전략, 성과만을 기술하므로 고도의 접근법을 제공하는 반면, 비협조 게임 이론은 교섭 절차가 각 연합 내에서의 성과물의 분배에 어떤 영향을 미칠 것인가에 대해서도 고찰한다. 비협조 게임 이론이 보다 일반적이기 때문에, 협력의 외부적 집행 가능성으로 인해 플레이어들이 이용할 수 있는 모든 가능한 전략을 포괄할 수 있는 충분한 가정이 이루어진다면, 비협조 게임 이론의 접근을 통해 협동 게임을 분석할 수 있다. 따라서 모든 게임을 비협조적 프레임워크로 표현할 수 있지만, 많은 경우 전략적 협상 과정에서 참가자가 사용할 수 있는 공식 절차를 정확하게 모델링할 수 있는 불충분한 정보가 제공되거나, 결과 모델이 너무 복잡하여 재계약 시 실질적인 도구를 제공할 수 없을 것이다.al world. 이런 경우 협동게임 이론은 협상력을 가정할 필요 없이 게임을 전반적으로 분석할 수 있는 단순화된 접근방식을 제공한다.

수학적 정의

모든 연합에 대한 가치를 명시함으로써 협동 게임이 주어진다. 형식적으로, 그 연합의. 게임 선수들 N{N\displaystyle}의 유한 집합, 대연정이라는 독특한 기능'v'의:2N→ R{\displaystyle v:2^{N}\to({R}}선수들에 대한 모든 가능한 연합체의 집합을 충족한 지불의 집합으로에서[4]v(∅) 돌아선 0{\displaystyle v(\emp로 구성되어 있다.ty$세트 )=0$ 일련의 플레이어가 연합을 형성함으로써 얼마나 집합적인 이익을 얻을 수 있는지를 기술하는 기능이며, 게임을 가치 게임이나 이익 게임이라고도 한다.

반대로 협동게임은 특성비용함수 $c{\displaystyle }$: ${\displaystyle {2N}^{}}$→ ${\displaystyle R\mathbb{}}$ ${\$ c$:2^{N}\to \mathb {R}$ 충족 $c$( ${\displaystyle \mathrm{\varnothing }}$)${\displaystyle }$= 0 ${\displaysty c(\empt )=0}$을(를)로 정의할 수도 있다.$$이 설정에서 플레이어들은 어떤 작업을 수행해야 하며 특성함수 $c{\displaystyle }$ ${\displaysty c}$는 원가를 나타낸다$$.한 무리의 선수들이 함께 그 임무를 완수한다. 이런 종류의 게임은 비용 게임으로 알려져 있다. 대부분의 협동 게임 이론이 수익 게임을 다루지만, 모든 개념은 비용 설정으로 쉽게 번역될 수 있다.

하사니 배당금

하사니 배당금(Harsani 배당금, 1963년^[5] 샤플리 가치를 일반화하는 데 사용한 John Harsanyi의 이름을 딴 것)은 협동 게임에서 플레이어들의 연합에 의해 창출되는 흑자를 파악한다. 이 잉여금을 특정하기 위해, 이 연합의 가치는 이미 아연합에 의해 창출된 잉여금에 의해 보정된다. 이를 위해 게임 $v{\displaystyle }$ ${\displaystyle v}$에서 연합 $S{\displaystyle }$ ${\displaystyle S}$의 배당금 $d{\displaystyle {}_{}}$ ${\displaystyle v_{}S)}$ ${\displaystyle$ v}을$(를) 재귀적$으로 결정한다$$.

${\displaystyle {\begin{aligned}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_{x}(\{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{aligned}}}$

An explicit formula for the dividend is given by ${\textstyle d_{v}(S)=\sum _{T\subseteq S}(-1)^{ S\setminus T }v(T)}$. The function ${\displaystyle d_{v}:2^{N}\to \mathbb {R} }$ is also known as the Möbius inverse of ${\displays$$tyle v:2^{N}\to \mathbb {R} }$.^[6] Indeed, we can recover ${\displaystyle v}$ from ${\displaystyle d_{v}}$ by help of the formula ${\textstyle v(S)=d_{v}(S)+\sum _{T\subsetneq S}d_{v}(T)}$.

Harsani 배당금은 게임과 솔루션 개념을 모두 분석하는데 유용하다. 예를 들어 샤플리 값은 회원들 사이에서 각 연정의 배당금을 분배하여 얻는다. 즉, 게임 $v{\displaystyle }$ ${\displaystyle i}$의 샤플리 값 ${\displaystyle {\varphi }_{}}$ i${\displaystyle {}_{}}$($){\displaysty \phi _{i}(v)}$는 게임 v}를$$ 합산하여 준다. 그녀가 속해 있는 모든 연합의 배당금에 대한 플레이어 몫, , $\underset{}{i}$ ${}_{}v$ $)$= $\underset{}{}$ $\underset{}{S}$ $\underset{}{\subset }$ N$\underset{}{}$: $i$ $\underset{}{\in }$ $\underset{}{S}$ d $v_{}$( S$$)$$/ S $textstyle \phi _{i}(v)=\sum _{S\subset N:i\in$ S$}{d_{v}(S)/{S$

이중성

$v{\displaystyle }$ ${\displaystyle v}$을(를) 수익 게임이 되게$$ 하라. $v{\displaystyle }$ ${\displaystyle v}$의 듀얼 게임은 다음과 같이$$ $정의$된 비용 게임 v$$∗{\$displaystyle$ v$^{*}$이다.

${\displaystyle v^{*}=v(N)-v(N\setminus S),\all ~S\s\subseteq N.}$

직관적으로 듀얼 게임은 $대연정{\displaystyle }$ N ${\displaystyle N}$에 가입하지 않은$$ 연합 $S{\displaystyle }$ ${\displaystyle$ $S$$}$에 대한 기회비용을 나타낸다$.$ 이중수익 $게임{\displaystyle {}^{}}$ $c{\displaystyle }$$∗{\$ c$^{*}$는 비용 게임 c ${\displaystyc$}에$대해$ 동일하게 정의할 수 있다$$$.$ 협동 게임과 그 이중은 어떤 의미에서는 동일하다.발렌타인, 그리고 그들은 많은 특성들을 공유한다. 예를 들어, 게임의 핵심과 그것의 이중은 같다. 공동 게임 이중성에 대한 자세한 내용은 예를 들어(Bilbao 2000)를 참조하십시오.

서브게임즈

$S{\displaystyle }$ ${\displaystyle ⊊}$ ${\displaystyle N}$ ${\displaystyle S\subsetneq N}$을(를) 선수들 간의 비빈 연합으로 하자$$. $S{\displaystyle }$ ${\displaystyle S}$의 하위 게임 ${\displaystyle v_{}}$: $2S$→ R ${\$에 대한 하위 게임은 자연스럽게 다음과 같이 정의된다$$.

${\displaystyle v_{S}(T)=v(T),\all ~T\subseteq S.}$

즉, 우리는 $S{\displaystyle }$ ${\displaystyle S}$에 포함된 연합에 우리의 주의를 제한한다$.$ 서브게임은 우리가 대연합을 위해 정의된 솔루션 개념을 더 작은 연합에 적용할 수 있게 해주기 때문에 유용하다.

특성화 속성

초가당성

특성 함수는 종종 초첨가로 가정된다(Owen 1995, 페이지 213). 이는 연합 해체 연합의 가치가 연합의 별도 가치의 합에 못지 않다는 것을 의미한다.

${\displaystyle v(S\cup T)\geq v(S)+v(T)}$ whenever ${\displaystyle S,T\subseteq N}$ satisfy ${\displaystyle S\cap T=\emptyset }$.

단조도

대규모 연합은 더 많은 이득을 얻는다.

${\displaystyle S}$ ${\displaystyle \subseteq }$ ${\displaystyle T}$ ${\displaystyle \Rightarrow }$ v${\displaystyle }$( ${\displaystyle S}$) ${\displaystyle \le }$ ${\displaystyle v}$( ${\displaystyle T}$ ) { v ( T${\displaystyle }$) ${\displaystyle S\subseteq T\Rightarrow v(S)\leq$ v$(T)}$.

이것은 초애감에서 따온 것이다. 즉, 보상이 정상화되어 싱글톤 연합이 0의 가치를 갖는 경우.

간단한 게임의 속성

연합 게임 v는 보상이 1 또는 0인 경우, 즉 연합이 "승리" 또는 "실패"^[7]인 경우 단순하게 간주된다.

이와 동등하게 간단한 게임은 W의 멤버들을 승리하는 연합이라고 부르고, 다른 멤버들은 연합을 잃는 연합의 집합체 W로 정의할 수 있다. 단순한 게임이 비어 있지 않거나 빈 세트가 들어 있지 않다고 가정하기도 한다. 그러나 수학의 다른 영역에서는 간단한 게임을 하이퍼그래프 또는 부울 함수(논리 함수)라고도 한다.

• 승리한 연정을 포함하는 연합이 승리하는 경우, 즉 $S{\displaystyle }$ ${\displaystyle \in }$ W ${\displaystyle S\in W}$과 ${\displaystyle S}$ ${\displaystyle \subseteq }$ T ${\displaystyle$ S$\subseteq T}$이 $T{\displaystyle }$ ${\displaystyle \in }$ W ${\displaystyle T\in W$을 의미한다면 단순한 게임 W는 단조롭다.
• 승리한 연합의 보완(반대)이 지고 있다면, $즉{\displaystyle }$ S${\displaystyle }$∈ ${\displaystyle W}$ ${\displaystyle S\in$ W$}$이(가) $N{\displaystyle }$ ${\displaystyle \setminus }$ ${\displaystyle S}$ ${\displaystyle \notin }$ W ${\displaystyle N\setminus S\notin W}$을(를) 내포한다면 간단한 게임 W가 적절하다$.$
• 패배한 연합의 보완이 승리하고 있다면, 즉 $S{\displaystyle }$s ${\displaystyle W}$ ${\displaystyle S\notin$ W$}$이(가) $N{\displaystyle }$ ${\displaystyle \setminus }$ ${\displaystyle S}$ ${\displaystyle \in }$ ${\displaystyle W}$ ${\displaystyle N\setminus S\in$ W$}$을(를) 내포하고$$ 있다면 간단한 게임 W는 강하다$.$
  • If a simple game W is proper and strong, then a coalition is winning if and only if its complement is losing, that is, ${\displaystyle S\in W}$ iff ${\displaystyle N\setminus S\notin W}$. (If v is a coalitional simple game that is proper and strong, ${\displaystyle v(S)=1-v(N\setminus S)}$$$ 모든 S.)
• 간단한 게임에서 거부권자(베토)는 모든 승리한 연합에 속하는 선수다. 거부권자가 있다고 가정할 때 거부권을 행사하지 않는 연합은 패배하고 있다. 간단한 게임 W는 거부권이 있는 경우 약하다(컬러지컬). 즉, 모든 승리한 연합의$$ ${\displaystyle \mathrm{교차점}}$ W ${\displaystyle :=}$ ${\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{S}}$ ${\displaystyle \underset{}{\in }}$ ${\displaystyle \underset{}{}}$ ${\displaystyle \bigcap$ W$:=\bigcap _{S\in$W}$S}$가 비어 있지 않은 경우.
  • 단순한 게임에서 독재자는 거부권을 행사하는 플레이어로, 이 플레이어를 포함하는 모든 연합이 승리하고 있다. 독재자는 패배한 연정에 속하지 않는다.(실험경제학에서의 독재자 게임은 이와 무관하다.)
• A carrier of a simple game W is a set ${\displaystyle T\subseteq N}$ such that for any coalition S, we have ${\displaystyle S\in W}$ iff ${\displaystyle S\cap T\in W}$. When a simple game has a carrier, any player not belonging to it is ignored. 단순한 게임은 한정된 캐리어를 가지고 있다면(N이 무한하더라도) 유한한 게임이라고 부르기도 한다.
• 단순한 게임의 나카무라 번호는 빈 교차로에 있는 최소한의 승리한 연합이다. 나카무라의 정리에 따르면, 그 수는 합리성의 정도를 측정한다; 그것은 집적 규칙이 어느 정도 잘 정의된 선택을 산출할 수 있는지를 나타내는 지표다.

위의 공리들 사이의 몇몇 관계는 다음과 같이 널리 인정되어 왔다(예: Pleleg, 2002, 2.1절^[8]).

• 간단한 게임이 약하면 적당하다.
• 단순한 게임은 강하고 약할 때만 독재적이다.

보다 일반적으로, 4개의 전통적인 공리(단조성, 적절성, 강인성, 비약성), 정밀성, 알고리즘 계산성^[9] 사이의 관계에 대한 완전한 조사가 이루어졌으며, 그 결과는 아래의 표 "단순한 게임의 존재"에 요약되어 있다(쿠마베와 미하라, 2011^[10]).

심플 게임^[11] 존재

유형	유한비콤프	유한 계산 가능	무한비콤프	무한 계산 가능
1111	아니요.	네	네	네
1110	아니요.	네	아니요.	아니요.
1101	아니요.	네	네	네
1100	아니요.	네	네	네
1011	아니요.	네	네	네
1010	아니요.	아니요.	아니요.	아니요.
1001	아니요.	네	네	네
1000	아니요.	아니요.	아니요.	아니요.
0111	아니요.	네	네	네
0110	아니요.	아니요.	아니요.	아니요.
0101	아니요.	네	네	네
0100	아니요.	네	네	네
0011	아니요.	네	네	네
0010	아니요.	아니요.	아니요.	아니요.
0001	아니요.	네	네	네
0000	아니요.	아니요.	아니요.	아니요.

단순한 게임의 다양한 공리가 나카무라 번호에 부과하는 제한도 광범위하게 연구되었다.^[12] 특히 거부권자가 없는 계산 가능한 간단한 게임은 적당하고 강하지 않은 게임일 경우에만 나카무라 번호가 3보다 크다.

비협조 이론과의 관계

G를 전략적(비협조적) 게임으로 하자. 그런 다음 연합이 조정된 행동을 강제할 수 있는 능력을 가지고 있다고 가정하면 G와 관련된 몇 가지 협동 게임이 있다. 이 게임들은 종종 G의 표현이라고 불린다. 두 가지 표준 표현은 다음과 같다.^[13]

• α 효과의 게임은 각 연합과 결합하여 회원들이 힘을 합쳐 '보증'할 수 있는 이득의 합을 연결한다. '보증'을 함으로써, 그 가치는 최대민(max-min)이라는 뜻으로, 예를 들어 반대파의 전략을 인수하는 최소치의 최대치를 의미한다.
• β 효과의 게임은 각 연합과 결합하여 회원들이 힘을 합쳐 '전략적으로 보장'할 수 있는 이득의 합을 연결한다. '전략적으로 보장한다'는 것은 그 가치가 최소치라는 뜻으로, 예를 들어 야당의 전략을 인수하는 최대치의 최소치라는 뜻이다.

솔루션 개념

협동 게임 이론의 주요 가정은 대연정 $N{\displaystyle }$ ${\displaystyle N}$이 형성될$$ 것이라는 것이다.^[14] 그 다음 과제는 $어떤{\displaystyle }$ 공정한 방법으로 선수들 사이에$$ 보상 v $){\displaystyle v(N)}$을 할당하는 것이다. (이 가정은 제한적이지 않다. 플레이어가 분리하여 더 작은 연합을 형성하더라도 우리는 실제로 어떤 연합을 형성하든 간에 정의된 서브게임에 솔루션 개념을 적용할 수 있기 때문이다.) 솔루션 개념은 벡터 $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}^{}}$N {\$displaystyle x\in \mathb {R}^{N}($또는 벡터 집합)으로 각 플레이어에 대한 할당을 나타낸다. 연구자들은 공정성에 대한 다른 개념에 기초하여 서로 다른 해결책 개념을 제안했다. 솔루션 개념에서 찾아야 할 몇 가지 속성은 다음과 같다.

• 효율성: 지불 벡터는 ${\displaystyle \underset{}{정확}}$하게 총 값을 분할한다: $\sum {\displaystyle \underset{}{}}$ i ${\displaystyle \underset{}{\in }}$ N ${\displaystyle x_{}}$ ${\displaystyle \underset{}{}{}_{}}$= ${\displaystyle v}$ (${\displaystyle N}$) ${\displaystyle \sum _{i\in N}x_{i}=v(N$
• 개별적 합리성: x ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle v}$(${\displaystyle }${ ${\displaystyle i}$ ${\displaystyle \}}$) ,${\displaystyle \mathrm{\forall }}$ ${\displaystyle \text{i}}$ ${\displaystyle \in }$ ${\displaystyle N}$ ${\displaystyle x_{i}\geq v(\{i\}),\forall ~i\in N$ .
• 존재: 솔루션 개념은 모든 게임 $v{\displaystyle }$ ${\displaystyle v}$에 대해 존재한다$.$
• 고유성: 솔루션 개념은 모든 게임 $v{\displaystyle }$ ${\displaystyle v}$에 대해 고유하다$.$
• 마진성: The payoff of a player depends only on the marginal contribution of this player, i.e., if these marginal contributions are the same in two different games, then the payoff is the same: ${\displaystyle v(S\cup \{i\})=w(S\cup \{i\}),\forall ~S\subseteq N\setminus \{i\}}$ implies that ${\displaystyle x_{}}$${\displaystyle i_{}}$ ${\$는 $v{\displaystyle }$ ${\displaystyle v}$과 w ${\displaystyle w}$에서 동일하다$.$
• 단조로움: The payoff of a player increases if the marginal contribution of this player increase: ${\displaystyle v(S\cup \{i\})\leq w(S\cup \{i\}),\forall ~S\subseteq N\setminus \{i\}}$ implies that ${\displaystyle x_{i}}$ is weakly greater in ${\displaystyle w}$ than in ${\displaystyle v}$$(\displaystyle$ v$\})$
• 계산 용이성: 솔루션 개념은 효율적으로 계산할 수 있다(즉, 플레이어 수 ${\displaystyle N}$ $displaystyle$N$}$에 대한 다항 시간).$$
• 대칭: 솔루션 개념 $x{\displaystyle }$ ${\displaystyle x}$은(는) 대칭 플레이어 $i{\displaystyle }$ ${\displaystyle i$ $j{\displaystyle }$ ${\displaystyle j}$에 동일한 $지급액{\displaystyle {}_{}}$ x${\displaystyle {}_{}{i}_{}}$ = ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$을 할당한다$.$ Two players ${\displaystyle i}$, ${\displaystyle j}$ are symmetric if ${\displaystyle v(S\cup \{i\})=v(S\cup \{j\}),\forall ~S\subseteq N\setminus \{i,j\}}$; that is, we can exchange one player for the other in any coalition that contains only one of the players and no보수가 바뀌다
• 추가성: 2경기 합계로 선수에게 할당하는 것은 각 개인 경기에서 선수에게 할당하는 총합이다. 수학적으로 $v{\displaystyle }$ ${\displaystyle v}$과 $\Omega {\displaystyle }$ ${\displaystyle$$$$\omega }$이(가) 게임인$$ 경우, 게임$({\displaystyle v}$ +${\displaystyle \Omega }$) {\$displaystyle ($v+\$omega)}$은 연정이 두 개별 게임에서 얻을 수 있는 보상의 합계를 어떤 연정에도 할당하기만 하면 된다. $부가{\displaystyle }$ 솔루션 개념은${\displaystyle }$(${\displaystyle v}$+ ${\displaystyle \Omega }$) ${\displaystyle (v+\omega )}$의 모든 플레이어에게 v ${\displaystyle v}$ 및$$ $\Omega {\displaystyle }$ ${\displaystyle \omega }$에서 수신되는 값의 합을$$ 할당한다$.$
• Null 플레이어에 대한 제로 할당: null 플레이어에 대한 할당은 0이다. A null player ${\displaystyle i}$ satisfies ${\displaystyle v(S\cup \{i\})=v(S),\forall ~S\subseteq N\setminus \{i\}}$. In economic terms, a null player's marginal value to any coalition that does not contain him is zero.

효율적인 지불 벡터는 사전 임팩팅이라고 하며, 개별적으로 합리적인 사전 임팩팅은 임팩팅이라고 한다. 대부분의 솔루션 개념은 귀책이다.

스테이블 세트

안정적인 게임 세트(von Neumann-Morgenstern 솔루션(von Neumann & Morgenstern 1944))는 2명 이상의 플레이어가 포함된 게임에 대해 제안된 첫 번째 솔루션이었다. $v{\displaystyle }$ ${\displaystyle v}$을(를) 게임으로$$ 하고 $x{\displaystyle }$ ${\displaystyle x$ $y{\displaystyle }$ ${\displaystyle y}$을(를) $v{\displaystyle }$ ${\displaystyle v}$의 두 개의 귀책으로 한다$$$.$ 그리고 나서){\displaystyle)}며, 일부 연합 S∅{S\neq \emptyset\displaystyle}가 ≠{이\displaystyle})나는입니다.;y는 나는, 나는 S{\displaystyle x_{나는}> ∈ ∀, y_{나는},\forall ~i\in S}과 ∑ 나는)나는}v(S){\displaystyle \sum_{Si\in}x_{나는}\leq v(S)≤ S∈. 다른 말로 선수들이 y. s${\displaystyle S}$은$($는) $y{\displaystyle }$ ${\displaystyle y}$보다 $x{\displaystyle }$ ${\displaystyle x}$의 보답을 선호하며$$, 스스로 얻는 보상은 적어도 $x{\displaystyle }$ ${\displaystyle$ x$}$에 따라 받는 할당만큼 크기 때문에 $y{\displaystyle }$ ${\displaysty$ y$}$가 사용되면$$ 대연정을 탈퇴하겠다고 위협할 수 있다$.$

안정 집합은 다음과 같은 두 가지 특성을 만족시키는 귀책 집합이다.

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

폰 노이만과 모르겐스턴은 마구간 세트를 사회에서 용인되는 행동의 집합체로 보았다. 어떤 것도 다른 것들보다 확실히 선호되지 않지만, 각각의 받아들일 수 없는 행동에 대해 선호하는 대안이 있다. 그 정의는 매우 일반적이어서 그 개념이 매우 다양한 게임 포맷으로 사용될 수 있다.

특성.

• 안정적인 세트는 존재할 수도 있고 없을 수도 있으며(Lucas 1969) 존재할 경우 일반적으로 고유하지 않다(Lucas 1992). 안정적인 세트는 보통 찾기 어렵다. 이것과 다른 어려움들은 많은 다른 해결책 개념들의 개발로 이어졌다.
• 협동 게임의 긍정적인 부분은 코어로 구성된 독특한 안정적인 세트를 가지고 있다. (Owen 1995, 페이지 240).
• 협동 게임의 긍정적인 부분은 $n{\displaystyle }$- $[\displaystyle n-2}$ 플레이어를$$ 차별하는 안정적인 세트를 가지고 있다. 그러한 세트에서는 차별받는 선수 중 $적어도$ n${\displaystyle }$- ${\displaystyle 3}$ ${\displaystyle n-3}$이(가) 제외된다(Owen 1995, 페이지 240).

핵심

$v{\displaystyle }$ ${\displaystyle v}$을(를) 게임으로$$ 합시다. $v{\displaystyle }$ ${\displaystyle v}$의 핵심이 보수 벡터 집합임$$

${\displaystyle C(v)=\left\{x\in \mathb {R}^{N:\sum_{i_{i}=v(N);\quad \sum \sum_{i\in S}x_\geq v(S);\all ~S\subseteq N\rig\rig\rig\rig.}$

즉, 핵심은 그 어떤 연합도 그 구성원의 보상의 합계보다 더 큰 가치를 가지고 있지 않은 귀책의 집합이다. 따라서 어떤 연정도 대연정을 떠나 더 큰 보수를 받을 동기가 없다.

특성.

• 게임의 핵심은 비어 있을 수 있다(Bondareva-Shapley 정리 참조). 코어가 비어 있지 않은 게임을 밸런스라고 한다.
• 비어 있지 않은 경우 코어에 반드시 고유한 벡터가 포함된 것은 아니다.
• 코어는 어떤 안정된 세트에 포함되어 있으며, 코어가 안정되어 있다면 그것은 독특한 안정 세트다; 증거는 (Driessen 1988)을 참조하라.

선호도에 대한 간단한 게임의 핵심

간단한 게임의 경우, 각 플레이어가 정해진 $X{\displaystyle }$ ${\displaystyle X}$의 대체 게임을 선호하는 것으로 가정할 때 코어에 대한 또 다른 개념이 있다. A profile is a list ${\displaystyle p=(\succ _{i}^{p})_{i\in N}}$ of individual preferences ${\displaystyle \succ _{i}^{p}}$ on ${\displaystyle X}$. Here ${\displaystyle x\succ _{i}^{p}y}$ means that individual ${\displaystyle i}$ prefers alternative ${\displaystyle x}$${\displaystyle x}$ to ${\displaystyle y}$ at profile ${\displaystyle p}$. Given a simple game ${\displaystyle v}$ and a profile ${\displaystyle p}$, a dominance relation ${\displaystyle \succ _{v}^{p}}$ is defined on ${\displaystyle X}$ by ${\displaystyle x\succ _{v}^$${p}y}$ if and only if there is a winning coalition ${\displaystyle S}$ (i.e., ${\displaystyle v(S)=1}$) satisfying ${\displaystyle x\succ _{i}^{p}y}$ for all ${\displaystyle i\in S}$. The core ${\displaystyle C(v,p)}$ of the simple game ${\displaystyle v}$ with r선호$$ $프로파일{\displaystyle }$ p ${\displaystyle$ p$}$을(를) 예로 들자면,$$${\displaystyle {}_{}^{}}$ v$$p {\$displaystyle \such _{$v}^{$p}}($${\displaystyle {}_{}^{}}$ ${\displaystyle v_{}^{}}$${\$$displaystyle$$\$$such \v}^{p$}}에$$ 대한 $X$의 최대 요소 집합):

${\displaystyle x}$ ${\displaystyle \in }$ ${\displaystyle C(v}$ ${\displaystyle ,}$ p${\displaystyle }$) ${\displaystyle x\in C(v,p)}($$만약$에 또는 $X})$가 없는 경우에만 y ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle$ $y$$\such _{v}^{p}x$

단순한 게임의 나카무라 번호는 빈 교차로에 있는 최소한의 승리한 연합이다. 나카무라($)$의 $정리$에서는 X {\$displaystyle$ X}이($)$ $유한$하고 X {\$displaystyle$ X$}$의 기수(원소 수)가$$ 나카무라(中村)보다 적은 경우에만, 코어 C(${\displaystyle v}$,${\displaystyle p)}$ ${\displaystystyle C$$($$v,p)$가 모든 프로파일 $p{\displaystyle }$ ${\daystyp}$에 대해 비어 있지 않다고 명시하고 있다$$. $v{\displaystyle }$ {\$displaystyle v}$의 수$.$ ${\displaystyle \mathrm{쿠마베}}$와 미하라에 의해 변형된 설명에 따르면 코어 $($$v$ , $p$ ) {\$displaystyle$ C($v,p$$)}$는 X의 기본 $번호$가$v$의 나카무라 수보다 작은$$ 경우에만 최대 요소가 있는 모든$$ 프로파일 $p{\displaystyle }$ ${\$$displaystyle$ p$}$에 대해 비어 있지$$ 않다.$Playstyle v}$. (자세한 내용은 나카무라 번호 참조)

강한 엡실론-코어

핵심이 비어 있을 수 있기 때문에 (Shapley & Shubik 1966)에 일반화가 도입되었다. 일부 $번호$에 대한 강력한 $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon }$ -core$$ the${\displaystyle R\mathbb{}}$ ${\$은(는$)$ 지불 벡터의 집합이다$$.

${\displaystyle 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\}.}$

경제적인 면에서 강력한 ${\displaystyle \varepsilon }$ -core는$$ 탈퇴에$$ 대해 $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon }$의 위약금을 지불해야 할 경우 대연정을 탈퇴함으로써 어떤 연합도 보수를 개선할 수 없는 사전 인상들의 집합이다. $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon }$은(는) 음수일 수 있으며$$, 이 경우 대연정 탈퇴에 대한 보너스를 나타낸다. 분명히 코어가 비어 있든 없든 간에, 강한 $strong{\displaystyle }$ ${\displaystyle \varepsilon }$ -core는$$ $enough{\displaystyle }$ ${\displaystyle \varepsilon }$의 큰 값에는 비어 있지 않고$$, $\epsilon {\displaystyle }$ ${\displaysty \varepsilon }$의 작은 값에는 비어 있을 것이다$.$ 이 추론 선에 따라, 최소 핵심이 도입되었다. in (Maschler, Pelleg & Shapley 1979)은 비어 있지 않은 모든 강한 $strong{\displaystyle }$ ${\displaystyle \varepsilon }$ - 코어의$$ 교차점이다. 또한 empt의 최소값인$$ $\epsilon {\displaystyle }$ ${\$$displaystyle \varepsilon }$ -core의$$ 강력한 $\epsilon {\displaystyle }$ ${\$displaystyle \varepsilon } -core로 볼 수 있으며, 이는 세트를 비어 있지 않게 만드는 ε {\$displaysty \$varepsilon $}.$

샤플리 값

샤플리 값은 효율적이고 대칭적이며 단조로움을 만족시키는 고유한 성과급 벡터다.^[15] 로이드 샤플리(Shapley 1953)에 의해 도입되었는데, 이 벡터는 효율적이고 대칭적이며 첨가되며 더미플레이어에게 제로 보급을 할당하는 독특한 페이오프 벡터임을 보여주었다. 슈퍼가디티브 게임의 샤플리 가치는 개인적으로는 합리적이나, 일반적으로 이것은 사실이 아니다.(Driessen 1988)

낟알

$v{\displaystyle }$: ${\displaystyle {2N}^{}}$→ ${\displaystyle R\mathbb{}}$ ${\$를) \mathb ${\$을(를) 게임으로$$ 하고, $x{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$을 효율적인 성과 벡터가 되게$$ 한다. x에 관해서 선수 j보다 선수 i의 최대 잉여는

${\displaystyle s_{ij}^{v}(x)=\max \left\{v(S)-\sum _{k\in S}x_{k}:S\subseteq N\setminus \{j\}i\in S\right\}}}$

i의 연정 탈퇴에 있는 다른 선수들이 x에 따른 보상에 만족한다고 가정했을 때, 보수 벡터 x 아래의 대연정 N에서 탈퇴함으로써 j 선수의 협조 없이 내가 얻을 수 있는 최대 금액 선수 최대 흑자는 한 선수가 다른 선수에 대해 협상력을 측정하는 방식이다. $v{\displaystyle }$ ${\displaystyle v}$의 커널은 충족되는 귀책 x의 집합임$$

• ${\displaystyle ({}_{}^{}}$ i ${\displaystyle {}_{}^{}}$ ${\displaystyle v_{}^{}}$(${\displaystyle x}$ ) -${\displaystyle }$s ${\displaystyle j_{}^{}}$ ${\displaystyle i_{}^{}}$ ${\displaystyle {}_{}^{}}$( ${\displaystyle x}$)${\displaystyle \times }$( ${\displaystyle x}$ ${\displaystyle j_{}}$- v${\displaystyle }$(${\displaystyle }$j ) )${\displaystyle }$× ( x j - ${\displaystyle v}$ ) ${\displaystyle \le }$ ${\displaystyle 0}$ ${\displaystyle (s_{ij}^{v}-s_{ji}^{ji}(x)}}^\caps (x_{j}-v)\leq$ 0$\}$ 및
• ${\displaystyle (s_{ji}^{v}(x)-s_{ij}^{v}(x)\cHB(x_{i}-v(i))\leq 0}$

모든 선수 쌍에 대해 i와 j. Intuitively, player i has more bargaining power than player j with respect to imputation x if ${\displaystyle s_{ij}^{v}(x)>s_{ji}^{v}(x)}$, but player j is immune to player i's threats if ${\displaystyle x_{j}=v(j)}$, because he can obtain this payoff on his own. 커널에는 다른 플레이어에 대해 이 협상력을 가진 플레이어가 없는 모든 비난이 들어 있다. 이 솔루션 개념은 (Davis & Maschler 1965)에서 처음 도입되었다.

뉴클레오루스

$v{\displaystyle }$: ${\displaystyle {2N}^{}}$→ ${\displaystyle R\mathbb{}}$ ${\$을(를) \mathb {\$displaystyle x\in \mathb {R}$^{N$}}}$을(를) 게임으로$$ 하고, $x{\displaystyle {}^{}}$ R N ${\$displaybor로 한다$$. The excess of ${\displaystyle x}$ for a coalition ${\displaystyle S\subseteq N}$ is the quantity ${\displaystyle v(S)-\sum _{i\in S}x_{i}}$; that is, the gain that players in coalition ${\displaystyle S}$ can obtain if they withdraw from the grand coalition ${\displaystyle N}$ $지불{\displaystyle }$ x ${\displaystyle x}$에서 대신$$ 지불 $v{\displaystyle }$( S${\displaystyle }$) ${\displaystyle v(S)}$을(를) 선택하십시오$.$

이제 $\theta {\displaystyle }$( ${\displaystyle x}$) ${\displaystyle \in }$ R ${\displaystyle {2^{}}^{}}$ ${\displaystyle {{\mathrm{}}^{}}^{}}$ ${\$을(를) x ${\displaystyle x}$의 초과 벡터가 되도록 하십시오$$$.$ 즉, 나는, 나는 < ∀, j{\displaystyle \theta_{나는}())\geq \theta _ᆯ()),\forall ~i<. j}.≥ θ j())())θ았던 x{\displaystyle)}의 코어 v{\displaystyle v}만일 그것은 pre-imputation과 θ 1())≤ 0{\displaystyle \theta_{1}())\leq 0}에게...규정할 수 nucleolu.s, 우리는 consider the lexicographic ordering of vectors in ${\displaystyle \mathbb {R} ^{2^{N}}}$: For two payoff vectors ${\displaystyle x,y}$, we say ${\displaystyle \theta (x)}$ is lexicographically smaller than ${\displaystyle \theta (y)}$ if for some index ${\displaystyle k}$, we have ${\displaystyle \theta _{i}(x)=\theta _{i}(y),\forall ~i<k}$ and ${\displaystyle \theta _{k}(x)<\theta _{k}(y)}$. (The ordering is called lexicographic because it mimics alphabetical ordering used to arrange words in a dictionary.) $v{\displaystyle }$ ${\displaystyle v}$의 뉴클레오루스는 이 순서에 근거한 사전 기록학적으로 최소한의 귀책이다. 이 솔루션 개념은 (Schmeidler 1969)에서 처음 도입되었다.

뉴클레오스의 정의는 추상적으로 보이지만(Maschler, Pelleg & Shapley 1979년) 보다 직관적인 설명을 했다. 최소 코어부터 ${\displaystyle \mathrm{시작}}$하여 C ${\displaystyle {\epsilon }_{}}$( v${\displaystyle }$) ${\displaystyle C_{\varipsilon }(v)}$의 정의에서 불평등의 우측을 더 줄일 수 없는$$ 연합을 세트를 비워 두지 않고 기록한다. 세트를 비우지 않고서는 줄일 수 없을 때까지 나머지 연합에 대한 오른쪽 측면을 계속 줄이십시오. 불평등이 평등하게 유지되는 새로운 연합군을 기록하라; 남아있는 연합의 오른쪽 측면을 계속 감소시키고, 모든 연합이 기록될 때까지 이 과정을 필요한 만큼 반복한다. 그 결과 발생하는 이익 벡터는 핵이다.

특성.

• 비록 정의가 명시적으로 명시되어 있지 않지만, 뉴클레오스는 항상 독특하다. (Driessen 1988)의 섹션 II.7 참조)
• 핵이 비어 있지 않으면 핵이 핵 안에 있다.
• 뉴클레오스는 항상 커널 안에 있고, 커널은 협상 세트에 포함되어 있기 때문에, 항상 협상 세트 안에 있다(자세한 내용은 (Driessen 1988 참조).

볼록스 협동 게임

샤플리가 (Shapley 1971)에 소개한 볼록한 협동 게임은 일부 게임이 "눈덩이"라는 직관적인 특성을 포착한다. 구체적으로, 게임은 그것의 특성 함수 $v{\displaystyle }$ ${\displaystyle v}$이(가) 슈퍼모델인 경우 볼록하다.

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

$v{\displaystyle }$ ${\displaystyle v}$의 초변형성이 v$$ {\displaystyle v}과(예: (Driessen 1988)의 섹션 V.1 참조)와 동일함을 나타낼 수 있다.

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

즉, "연정이 커질수록 연정에 동참할 동기가 증가한다"(Shapley 1971)는 앞서 언급한 눈덩이 효과로 이어진다. 코스트 게임의 경우 불평등이 역전되어 특성 함수가 하위모델일 경우 코스트 게임이 볼록하다고 말한다.

특성.

볼록스 협동 게임은 많은 좋은 특성을 가지고 있다.

• 초변형성은 사소한 것으로 초가성을 내포하고 있다.
• 볼록스 게임은 완전히 균형을 이루고 있다. 볼록한 게임의 핵심은 비어 있지 않고, 볼록한 게임의 어떤 서브게임도 볼록하기 때문에 어떤 서브게임의 핵심도 비어 있지 않다.
• 볼록한 게임은 코어와 일치하는 독특한 안정 세트를 가지고 있다.
• 볼록한 게임의 샤플리 가치는 그 중심부의 무게 중심이다.
• 코어의 극한점(Vertex)은 다항식 시간에 탐욕 알고리즘: Let $let{\displaystyle }$: ${\displaystyle N}$→ N ${\displaystyle \pi$:$N\to N}$ be a permutation of the players, and let ${\displaystyle S_{i}=\{j\in N:\pi (j)\leq i\}}$ be the set of players ordered ${\displaystyle 1}$ through ${\displaystyle i}$ in ${\displaystyle \pi }$, for any ${\displaystyle i=0,\ldots ,n}$, with ${\displaystyle S_0=\mathrm{\varnothing }}$${\displaystyle S_{0}=\emptyset }$. Then the payoff ${\displaystyle x\in \mathbb {R} ^{N}}$ defined by ${\displaystyle x_{i}=v(S_{\pi (i)})-v(S_{\pi (i)-1}),\forall ~i\in N}$ is a vertex of the core of ${\displaystyle v}$. Any vertex of the core 적절한 순열 ${\displaystyle \pi }$을(를) 선택하여 이러한 방식으로 구성할 수 있다$.$

조합 최적화와 유사성 및 차이점

서브모듈라 및 초모듈라 집합함수는 조합 최적화에 있어서도 연구된다. (Shapley 1971)의 많은 결과들은 (Edmonds 1970)에서 유사성을 가지고 있는데, 여기서 하위모형 함수는 처음에 모종 함수를 모종의 일반화로 제시하였다. 이런 맥락에서 볼록코스트 게임의 핵심을 기본 다면체라고 하는데, 그 요소들이 매트로이드의 기본 특성을 일반화하기 때문이다.

그러나 최적화 커뮤니티는 두 가지 유형의 기능의 최소화가 계산적으로 추적가능하기 때문에 일반적으로 하위모형 함수를 볼록함수의 이산 유사점(Lovász 1983)으로 간주한다. 불행히도, 이것은 "콘벡스"로서 초모듈러 함수를 원래 정의했던 샤플리와 직접적으로 충돌한다.

참고 항목

• 컨센서스 의사결정
• 코디네이션 게임
• 가정내 교섭
• 헤도닉 게임
• 선형생산게임

참조

추가 읽기

• Bilbao, Jesús Mario (2000), Cooperative Games on Combinatorial Structures, Kluwer Academic Publishers, ISBN 9781461543930

• Davis, M.; Maschler, M. (1965), "The kernel of a cooperative game", Naval Research Logistics Quarterly, 12 (3): 223–259, doi:10.1002/nav.3800120303

• Driessen, Theo (1988), Cooperative Games, Solutions and Applications, Kluwer Academic Publishers, ISBN 9789401577878

• Edmonds, Jack (1970), "Submodular functions, matroids and certain polyhedra", in Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J. (eds.), Combinatorial Structures and Their Applications, New York: Gordon and Breach, pp. 69–87

• Lovász, László (1983), "Submodular functions and convexity", in Bachem, A.; Grötschel, M.; Korte, B. (eds.), Mathematical Programming—The State of the Art, Berlin: Springer, pp. 235–257

• Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1. 88페이지의 수학 소개; 8장을 참조하라. 많은 대학에서 무료 온라인(구독 필요)

• Lucas, William F. (1969), "The Proof That a Game May Not Have a Solution", Transactions of the American Mathematical Society, 136: 219–229, doi:10.2307/1994798, JSTOR 1994798.

• Lucas, William F. (1992), "Von Neumann-Morgenstern Stable Sets", in Aumann, Robert J.; Hart, Sergiu (eds.), Handbook of Game Theory, Volume I, Amsterdam: Elsevier, pp. 543–590

• Luce, R.D. and Raiffa, H. (1957) Games and Decisions: An Introduction and Critical Survey, Wiley & Sons. (see Chapter 8).
• Maschler, M.; Peleg, B.; Shapley, Lloyd S. (1979), "Geometric properties of the kernel, nucleolus, and related solution concepts", Mathematics of Operations Research, 4 (4): 303–338, doi:10.1287/moor.4.4.303

• Osborne, M.J. and Rubinstein, A. (1994) A Course in Game Theory, MIT Press (see Chapters 13,14,15)
• Moulin, Herve (1988), Axioms of Cooperative Decision Making (1st ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-42458-5

• Owen, Guillermo (1995), Game Theory (3rd ed.), San Diego: Academic Press, ISBN 978-0-12-531151-9

• Schmeidler, D. (1969), "The nucleolus of a characteristic function game", SIAM Journal on Applied Mathematics, 17 (6): 1163–1170, doi:10.1137/0117107.

• Shapley, Lloyd S. (1953), "A value for ${\displaystyle n}$-person games", in Kuhn, H.; Tucker, A.W. (eds.), Contributions to the Theory of Games II, Princeton, New Jersey: Princeton University Press, pp. 307–317

• Shapley, Lloyd S. (1971), "Cores of convex games", International Journal of Game Theory, 1 (1): 11–26, doi:10.1007/BF01753431, S2CID 123385556

• Shapley, Lloyd S.; Shubik, M. (1966), "Quasi-cores in a monetary economy with non-convex preferences", Econometrica, 34 (4): 805–827, doi:10.2307/1910101, JSTOR 1910101

• Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7. A comprehensive reference from a computational perspective; see Chapter 12. Downloadable free online.

• von Neumann, John; Morgenstern, Oskar (1944), "Theory of Games and Economic Behavior", Nature, Princeton: Princeton University Press, 157 (3981): 172, Bibcode:1946Natur.157..172R, doi:10.1038/157172a0, S2CID 29754824

• Yeung, David W.K. and Leon A. Petrosyan. Cooperative Stochastic Differential Games (Springer Series in Operations Research and Financial Engineering), Springer, 2006. Softcover-ISBN 978-1441920942.
• Yeung, David W.K. and Leon A. Petrosyan. Subgame Consistent Economic Optimization: An Advanced Cooperative Dynamic Game Analysis (Static & Dynamic Game Theory: Foundations & Applications), Birkhäuser Boston; 2012. ISBN 978-0817682613

External links

• "Cooperative game", Encyclopedia of Mathematics, EMS Press, 2001 [1994]