協力ゲーム（きょうりょくゲーム、）とは、ゲーム理論において、複数のプレイヤーによる提携 (coalition) 行動が可能であるとされた場合のゲームである。協力ゲームにおける提携行動は、提携をする各プレイヤーの利得を増加される場合に行われるとされている。提携行動を行うためには、事前の交渉と互いに拘束力のある合意が必要であると考えられている。この考え方にしたがって、協力ゲームを交渉を行う非協力ゲームから説明しようという研究計画をナッシュプログラムという。協力ゲームはあらゆるNの部分集合S("提携")にある値を特定することにより与えられる。数学的には、このゲーム (提携ゲーム) は有限なプレイヤー集合formula_1と関数 formula_2によって定義される。この関数は特性関数 (characteristic function) とも呼ばれる。協力ゲームはプレイヤーの集合Nと特性関数vの組formula_3によって表される。協力ゲームの表現・解析には特性関数がよく用いられ、vをゲームと呼ぶこともある。関数formula_4は、formula_1における提携それぞれに報酬を対応づけるものと解釈される。ある提携Sに対する特性関数の値v(S)はSのプレイヤーが獲得できる最良の値を表し、formula_6を"提携値"と呼ぶ。通常はformula_7（誰も参加しない提携への報酬を与えないこと）を仮定する。また、提携ゲームにおける報酬とは反対に、formula_1における提携それぞれでの費用を対応づける費用関数(cost function) formula_9を用いて記述する方法もある。これを費用ゲーム(cost game)と呼ぶ。費用関数によって得られる値は提携したプレイヤーたちが支払う費用を示す。提携ゲームでの概念は費用ゲームにおける概念へ簡単に書き換えることができる。formula_4 を報酬ゲームの関数とする。formula_4 の"双対ゲーム"(dual game)である費用ゲームの関数formula_12 の値は以下のように定められる。直観的に、双対ゲームは全体提携 N に参加しないことによる提携 formula_14の機会費用(opportunity cost)を表現していると考えられる。報酬ゲームformula_15は同様に、費用ゲームformula_16の双対報酬ゲームとして決まる。協力ゲームとその双対ゲームはいくつかの意味において等価なものであり、それらは多くの性質を共有している。例えば、あるゲームとその双対ゲームにおいてそのコアは等しい。ある提携ゲーム formula_3 において formula_18を空でないプレイヤーの集合とする。formula_14での"部分ゲーム"formula_20は自ずとと定められる。言い換えれば、単にSに含まれる提携に制限して注目するということである。部分ゲームは、全体提携 N に対して定められた 解の概念 を N より小さな提携に適用することを可能とするため有用である。A と B が2つの非交和（formula_22）提携である場合、A と B の大提携の値は単独での値の和以上になる。すなわち、formula_23 if formula_22.優加法性は特性関数の特徴であり、 を満たすと仮定される。提携が大きいと報酬も大きい: formula_25.「単純ゲーム」(シンプルゲーム; 投票ゲーム) とは 1 または 0 の利得 (値) だけを取る協力ゲームであり、利得が 1 となる提携を「勝利提携 (勝ち提携)」、利得が 0 となる提携を「敗北提携 (負け提携)」とよぶ。通常は単純ゲームは提携のあつまり formula_26 として定義し、このばあいは formula_26 に属する提携を勝利提携，属さないものを敗北提携とみなす。単純ゲームが非空であること、空集合をふくまないことを仮定することも多い。数学の他の分野では、単純ゲームは「ハイパーグラフ」あるいは「ブール関数」(論理関数) とよばれることもある。単純ゲームの持つ性質 (公理) のあいだの関係については以下が広く知られている (e.g., Peleg, 2002, Section 2.1):より一般的には、単純ゲームにかんする伝統的な４つの性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか) に加え、有限かどうか、「計算可能」かどうかをふくめた６つの性質のあいだの関係が完全に解明されており(Kumabe and Mihara, 2011)、その結果は以下の表「単純ゲームの存在」に要約できる。たとえば伝統的４性質の組合せで定義される「タイプ」が無限ゲームを含むとき、そのタイプには計算可能なものも計算不能なものも含まれることが分かる。単純ゲームにかかわる代表的な性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか、有限かどうか) がその中村ナンバーにあたえる制限については、完全に解明されている。特に、アルゴリズムによって計算可能でかつ拒否権プレーヤーをもたない単純ゲームが3より大きい中村ナンバーをもつとき、 その単純ゲームはプロパーかつ強くないことが分かっている。協力ゲームは提携に対する報酬を記述する。プレイヤーは提携に参加した方がしない場合より得をする場合に限り提携に参加する。したがって、どんな提携が実際に組まれるかを見出すには、異なる提携間の相対的な力関係および各提携内の異なるプレイヤーの強さを評価する必要がある。報酬を各プレイヤーにどう分配するのかを考えるのが協力ゲームの重要な目的であり、この目的のためにさまざまな解概念が提示されている。協力ゲームにおいて中心となる仮定は、全体提携 N が形成されるということである。ここで公平な方法でプレイヤー達に全体提携で得られた v(N) を分配するよう取り組まなくてはならない。(例え個人の提携や小規模な提携を形成しても、その形成された提携から部分ゲームを求めれば解の概念を部分ゲームに適用できるので、この仮定は限定的なものではない。)解の概念は、それぞれのプレイヤー得られる配分を示すformula_52というベクトルによって与えられる。様々な公平性の基準によって、複数種の解の概念が提案されている。解の概念にはいくつかの性質が含まれることがある。ここに解の概念に現れることのある性質について述べておく。また、利得ベクトルのうち、全体合理性を満たす準配分 (pre-imputation) 、全体合理性と個人合理性を満たすものを配分 (imputation) と呼ぶ。ほとんどの解の概念は、ゲームの解として配分を与える。解の利得ベクトルが全体提携の提携値を分配する性質。すなわち、が成り立つことを言う。全てのプレイヤーは自身のみで獲得できる以上に利得を得られる性質。であることを言う。利得ベクトルformula_55が対称なプレイヤーformula_56, formula_57に対して等しい利得を与える(formula_58) 性質。ここで対称なプレイヤーとは、formula_59が成り立つようなプレイヤーformula_56, formula_57のことである。対称性のある解の概念は、入れ替え可能なプレイヤーについては利得に違いを与えない。2つのゲームの和からなるゲームにおいて、プレイヤーへの利得が(和を取った)それぞれのゲームでの利得の和に等しくなる性質。formula_62 と formula_63 をゲームとすると、ゲームformula_64は、提携"S"に対してそれぞれのゲームの提携値の和を提携値 formula_65 として与えるゲームである。加法性のある解の概念は、formula_64の全てのプレイヤーに対してformula_62 と formula_63で得られる利得の合計値を利得として割り振る。ナルプレイヤー (Null Players) に与える利得がゼロになる性質。ナルプレイヤーとは、formula_69を満たすプレイヤーformula_56のことである。経済的に言い換えれば、ナルプレイヤーはいかなる自身を含まない提携に対しても与える寄与分がゼロである。解の概念による解がいかなるゲーム"v"についても存在する。解の概念による解がいかなるゲーム"v"についても唯一である。解の概念が効率よく計算できる性質。すなわち、プレイヤーの人数formula_71に関して多項式時間計算可能である。ゲームの「安定集合」（フォン・ノイマン＝モルゲンシュテルン解）)　は3人以上のゲームに関し提案された最初の解である。安定集合はこれら2つの性質をもつ配分の集合である。フォン・ノイマンとモルゲンシュテルンは安定集合を社会的に受け入れられる振舞いの集合と見た。どれも明らかに他よりも好かれてはいないが、受け入れられない振舞いのどれにもそれより優れた代案がある。この定義は非常に一般的であるため、広範な種類のゲームの形式に使われている。この事実とその他の困難から、他に多数の解の概念が発展した。formula_62をゲームとして、formula_55とformula_76をそれぞれformula_62の配分とする。formula_78 と formula_79を満たすような提携 formula_80(ただし、formula_81)が存在するとき、formula_55 は formula_76 を"支配する"という。すなわち、このときSのプレイヤー達はformula_76によって得る利得よりもformula_55によって得る利得を好み、formula_76が使われれば全体提携を抜けると脅すだろうと考えられる。「コア」とは、ゲームにおいてプレイヤーに報酬を配分するベクトルの集合であり、以下の条件を満たすものである。ここで、formula_62をゲームとすれば、formula_62のコアformula_89は、以下のような利得ベクトルの集合である。言い換えれば、提携Sのメンバーの得られる利得の合計が提携値v(S)以上になるよう定めた配分の集合がコアである。すなわち、コアの利得ベクトルによって利得を獲得するなら、どの提携 S においても全体提携 N から抜けて多くの利得を獲得しようという動機が無くなる。コアは空集合になる場合もあることに注意されたい。単純ゲームについては、ある選択肢集合 formula_91 上で各プレイヤーの選好が定義されるとき、上記と異なる「コア」の概念が存在する。「選好プロファイル」とは各個人 formula_92 の選好formula_93からなるリスト (列) formula_94 のことである。ここで formula_95 は、「個人 formula_92 がプロファイルformula_97 において、選択肢 formula_98を選択肢 formula_99より好む」ことを指す。シンプルゲーム formula_4 と選好プロファイル formula_97 が与えられたとき、formula_91上で「支配関係」formula_103 を 以下のように定義する: formula_104 とは、ある勝利提携 formula_42 (i.e., formula_106) が存在して、すべての formula_107 について formula_95 となることである。「選好プロファイルformula_97にかんする単純ゲームformula_4のコア」formula_111 とは、関係formula_103によって支配されないような選択肢の集合(formula_103 についての集合 formula_91 上の極大要素の集合) のことである:単純ゲームの「中村ナンバー」とは、共通部分が空集合となるような勝利提携の最少数のことである(この数だけ勝利提携を集めればインターセクションを空にできることがあるが、これ未満の数だけ集めてもけっしてインターセクションを空にはできない)。中村の定理によれば、すべての非循環的選好 (推移的選好としても同様) のプロファイル formula_97 にかんしてコア formula_111 が非空になることは、選択肢集合 formula_91 が有限かつその濃度 (要素数) が formula_4 の中村ナンバーよりも小さいことと同値である。Kumabe and Mihara によるその定理の変種によれば、極大要素を持つ選好からなる任意のプロファイル formula_97 にかんしてコア formula_111 が非空になることは、選択肢集合の濃度が formula_4 の中村ナンバーよりも小さいことと同値である。詳細は「中村ナンバー」参照。カーネルとは、報酬を割り当てるベクトルのうち、を満足するものである。複数企業formula_125の共同事業を考えよう。それぞれの企業の利益を、とする。ここで、例えばformula_127とは企業 A, B が協力したときの利益を示す。この例では、「優加法性」が常に成立しているといえる。例えば、(formula_128 である。)優加法的である場合、提携したほうが全体の利得は大きくなる。しかし、個々の企業にとって提携するかどうかは利得の分配によって変わる。3社が共同したときの企業formula_125の利得をそれぞれformula_130とする。例として、利得がformula_131の場合を考える。この場合、formula_132となるので、企業 A, B は2社だけで提携し、利得formula_133を受け取ったほうが有利である。そのため、この条件では企業 A, B は C を含んだ3社の提携を拒否するであろう。このような状態のことを、提携 formula_134に関して、配分formula_133は配分formula_136を支配するという。他方、配分formula_137の場合、いずれの2社の提携によっても、その提携に参加したすべての企業の利得を増加させることができない。このような配分のみがコアに属する。本記事の一部はウィキペディア英語版記事

出典:wikipedia