協力ゲーム 数学的な定義

ウィキペディア

協力ゲーム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/11 03:35 UTC 版)

数学的な定義

協力ゲームはあらゆるNの部分集合S(提携)にある値を特定することにより与えられる。数学的には、このゲーム (提携ゲーム) は有限なプレイヤー集合$N$と関数 $v:2^{N}\to \mathbb {R}$ によって定義される。この関数は特性関数 (characteristic function) とも呼ばれる。協力ゲームはプレイヤーの集合Nと特性関数vの組$(N,v)$によって表される。協力ゲームの表現・解析には特性関数がよく用いられ、vをゲームと呼ぶこともある。

関数$v$は、$N$における提携それぞれに報酬を対応づけるものと解釈される。ある提携Sに対する特性関数の値v(S)はSのプレイヤーが獲得できる最良の値を表し、$v(S)$を提携値と呼ぶ。通常は$v(\emptyset )=0$（誰も参加しない提携への報酬を与えないこと）を仮定する。

また、提携ゲームにおける報酬とは反対に、$N$における提携それぞれでの費用を対応づける費用関数(cost function) $C:2^{N}\to \mathbb {R}$を用いて記述する方法もある。これを費用ゲーム(cost game)と呼ぶ。費用関数によって得られる値は提携したプレイヤーたちが支払う費用を示す。提携ゲームでの概念は費用ゲームにおける概念へ簡単に書き換えることができる。

双対性

$v$ を報酬ゲームの関数とする。$v$ の双対ゲーム(dual game)である費用ゲームの関数$v^{*}$ の値は以下のように定められる。

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

直観的に、双対ゲームは全体提携 N に参加しないことによる提携 $S$の機会費用(opportunity cost)を表現していると考えられる。

報酬ゲーム$C^{*}$は同様に、費用ゲーム$C$の双対報酬ゲームとして決まる。 協力ゲームとその双対ゲームはいくつかの意味において等価なものであり、 それらは多くの性質を共有している。 例えば、あるゲームとその双対ゲームにおいてそのコアは等しい。 (協力ゲームの双対についての詳細は (Bilbao 2000) を参照のこと。)

部分ゲーム

ある提携ゲーム $(N,v)$ において $S\subsetneq N$を空でないプレイヤーの集合とする。 $S$での部分ゲーム$v_{S}:2^{S}\to \mathbb {R}$は自ずと

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

と定められる。

言い換えれば、単にSに含まれる提携に制限して注目するということである。 部分ゲームは、全体提携 N に対して定められた 解の概念 を N より小さな提携に適用することを可能とするため有用である。