協力ゲーム

提供: miniwiki
移動先:案内、検索


協力ゲーム（きょうりょくゲーム、英: cooperative game）とは、ゲーム理論において、複数のプレイヤーによる提携 (coalition) 行動が可能であるとされた場合のゲームである。協力ゲームにおける提携行動は、提携をする各プレイヤーの利得を増加される場合に行われるとされている。

提携行動を行うためには、事前の交渉と互いに拘束力のある合意が必要であると考えられている。この考え方にしたがって、協力ゲームを交渉を行う非協力ゲームから説明しようという研究計画をナッシュプログラムという。

数学的な定義

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

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

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

双対性

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

[math] v^*(S) = v(N) - v( N \setminus S ), \forall~ S \subseteq N.\, [/math]

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

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

部分ゲーム

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

[math] v_S(T) = v(T), \forall~ T \subseteq S.\, [/math]

と定められる。

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

特性関数の性質

優加法性

A と B が2つの非交和（[math]A\cap B = \emptyset[/math]）提携である場合、 A と B の大提携の値は単独での値の和以上になる。すなわち、

[math] v (A \cup B) \; \ge \; v (A) \; + \; v (B) [/math] if [math]A\cap B = \emptyset[/math].

優加法性は特性関数の特徴であり、{{#invoke:Footnotes | harvard_citation }} を満たすと仮定される。

単調性

提携が大きいと報酬も大きい: [math] A \subseteq B \Rightarrow v (A) \le v (B) [/math].

単純ゲームの性質

「単純ゲーム」(シンプルゲーム; 投票ゲーム) とは 1 または 0 の利得 (値) だけを取る協力ゲームであり、利得が 1 となる提携を「勝利提携 (勝ち提携)」、利得が 0 となる提携を「敗北提携 (負け提携)」とよぶ。通常は単純ゲームは提携のあつまり [math]W[/math] として定義し、このばあいは [math]W[/math] に属する提携を勝利提携，属さないものを敗北提携とみなす。単純ゲームが非空であること、空集合をふくまないことを仮定することも多い。

  • 単純ゲーム [math]W[/math] が「単調である」とは、勝利提携をふくむ提携がかならず勝利提携になることをいう。すなわち [math]S \in W[/math] かつ [math]S\subseteq T[/math] ならば [math]T \in W[/math] となることをいう。
  • 単純ゲーム [math]W[/math] が「プロパーである」とは、勝利提携の補集合（補提携）がかならず敗北提携になることをいう。 すなわち [math]S \in W[/math] ならば [math]N\setminus S \notin W[/math] となることをいう。
  • 単純ゲーム [math]W[/math] が「強い」とは、敗北提携の補集合（補提携）はかならず勝利提携になることをいう。 すなわち [math]S \notin W[/math] ならば [math]N\setminus S \in W[/math] となることをいう。
    • 単純ゲーム [math]W[/math] がプロパーで強いとき、ある提携が勝つことと、その補提携が負けることは同値である。 すなわち [math]S \in W[/math] と [math]N\setminus S \notin W[/math] が同値である。 (プロパーで強い単純ゲームを提携ゲーム [math]v[/math] で表せば、任意の提携 [math]S[/math] について，[math]v(S) = 1 - v(N \setminus S)[/math] となる。)
  • 単純ゲームにおける「拒否権プレイヤー」とは、どの勝利提携の要素（メンバー）にもなっているプレイヤーである。すなわち、拒否権プレイヤーが存在するような単純ゲームでは、拒否権プレイヤーがいない提携は必ず負ける。単純ゲーム [math]W[/math] が「弱い」とは、拒否権プレイヤーが存在することである。すなわち、すべての勝利提携のインターセクション [math]\bigcap W := \bigcap_{S\in W} S[/math] が非空となることである。
    • 単純ゲームにおける「独裁者」とは、そのプレイヤーをふくむ任意の提携が勝利提携となるような拒否権プレイヤーのことである。独裁者が敗北提携に属することはない。
  • 単純ゲーム [math]W[/math] の「キャリア」とは、集合 [math]T \subseteq N[/math] で、任意の提携 [math]S[/math] について、[math]S \in W[/math] と [math]S\cap T \in W[/math] とが同値となるものである。キャリアに属さないプレイヤーは無視される。単純ゲームが有限のキャリアを持つとき、(たとえ [math]N[/math] が無限でも) その単純ゲームが「有限である」ということもある。
  • 単純ゲームの「中村ナンバー」とは、共通部分が空集合になるような勝利提携の最少数のことである。中村の定理によれば、この数は合理性の程度をはかる指標といえ、これ未満の数の選択肢までならうまくあつかえることが分かっている。

単純ゲームの持つ性質 (公理) のあいだの関係については以下が広く知られている (e.g., Peleg, 2002, Section 2.1[1]):

  • 弱い単純ゲームはプロパーである。
  • 単純ゲームが独裁者を持つことは、それが強くて弱いことと同値である。

より一般的には、単純ゲームにかんする伝統的な４つの性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか) に加え、有限かどうか、「計算可能」かどうか[2] をふくめた６つの性質のあいだの関係が完全に解明されており (Kumabe and Mihara, 2011[3]) 、その結果は以下の表「単純ゲームの存在」に要約できる。たとえば伝統的４性質の組合せで定義される「タイプ」が無限ゲームを含むとき、そのタイプには計算可能なものも計算不能なものも含まれることが分かる。

単純ゲームの存在[4]
Type 有限計算不能 有限計算可能 無限計算不能 無限計算可能
1111 no yes yes yes
1110 no yes no no
1101 no yes yes yes
1100 no yes yes yes
1011 no yes yes yes
1010 no no no no
1001 no yes yes yes
1000 no no no no
0111 no yes yes yes
0110 no no no no
0101 no yes yes yes
0100 no yes yes yes
0011 no yes yes yes
0010 no no no no
0001 no yes yes yes
0000 no no no no

単純ゲームにかかわる代表的な性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか、有限かどうか) がその中村ナンバーにあたえる制限については、完全に解明されている[5]。特に、アルゴリズムによって計算可能でかつ拒否権プレーヤーをもたない単純ゲームが3より大きい中村ナンバーをもつとき、 その単純ゲームはプロパーかつ強くないことが分かっている。

解の概念

協力ゲームは提携に対する報酬を記述する。 プレイヤーは提携に参加した方がしない場合より得をする場合に限り提携に参加する。 したがって、どんな提携が実際に組まれるかを見出すには、異なる提携間の相対的な力関係および各提携内の異なるプレイヤーの強さを評価する必要がある。 報酬を各プレイヤーにどう分配するのかを考えるのが協力ゲームの重要な目的であり、この目的のためにさまざまな解概念が提示されている。

協力ゲームにおいて中心となる仮定は、全体提携 N が形成されるということである。 ここで公平な方法でプレイヤー達に全体提携で得られた v(N) を分配するよう取り組まなくてはならない。 (例え個人の提携や小規模な提携を形成しても、その形成された提携から部分ゲームを求めれば 解の概念を部分ゲームに適用できるので、この仮定は限定的なものではない。)

解の概念は、それぞれのプレイヤー得られる配分を示す [math] x \in \mathbb{R}^N [/math]というベクトルによって与えられる。 様々な公平性の基準によって、複数種の解の概念が提案されている。

解の概念の性質

解の概念にはいくつかの性質が含まれることがある。 ここに解の概念に現れることのある性質について述べておく。

また、利得ベクトルのうち、全体合理性を満たす準配分 (pre-imputation) 、 全体合理性と個人合理性を満たすものを配分 (imputation) と呼ぶ。 ほとんどの解の概念は、ゲームの解として配分を与える。

  • 効率性 (Efficiency)・全体合理性

解の利得ベクトルが全体提携の提携値を分配する性質。すなわち、

[math] \sum_{ i \in N } x_i = v(N) [/math]

が成り立つことを言う。

全てのプレイヤーは自身のみで獲得できる以上に利得を得られる性質。

[math] x_i \geq v(\{i\}), \forall~ i \in N [/math]

であることを言う。

  • 対称性 (Symmetry)

利得ベクトル[math] x [/math]が対称なプレイヤー[math] i [/math], [math] j [/math]に対して等しい利得を与える([math] x_i = x_j [/math]) 性質。 ここで対称なプレイヤーとは、[math] v( S \cup \{ i \} ) = v( S \cup \{ j \} ), \forall~ S \subseteq N \setminus \{ i, j \} [/math]が成り立つようなプレイヤー[math] i [/math], [math] j [/math]のことである。 対称性のある解の概念は、入れ替え可能なプレイヤーについては利得に違いを与えない。

  • 加法性 (Additivity)

2つのゲームの和からなるゲームにおいて、プレイヤーへの利得が (和を取った)それぞれのゲームでの利得の和に等しくなる性質。 [math] v [/math] と [math] \omega [/math] をゲームとすると、 ゲーム[math] ( v + \omega ) [/math]は、提携Sに対してそれぞれのゲームの提携値の和を 提携値 [math] ( v + \omega )(S) [/math] として与えるゲームである。 加法性のある解の概念は、[math] ( v + \omega ) [/math]の全てのプレイヤーに対して [math] v [/math] と [math] \omega [/math]で得られる利得の合計値を利得として割り振る。

  • ナルプレイヤーに関する性質

ナルプレイヤー (Null Players) に与える利得がゼロになる性質。ナルプレイヤーとは、[math] v( S \cup \{ i \} ) = v( S ), \forall~ S \subseteq N \setminus \{ i \} [/math]を満たすプレイヤー[math] i [/math]のことである。 経済的に言い換えれば、ナルプレイヤーはいかなる自身を含まない提携に対しても与える寄与分がゼロである。

  • 存在性 (Existence)

解の概念による解がいかなるゲームvについても存在する。

  • 唯一性 (Uniqueness)

解の概念による解がいかなるゲームvについても唯一である。

  • 計算容易性 (Computational ease)

解の概念が効率よく計算できる性質。すなわち、プレイヤーの人数[math] |N| [/math]に関して多項式時間計算可能である。

安定集合

ゲームの「安定集合」（フォン・ノイマン＝モルゲンシュテルン解）{{#invoke:Footnotes | harvard_citation }})　 は3人以上のゲームに関し提案された最初の解である。

安定集合の定義

安定集合はこれら2つの性質をもつ配分の集合である。

  • 「内部安定性」：安定集合の要素はどれ一つとして他の要素に支配されない。
  • 「対外安定性」：安定集合外の候補は安定集合の要素の少くとも一つに支配される。

フォン・ノイマンと モルゲンシュテルンは安定集合を 社会的に受け入れられる振舞いの集合と見た。 どれも明らかに他よりも好かれてはいないが、 受け入れられない振舞いのどれにもそれより優れた代案がある。

この定義は非常に一般的であるため、広範な種類のゲームの形式に使われている。

安定集合の性質

  • 安定集合は存在する場合もしない場合もあり、{{#invoke:Footnotes | harvard_citation }} 存在しても典型的には一意ではない。{{#invoke:Footnotes | harvard_citation }}. 安定集合を見出すのは普通は難しい。

この事実とその他の困難から、他に多数の解の概念が発展した。

  • 協力ゲームの positive fraction はコアからなる一意な安定集合をもつ。{{#invoke:Footnotes | harvard_citation }}.
  • 協力ゲームの positive fraction は [math]n - 2[/math] 人のプレイヤーを区別する安定集合をもつ。このような安定集合は少くとも [math]n - 3[/math] の被差別プレイヤーを排除する。 {{#invoke:Footnotes | harvard_citation }}

配分の支配

[math] v [/math]をゲームとして、[math] x [/math]と[math] y [/math]をそれぞれ[math] v [/math]の配分とする。 [math] x_i \gt y _i, \forall~ i \in S [/math] と [math] \sum_{ i \in S } x_i \leq v(S) [/math]を満たすような 提携 [math] S \subseteq N[/math](ただし、[math]S \neq \emptyset[/math])が存在するとき、 [math] x [/math] は [math] y [/math] を支配するという。

すなわち、このときSのプレイヤー達は[math] y [/math]によって得る利得よりも[math] x [/math]によって得る利得を好み、 [math] y [/math]が使われれば全体提携を抜けると脅すだろうと考えられる。

コア

コアの定義

"「コア (ゲーム理論)」"

「コア」とは、ゲームにおいてプレイヤーに報酬を配分するベクトルの集合であり、以下の条件を満たすものである。

  • 「効率性」：プレイヤーが「大提携」（全プレイヤーからなる提携）を行い、各人への報酬の総額は大提携の値と等しくなるべきである。
  • 「戦略安定性」または「均衡」：どの連携も大連携を裏切って得をすることはできない。
（たとえば、どの提携も各成員の報酬の総額よりも大きくはならない。（疑問あり））

ここで、[math] v [/math]をゲームとすれば、[math] v [/math]のコア[math] C(v) [/math]は、以下のような利得ベクトルの集合である。

[math] 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\}.\, [/math]

言い換えれば、提携Sのメンバーの得られる利得の合計が提携値v(S)以上になるよう定めた配分の集合がコアである。 すなわち、コアの利得ベクトルによって利得を獲得するなら、 どの提携 S においても全体提携 N から抜けて多くの利得を獲得しようという動機が無くなる。

コアは空集合になる場合もあることに注意されたい。

選好プロファイルにおける単純ゲームのコア

単純ゲームについては、ある選択肢集合 [math]X[/math] 上で各プレイヤーの選好が定義されるとき、上記と異なる「コア」の概念が存在する。 「選好プロファイル」とは各個人 [math]i[/math] の選好[math]\succ_i^p[/math]からなるリスト (列) [math]p=(\succ_i^p)_{i \in N}[/math] のことである。 ここで [math]x \succ_i^p y[/math] は、「個人 [math]i[/math] がプロファイル[math]p[/math] において、選択肢 [math]x[/math]を選択肢 [math]y[/math]より好む」ことを指す。 シンプルゲーム [math]v[/math] と選好プロファイル [math]p[/math] が与えられたとき、[math]X[/math]上で「支配関係」[math]\succ^p_v[/math] を 以下のように定義する: [math]x \succ^p_v y[/math] とは、ある勝利提携 [math]S[/math] (i.e., [math]v(S)=1[/math]) が存在して、すべての [math]i \in S[/math] について [math]x \succ_i^p y[/math] となることである。 「選好プロファイル[math]p[/math]にかんする単純ゲーム[math]v[/math]のコア」[math]C(v,p)[/math] とは、 関係[math]\succ^p_v[/math]によって支配されないような選択肢の集合 ([math]\succ^p_v[/math] についての集合 [math]X[/math] 上の極大要素の集合) のことである:

[math]x \in C(v,p)[/math] は、[math]y \succ^p_v x[/math]となる[math]y\in X[/math]が存在しないことと同値である。

単純ゲームの「中村ナンバー」とは、共通部分が空集合となるような勝利提携の最少数のことである (この数だけ勝利提携を集めればインターセクションを空にできることがあるが、これ未満の数だけ集めてもけっしてインターセクションを空にはできない)。 中村の定理によれば、すべての非循環的選好 (推移的選好としても同様) のプロファイル [math]p[/math] にかんしてコア [math]C(v,p)[/math] が非空になることは、選択肢集合 [math]X[/math] が有限かつその濃度 (要素数) が [math]v[/math] の中村ナンバーよりも小さいことと同値である。 Kumabe and Mihara によるその定理の変種によれば、極大要素を持つ選好からなる任意のプロファイル [math]p[/math] にかんしてコア [math]C(v,p)[/math] が非空になることは、選択肢集合の濃度が [math]v[/math] の中村ナンバーよりも小さいことと同値である。詳細は「中村ナンバー」参照。

カーネル

カーネルとは、報酬を割り当てるベクトルのうち、

  • 効率性
  • 個別合理性

を満足するものである。

シャープレイ値

"「シャープレイ値」"

協力ゲームの例

複数企業[math] A, B, C [/math]の共同事業を考えよう。それぞれの企業の利益を、

[math] v(\{A\}) = 3, v(\{B\}) = 6, v(\{C\}) = 5, v(\{A,B\}) = 10, v(\{A,C\}) = 10, v(\{B,C\}) = 12, v(\{A,B,C\}) = 18 [/math]

とする。

ここで、例えば[math] v(\{A,B\}) [/math]とは企業 A, B が協力したときの利益を示す。この例では、「優加法性」が常に成立しているといえる。例えば、([math] v(\{A,B,C\}) = 18 \geqq v(\{A,B\}) + v(\{C\}) = 15 [/math] である。)優加法的である場合、提携したほうが全体の利得は大きくなる。しかし、個々の企業にとって提携するかどうかは利得の分配によって変わる。

3社が共同したときの企業[math] A, B, C [/math]の利得をそれぞれ[math]x_A, x_B, x_C[/math]とする。

例として、利得が[math] x_A = 4, x_B = 4, x_C = 10 [/math]の場合を考える。この場合、[math]x_A + x_B = 8 \lt v(\{A,B\}) = 10 [/math]となるので、企業 A, B は2社だけで提携し、利得[math] (x_A = 5, x_B = 5) [/math]を受け取ったほうが有利である。そのため、この条件では企業 A, B は C を含んだ3社の提携を拒否するであろう。このような状態のことを、提携 [math] (AB) [/math]に関して、配分[math] (x_A = 5, x_B = 5) [/math]は配分[math] (x_A = 4, x_B = 4, x_C = 10) [/math]を支配するという。

他方、配分[math] (x_A = 5, x_B = 7, x_C = 6) [/math]の場合、いずれの2社の提携によっても、その提携に参加したすべての企業の利得を増加させることができない。このような配分のみがコアに属する。

脚注

  1. ↑ テンプレート:Cite doi
  2. ↑ 単純ゲームが 「計算可能である」ことの定義は、ライスの定理に類する結果を参照。特に、任意の有限ゲームは計算可能である。
  3. ↑ テンプレート:Cite doi
  4. ↑ Kumabe and Mihara (2011) の Table 1 を修正。 16個ある Type は伝統的な４つの性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか) で決まる。 たとえば type 1110 とは単調 (1) でプロパー (1) で強く (1) 拒否権プレーヤーあり (0) の単純ゲームたちを指す。 その行は type 1110 ゲームのなかに、有限かつ計算不能なものが不在であり、有限かつ計算可能なものが存在し、無限かつ計算不能なのものが不在であり、無限かつ計算可能なものが不在であることをしめす。
  5. ↑ テンプレート:Cite doi

参考文献

翻訳元

本記事の一部はウィキペディア英語版記事

  • Cooperative game. Wikipedia: Free Encyclopedia. [[:en:Cooperative_game]|21:37, 25 April 2011] からの抄訳に基づいて作成された。

テンプレート:ゲーム理論



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=協力ゲーム&oldid=105925」から取得