協力ゲーム理論

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

${\displaystyle v(S\cup T)\geq v(S)+v(T)}$いつでも${\displaystyle S,T\subseteq N}$満足する${\displaystyle S\cap T=\emptyset }$。

より大きな連合はより多くの利益を得る：

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

これは超加法性から導かれる。つまり、利得が正規化され、単独連合の価値がゼロになる場合である。

連合ゲームvは、利得が1または0、つまり連合が「勝つ」か「負ける」かのいずれかである場合、単純であるとみなされる。 ^{[ 7 ]}

言い換えれば、単純ゲームは、 Wの集合として定義できます。W の要素は勝利連合、それ以外の要素は敗北連合と呼ばれます。単純ゲームは空集合ではない、あるいは空集合を含まないと仮定される場合もあります。しかし、数学の他の分野では、単純ゲームはハイパーグラフまたはブール関数（論理関数）とも呼ばれます。

• 単純ゲームWは、勝利連合を含む任意の連合が勝利連合でもある場合、単調である。つまり、${\displaystyle S\in W}$そして${\displaystyle S\subseteq T}$暗示する${\displaystyle T\in W}$。
• 単純ゲームWは、任意の勝利連合の補集合（反対勢力）が敗北連合である場合、すなわち、${\displaystyle S\in W}$暗示する${\displaystyle N\setminus S\notin W}$。
• 単純なゲームWは、任意の敗北連合の補集合が勝利連合である場合、つまり、${\displaystyle S\notin W}$暗示する${\displaystyle N\setminus S\in W}$。
  • 単純ゲームWが適切かつ強い場合、連合が勝利するのは、その補集合が敗北する場合に限る。つまり、${\displaystyle S\in W}$もし ${\displaystyle N\setminus S\notin W}$（vが適切かつ強力な連合単純ゲームである場合、${\displaystyle v(S)=1-v(N\setminus S)}$任意のSに対して。）
• 単純ゲームにおける拒否権プレイヤー（拒否者）とは、すべての勝利連合に属するプレイヤーのことである。拒否権プレイヤーが存在する場合、拒否権プレイヤーを含まない連合はすべて敗北する。単純ゲームWは、拒否権プレイヤーが存在する場合、すなわち、すべての勝利連合の共通部分が、すべての勝利連合の共通部分と${\displaystyle \bigcap W:=\bigcap _{S\in W}S}$すべての勝利連合は空集合ではない。
  • 単純なゲームにおける独裁者とは、拒否権を持つプレイヤーであり、このプレイヤーを含む連合はすべて勝利する。独裁者は、敗北する連合には属さない。（実験経済学における独裁者ゲームは、これとは無関係である。）
• 単純ゲームWのキャリアは集合である${\displaystyle T\subseteq N}$任意の連合Sに対して、${\displaystyle S\in W}$もし${\displaystyle S\cap T\in W}$単純ゲームにキャリアがある場合、そのキャリアに属さないプレイヤーは無視されます。単純ゲームは、有限のキャリアを持つ場合（Nが無限であっても） 、有限ゲームと呼ばれることがあります。
• 単純ゲームにおけるナカムラ数とは、空集合を持つ勝利連合の最小数である。ナカムラの定理によれば、この数は合理性の度合いを測る指標であり、集約ルールが明確な選択肢を生み出す能力の程度を示すものである。

上記の公理間の関係は、以下のようなものが広く認識されている（例：Peleg、2002、セクション2.1 ^{[ 8 ]}）。

• 単純なゲームが弱いのであれば、それは正しいことだ。
• 単純なゲームが独裁的であるのは、それが強弱両方を兼ね備えている場合に限る。

より一般的には、4 つの従来の公理 (単調性、適切性、強弱性、非弱性)、有限性、およびアルゴリズム的計算可能性^{[ 9 ]}の関係についての完全な調査 が行われており (熊部と三原、2011 ^{[ 10 ]} )、その結果は、以下の表「単純ゲームの存在」にまとめられています。

単純ゲームに関するさまざまな公理が、その中村数に課す制約についても、広範囲にわたって研究された。^{[ 12 ]}特に、拒否権を持つプレイヤーがいない計算可能な単純ゲームは、それが適切な非強ゲーム である場合に限り、中村数が3より大きくなる。

ゲームの安定集合（フォン・ノイマン＝モルゲンシュテルン解（フォン・ノイマン＆モルゲンシュテルン 1944 ）としても知られる）は、2人以上のプレイヤーがいるゲームに対して最初に提案された解である。${\displaystyle v}$ゲームにして${\displaystyle x}$、${\displaystyle y}$2 つの推論${\displaystyle v}$。 それから${\displaystyle x}$支配する${\displaystyle y}$もし何らかの連合が${\displaystyle S\neq \emptyset }$満たす${\displaystyle x_{i}>y_{i},\forall ~i\in S}$そして${\displaystyle \sum _{i\in S}x_{i}\leq v(S)}$言い換えれば、プレイヤーは${\displaystyle S}$報酬を好む${\displaystyle x}$から${\displaystyle y}$そして、彼らは大連立政権から離脱すると脅すことができる。${\displaystyle y}$が使用されるのは、彼らが自力で得る利益が、彼らが受け取る配分と少なくとも同等であるためです。${\displaystyle x}$。

安定セットとは、以下の2つの特性を満たす帰属の集合である。

• 内部安定性：安定集合内のどの利得ベクトルも、集合内の他のベクトルによって支配されない。
• 外部安定性：集合外にあるすべての利得ベクトルは、集合内の少なくとも1つのベクトルによって支配される。

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

させて${\displaystyle v}$ゲームである。${\displaystyle v}$はペイオフベクトルの集合です

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

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

単純なゲームの場合、コアの概念は別のものになり、各プレイヤーは集合に対する選好を持っていると仮定される。${\displaystyle X}$代替案のリスト。プロファイルはリストです${\displaystyle p=(\succ _{i}^{p})_{i\in N}}$個人の好み$\displaystyle \succ _{i}^{p}}$の上${\displaystyle X}$。 ここ${\displaystyle x\succ _{i}^{p}y}$個人${\displaystyle i}$代替案を好む${\displaystyle x}$ に${\displaystyle y}$プロフィール${\displaystyle p}$単純なゲームが与えられた場合${\displaystyle v}$そしてプロフィール${\displaystyle p}$優劣関係​${\displaystyle \succ _{v}^{p}}$は定義される${\displaystyle X}$による${\displaystyle x\succ _{v}^{p}y}$勝利連合が存在する場合に限る${\displaystyle S}$ （つまり、${\displaystyle v(S)=1}$満足${\displaystyle x\succ _{i}^{p}y}$すべての人々のために${\displaystyle i\in S}$中核​${\displaystyle C(v,p)}$シンプルなゲーム${\displaystyle v}$プロフィールに関して${\displaystyle p}$選好の集合は、${\displaystyle \succ _{v}^{p}}$ （最大要素の集合）${\displaystyle X}$に関して${\displaystyle \succ _{v}^{p}}$):

${\displaystyle x\in C(v,p)}$存在しない場合に限り${\displaystyle y\in X}$そのため${\displaystyle y\succ _{v}^{p}x}$。

単純ゲームにおけるナカムラ数は、空集合の共通部分を持つ勝利連合の最小数である。 ナカムラの定理は、コアが${\displaystyle C(v,p)}$すべてのプロファイルで空ではない${\displaystyle p}$非巡回的（あるいは推移的）な選好の条件は、${\displaystyle X}$は有限であり、基数（要素の数）は${\displaystyle X}$中村数より小さい${\displaystyle v}$熊部と三原による変種では、コアは${\displaystyle C(v,p)}$すべてのプロファイルで空ではない${\displaystyle p}$ 最大要素を持つ選好の基数が${\displaystyle X}$中村数より小さい${\displaystyle v}$（詳細は中村番号を参照。）

コアが空である可能性があるため、(Shapley & Shubik 1966) で一般化が導入されました。${\displaystyle \varepsilon }$-コア数${\displaystyle \varepsilon \in \mathbb {R} }$はペイオフベクトルの集合です

${\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 は、ペナルティを支払わなければならない場合、どの連合も大連合から離脱することで利得を改善できない事前帰属のセットです。${\displaystyle \varepsilon }$去るために。${\displaystyle \varepsilon }$負の値になる場合もあり、その場合は大連合を離脱するボーナスを表します。明らかに、コアが空かどうかに関わらず、強力な${\displaystyle \varepsilon }$-core は、十分大きな値に対して空ではありません${\displaystyle \varepsilon }$十分小さい値（負の値の可能性もある）の場合は空になります${\displaystyle \varepsilon }$この推論の流れに沿って、( Maschler, Peleg & Shapley 1979 )で導入された最小コアは、すべての空でない強いコアの共通部分である。${\displaystyle \varepsilon }$-コア。それはまた、強力な${\displaystyle \varepsilon }$-コアの最小値${\displaystyle \varepsilon }$これにより、集合は空集合ではなくなる（ビルバオ 2000 ）。

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

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

${\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の下で大連合Nから離脱することで、プレイヤーjの協力なしに得られる最大額。ただし、 i の離脱連合内の他のプレイヤーはxの下での利得に満足していると仮定する。最大余剰は、あるプレイヤーの別のプレイヤーに対する交渉力を測定する方法である。${\displaystyle v}$は、次の条件を満たす補完xの集合である。

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

プレイヤーiとjの任意のペアについて。直感的に、プレイヤーi は、帰属xに関してプレイヤーjよりも交渉力があるのは、次の場合である。${\displaystyle s_{ij}^{v}(x)>s_{ji}^{v}(x)}$しかし、プレイヤーjはプレイヤーi の脅威に対して免疫を持つ。${\displaystyle x_{j}=v(j)}$なぜなら、彼はこの利益を自力で得ることができるからである。カーネルには、どのプレイヤーも他のプレイヤーに対してこのような交渉力を持たないすべての推論が含まれる。この解の概念は、( Davis & Maschler 1965 )で初めて導入された。

ハーサニー配当（1963年にシャプレー値を一般化するためにこれを用いたジョン・ハーサニーにちなんで名付けられた^{[ 16 ]}）は、協力ゲームにおけるプレイヤーの連合によって生み出される余剰を特定する。この余剰を特定するために、この連合の価値は、サブ連合によって既に生み出された余剰を差し引くことによって修正される。この目的のために、配当は${\displaystyle d_{v}(S)}$連合の${\displaystyle 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_{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}}}$

配当金の明示的な式は次のように表される。${\textstyle d_{v}(S)=\sum _{T\subseteq S}(-1)^{|S\setminus T|}v(T)}$. 機能${\displaystyle d_{v}:2^{N}\to \mathbb {R} }$は、メビウスの逆とも呼ばれる。${\displaystyle v:2^{N}\to \mathbb {R} }$[ ^{17 ]}実際、我々は回復することが^できる${\displaystyle v}$から${\displaystyle d_{v}}$公式の助けを借りて${\textstyle v(S)=d_{v}(S)+\sum _{T\subsetneq S}d_{v}(T)}$。

ハルサニ配当は、ゲームと解概念の両方を分析するのに役立ちます。たとえば、シャプレー値は、各連合の配当をそのメンバー間で分配することによって得られます。つまり、シャプレー値は、${\displaystyle \phi _{i}(v)}$プレイヤーの${\displaystyle i}$ゲーム内${\displaystyle v}$これは、プレイヤーが所属するすべての連合の配当金の分配額を合計することによって与えられます。${\textstyle \phi _{i}(v)=\sum _{S\subset N:i\in S}{d_{v}(S)}/{|S|}}$。

させて${\displaystyle v:2^{N}\to \mathbb {R} }$ゲームにして、${\displaystyle x\in \mathbb {R} ^{N}}$ペイオフベクトルとなる。${\displaystyle x}$連立政権のために${\displaystyle S\subseteq N}$数量${\displaystyle v(S)-\sum _{i\in S}x_{i}}$つまり、連合のプレーヤーが得る利益は${\displaystyle S}$大連立政権から離脱すれば得られるもの${\displaystyle N}$報酬不足${\displaystyle x}$そして代わりに報酬を受け取る${\displaystyle v(S)}$核小体の${\displaystyle v}$は、すべての連合の超過ベクトル（ベクトル）の帰属です。${\displaystyle \mathbb {R} ^{2^{N}}}$）はレキシミンのオーダーで最小である。核小体は（Schmeidler 1969 ）で導入された。

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

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

• 超モジュラリティは自明に超加法性を意味する。
• 凸ゲームは完全にバランスが取れている。凸ゲームのコアは空ではなく、凸ゲームの任意の部分ゲームは凸であるため、任意の部分ゲームのコアも空ではない。
• 凸ゲームには、そのコアと一致する一意の安定集合が存在する。
• 凸ゲームのシャプレー値は、そのコアの重心である。
• 貪欲アルゴリズムを使用すれば、コアの極点（頂点）を多項式時間で見つけることができます。${\displaystyle \pi :N\to N}$はプレイヤーの順列であり、${\displaystyle S_{i}=\{j\in N:\pi (j)\leq i\}}$プレイヤーの集合を順番に並べる${\displaystyle 1}$を通して${\displaystyle i}$で${\displaystyle \pi }$どのような場合でも${\displaystyle i=0,\ldots ,n}$、 と${\displaystyle S_{0}=\emptyset }$そして報酬${\displaystyle x\in \mathbb {R} ^{N}}$定義される${\displaystyle x_{i}=v(S_{\pi (i)})-v(S_{\pi (i)-1}),\forall ~i\in N}$はコアの頂点です${\displaystyle v}$コアの任意の頂点は、適切な順列を選択することによってこのように構築できます。${\displaystyle \pi }$。

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

しかし、最適化分野では一般的に、劣モジュラ関数は凸関数の離散版であると考えられています（Lovász 1983 ）。これは、どちらのタイプの関数も最小化が計算上扱いやすいためです。残念ながら、これはシャプレーによる超モジュラ関数の「凸」という定義と真っ向から矛盾します。

• ビルバオ、ヘスス・マリオ（2000）、『組合せ構造上の協力ゲーム』、クルーワー・アカデミック・パブリッシャーズ、ISBN 9781461543930

• Davis, M.; Maschler, M. (1965)、「協力ゲームの核心」、Naval Research Logistics Quarterly、12 (3): 223–259、doi : 10.1002/nav.3800120303

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

• Edmonds, Jack (1970)、「劣モジュラ関数、マトロイド、および特定の多面体」、Guy, R.、Hanani, H.、Sauer, N.、Schönheim, J. (編)、『組合せ構造とその応用』、ニューヨーク：Gordon and Breach、pp . 69–87 

• Lovász, László ( 1983)、「劣モジュラ関数と凸性」、Bachem, A.、Grötschel, M.、Korte, B. (編)、『数理計画法―現状』、ベルリン：Springer、pp. 235–257 

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

• Lucas, William 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)ゲームと意思決定：入門と批判的概観、Wiley & Sons。（第 8 章を参照）。
• Maschler, M. ; Peleg, B.; Shapley, Lloyd S. (1979)、「核、核小体、および関連する解概念の幾何学的性質」、Mathematics of Operations Research、4 (4): 303– 338、doi : 10.1287/moor.4.4.303

• Osborne, MJ およびRubinstein, A. (1994)ゲーム理論入門、MIT Press (第 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)、「${\displaystyle n}$「-人ゲーム」、Kuhn, H.、Tucker, AW (編)『ゲーム理論への貢献 II』、プリンストン、ニュージャージー州：プリンストン大学出版局、pp. 307–317 

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

• シャプレー、ロイド S. (1971)、「凸ゲームのコア」、International Journal of Game Theory、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 Series in Operations Research and Financial Engineering）、Springer、2006 年。ソフトカバー - ISBN 978-1441920942。
• Yeung, David WK および Leon A. Petrosyan。『部分ゲーム整合型経済最適化：高度な協調動的ゲーム分析』（静的・動的ゲーム理論：基礎と応用）、Birkhäuser Boston; 2012年。ISBN 978-0817682613