凸ゲーム・優モジュラゲーム（TUゲームの分類）

凸性の仮定

プレイヤーたちが直面する戦略的状況が協力ゲームであり、それが譲渡可能効用を前提とする提携型ゲーム（TUゲーム）\begin{equation*}
G=\left\{ I,v\right\}
\end{equation*}として記述されているものとします。ただし、\(I\)はプレイヤー集合であり、\(v:2^{I}\rightarrow \mathbb{R} \)は特性関数です。多くの場合、特性関数\(v\)は以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ v\left( \phi \right) =0 \\
&&\left( b\right) \ \forall C\in 2^{I}:v\left( C\right) \geq 0
\end{eqnarray*}を満たすものと仮定します。\(\left( a\right) \)を正規化の仮定と呼び、\(\left(b\right) \)を非負性の仮定と呼びます。以降ではこれをシンプルに提携型ゲームと呼ぶこととします。

協力ゲームが提携型ゲーム\(G\)によって表現される場合、プレイヤーたちがどのような提携を形成し、さらに、提携の内部においてどのように資源を配分するかが問題になりますが、それは提携型ゲームの結果\begin{equation*}\left( \mathcal{C},a\right)
\end{equation*}として記述されます。ただし、提携構造\(\mathcal{C}=\left\{ C_{1},\cdots ,C_{K}\right\} \)はプレイヤー集合\(I\)の分割であり、以下の条件\begin{eqnarray*}&&\left( a\right) \ I=\bigcup_{k=1}^{K}C_{k} \\
&&\left( b\right) \ \forall k,k^{\prime }\in \left\{ 1,\cdots ,K\right\}
:\left( k\not=k^{\prime }\Rightarrow C_{k}\cap C_{k^{\prime }}=\phi \right)
\end{eqnarray*}を満たすものとして定義され、利得ベクトル\(a\)は以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall i\in I:a_{i}\geq 0 \\
&&\left( b\right) \ \forall k\in \left\{ 1,\cdots ,K\right\} :\sum_{i\in
C_{k}}a_{i}\leq v\left( C\right)
\end{eqnarray*}を満たすものとして定義されます。

プレイヤー\(i\in I\)およびプレイヤー\(i\)が属さない提携\(C\subset I\backslash \left\{ i\right\} \)が与えられた状況を想定します。プレイヤー\(i\)が提携\(C\)に加入することにより増加する提携値は、特性関数\(v:2^{I}\rightarrow \mathbb{R} \)を用いて、\begin{equation*}MC_{i}\left( C\right) =v\left( C\cup \left\{ i\right\} \right) -v\left(
C\right)
\end{equation*}と表現されますが、これをプレイヤー\(i\)の提携\(C\)に対する限界貢献度（marginal contribution of player \(i\) for acoalition \(C\)）と呼びます。

提携型ゲーム\(G\)を分析する際には多くの場合、特性関数\(v:2^{I}\rightarrow \mathbb{R} \)に対して正規化と非負性を仮定するとともに、以下の条件\begin{equation*}\forall i\in I,\ \forall C,D\in 2^{I}:\left[ C\subset D\subset I\backslash
\left\{ i\right\} \Rightarrow MC_{i}\left( C\right) \leq MC_{i}\left(
D\right) \right] \end{equation*}すなわち、\begin{equation*}
\forall i\in I,\ \forall C,D\in 2^{I}:\left[ C\subset D\subset I\backslash
\left\{ i\right\} \Rightarrow v\left( C\cup \left\{ i\right\} \right)
-v\left( C\right) \leq v\left( D\cup \left\{ i\right\} \right) -v\left(
D\right) \right] \end{equation*}が成り立つものと仮定します。つまり、それぞれのプレイヤー\(i\)の限界貢献度は、より大きい提携に対してより高く評価されるということです。これを凸性（convex）の仮定と呼びます。また、特性関数\(v\)が凸性を満たすような提携型ゲーム\(G\)を凸ゲーム（convex game）と呼びます。

優モジュラ性の仮定

提携型ゲーム\(G\)を分析する際には多くの場合、特性関数\(v:2^{I}\rightarrow \mathbb{R} \)に対して正規化と非負性を仮定するとともに、以下の条件\begin{equation*}\forall C,D\in 2^{I}:v\left( C\right) +v\left( D\right) \leq v\left( C\cup
D\right) +v\left( C\cap D\right)
\end{equation*}が成り立つものと仮定します。これを優モジュラ性（supermodular）の仮定と呼びます。また、特性関数\(v\)が優モジュラ性を満たすような提携型ゲーム\(G\)を優モジュラゲーム（suparmodular game）と呼びます。

特性関数が優モジュラ性を満たすことと凸性を満たすことは必要十分です。

凸ゲームは優加法ゲームである

特性関数\(v:2^{I}\rightarrow \mathbb{R} \)が正規化の仮定と凸性を満たす場合、\(v\)は優加法性を満たします。つまり、\begin{equation*}\forall C,D\in 2^{I}:\left[ C\cap D=\phi \Rightarrow v\left( C\right)
+v\left( D\right) \leq v\left( C\cup D\right) \right] \end{equation*}が成り立つということです。

優加法ゲームは凸ゲームであるとは限らない

正規化の仮定を認める場合、凸性を満たす特性関数は優加法性を満たすことが明らかになりましたが、その逆は成立するとは限りません。つまり、優加法性を満たす特性関数は凸性を満たすとは限らないということです。以下の例より明らかです。

凸ゲームのもとでの全体提携の提携値

特性関数が正規化の仮定と非負性および凸性を満たす場合、全体提携のもとで提携値は最大化されます。

正規化の仮定と非負性を認める場合、凸ゲームでは、全体提携のもとで提携値は最大化されることが明らかになりました。したがって、凸ゲームにおいてプレイヤーたちは複雑な提携を形成する必要はなく、全体提携\(I\)を形成することが最適になります。つまり、凸ゲームにおける結果\(\left( \mathcal{C},v\right) \)を構成する提携構造は、\begin{equation*}\mathcal{C}=\left\{ I\right\}
\end{equation*}であり、利得ベクトル\(a\)は以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall i\in I:a_{i}\geq 0 \\
&&\left( b\right) \ \sum_{i\in I}a_{i}=V\left( I\right)
\end{eqnarray*}を満たすことが予想されます。凸ゲームでは全体提携\(I\)のみが形成され、全体提携の提携値を全員で分け合うことになるため、利得ベクトル\(a\)の選択だけが分析課題となります。

演習問題