提携形ゲーム

【ていけいけいげーむ (game in coalitional form)】

概要

協力ゲームの表現形式の1つ. プレイヤー集合 $N\,$と特性関数 $v\,$ (提携の形成により獲得可能な利得の和を表す関数)の組 $(N,v)\,$で表わされる.特性関数形ゲームとも呼ばれる. また, 特性関数の値が利得ベクトルの集合で表される場合もある(譲渡可能効用をもたないゲーム).協力により得られた成果を合理的な基準を基に各プレイヤーに分配した結果を提携形ゲームの解と呼び, コア, 安定集合, 交渉集合, カーネル, 仁, シャープレイ値などがある.

詳説

　提携形ゲーム (game in coalitional form) は協力ゲームの表現形式の一つであり, プレイヤー集合$N\,$と, プレイヤーが提携 (coalition) を形成し共同行動をとる際に実現可能な結果を表す特性関数 (characteristic function) $v\,$の組$(N,v)\,$で表わされる. このために提携形ゲームは特性関数形ゲーム (game in characteristic function form) とよばれることもある. 特性関数の値は, 提携がそのメンバーだけで実現可能な利得の総和 (実数値) で表される場合 (譲渡可能効用を持つゲーム, game with transferable utility, TU-game) と, 提携の各メンバーの実現可能な利得ベクトルの集合で表される場合 (譲渡可能効用を持たないゲーム, game without transferable utility, NTU-game) がある. 譲渡可能効用を持つゲームでは, 共同行動の利害を調整するために貨幣などの媒介物による利得の別払い (sidepayment) が必要となる. 譲渡可能効用を持たないゲームの詳細については [13] を参照.

　提携形ゲーム$(N,v)\,$における基本的な問題は, プレイヤー間の協力の結果, (1) いかなる提携が形成され, (2) 提携のメンバーの間で利得がどのように分配されるか, である. 協力に関する交渉の結果, 各プレイヤー$i\,$に最終的に分配される利得$x_{i}\,$から成るベクトル$x=(x_{1},x_{2},\ldots ,x_{n})\,$を利得ベクトルとよび, さまざまな合理性の基準により, 結果として到達されると考えられる利得ベクトルの集合を提携形ゲームの解とよぶ.

　優加法性 (superadditivity) をみたすゲームにおいてはプレイヤー全体による提携Nが形成されると考えられるので$v(N)\,$の値をどのようにプレイヤー間で分配すべきかが問題となる. このとき, ゲームの解の基本的な条件としては全体合理性 (total group rationality) と個人合理性 (individual rationality) の2つがあげられる. 前者は, 利得ベクトルが, プレイヤーが協力して実現できる実現可能集合においてパレート最適 (Pareto optimum) であることを要請し, 後者はゲームに参加して協力することの結果が, 単独で行動するよりも悪くならないことを要請している. 全体合理性をみたす利得ベクトルを準配分 (preimputation) とよび, 全体合理性と個人合理性の両方をみたす利得ベクトルを配分 (imputation)とよぶ.

　提携形ゲームの解で, 経済分析や費用分担問題などの応用も多く, よく知られているのはコア (core) である. コアは常に存在するとは限らないが, 存在のための必要十分条件がボンダレーヴァ (O. N. Bondareva) やシャープレイ (L. S. Shapley) によって研究されている. 特に, 市場経済をゲームとして定式化した市場ゲームについては多くの研究があり, 競争均衡がコアに含まれることが知られている. また, 非分割財市場ゲームなどの種々の割当て市場ゲームや投票ゲーム, 費用分担ゲームなどにおいても, コアは分配案の安定性を示す重要な概念となっている.

　コアと同様に 支配 (domination) 関係によって定義された解として知られているのはフォンノイマン (J. von Neumann) とモルゲンシュテルン (O. Morgenstern) によって提唱された安定集合 (stable set) である [14]. 安定集合はフォンノイマン・モルゲンシュテルン解 (von Neumann-Morgenstern solution) とよばれることもある. 安定集合は存在しない場合もあるし, 複数存在する場合もあるが, 存在すればコアを含む. また, コア自身が安定集合であれば, コア以外に安定集合は存在しない.

　一方, 提携構造を考慮に入れた特性関数を基に始まった一連の研究があり, それらのゲームの解としては交渉集合 (bargaining set) , カーネル (kernel), 仁 (nucleolus) がある. 交渉集合はオーマン (R. J. Aumann) とマシュラー (M. Maschler) によって異議と逆異議を用いて定義された解であり, 常に存在し, コア, カーネル, 仁を含んでいる [2]. カーネルと仁は提携のもつ利得ベクトルへの不満 (超過要求) に基づいて定義された解である. カーネルはデービス (M. Davis) とマシュラーにより導入され [4], 仁はシュマイドラー (D. Schmidler) により導入された [10]. カーネルと仁はともに常に存在し, 仁はカーネルと最小コア (least core) の共通部分に含まれている. 仁は常にただ1つの配分から成り, その計算法についてもいろいろな研究がなされている. 破産問題においては, ユダヤ教の教典かつ律法書であるタルムード (Talmud) に1500年前に記述された分配方法とカーネルの与える分配が一致するという興味深い結果が知られている [3]. カーネルと仁は配分の集合を基に, 定義されているが, 準配分の集合において同等の定式化を行うと, 準カーネル, 準仁などの概念が導かれる. これらの解の性質については [1]の18章にまとめられている.

　提携形ゲームにおいて, プレイヤーがそのゲームに参加する場合のゲームの事前評価の値をゲームの値という. ゲームの値の概念の中で最もよく知られたものはシャープレイ値 (Shapley value) である [11] . シャープレイ値は全体合理性, 対称性, 加法性, ナルプレイヤーのゼロ評価の４公理をみたす唯一の値 (ゲームの関数) として与えられる. シャープレイ値の応用の1つは投票ゲームへの適用である. シャープレイ・シュービック指数と呼ばれ, 各投票者の影響力を示すパワー指数の1つとして広く用いられている.

　提携形ゲームにはこのように多数の解概念が提唱されているが, それらの解概念の共通点や差異を調べるためにいろいろなゲームのクラスにおいて, 解の間の幾何学的関係が研究されている. 凸ゲーム (convex game) のクラスにおいては, 交渉集合がコアおよび安定集合と一致し, シャープレイ値はコアの重心になる. また, カーネルは仁と一致することが知られている. 凸ゲームを含む広いゲームのクラスや他のゲームのクラスにおける解の関係については [5] を参照されたい.

　近年, 公理化のアプローチを多くの提携形ゲームの解概念に用い, 統一的な公理(整合性公理)で解の性質を解明しようとする研究が進んでいる. ある状況 (ゲーム) で解の与える利得分配と, プレイヤー数名が解の与える利得を持ってそのゲームから退出し, 残された状況 (縮小ゲーム) での解の与える利得分配を比較する. 整合性公理は, この両方の状況での解の与える利得分配が一致することを要請している. このとき, 残されたプレイヤーへの退出プレイヤーの協力の形態により縮小ゲームの構造が異なり, この縮小ゲームの差異を基に, コア, 準仁, 準カーネル, シャープレイ値などの整合性公理による公理化が研究されている. この分野に関しては例えば [6] を参照.

　なお, 提携形ゲーム全般の詳しい解説は [7], [8], [9], [12], [13] などを参照されたい. また, [1] のいくつかの章には, 提携形ゲームに関するトピックがテーマごとに詳細にまとめられており参考になる.

---

参考文献

[1] R. J. Aumann and S. Hart, eds., Handbook of Game Theory Volume I, Volume II, North-Holland, 1992, 1994.

[2] R. J. Aumann and M. Maschler, "The Bargaining Set for Cooperative Games," in Advances in Game Theory, M. Dresher, L. S. Shapley and A. W. Tucker, eds., Princeton University Press, 1964.

[3] R. J. Aumann and M. Maschler, "Game Theoretic Analysis of a Bankruptcy Problem," Journal of Economic Theory, 36 (1985), 195-213.

[4] M. Davis and M. Maschler, "The Kernel of a Cooperative Game," Naval Research Logistics Quarterly, 12 (1965), 223-259.

[5] T. S. H. Driessen, Cooperative Games, Solutions and Applications, Kluwer Academic Publishers, 1988.

[6] T. S. H. Driessen, "A Survey of Consistency Properties in Cooperative Game Theory," SIAM Review, 33 (1991), 43-59.

[7] 船木由喜彦, エコノミックゲームセオリー, サイエンス社, 2001.

[8] 武藤滋夫, ゲーム理論入門, 日本経済新聞社, 2001.

[9] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

[10] D. Schmeidler, "The Nucleolus of a Characteristic Function Game," SIAM Journal of Applied Mathematics, 17 (1969), 1163-1170.

[11] L. S. Shapley, "A Value for n-Person Games," in Contributions to the Theory of Games II, H. Kuhn and A. W. Tucker, eds., Princeton University Press, 1953.

[12] 鈴木光男, 『新ゲーム理論』, 勁草書房, 1994.

[13] 鈴木光男, 武藤滋夫, 『協力ゲームの理論』, 東京大学出版会, 1985.

[14] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, 3rd ed., Princeton University Press, 1953.