譲渡可能効用を前提とした提携型ゲーム（TUゲーム）

協力ゲーム

複数の主体が関与する問題が与えられたとき、その問題に関与するそれぞれの主体にとって、自分の行動が他者の行動に影響を与えるとともに、他者の行動が自分の行動にも影響を与える場合、主体の間には戦略的相互依存性（strategic interdependence）が成立していると言います。ゲーム理論（game theory）は、戦略的相互依存性に直面した主体による意思決定を分析する学問です。

主体の間に戦略的相互依存性が成立する状況をゲーム（game）と呼びます。ゲームをモデル化する際には、以下の要素を具体的に記述します。

1. ゲームにおいて意思決定を行う主体は誰か。つまり、ゲームのプレイヤー（player）は誰か。
2. プレイヤーたちはどのような順番（turn）で意思決定を行うか。
3. プレイヤーたちが意思決定を行う際にどのような選択肢が与えられているか。つまり、プレイヤーたちはどのような行動（action）が選択可能か。
4. プレイヤーが意思決定を行う際にどのような情報（information）が与えられているか。
5. プレイヤーたちが意思決定を行う帰結として、どのような結果（outcome）が起こり得るか。
6. プレイヤーたちはそれぞれの結果をどの程度評価しているか。すなわち、プレイヤーはどのような利得（payoff）の体系を持っているか。

以上の要素をゲームのルール（rule）と呼びます。ゲームの開始後、それぞれの「プレイヤー」は自身が行動する「順番」になったら、その時点においてアクセス可能な「情報」を活用しつつ、何らかの行動原理にもとづいて、与えられた選択肢の中から特定の「行動」を選択します。すべてのプレイヤーによる意志決定が終了したら、プレイヤーたちが選んだ行動の組み合わせに応じて特定の「結果」が実現し、それぞれのプレイヤーは実現した結果から「利得」を得ます。

ゲームに直面したプレイヤーたちは、自身にとってより望ましい結果を導くために、最終的な意志決定を行う前に他のプレイヤーと交渉を行う可能性があります。事前交渉の結果に対してプレイヤーたちの間に拘束的な合意が成立するのであれば、つまり、合意通りに行動せざるを得ない何らかの仕組みが存在する場合には、プレイヤーたちは集団を形成した上で協力的な意志決定を行う可能性があります。拘束的な合意が成立する場合とそうでない場合とでは、プレイヤーにとって最適な行動は変化するため、ゲームを分析する際には、プレイヤーたちの間に拘束的な合意が成立するかどうかを事前に明らかにしておく必要があります。本節の分析対象である協力ゲーム（cooperative game）とは、プレイヤーたちの間に拘束的な合意が成立する状況を想定したゲームです。

プレイヤーの間に拘束的な合意が成立する場合には、プレイヤーたちは提携（coalition）と呼ばれる集団を形成した上で、互いに拘束的な意志決定を行います。協力ゲームでは個々のプレイヤーどうしの戦略的相互依存関係を分析できるだけでなく、提携間の戦略的相互依存関係も分析できます。

「協力」ゲームとはいっても、プレイヤーたちの対立が完全に解消された状況を想定するわけではありません。そこでは依然としてプレイヤーや提携の間で競争が行われます。協力ゲームにおいて提携が形成され内部で統一的な意思決定が行われるのは、そうすることにより提携に参加する個々のプレイヤーの利得が増加するからです。

プレイヤーの表現

協力ゲームに参加するすべてのプレイヤーからなる集合をプレイヤー集合（player set）やプレイヤー空間（player space）などと呼び、これを、\begin{equation*}
I
\end{equation*}で表記します。

戦略的相互依存関係は複数のプレイヤーが存在することにより成立するため、プレイヤーの数が複数であることはゲームの基本的な条件となります。そこで、多くの場合、プレイヤーの人数は\(2\)以上の整数であるものと仮定します。

プレイヤーの人数が\(n\)であるとき、そのようなゲームを\(n\)人ゲーム（\(n\)-players game）と呼びます。\(n\)人ゲームのプレイヤー集合を、\begin{equation*}I=\left\{ 1,2,\cdots ,n\right\}
\end{equation*}で表記し、その要素である\(i\ \left( =1,2,\cdots ,n\right) \)番目のプレイヤーをプレイヤー\(i\)（player \(i\)）と呼びます。\(i\in I\)です。

プレイヤーの単位は分析対象であるゲームに応じて変化します。個人をプレイヤーと定める場合もあれば、組織や国家などをプレイヤーとする場合もあります。重要なことは、問題としているゲームにおいて自律的な意思決定を行う最小単位をプレイヤーとみなすということです。

ゲームに関与している主体の中でも、他の主体と影響を与え合いながら意思決定を行っているのではなく、外生的に変化する状況に対応する形でのみ意志決定を行う主体はプレイヤーとはみなされず、モデルの環境変数とみなされます。

提携の表現（提携構造）

協力ゲームではプレイヤーたちが自発的に集団を形成した上で、集団として意思決定を行う状況を許容しています。つまり、お互いにとってメリットがある場合にはプレイヤーたちは集団を形成し、集団の内部で決めた通りに各々が振る舞う状況を想定するということです。そこで、プレイヤーたちが形成する集団を提携（coalition）と呼び、これをプレイヤー集合\(I\)の部分集合\begin{equation*}C\subset I
\end{equation*}として表現します。同じことを、\begin{equation*}
C\in 2^{I}
\end{equation*}と表現することもできます。ただし、\(2^{I}\)はプレイヤー集合\(I\)のベキ集合、すなわち\(I\)の部分集合をすべて集めた集合族です。

個々のプレイヤーは何らかの提携に属することを強制されるわけではありません。いかなる提携にも属さないという選択肢は常に残されています。その一方で、プレイヤーたちはメリットのある場合に提携を形成する状況を想定しているため、提携に属するプレイヤーたちは、提携の内部で定めた行動通りに振る舞うものとします。つまり、提携の内部における合意には拘束性があるということです。

プレイヤー集合\(I\)が有限\(K\)個の提携\(C_{1},\cdots ,C_{K}\subset 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*}がともに成り立つ場合には、これらの提携からなる集合を、\begin{equation*}
\mathcal{C}=\left\{ C_{1},\cdots ,C_{K}\right\}
\end{equation*}で表記し、これを提携構造（coalition structure）と呼びます。

提携が得る利得の表現（特性関数）

それぞれの提携\(C\in 2^{I}\)に対して実数\(v\left( C\right) \in \mathbb{R} \)を1つずつ割り当てる関数\begin{equation*}v:2^{I}\rightarrow \mathbb{R} \end{equation*}を定義し、これを特性関数（characteristic function）と呼びます。

特性関数\(v\)が提携\(C\)に対して定める値\(v\left( C\right) \)を提携\(C\)の提携値（coalition value）と呼びますが、これは、提携\(C\)に属するプレイヤーたちが協力した場合に、提携\(C\)に属さないプレイヤーたちがどのように振る舞った場合においても提携\(C\)が確保できる利得に相当します。では、提携値をどのように算出できるのでしょうか。順番に考えます。

プレイヤーたちが直面する戦略的状況が戦略型ゲーム\begin{equation*}
G=\left( I,\left\{ S_{i}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in
I}\right)
\end{equation*}として記述されているものとします。ただし、\(I\)はプレイヤー集合、\(S_{i}\)はプレイヤー\(i\in I\)の純粋戦略集合、\(u_{i}:S_{I}\rightarrow \mathbb{R} \)はプレイヤー\(i\)の利得関数です。

提携\(C\subset I\)が与えられれば、プレイヤー集合\(I\)は2つの提携\(C\)および\(I\backslash C\)に分割されます。ただし、\(I\backslash C\)は提携\(C\)に属さないプレイヤーたちからなる提携です。提携\(C\)に属するプレイヤーたちの純粋戦略からなる組は\(s_{C}=\left( s_{i}\right) _{i\in C}\)であり、提携\(I\backslash C\)に属するプレイヤーたちの純粋戦略からなる組は\(s_{I\backslash C}=\left( s_{i}\right) _{i\in I\backslash C}\)ですが、それぞれの提携の内部においてプレイヤーたちが協力的に振る舞う状況を想定します。つまり、提携\(C\)に属するプレイヤーたちは提携全体の利得\(\sum_{i\in C}u_{i}\left( s_{C},s_{I\backslash C}\right) \)を最大化するような戦略\(s_{C}\)を協力して選択する一方で、提携\(I\backslash C\)に属するプレイヤーたちは提携全体の利得\(\sum_{i\in I\backslash C}u_{i}\left(s_{C},s_{I\backslash C}\right) \)を最大化するような戦略\(s_{I\backslash C}\)を協力して選択する状況を想定します。言い換えると、2つの提携\(C,I\backslash C\)がプレイヤーであるような2人ゲームを想定するということです。さらに、この2人ゲームがゼロサムゲーム（または定和ゲーム）であるならば、自身の利得を最大化することと相手の利得を最小化することは必要十分であるため、提携\(C\)が戦略\(s_{C}\)を選択した場合に、最悪のシナリオのもとでも確保できる利得は、\begin{equation*}\min_{s_{I\backslash C}}\sum_{i\in C}u_{i}\left( s_{C},s_{I\backslash
C}\right)
\end{equation*}となります。提携\(C\)は自身がそれぞれの戦略\(s_{C}\)を選んだ場合に最低でも確保できる利得を導出した上で、それらを比較できます。その結果、最低でも確保できる利得が戦略\(s_{C}^{\ast }=\left( s_{i}^{\ast }\right)_{i\in C}\)のもとで最大化されるのであれば、すなわち、\begin{equation*}\min_{s_{I\backslash C}}\sum_{i\in C}u_{i}\left( s_{C}^{\ast
},s_{I\backslash C}\right) =\max_{s_{C}}\min_{s_{I\backslash C}}\sum_{i\in
C}u_{i}\left( s_{C},s_{I\backslash C}\right)
\end{equation*}が成り立つ場合には、この戦略\(s_{C}^{\ast }\)を提携\(C\)のマックスミニ戦略（maxmini strategy）と呼びます。提携\(C\)がマックスミニ戦略を選択した場合に得られる利得、すなわちマックスミニ値（maxmini value）は、提携\(C\)に属するプレイヤーたちが協力した場合に、提携\(C\)に属さないプレイヤーたちがどのように振る舞った場合においても提携\(C\)が確保できる利得に他なりません。したがって、提携\(C\)の提携値\(v\left( C\right) \)はマックスミニ値として算出されます。つまり、提携値は以下の関係\begin{equation*}v\left( C\right) =\max_{s_{C}}\min_{s_{I\backslash C}}\sum_{i\in
C}u_{i}\left( s_{C},s_{I\backslash C}\right)
\end{equation*}より算出されるということです。

提携型ゲーム\(G\)を分析する際には多くの場合、特性関数\(v:2^{I}\rightarrow \mathbb{R} \)について、以下の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) \)は、プレイヤーが属さない提携\(\phi \)の提携値を\(0\)と定めることを意味します。これを正規化（normalization）の仮定と呼びます。

条件\(\left( b\right) \)は、任意の提携の提携値が非負であることを意味します。これを非負性（non-negativity）の仮定と呼びます。

利得の譲渡可能性

協力ゲームのプレイヤーは、様々な提携の提携値どうしを比べながら、自分がどの提携に属するか、もしくは提携に属さないかを決定します。ただ、提携値\(v\left( C\right) \)は提携\(C\)が全体として獲得する利得であり、提携\(C\)の内部において提携値\(v\left( C\right) \)がどのような形で分配されるかについて何も語っていません。具体例を挙げると、提携\(C\)に属する誰か1人が提携値\(v\left( C\right) \)を独占する場合と、提携値\(v\left( C\right) \)を提携\(C\)の内部で均等に分配する場合とでは資源配分として明らかに異なりますが、これらはともに同一の提携値\(v\left( C\right) \)として表現されることになります。このような事情を踏まえると、プレイヤーが意思決定を行う上で、提携値だけでは判断材料として不十分であると言えます。ただし、一定の条件のもとでは、このような問題は解決可能です。

2人のプレイヤー\(1,2\)が提携\(\left\{ 1,2\right\} \)を形成した状況を想定します。提携値は\(v\left( \left\{ 1,2\right\} \right) \)です。プレイヤー\(1\)が提携から得る分け前を\(a_{1}\)で表記し、プレイヤー\(2\)が提携から得る分け前を\(a_{2}\)で表記する場合、以下の関係\begin{equation}w\left( a_{1}\right) +w\left( a_{2}\right) =w\left( v\left( \left\{
1,2\right\} \right) \right) \quad \cdots (1)
\end{equation}が成立します。ただし、\(w\)は提携値を金銭の量に換算する関数です。プレイヤー\(1\)は以上の配分\(\left( a_{1},a_{2}\right) \)とは異なる配分\(\left( a_{1}^{\prime},a_{2}^{\prime }\right) \)を望んでいるものとします。ただし、\begin{equation}w\left( a_{1}^{\prime }\right) +w\left( a_{2}^{\prime }\right) =w\left(
v\left( \left\{ 1,2\right\} \right) \right) \quad \cdots (2)
\end{equation}です。このような状況において、双方が納得する形で\(\left( a_{1},a_{2}\right) \)から\(\left( a_{1}^{\prime },a_{2}^{\prime }\right) \)へ移行できることが保証されているのであれば、提携の内部で事後的に利害の調整ができるということになるため、事前の判断材料としては提携値さえ与えられれば十分であるということになります。

プレイヤー\(1,2\)の利得関数の形状を、\begin{eqnarray}u_{1}\left( a_{1},t\right) &=&w\left( a_{1}\right) +t \quad \cdots (3) \\
u_{2}\left( a_{2},t\right) &=&w\left( a_{2}\right) +t \quad \cdots (4)
\end{eqnarray}と特定できるものとします。ただし、\(w\left(a_{i}\right) \)はプレイヤー\(i\)が提携のメンバーとして得る提携値\(a_{i}\)を金銭に換算した値であり、\(t\in \mathbb{R} \)は金銭の数量です。このような利得関数を準線型（quasi-linear）の利得関数と呼びます。この場合、プレイヤー\(1\)については、\begin{eqnarray*}u_{1}\left( a_{1}^{\prime },t\right) &=&w\left( a_{1}^{\prime }\right)
+t\quad \because \left( 3\right) \\
&=&w\left( v\left( \left\{ 1,2\right\} \right) \right) -w\left(
a_{2}^{\prime }\right) +t\quad \because \left( 2\right) \\
&=&w\left( a_{1}\right) +w\left( a_{2}\right) -w\left( a_{2}^{\prime
}\right) +t\quad \because \left( 1\right) \\
&=&u_{1}\left( a_{1},w\left( a_{2}\right) -w\left( a_{2}^{\prime }\right)
+t\right) \quad \because \left( 3\right)
\end{eqnarray*}が成り立ちます。つまり、プレイヤー\(1\)は\(a_{1}\)から\(a_{1}^{\prime }\)へ移行する対価として\(w\left( a_{2}\right)-w\left( a_{2}^{\prime }\right) \)だけ金銭を支払う意思があります。プレイヤー\(2\)が\(a_{2}\)から\(a_{2}^{\prime }\)へ移行する対価としてプレイヤー\(1\)から金銭\(w\left( a_{2}\right) -w\left(a_{2}^{\prime }\right) \)を受け取る場合には、\begin{eqnarray*}u_{2}\left( a_{2}^{\prime },w\left( a_{2}\right) -w\left( a_{2}^{\prime
}\right) +t\right) &=&w\left( a_{2}^{\prime }\right) +w\left( a_{2}\right)
-w\left( a_{2}^{\prime }\right) +t\quad \because \left( 4\right) \\
&=&w\left( a_{2}\right) +t \\
&=&u_{2}\left( a_{2},t\right) \quad \because \left( 4\right)
\end{eqnarray*}が成り立つため、プレイヤー\(2\)は\(a_{2}\)から\(a_{2}^{\prime }\)への移行を容認することになります。プレイヤー\(1\)が支払う金額とプレイヤー\(2\)が受け取る金額は一致するため、\(\left( a_{1},a_{2}\right) \)から\(\left( a_{1}^{\prime },a_{2}^{\prime }\right) \)へ移行するための利害調整に際して、提携の内部において追加的な費用は発生していないことに注意してください。提携が2人以上のプレイヤーを含む場合にも同様の議論が成り立ちます。

以上の議論より、プレイヤーたちが準線型の利得関数を持つ場合には、金銭を用いることにより、提携の内部で事後的に利害を調整できることが明らかになりました。言い換えると、プレイヤーたちが準線型の利得関数を持つ場合には、提携の内部においてプレイヤーどうしが金銭を媒介する形で利得（提携値）を自由に譲渡できます。したがって、以上の想定のもとでは、プレイヤーたちがどの提携に属するかを決定する事前の段階において、提携値に関する情報さえ与えられれば判断材料として十分です。このような事情を踏まえた上で、協力ゲームの利得構造を提携関数\(v:2^{I}\rightarrow \mathbb{R} \)を用いて記述する場合、そのようなモデルを譲渡可能効用を前提とする協力ゲーム（cooperative game with transferable utility）と呼びます。

プレイヤーが得る利得の表現

協力ゲームにおいてプレイヤーたちがどのような提携を形成するか、その結果はプレイヤー集合\(I\)の分割に相当する提携構造\begin{equation*}\mathcal{C}=\left\{ C_{1},\cdots ,C_{K}\right\}
\end{equation*}として表現されます。形成されたそれぞれの提携\(C_{1},\cdots ,C_{K}\)が得る利得、すなわち提携値は特性関数\(v:2^{I}\rightarrow \mathbb{R} \)から、\begin{equation*}v\left( C_{1}\right) ,\cdots ,v\left( C_{K}\right)
\end{equation*}と特定できます。

提携構造\(\mathcal{C}\)とそれぞれの提携\(C_{1},\cdots ,C_{K}\)の提携値\(v\left( C_{1}\right) ,\cdots ,v\left( C_{K}\right) \)が決定したら、続いて問題になるのは、それぞれの提携の内部における資源分配です。プレイヤーが他のプレイヤーと提携を形成しない場合に得る利得を\(0\)と表現するのであれば、プレイヤーたちが得る利得からなる組\begin{equation*}a=\left( a_{1},\cdots ,a_{n}\right)
\end{equation*}は以下の条件\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*}をともに満たす必要があります。条件\(\left(a\right) \)は、すべてのプレイヤーが得る利得が非負であることを意味し、条件\(\left( b\right) \)は、それぞれの提携\(C_{k}\)の内部においてプレイヤーたちに割り当てられる利得の総和は、その提携の提携値\(v\left( C\right) \)を上回ることはできないことを意味します。

提携構造\(\mathcal{C}\)と利得の組\(a\)からなる組\begin{equation*}\left( \mathcal{C},a\right)
\end{equation*}を協力ゲームの結果（outcome）と呼びます。

特に、結果\(\left( \mathcal{C},a\right) \)のもとで先の条件\(\left(b\right) \)が等号で成立する場合には、すなわち、\begin{equation*}\left( b\right) \ \forall k\in \left\{ 1,\cdots ,K\right\} :\sum_{i\in
C_{k}}a_{i}=v\left( C\right)
\end{equation*}が成り立つ場合には、この結果\(\left( \mathcal{C},a\right) \)は効率的（efficient）であると言います。これは、それぞれの提携\(C_{k}\)の内部においてプレイヤーたちに割り当てられる利得の総和が、その提携の提携値\(v\left( C\right) \)と一致すること、すなわちプレイヤーたちに配分されずに残る資源が存在しないことを意味します。

先の議論から明らかになったように、協力ゲームの利得構造を提携関数\(v:2^{I}\rightarrow \mathbb{R} \)として記述する場合には、提携の内部において利得の譲渡が可能である状況を想定していることになります。したがって、提携構造\(\mathcal{C}\)が与えられたとき、それに対して、先の2つの条件\(\left( a\right) ,\left( b\right) \)を満たす利得の組\(a\)はいずれも実行可能です。なぜなら、条件\(\left( a\right) ,\left( b\right) \)を満たす利得の組\(a,a^{\prime}\)が与えられたとき、提携の内部においてプレイヤーどうしが金銭を媒介する形で利得を譲渡すれば\(a\)から\(a^{\prime }\)へ移行することが常に可能だからです。

譲渡可能効用を持つ提携型ゲーム

協力ゲームがプレイヤー集合\(I\)と特性関数\(v:2^{I}\rightarrow \mathbb{R} \)によって記述されている場合、これらの要素からなるモデルを、\begin{equation*}G=\left\{ I,v\right\}
\end{equation*}で表記し、これを譲渡可能効用を前提とする提携型ゲーム（coalitional game with transferable utility）と呼びます。もしくは、頭文字をとってTUゲーム（TU game）と呼ぶ場合もあります。誤解の恐れがない場合、これをシンプルに提携型ゲーム（coalitional game）と呼ぶこととします。

協力ゲームが提携型ゲーム\(G\)によって表現される場合、\(G\)を構成するすべての要素はプレイヤーたちの共有知識です。

協力ゲームが提携型ゲーム\(G\)によって表現される場合、プレイヤーたちがどのような提携を形成し、さらに、提携の内部においてどのように資源を配分するかが問題になりますが、それは提携型ゲームの結果\begin{equation*}\left( \mathcal{C},a\right)
\end{equation*}として記述されます。

演習問題