協力ゲーム理論

ゲーム理論において、協力ゲームまたは連合ゲームとは、プレイヤーのグループが拘束力のある「連合」を形成し、協力行動を外部から強制するゲーム（例えば契約法など）を指します。これは、同盟を形成する可能性が全くないか、すべての合意が自己強制的である必要がある非協力ゲーム（例えば、信頼できる脅威など）とは異なります。^[1]

協力ゲームは、形成される可能性のある連合、グループが取ることができる共同行動、そしてその結果得られる集団的利益に焦点を当てて分析される。^[2]^[3]

数学的な定義

協力ゲームは、各連合の価値を指定することによって定義される。正式には、連合ゲームは、大連合と呼ばれる有限のプレイヤー集合と、プレイヤーのあらゆる可能な連合の集合から、を満たす支払集合への特性関数^[4]から構成される。この関数は、プレイヤー集合が連合を形成することでどれだけの集団的利得を得ることができるかを記述する。 $N$ $v:2^{N}\to \mathbb {R}$ $v(\emptyset )=0$

主な属性

協力ゲーム理論は、プレイヤーが連合を形成し、互いに協力し、拘束力のある合意を結ぶゲームを研究するゲーム理論の一分野です。この理論は、2人以上のプレイヤーが他のプレイヤーの幸福に影響を与える選択を迫られるシナリオを分析するための数学的手法を提供します。^[5]

共通の利益：協力ゲームでは、プレイヤーは特定の目標または結果を達成するという共通の利益を共有します。プレイヤーは協力の基盤と根拠を確立するために、共通の利益を特定し、合意する必要があります。プレイヤーが共通の利益を明確に理解すれば、それを達成するために協力することができます。^[要出典]
必要な情報交換：協力には、プレイヤー間のコミュニケーションと情報交換が不可欠です。プレイヤーは、相互利益の機会を特定するために、それぞれの好み、資源、制約に関する情報を共有する必要があります。情報を共有することで、プレイヤーは互いの目標をより深く理解し、協力して達成に向けて取り組むことができます。^[要出典]
自発性、平等性、そして相互利益：協力ゲームでは、プレイヤーは自発的に集まり、連合を形成し、合意を形成します。プレイヤーは連合において対等なパートナーでなければならず、いかなる合意も相互に利益をもたらすものでなければなりません。協力は、すべての当事者が利益を公平に受け取っていると感じている場合にのみ持続可能です。^[要出典]
強制契約：協力ゲームにおいて、プレイヤー間の合意は拘束力を持ち、義務的なものである。プレイヤーが特定の行動方針に合意したら、それを履行する義務が生じる。プレイヤーは互いに信頼し合い、約束を守る必要があり、合意を強制するための仕組みが整備されている必要がある。合意を拘束力を持ち、義務的なものにすることで、プレイヤーは共通の目標を達成することを保証できる。^[要出典]

サブゲーム

プレイヤーの空でない連合をとする。上の部分ゲームは自然に次のように定義される。 $S\subsetneq N$ $v_{S}:2^{S}\to \mathbb {R}$ $S$

v_{S}(T)=v(T),\forall ~T\subseteq S.

言い換えれば、我々は単にに含まれる連合にのみ注目することになります。サブゲームは、大連合に対して定義されたソリューションの概念をより小さな連合に適用できるため便利です。 $S$

数学的性質

超加法性

特性関数はしばしば超加法的であると仮定される（Owen 1995, p. 213）。これは、互いに素な連合の和の値は、連合の個々の値の合計に等しいことを意味する。

$v(S\cup T)\geq v(S)+v(T)$ いつでも満足してください。 $S,T\subseteq N$ $S\cap T=\emptyset$

単調性

大規模な連合はより多くの利益を得る:

$S\subseteq T\Rightarrow v(S)\leq v(T)$ 。

これは超加法性から導き出されます。つまり、報酬が正規化されると、シングルトン連合の値はゼロになります。

シンプルなゲームのプロパティ

連合ゲーム $v$ は、利得が1か0、つまり連合が「勝つ」か「負ける」かのどちらかである場合、単純であるとみなされる。 ^[6]

同様に、単純ゲームは $W個$ の連合の集合として定義することができ、 $W$ のメンバーは勝利連合、その他のメンバーは敗北連合と呼ばれます。単純ゲームは空ではない、あるいは空集合を含まないと想定される場合もあります。しかし、数学の他の分野では、単純ゲームはハイパーグラフやブール関数（論理関数）とも呼ばれます。

単純なゲーム $Wが$ 単調であるとは、勝利している連合を含む任意の連合も勝利している場合、つまりでありを意味する場合です。 $S\in W$ $S\subseteq T$ $T\in W$
単純なゲーム $Wが$ 適切であるとは、任意の勝利連合の補連合（反対連合）が敗北している場合、つまりを意味する場合です。 $S\in W$ $N\setminus S\notin W$
単純なゲームWは、負けている連合の補連合が勝っている場合、つまりを意味する場合、強いゲームです。 $S\notin W$ $N\setminus S\in W$
- 単純ゲーム $W$ が適切かつ強いゲームである場合、連合が勝っているのは、その補ゲームが負けている場合のみであり、つまり、の場合に限ります。（ $v が任意の$ $S$ に対して適切かつ強い連合単純ゲームである場合）。 $S\in W$ $N\setminus S\notin W$ $v(S)=1-v(N\setminus S)$
単純ゲームにおける拒否権プレイヤー（拒否権者）とは、すべての勝利連合に属するプレイヤーのことである。拒否権プレイヤーが存在すると仮定すると、拒否権プレイヤーを含まない連合は敗北する。単純ゲームWは、拒否権プレイヤーが存在する場合、つまりすべての勝利連合の交点が空でない場合、弱い（協調的）ゲームである。 $\bigcap W:=\bigcap _{S\in W}S$
- 単純ゲームにおける独裁者とは、拒否権を持つプレイヤーであり、そのプレイヤーを含む連合はいずれも勝利する。独裁者は敗北する連合には属さない。（実験経済学における独裁者ゲームはこれとは無関係である。）
単純ゲーム $W$ のキャリアとは、任意の連合 $S$ に対して、かつが成り立つような集合である。単純ゲームにキャリアが存在する場合、そのゲームに所属しないプレイヤーは無視される。単純ゲームは、キャリアが有限である場合（ $N$ が無限であっても）、有限ゲームと呼ばれることがある。 $T\subseteq N$ $S\in W$ $S\cap T\in W$
単純ゲームにおける中村数とは、交差点が空である勝利連合の最小数である。中村の定理によれば、この数は合理性の度合いを測るものであり、集約ルールが明確に定義された選択肢をどの程度生み出せるかを示す指標である。

上記の公理の間には、次のようないくつかの関係が広く認識されている（例えば、Peleg, 2002、セクション2.1 ^[7]）。

単純なゲームが弱ければ、それは適切です。
単純なゲームは、強いか弱いかのどちらかである場合に限り独裁的になります。

より一般的には、4つの従来の公理（単調性、適切性、強さ、非弱さ）、有限性、アルゴリズムの計算可能性^[8]の関係についての完全な調査が行われており（Kumabe and Mihara, 2011 ^[9]）、その結果は以下の表「単純なゲームの存在」にまとめられている。

単純なゲームの存在^[10]
タイプ	有限非補償	有限計算可能	無限の非コンプ	無限に計算可能
1111	いいえ	はい	はい	はい
1110	いいえ	はい	いいえ	いいえ
1101	いいえ	はい	はい	はい
1100	いいえ	はい	はい	はい
1011	いいえ	はい	はい	はい
1010	いいえ	いいえ	いいえ	いいえ
1001	いいえ	はい	はい	はい
1000	いいえ	いいえ	いいえ	いいえ
0111	いいえ	はい	はい	はい
0110	いいえ	いいえ	いいえ	いいえ
0101	いいえ	はい	はい	はい
0100	いいえ	はい	はい	はい
0011	いいえ	はい	はい	はい
0010	いいえ	いいえ	いいえ	いいえ
0001	いいえ	はい	はい	はい
0000	いいえ	いいえ	いいえ	いいえ

単純ゲームに対する様々な公理がナカムラ数に課す制約も広く研究された。^{[11]特に、拒否権を持つプレイヤーがいない計算可能な単純ゲームは、それが}適切かつ非強ゲームである場合にのみ、ナカムラ数が3より大きい。

非協力理論との関係

Gを戦略的（非協力的）ゲームとする。連合が協調行動を強制する能力を持つと仮定すると、Gには複数の協力ゲームが関連付けられる。これらのゲームはしばしばG の表現と呼ばれる。標準的な2つの表現は以下の通りである：^[12]

α効果ゲームでは、各連合に、その構成員が力を合わせることで「保証」できる利益の合計が関連付けられます。「保証」とは、その値が最大最小値、例えば、反対勢力の戦略における最小値の最大値を意味します。
β効果ゲームでは、各連合に、その構成員が力を合わせることで「戦略的に保証」できる利益の合計が関連付けられます。「戦略的に保証」とは、その値が最小値と最大値、例えば、反対勢力の戦略における最大値の最小値であることを意味します。

ソリューションのコンセプト

協力ゲーム理論における主要な仮定は、大連合が形成されるというものである。^[13]課題は、プレイヤー間で何らかの方法で利得を分配することである。（この仮定は限定的なものではない。プレイヤーが分裂してより小規模な連合を形成した場合でも、実際に形成される連合によって定義されるサブゲームに解決概念を適用できるからである。）解決概念とは、各プレイヤーへの配分を表すベクトル（またはベクトルの集合）である。研究者たちは、公平性の概念に基づいて、様々な解決概念を提案してきた。解決概念に求められる特性には、以下のようなものがある。 $N$ $v(N)$ $x\in \mathbb {R} ^{N}$

効率: ペイオフベクトルは合計値を正確に分割します: 。 $\sum _{i\in N}x_{i}=v(N)$
個人の合理性: どのプレイヤーも、単独で得られる金額よりも少ない金額を受け取ることはありません。 $x_{i}\geq v(\{i\}),\forall ~i\in N$
存在: どのゲームにもソリューションコンセプトが存在します。 $v$
独自性: ソリューションのコンセプトはどのゲームでも独自です。 $v$
限界性: プレイヤーの報酬は、このプレイヤーの限界貢献度のみによって決まります。つまり、これらの限界貢献度が 2 つの異なるゲームで同じであれば、報酬も同じになります。つまり、とではが同じであることを意味します。 $v(S\cup \{i\})=w(S\cup \{i\}),\forall ~S\subseteq N\setminus \{i\}$ $x_{i}$ $v$ $w$
単調性: プレイヤーの限界貢献が増加すると、そのプレイヤーの報酬も増加します。つまり、ではがよりも弱く大きくなることを意味します。 $v(S\cup \{i\})\leq w(S\cup \{i\}),\forall ~S\subseteq N\setminus \{i\}$ $x_{i}$ $w$ $v$
計算の容易さ: ソリューションの概念は、効率的に計算できます (つまり、プレーヤーの数に関して多項式時間で計算できます)。 $|N|$
対称性：このソリューションのコンセプトは、対称的なプレイヤー、に均等な支払いを割り当てることです。2 人のプレイヤー、が対称的であるとは、の場合です。つまり、プレイヤーの 1 人だけが参加する任意の連合において、1 人のプレイヤーを他のプレイヤーと交換しても、支払いは変わりません。 $x$ $x_{i}=x_{j}$ $i$ $j$ $i$ $j$ $v(S\cup \{i\})=v(S\cup \{j\}),\forall ~S\subseteq N\setminus \{i,j\}$
加法性：2つのゲームの合計におけるプレイヤーへの配分は、各ゲームにおけるプレイヤーへの配分の合計です。数学的には、とがゲームである場合、このゲームは、連合が2つのゲームで得るであろう利得の合計を、任意の連合に割り当てます。加法的な解の概念は、各プレイヤーにとで受け取るであろう利得の合計を割り当てます。 $v$ $\omega$ $(v+\omega )$ $(v+\omega )$ $v$ $\omega$
ヌルプレイヤーへの配分ゼロ：ヌルプレイヤーへの配分はゼロです。ヌルプレイヤーは を満たします。経済学的に言えば、ヌルプレイヤーを含まない連合におけるヌルプレイヤーの限界価値はゼロです。 $i$ $v(S\cup \{i\})=v(S),\forall ~S\subseteq N\setminus \{i\}$

効率的な利得ベクトルは前置と呼ばれ、個々に合理的な前置は代入と呼ばれます。ほとんどの解の概念は代入です。

安定したセット

ゲームの安定集合（フォン・ノイマン・モルゲンシュテルンの解（フォン・ノイマン＆モルゲンシュテルン、1944年）としても知られる）は、2人以上のプレイヤーがいるゲームに対して提案された最初の解であった。をゲームとし、、の2つの代入をそれぞれとすると、いずれかの連合がおよびを満たす場合、が優勢となる。言い換えれば、のプレイヤーはからの利得をからの利得よりも好み、が使用される場合、彼らが大連合から離脱すると脅す可能性がある。なぜなら、彼らが単独で得る利得は、のもとで受け取る配分と少なくとも同じ大きさだからである。 $v$ $x$ $y$ $v$ $x$ $y$ $S\neq \emptyset$ $x_{i}>y_{i},\forall ~i\in S$ $\sum _{i\in S}x_{i}\leq v(S)$ $S$ $x$ $y$ $y$ $x$

安定セットとは、次の 2 つの特性を満たす代入セットです。

内部安定性: 安定したセット内のどのペイオフベクトルも、セット内の別のベクトルによって支配されません。
外部安定性: セット外部のすべてのペイオフベクトルは、セット内の少なくとも 1 つのベクトルによって支配されます。

フォン・ノイマンとモルゲンシュテルンは、安定集合を社会において許容される行動の集合と捉えました。つまり、ある行動が他の行動よりも明確に優れているという概念は存在しませんが、許容されない行動にはそれぞれ、好ましい代替行動が存在するという概念です。この定義は非常に一般的なため、様々なゲーム形式でこの概念を使用することができます。^[要出典]

プロパティ

安定集合は存在する場合もあれば存在しない場合もあります（Lucas 1969）。また、存在する場合でも、通常は一意ではありません（Lucas 1992）。安定集合を見つけるのは通常困難です。こうした困難さやその他の困難さから、多くの解法概念が開発されてきました。
協力ゲームの正の割合は、コアからなる一意の安定したセットを持ちます(Owen 1995、p. 240)。
協力ゲームの正の割合は、プレイヤーを差別する安定集合を持つ。そのような集合では、少なくとも差別されるプレイヤーの少なくとも一部は排除される（Owen 1995, p. 240）。 $n-2$ $n-3$

コア

をゲームとする。その核となるのは利得ベクトルの集合である。 $v$ $v$

C(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),\forall ~S\subseteq N\right\}.

言葉で言えば、コアとは、どの連合もその構成員の利得の合計よりも大きな価値を持たないような帰属集合である。したがって、どの連合も大連合から離脱してより大きな利得を得るインセンティブを持たない。

プロパティ

ゲームの核は空である場合がある（ボンダレヴァ・シャプレーの定理を参照）。核が空でないゲームは均衡していると呼ばれる。
空でない場合、コアには必ずしも一意のベクトルが含まれるわけではありません。
コアは任意の安定集合に含まれており、コアが安定している場合、それは唯一の安定集合です。証明については (Driessen 1988) を参照してください。

好みに関するシンプルなゲームの核

単純なゲームでは、各プレイヤーが選択肢の集合に対して選好を持っていると仮定した場合、コアという別の概念が存在します。プロファイルとは、における個人の選好のリストです。ここで、は、個人がプロファイルにおいてに対する代替案を好むことを意味します。単純なゲームとプロファイルが与えられた場合、すべてのに対してを満たす勝利連合（すなわち、）が存在する場合にのみ、における優位関係がによって定義されます。選好のプロファイルに関する単純なゲームのコアは、によって優位にならない選択肢の集合（に関するの最大元の集合）です。 $X$ $p=(\succ _{i}^{p})_{i\in N}$ $\succ _{i}^{p}$ $X$ $x\succ _{i}^{p}y$ $i$ $x$ $y$ $p$ $v$ $p$ $\succ _{v}^{p}$ $X$ $x\succ _{v}^{p}y$ $S$ $v(S)=1$ $x\succ _{i}^{p}y$ $i\in S$ $C(v,p)$ $v$ $p$ $\succ _{v}^{p}$ $X$ $\succ _{v}^{p}$

x\in C(v,p)

が存在しない場合に限ります。

y\in X

y\succ _{v}^{p}x

単純ゲームの中村数は、交差点が空である勝利連合の最小数です。中村の定理は、が有限での基数（要素の数）がの中村数より小さい場合、かつその場合に限り、非巡回（あるいは推移的）な選好のすべてのプロファイルに対して核が空でないことを定義します。熊部と三原による変形では、の基数がの中村数より小さい場合、かつその場合に限り、最大要素を持つ選好のすべてのプロファイルに対して核が空でないことを定義します。（詳細は中村数を参照してください。） $C(v,p)$ $p$ $X$ $X$ $v$ $C(v,p)$ $p$ $X$ $v$

強力なイプシロンコア

核は空である可能性があるため、(Shapley & Shubik 1966)で一般化が導入された。ある数の強核は $\varepsilon$ 、利得ベクトルの集合である。 $\varepsilon \in \mathbb {R}$

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\}.

経済学の用語では、強い-コアとは、連合が大連立を離脱することでその報酬を改善できない、つまり離脱することでのペナルティを支払わなければならないような事前帰属の集合である。は負である可能性があり、その場合には大連立を離脱することに対するボーナスを表す。明らかに、コアが空であるかどうかに関わらず、強い-コアはが十分に大きい値の場合には空でなくなり、が十分に小さい（おそらく負の）値の場合には空になる。この論理に従えば、 (Maschler, Peleg & Shapley 1979) で導入された最小コアは、空でないすべての強い -コアの共通部分である。これは、集合が空でなくなるの最小値の強い -コアとみなすこともできる(Bilbao 2000)。 $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$

シャプレー値

シャプレー値とは、効率的、対称的、かつ単調性を満たす唯一の利得ベクトルである。^[14]ロイド・シャプレー（Shapley 1953）によって導入され、効率的、対称的、加法的であり、ダミープレイヤーにゼロの利得を割り当てる唯一の利得ベクトルであることを示した。超加法的ゲームにおけるシャプレー値は個々に合理的であるが、一般にはそうではない。（Driessen 1988）

カーネル

をゲームとし、を効率的な利得ベクトルとする。プレイヤーiのプレイヤーjに対するxに関する最大余剰は $v:2^{N}\to \mathbb {R}$ $x\in \mathbb {R} ^{N}$

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

プレイヤーiがプレイヤーjの協力なしに、利得ベクトルxのもとで大連合Nから撤退することで得られる最大額。ただし、 iの撤退する連合の他のプレイヤーはxのもとでそれぞれの利得に満足していると仮定する。最大余剰は、あるプレイヤーが他のプレイヤーに対して持つ交渉力を測る方法である。の核は、以下の条件を満たす帰属xの集合である。 $v$

$(s_{ij}^{v}(x)-s_{ji}^{v}(x))\times (x_{j}-v(j))\leq 0$ 、そして
$(s_{ji}^{v}(x)-s_{ij}^{v}(x))\times (x_{i}-v(i))\leq 0$

プレイヤーiとjのあらゆるペアについて、となる。直感的に、の場合には、プレイヤーiは代入xに関してプレイヤーjよりも交渉力が高いが、の場合には、プレイヤーjは自分でこの利得を獲得できるため、プレイヤーi の脅威の影響を受けない。カーネルには、どのプレイヤーも他のプレイヤーに対してこの交渉力を持たないすべての代入が含まれる。この解の概念は、(Davis & Maschler 1965) で初めて導入された。 $s_{ij}^{v}(x)>s_{ji}^{v}(x)$ $x_{j}=v(j)$

ハルサニ配当

ハーサニ配当（1963年にシャプレー値を一般化するために用いたジョン・ハーサニにちなんで名付けられた^[15]）は、協力ゲームにおけるプレイヤーの連合によって生み出される余剰を特定する。この余剰を特定するために、この連合の価値は、部分連合によって既に生み出された余剰を差し引くことによって補正される。この目的のため、ゲームにおける連合の配当は、再帰的に次のように決定される。 $d_{v}(S)$ $S$ $v$

${\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_{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{aligned}}$

被除数の明示的な式はで与えられる。この関数はのメビウス逆関数としても知られている。^[16]実際、という式を用いることでからを復元することができる。 ${\textstyle d_{v}(S)=\sum _{T\subseteq S}(-1)^{|S\setminus T|}v(T)}$ $d_{v}:2^{N}\to \mathbb {R}$ $v:2^{N}\to \mathbb {R}$ $v$ $d_{v}$ ${\textstyle v(S)=d_{v}(S)+\sum _{T\subsetneq S}d_{v}(T)}$

Harsanyi 配当は、ゲームとソリューションの概念の両方を分析するのに役立ちます。たとえば、Shapley 値は各連合の配当をそのメンバーに分配することによって得られます。つまり、ゲーム内のプレイヤーのShapley 値は、プレイヤーが属するすべての連合の配当の取り分を合計することによって得られます。 $\phi _{i}(v)$ $i$ $v$ ${\textstyle \phi _{i}(v)=\sum _{S\subset N:i\in S}{d_{v}(S)}/{|S|}}$

核小体

をゲームとし、を利得ベクトルとする。連合におけるの超過量はである。つまり、連合のプレイヤーが利得の下で大連合から離脱し、代わりに利得を受け取った場合に得られる利得である。の核小体とは、すべての連合の超過量のベクトル（のベクトル）がレキシミン順序において最小となるような帰属である。核小体は(Schmeidler 1969)で導入された。 $v:2^{N}\to \mathbb {R}$ $x\in \mathbb {R} ^{N}$ $x$ $S\subseteq N$ $v(S)-\sum _{i\in S}x_{i}$ $S$ $N$ $x$ $v(S)$ $v$ $\mathbb {R} ^{2^{N}}$

(Maschler, Peleg & Shapley 1979) はより直感的な説明を与えている。コアが最も小さいものから始めて、定義における不等式の右辺をこれ以上縮小すると集合が空になるような提携を記録する。残りの提携についても、右辺を縮小し続け、集合が空にならない限り縮小できなくなるまで縮小を続ける。不等式が等しくなる新しい提携集合を記録し、残りの提携についても右辺を縮小し続け、このプロセスを必要な回数だけ繰り返し、すべての提携を記録する。結果として得られる利得ベクトルが核小体である。 $C_{\varepsilon }(v)$

プロパティ

定義では明示的に述べられていないが、核小体は常に一意である。（証明については、(Driessen 1988)のセクションII.7を参照。）
核が空でない場合は、核小体は核の中にあります。
核小体は常に核内にあり、核は交渉セットに含まれているため、核は常に交渉セット内にあります (詳細については (Driessen 1988) を参照)。

凸協力ゲーム

凸協力ゲームは、 Shapley (1971)によって導入され、一部のゲームが持つ「スノーボール」という直感的な性質を捉えています。具体的には、特性関数が超モジュラーである場合、ゲームは凸ゲームです。 $v$

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

のスーパーモジュラリティは次式と等価であることが示される（例えば、(Driessen 1988)のセクションV.1を参照）。 $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 1971）ため、前述の雪だるま効果が生じる。コストゲームの場合、不等式は逆になり、特性関数が劣モジュラである場合、コストゲームは凸であると言える。

プロパティ

凸協力ゲームには多くの優れた特性があります。

超モジュラ性は、自明に超加法性を意味します。
凸ゲームは完全にバランスが取れています。凸ゲームのコアは空ではなく、凸ゲームのサブゲームはどれも凸であるため、サブゲームのコアも空ではありません。
凸ゲームには、そのコアと一致する一意の安定集合があります。
凸ゲームのシャプレー値は、そのコアの重心です。
コアの極点（頂点）は、貪欲アルゴリズムを用いて多項式時間で見つけることができます。をプレイヤーの順列とし、を任意のについてにおいてを通して順序付けられたプレイヤーの集合とします。このとき、によって定義される利得はのコアの頂点です。適切な順列を選択することで、コアの任意の頂点をこのように構築できます。 $\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$

組み合わせ最適化との類似点と相違点

サブモジュラ集合関数とスーパーモジュラ集合関数は、組合せ最適化においても研究されている。(Shapley 1971)の結果の多くは、サブモジュラ関数がマトロイドの一般化として初めて提示された(Edmonds 1970)に類似している。この文脈において、凸コストゲームの核となる部分は、その要素がマトロイドの基本特性を一般化するため、基本多面体と呼ばれる。

しかしながら、最適化コミュニティでは一般的に、サブモジュラ関数は凸関数の離散的な類似物であると考えられています（Lovász 1983）。これは、どちらのタイプの関数も最小化が計算的に扱いやすいためです。残念ながら、これはシャプレーによるスーパーモジュラ関数の「凸」という本来の定義と直接矛盾します。

協力ゲーム理論と企業の関係

企業の戦略的意思決定は、協力ゲーム理論を通じて価値を創造し発展させることができる。^[17]これは、協力ゲーム理論が企業の戦略理論となり、異なるCGTソリューションが異なる制度をシミュレートできることを意味する。

参照

参考文献

^ Shor, Mike. 「非協力ゲーム - ゲーム理論.net」www.gametheory.net . 2016年9月15日閲覧。
^ Chandrasekaran, R.「協力ゲーム理論」（PDF）。
^ ブランデンブルガー、アダム. 「協力ゲーム理論：特性関数、配分、限界貢献」（PDF） . 2016年5月27日時点のオリジナル（PDF）からアーカイブ。
^ はのべき集合を表します。 $2^{N}$ $N$
^ Javier Muros, Francisco (2019). Cooperative Game Theory Tools in Coalitional Control Networks (1 ed.). Springer Cham. pp. 9– 11. ISBN 978-3-030-10488-7。
^ゲオルギオス ・ハルキアダキス、エディス・エルキンド、マイケル・J・ウールドリッジ（2011年10月25日）。『協力ゲーム理論の計算論的側面』Morgan & Claypool Publishers。ISBN 978-1-60845-652-9。
^ Peleg, B. (2002). 「第8章委員会における投票のゲーム理論的分析」『社会選択と福祉ハンドブック』第1巻. 第1巻. pp. 395– 423. doi :10.1016/S1574-0110(02)80012-1. ISBN 9780444829146。
^ 計算可能な単純ゲームの定義については、ライスの定理のセクションを参照。特に、すべての有限ゲームは計算可能である。
^ 隈部正之; 三原 HR (2011). 「単純ゲームの計算可能性：64の可能性の完全な調査」（PDF） . Journal of Mathematical Economics . 47 (2): 150– 158. arXiv : 1102.4037 . Bibcode :2011arXiv1102.4037K. doi :10.1016/j.jmateco.2010.12.003. S2CID 775278.
^ Kumabe and Mihara (2011) の表1を修正。16のタイプは、4つの慣習的な公理（単調性、適正性、強弱性、非弱弱性）によって定義される。例えば、タイプ1110は、単調性（1）、適正性（1）、強ゲーム（1）、弱ゲーム（非弱ではないため0）を表す。タイプ1110のゲームには、有限の非計算可能ゲームは存在せず、有限の計算可能ゲームは存在し、無限の非計算可能ゲームは存在せず、無限の計算可能ゲームは存在しない。タイプ1110を除いて、最後の3列は同じであることに注意されたい。
^ 隈部正之; 三原弘之 (2008). 「計算可能単純ゲームにおける中村数」.社会選択と福祉. 31 (4): 621. arXiv : 1107.0439 . doi :10.1007/s00355-008-0300-5. S2CID 8106333.
^ Aumann, Robert J.「サイドペイメントのない協力ゲームの核心」アメリカ数学会誌（1961年）：539-552。
^ ピーターズ、ハンス (2008).ゲーム理論：多段階アプローチ. シュプリンガー. pp. 123. doi :10.1007/978-3-540-69291-1_17. ISBN 978-3-540-69290-4。
^ Young, HP (1985-06-01). 「協力ゲームの単調解」.国際ゲーム理論ジャーナル. 14 (2): 65– 72. doi :10.1007/BF01769885. ISSN 0020-7276. S2CID 122758426.
^ Harsanyi, John C. (1982). 「n人協力ゲームのための簡略化された交渉モデル」.ゲーム理論論文集. 理論と意思決定ライブラリー. Springer, ドルドレヒト. pp. 44– 70. doi :10.1007/978-94-017-2527-9_3. ISBN 9789048183692。
^ 意思決定における集合関数、ゲーム、能力 | ミシェル・グラビッシュ | シュプリンガー. 理論と意思決定ライブラリ C. シュプリンガー. 2016. ISBN 9783319306889。
^ Ross, David Gaddis (2018-08-01). 「協力ゲーム理論を用いた戦略研究への貢献」. Strategic Management Journal . 39 (11): 2859– 2876. doi :10.1002/smj.2936. S2CID 169982369.

さらに読む

ビルバオ、ヘスス・マリオ（2000年）、組合せ構造における協力ゲーム、クルーワー・アカデミック・パブリッシャーズ、ISBN 9781461543930

デイビス、M.;マシュラー、M. (1965)「協力ゲームの核」海軍研究ロジスティクス季刊誌、12 (3): 223– 259、doi :10.1002/nav.3800120303

ドリーズセン、テオ（1988）、協力ゲーム、ソリューションとアプリケーション、クルーワーアカデミックパブリッシャーズ、ISBN 9789401577878

エドモンズ、ジャック（1970）「劣モジュラー関数、マトロイド、および特定の多面体」ガイ、R.、ハナニ、H.、ザウアー、N.、シェーンハイム、J.（編）『組合せ構造とその応用』、ニューヨーク：ゴードン・アンド・ブリーチ、pp . 69-87

ロヴァース、ラースロー(1983)、「劣モジュラー関数と凸性」、Bachem, A.; Grötschel, M .; Korte, B. (編)、『数学プログラミング—最新技術』、ベルリン: シュプリンガー、pp. 235– 257

レイトン・ブラウン、ケビン、ショーハム、ヨアブ（2008年）、ゲーム理論のエッセンス：簡潔で学際的な入門、サンラファエル、カリフォルニア州：モーガン＆クレイプール出版社、ISBN 978-1-59829-593-188ページの数学入門書。第8章を参照。オンラインで無料（購読が必要）多くの大学のWayback Machineで2000年8月15日にアーカイブ。

ルーカス、ウィリアム F. (1969)、「ゲームに解が存在しない可能性があることの証明」、アメリカ数学会誌、136 : 219–229、doi : 10.2307/1994798、JSTOR 1994798。

Lucas、William F. (1992)、「Von Neumann-Morgenstern Stable Sets」、Aumann、Robert J. ; Hart、Sergiu (編)、Handbook of Game Theory、第 1 巻、アムステルダム:エルゼビア、 543 ～ 590ページ

Luce, RDおよびRaiffa, H. (1957) Games and Decisions: An Introduction and Critical Survey、Wiley & Sons。(第 8 章を参照)。
Maschler, M. ; Peleg, B. ; Shapley, Lloyd S. (1979)「核、核小体、および関連する解概念の幾何学的性質」、オペレーションズ・リサーチ数学、4 (4): 303– 338、doi :10.1287/moor.4.4.303

オズボーン、MJ、ルービンシュタイン、A.（1994）ゲーム理論講座、MIT出版（第13章、第14章、第15章参照）
ムーラン、エルヴェ（1988年）、協調的意思決定の公理（第1版）、ケンブリッジ：ケンブリッジ大学出版局、ISBN 978-0-521-42458-5

オーウェン、ギジェルモ（1995）、ゲーム理論（第3版）、サンディエゴ：アカデミックプレス、ISBN 978-0-12-531151-9

Schmeidler, D. (1969)「特性関数ゲームの核小体」、SIAM Journal on Applied Mathematics、17 (6): 1163– 1170、doi :10.1137/0117107。

シャプレー、ロイド・S. ( 1953)、「-人ゲームの価値」、クーン、H.、タッカー、AW（編）、ゲーム理論への貢献II、プリンストン、ニュージャージー：プリンストン大学出版、pp. 307-317 $n$

シャプレー、ロイド・S.（1952年3月18日）「N人ゲームの価値」、カリフォルニア州サンタモニカ：ランド研究所

シャプレー、ロイド・S.（1971）「凸ゲームの核」、国際ゲーム理論ジャーナル、1（1）：11–26、doi：10.1007/BF01753431、S2CID 123385556

シャプレー、ロイド・S. ; シュビック、M. (1966)、「非凸選好を持つ貨幣経済における準コア」、エコノメトリカ、34 (4): 805– 827、doi :10.2307/1910101、JSTOR 1910101

ショーハム、ヨアブ、レイトンブラウン、ケビン（2009）、マルチエージェントシステム：アルゴリズム、ゲーム理論的、論理的基礎、ニューヨーク：ケンブリッジ大学出版局、ISBN 978-0-521-89943-7計算の観点から見た包括的なリファレンス。第 12 章を参照してください。オンラインで無料でダウンロードできます。

フォン・ノイマン、ジョン；モルゲンシュテルン、オスカー（1944）、「ゲーム理論と経済行動」、ネイチャー、157（3981）、プリンストン：プリンストン大学出版局：172、Bibcode：1946Natur.157..172R、doi：10.1038/157172a0、S2CID 29754824

Yeung, David WK、Leon A. Petrosyan著『協力的確率微分ゲーム』（Springerシリーズ、オペレーションズ・リサーチ・アンド・ファイナンシャル・エンジニアリング）、Springer、2006年、ソフトカバー、ISBN 978-1441920942。
Yeung, David WK、Leon A. Petrosyan著『サブゲーム整合型経済最適化：高度な協力的動的ゲーム分析（静的・動的ゲーム理論：基礎と応用）』、ビルクハウザー・ボストン、2012年。ISBN 978-0817682613

外部リンク

「協力ゲーム」、数学百科事典、EMSプレス、2001 [1994]

[1] Shor, Mike. 「非協力ゲーム - ゲーム理論.net」www.gametheory.net . 2016年9月15日閲覧。

[2] Chandrasekaran, R.「協力ゲーム理論」（PDF）。

[3] ブランデンブルガー、アダム. 「協力ゲーム理論：特性関数、配分、限界貢献」（PDF） . 2016年5月27日時点のオリジナル（PDF）からアーカイブ。

[4] はのべき集合を表します。 $2^{N}$ $N$

[5] Javier Muros, Francisco (2019). Cooperative Game Theory Tools in Coalitional Control Networks (1 ed.). Springer Cham. pp. 9– 11. ISBN 978-3-030-10488-7。

[ChalkiadakisElkind2011-6] ^ゲオルギオス ・ハルキアダキス、エディス・エルキンド、マイケル・J・ウールドリッジ（2011年10月25日）。『協力ゲーム理論の計算論的側面』Morgan & Claypool Publishers。ISBN 978-1-60845-652-9。

[peleg02hbscw-7] Peleg, B. (2002). 「第8章委員会における投票のゲーム理論的分析」『社会選択と福祉ハンドブック』第1巻. 第1巻. pp. 395– 423. doi :10.1016/S1574-0110(02)80012-1. ISBN 9780444829146。

[8] 計算可能な単純ゲームの定義については、ライスの定理のセクションを参照。特に、すべての有限ゲームは計算可能である。

[kumabe-m11jme-9] 隈部正之; 三原 HR (2011). 「単純ゲームの計算可能性：64の可能性の完全な調査」（PDF） . Journal of Mathematical Economics . 47 (2): 150– 158. arXiv : 1102.4037 . Bibcode :2011arXiv1102.4037K. doi :10.1016/j.jmateco.2010.12.003. S2CID 775278.

[10] Kumabe and Mihara (2011) の表1を修正。16のタイプは、4つの慣習的な公理（単調性、適正性、強弱性、非弱弱性）によって定義される。例えば、タイプ1110は、単調性（1）、適正性（1）、強ゲーム（1）、弱ゲーム（非弱ではないため0）を表す。タイプ1110のゲームには、有限の非計算可能ゲームは存在せず、有限の計算可能ゲームは存在し、無限の非計算可能ゲームは存在せず、無限の計算可能ゲームは存在しない。タイプ1110を除いて、最後の3列は同じであることに注意されたい。

[kumabe-m08scw-11] 隈部正之; 三原弘之 (2008). 「計算可能単純ゲームにおける中村数」.社会選択と福祉. 31 (4): 621. arXiv : 1107.0439 . doi :10.1007/s00355-008-0300-5. S2CID 8106333.

[12] Aumann, Robert J.「サイドペイメントのない協力ゲームの核心」アメリカ数学会誌（1961年）：539-552。

[13] ピーターズ、ハンス (2008).ゲーム理論：多段階アプローチ. シュプリンガー. pp. 123. doi :10.1007/978-3-540-69291-1_17. ISBN 978-3-540-69290-4。

[14] Young, HP (1985-06-01). 「協力ゲームの単調解」.国際ゲーム理論ジャーナル. 14 (2): 65– 72. doi :10.1007/BF01769885. ISSN 0020-7276. S2CID 122758426.

[15] Harsanyi, John C. (1982). 「n人協力ゲームのための簡略化された交渉モデル」.ゲーム理論論文集. 理論と意思決定ライブラリー. Springer, ドルドレヒト. pp. 44– 70. doi :10.1007/978-94-017-2527-9_3. ISBN 9789048183692。

[16] 意思決定における集合関数、ゲーム、能力 | ミシェル・グラビッシュ | シュプリンガー. 理論と意思決定ライブラリ C. シュプリンガー. 2016. ISBN 9783319306889。

[17] Ross, David Gaddis (2018-08-01). 「協力ゲーム理論を用いた戦略研究への貢献」. Strategic Management Journal . 39 (11): 2859– 2876. doi :10.1002/smj.2936. S2CID 169982369.