ORWiki - 利用者の投稿記録 [ja]

《多変量解析》

2007-07-08T17:37:43Z

219.161.35.37:

'''【たへんりょうかいせき (multivariate analysis) 】'''

　解析の対象 (会社, 地域, 人など) に対して, 複数の変数 (特性) についての値が得られているときに, それらを用いて, 総合的に解析するのを多変量解析という. 変数の型および変数の扱い方により, 種々の解析方法がある.

　変数の型は, 同異だけがわかる名義尺度変数 (質的変数) と差に意味がある間隔尺度変数 (量的変数) に分かれる. 会社名, 地名, 人名などは, 名義尺度変数である. 名義尺度変数は, 分類にしか使えないが, 複数の間隔尺度変数は, 重み(係数)を乗じて, 加えた関数を考えることができる.

　変数の扱い方には, すべての変数を同じに扱う場合と二つに分ける場合がある. 後者では, 第1のグループの変数の関数と第2のグループの変数の対応を求める. 第1のグループの変数を説明変数, 第2のグループの変数を目的変数という. 目的変数は, 1個であることが多い.

[解析方法の種類]

　1. すべての変数を同じに扱う場合

　すべての変数が名義尺度変数である場合は, 対象を多重に分類した分割表を解析する方法があるが, 通常は, 多変量解析の対象にしていないので, ここでは, すべての変数が間隔尺度変数であるとする.

　(1) 総合特性値を求める方法

　元の変数との関係をできるだけ失わないようにして, より少数の総合特性値をいくつか求める方法として, [[主成分分析]]や[[因子分析]]がある. 主成分分析では, 主成分といわれる元の変数の線形式を順次一つずつ求めていく. したがって, 第$<math>k\, </math>$(≧2)主成分には, すでに定まっている第1から第$<math>(k-1)\, </math>$主成分までに追加するのに最適なものが選ばれる. しかし, とりあげる総合特性値の数$<math>k\, </math>$が予め定まっている場合は, 第1主成分から第$<math>k\, </math>$主成分の1次変換であれば, どれでもよいので, 意味を考えて, よりよい$<math>k\, </math>$個の因子と呼ばれる総合特性値を求めるのが因子分析である.

　(2) 対象を分類する方法

　対象をいくつかのグループに分類する方法として, クラスター分析がある.

　2. 説明変数と目的変数に分かれている場合

　説明変数は, すべて間隔尺度変数であるとする. 目的変数との関係がある説明変数の関数を求める方法がいくつか考えられている.

　(1) 目的変数が名義尺度変数である場合

　目的変数によって対象をグループ分けしたとき, 同じグループ内では近い値をとり, 異なるグループでは離れた値をとる説明変数の関数が求められれば, 説明変数で目的変数を判別することができる. 目的変数を判別するために用いる説明変数の関数を判別関数という.

　(2) 目的変数が間隔尺度変数である場合

　その値が目的変数の値とできるだけ近くなるような説明変数の関数を求める方法として, 回帰分析がある.

[変数の型の変換]

　ある特徴の有無, 質問の肯定・否定による回答などのように, 二つに分けられる名義尺度変数は, 0か1の値をとる0-1変数におきかえることで, 間隔尺度変数のように扱うことができる. 一般に, $<math>k\, </math>$個に分ける名義尺度変数は, $<math>k\, </math>$個の0-1変数に置き換えることができる.

　0-1変数だけの多変量解析として, 各種の数量化法が提案されている.

　順序だけ意味がある順序尺度変数は, 点数化によって, 間隔尺度変数にできる. たとえば, 品物に松, 竹, 梅のランクが付けられている場合, それぞれに, 3, 2, 1や5, 2, 1の数値を対応させれば, 間隔尺度変数として扱うことができる. なお, 順序尺度変数は, [[順位相関係数]]を用いて, 解析することもできる.

　比が意味を持つ比尺度変数は, その対数をとることによって, 間隔尺度変数になる.

[単位に関する注意]

　複数の変数を扱うとき, 単位に注意する必要がある. 単位がすべて同じであれば, ほとんど問題がないが, $<math>x_1\, </math>$ の単位はm, $<math>x_2\, </math>$ はcm, $<math>x_3\, </math>$ はgのように, 異なるときは, 重み (係数) $<math>a_1, a_2, a_3\, </math>$ の単位を変えることによって, 重み付きの和

$a_{1}x_1+a_{2}x_2+a_{3}x_3$

が意味を持つ. このときに, 重みの2乗和

$a_1^2+a_2^2+a_3^2$

を1にするといった誤りをしないように, 注意されたい.

　多変量解析では, 単位を揃えることとばらつきを揃えることを兼ねて, 初めにその変数の標準偏差で割る変数変換がよく行われる.

----
'''参考文献'''

[1] 奥野忠一, 久米均, 芳賀敏郎, 吉澤正, 『多変量解析法(改訂版)』, 日科技連出版, 1981.

[2] M. G. Kendall 著, 奥野忠一, 大橋靖雄訳, 『多変量解析』, 培風館, 1981.

《数量化法》

2007-07-08T17:34:59Z

219.161.35.37:

'''【すうりょうかほう (quantification method) 】'''

　数量化法は, 林知己夫氏が提唱した記述的多次元データ解析の方法である. 現象を解明するには, データの取得計画, 具体的なデータ取得法, 現象に合わせた適切なデータ解析法の三者が均衡を保つことが重要であるという思想的枠組の中から数量化法が誕生した. いくつかの方法が提案されているが, 各方法の誕生の経緯に共通することは, いずれも具体的な現象解明のための応用実務の探索的データ解析を目指していることである.

　扱うデータの中に, ‘はい’か‘いいえ’で答えたり, いくつかの選択肢の中から選んだりするアンケートの回答のような質的変数のデータを含んでいるのが特徴である. 変数の型, 扱い方と目的によって, 数量化I類からVI類までに分かれている. はじめに, I類からIV類までが提唱されて, あとで, V類とVI類が追加された. 変数がすべて同じに扱われる場合と一つの変数だけ区別して, それを他の変数で説明する場合がある. 後者の場合, 説明に用いる変数を説明変数, それらで説明される変数を目的変数という. 目的変数を外的基準ということもあり, 外的基準がある場合/ない場合という表現を使う.

［質的変数に対応するダミー変数］

　質的変数は, アイテム, 項目と呼ばれることがあり, それがとる状態はカテゴリーと呼ばれる. アンケートの回答結果がデータである場合, 質問における対象がアイテムに当たり, 回答における選択肢がカテゴリーに当たる. たとえば, ‘この車のデザインは好きですか’という質問を‘好き’か‘嫌い’で答える場合, ‘この車のデザイン’がアイテムであり, ‘好き’と‘嫌い’がカテゴリーである.

　この質問のようにカテゴリー数が2であって, 二者択一である場合は, 0か1の値をとるダミー変数を対応させる. カテゴリー数が3以上であるか, 2であっても両方選ぶことができる場合は, カテゴリー数だけダミー変数を用意し, そのカテゴリーを選んだことを1で, 選ばなかったことを0で表す. このとき, ダミー変数の一次式における係数を定めることは, 各カテゴリーに数量を割り当てることを意味する.

［数量化I類］

　外的基準がある場合で, 説明変数がすべて質的変数であり, 目的変数が量的変数である予測型手法である. 量的データの解析における重回帰分析に対応する.

［数量化II類］

　外的基準がある場合で, 説明変数がすべて質的変数であるが, I類と異なり, 目的変数も質的変数である判別分析型手法である. 量的データの解析における判別関数を求めることに対応する.

［数量化III類］

　外的基準がない場合で, 二つのアイテムについて, カテゴリー別にそれを選んだ度数を集計して作られる2元分割表, クロス表が与えられている. このとき, 相関係数が最大になるように, 二つのアイテムの各カテゴリーに数値を割り当てて, それらの関係を解明する.

　数量化III類と同じように, 質的データの数量化を行う同等または類似の手法として, 対応分析[5] , 双対尺度法 [6] などがある.

［数量化IV類, V類, VI類］

　数量化IV類は, 分析の対象がいくつか考えられているときに, 2対象間の類似性または親近性の程度を表す数値から, 低次元空間における対象の位置を定める方法である. 多次元尺度構成法の一つと見ることもできる. その発展型として, V類, VI類がある.

----
'''参考文献'''

[1] 林知己夫, 『数量化--理論と方法』, 朝倉書店, 1993.

[2] 林知己夫, 鈴木達三, 『社会調査と数量化(増補版)』, 岩波書店, 1997.

[3] 駒澤勉, 『数量化理論とデータ処理』, 朝倉書店, 1982.

[4] 大隅昇, L. ルバール他, 『記述的多変量解析法』, 日科技連出版社, 1994.

[5] J. P. Benzecri, ''Correspondence Analysis Handbook'', Marcel Dekker, 1992.

[6] S. Nishisato, ''Analysis of Categorical Data : Dual Scaling and Its Applications'', University of Toronto Press, 1980.

《多次元尺度構成法》

2007-07-08T17:34:03Z

219.161.35.37:

'''【たじげんしゃくどこうせいほう (multidimensional scaling) 】'''

　マーケティングにおける製品のように, 分析の対象がいくつか考えられているときに, 2対象間の距離または類似度などから, 多次元の空間における対象の配置を決定する方法を多次元尺度構成法MDSといい, 対象の配置を布置configurationという.

　対象の数を $<math>n\, </math>$, 対象 $<math>i\, </math>$ と対象 $<math>j\ (i,j=1,2,\ldots ,n)\, </math>$ の間の実測距離を $<math>\delta_{ij}\, </math>$ とする. 類似度が得られているときは, 類似度が大きいほど距離が小さくなるように, 類似度から距離を定める. 次元の数を $<math>p\, </math>$ とすると, 求めるものは, 対象 $<math>i\ (i=1,2,\ldots ,n)\, </math>$ の座標 $<math>\mbox{\boldmath$x$}_i=(x_{i1}, x_{i2},\ldots ,x_{ip})$\, </math> である. 対象の布置は, 視覚的にわかりやすく表示する必要があるので, $<math>p\, </math>$ には, 2, 3のような小さい値を選ぶ.

　各点の座標が定まると, $<math>\mbox{\boldmath $x$}_i\, </math>$ と $<math>\mbox{\boldmath $x$}_j\, </math>$ から, たとえば, ユークリッド距離により, 対象 $<math>i\, </math>$ と対象 $<math>j\, </math>$ の間の距離 $<math>d_{ij}\, </math>$ を計算することができる. このとき, $<math>(d_{ij})\, </math>$ は, $<math>(\delta_{ij})\, </math>$ に全体的に適合
している方がよい. そこで, $<math>(d_{ij})\, </math>$ が $<math>(\delta_{ij})\, </math>$ に適合している程度を表す適合度を定めて, それを最小にする $<math>(\mbox{\boldmath $x$}_i)\, </math>$ を求める.

　適合度の定義は, いくつか考えられているが, $<math>d_{ij}\, </math>$ と $<math>\delta_{ij}\, </math>$ の差を用いて表すものや, その差が意味を持たない場合に, $<math>(\delta_{ij})\, </math>$ と大きさに関してほぼ同じ順序を持っている距離 $<math>(d^*_{ij})\, </math>$ を求め, $<math>(d_{ij})\, </math>$ と $<math>(d^*_{ij})\, </math>$ の差を用いるものもある [3]. 適合度を最小にする $<math>(\mbox{\boldmath $x$}_i)\, </math>$ を求めるのは, 非線形計画問題になる. $<math>\delta_{ij}\, </math>$ が順位で与えられているときに, 相関係数の形に似た単調性係数を用いるものもある.

　次元の数が定まっていないときは, $<math>p\, </math>$ の値を1から出発して, 1ずつ増やしていく方法もある. $<math>p\, </math>$ が大きくなるほど, 適合度は小さくなるが, 対象の布置はわかりにくくなる. したがって, 適合度の減少分がある限度以下になれば, 終了する.

　2対象間の距離の代わりに, 複数の評定者による2対象間の選好結果が与えられていることもある. 選好結果は, 各評定者毎に, 2対象のどちらをより好むかを示す. このときは, 選考結果の集計から, 2対象の距離を計算して, 対象の布置を求めることができるだけでなく, 評定者の理想点の位置も求められる [4]. 選考判断は, 全対象に対する好みの順序で与えられることもある.

　これらの他にも, 線形計画法で分析する方法 [5] や, 対象毎に, それから近い順に他の対象を並べるときの順位を求めて, それから解析する方法 [5] など, 様々な方法が提案されている.

　また, $<math>\delta_{ij}\, </math>$ を確率変数の実現値とみなす確率モデルを規定して, 最尤法などで $<math>(\mbox{\boldmath $x$}_i)\, </math>$ を推定する方法もある [6] .

----
'''参考文献'''

[1] 斎藤堯幸, 『多次元尺度構成法』, 朝倉書店, 1980.

[2] 高根芳雄, 『多次元尺度法』, 東京大学出版会, 1980.

[3] J. B. Kruskal, "Multidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric Hypothesis," ''Psychometrika'', '''29''' (1964), 1-27.

[4] J. D. Carroll, "Individual Differences and Multidimensional Scaling," in ''Multidimensional Scaling : Theory and Applications in the Behavioral Sciences Vol. 1'', R. N. Shepard, et al. eds., New York : Seminar Press, 105-155, 1972. 岡太彬訓, 渡邊惠子訳, 『多次元尺度構成法I理論編』, 共立出版, 1976.

[5] V. Srinivasan and A. D. Shocker,
"Linear Programming Techniques for Multidimensional Analysis of Preferences," ''Psychometrika'', '''38''' (1973), 337-369.

[6] 片平秀貴, 『新しい消費者分析 LOGMAPの理論と応用』, 東京大学出版会, 1991.

《判別関数》

2007-07-08T17:30:31Z

219.161.35.37:

'''【はんべつかんすう (discriminant function) 】'''

　いくつかの変数(特性)についての測定値が得られている対象に対して, それが属している可能性があるグループが複数考えられるときに, それらの変数の関数を用いて対象の属するグループを判別することにする. このときに用いる関数を判別関数という.

　いくつかの特性の値からグループを判別するから,特性が説明変数であり, グループが(質的)目的変数である.説明変数を$<math>x_i(i=1,\ 2,\ \cdots,\ p)\, </math>$, 目的変数を$<math>y\, </math>$で表す.また, $<math>y\, </math>$のとりうる値(グループ名)を$<math>G_h(h=1,\ 2,\ \cdots,\ r)\, </math>$とする.すなわち, $<math>r\, </math>$ 個のグループが考えられているとする. グループの判別には, <math>{\boldmath $x$}($x_i(i=1,\ 2,\ \cdots,\ p)\, </math>$を並べたベクトル)と$<math>G_h(h=1,\ 2,\ \cdots,\ r)\, </math>$の中心(平均)の間の距離$<math>D_h$({\boldmath $x$})\, </math>を用いる. $<math>G_h\, </math>$における平均ベクトル <math>($x_i(i=1,\ 2,\ \cdots,\ p)\, </math>$ の平均を並べたベクトル) を$<math>\mbox{\boldmath $m$}_h\, </math>$, 分散共分散行列の逆行列を <math>$C_h\, </math>$ とする. このとき, $<math>D_h$({\boldmath $x$})\, </math> は, 次式で計算される.

　D_h(\mbox{\boldmath $x$})=
(\mbox{\boldmath $x$}-\mbox{\boldmath $m$}_h)^{\top}
C_h(\mbox{\boldmath $x$}-\mbox{\boldmath $m$}_h)

グループが正規母集団とみなされ, 分散共分散行列がすべて等しいとき, 上の式で <math>{\boldmath $x$}\,=\,$\mbox{\boldmath $m$}_k\, </math>$とおいて得られる距離を, $<math>G_k\, </math>$と$<math>G_h\, </math>$の間のマハラノビス汎距離という. 平均や分散共分散行列は, 各グループに属していることがわかっている対象についての測定値より計算される. $<math>D_h(\mbox{\boldmath $x$}) (h=1,\ 2,\ \cdots,\ r)\, </math>$ の中で,$<math>D_k(\mbox{\boldmath $x$})\, </math>$ が最小であれば, この対象は,$<math>G_k\, </math>$に属していると判別すればよい. また, どれにも属さないという判別が許される場合は, あらかじめ上限を設定しておいて, $<math>D_k(\mbox{\boldmath $x$})\, </math>$ がそれを越えたときは, どれにも属さないと判別すればよい.

　$<math>r=2\, </math>$ のときは, $<math>{\mit\Delta}D_{12}(\mbox{\boldmath $x$})=D_1(\mbox{\boldmath $x$})-D_2(\mbox{\boldmath $x$})\, </math>$ を計算して, $<math>{\mit\Delta}D_{12}(\mbox{\boldmath $x$})>0\, </math>$であれば $<math>G_2\, </math>$に属し, $<math>{\mit\Delta}D_{12}(\mbox{\boldmath $x$})<0\, </math>$であれば $<math>G_1\, </math>$に属すると判別すればよい. 分散共分散行列が等しいとき, すなわち, $<math>C_1=C_2=C\, </math>$であるとき,

$${\mit\Delta}D_{12}(\mbox{\boldmath $x$})
=2(\mbox{\boldmath $m$}_2-\mbox{\boldmath $m$}_1)^{\top}
C\mbox{\boldmath $x$}-(\mbox{\boldmath $m$}_2-\mbox{\boldmath $m$}_1)^{\top}
C(\mbox{\boldmath $m$}_1+\mbox{\boldmath $m$}_2)$$

と変形できるので, $<math>{\mit\Delta}D_{12}(\mbox{\boldmath $x$})\, </math>$は, $<math>x_i(i=1,\ 2,\ \cdots,\ p)\, </math>$の線形式になる. したがって, これを($<math>G_1\, </math>$と$<math>G_2\, </math>$を判別する)線形判別関数という. $<math>r\, </math>$が3以上のときは, 線形判別関数は, $<math>{}_r{\rm C}_2\, </math>$ 個できる. なお, 分散共分散行列が等しくないときは, $<math>{\mit\Delta}D_{12}(\mbox{\boldmath $x$})\, </math>$ は, $<math>x_i(i=1,\ 2,\ \cdots,\ p)\, </math>$ の2次式になる.

----
'''参考文献'''

[1] 奥野忠一, 久米均, 芳賀敏郎, 吉澤正, 『多変量解析法(改訂版)』, 日科技連出版, 1981.

《クラスター分析》

2007-07-08T17:25:24Z

219.161.35.37:

'''【クラスターぶんせき (cluster analysis) 】'''

　現象解析の基本操作の一つである分類を行う方法に関わる探索的方法論の総称がクラスター分析である. 博物学, 考古学, 生物分類学, 計量心理学など適用分野がきわめて多岐にわたることが特徴である. 欧州圏では, 自動分類法(automatic classification)と呼称することが多い. 分類操作とは, 解析の対象すべてをいくつかの群に分けて, 何らかの基準に従って似ているものが同じ群に入っているようにすることである. 群をクラスターという.

　すべての対象の集合を$<math>\Omega\, </math>$とする. これの部分集合の集合$<math>\Gamma=\{C_1,\ C_2,\ \ldots,\ C_p\}\, </math>$が, 次の条件を満たすとき,$<math>\Omega\, </math>$の分割という.

(1) $C_1\cup C_2\cup\ldots\cup C_p=\Omega$

(2) $C_i\cap C_j=\phi\ (i\neq j)$

このとき, $<math>C_k(k=1,\ 2,\ \ldots,\ p)\, </math>$がクラスターであり,クラスター分析の目的は, 与えられた基準に従って, 最適な分割を求めることである.

[分類結果の評価]

　分類の目的によって, 分類結果, すなわち, 得られた分割$<math>\Gamma\, </math>$に対する評価基準が定まる. これは, 目的関数で示される. たとえば, 同じクラスターに属する対象は, お互いに類似しているほうがよいのであれば, 同じクラスターに属する2対象間の類似度の最小値を目的関数にして, それをできるだけ大きくすればよいし, 異なるクラスターに属する対象は, できるだけ類似していないほうがよければ, 異なるクラスターに属する2対象間の類似度の最大値を目的関数にして, それをできるだけ小さくすればよい.

[分類手法]

　分類方法は, いろいろ提案されているが, 大きく, 階層的分類法 (hierarchical classification) と非階層的分類法に分けられ, 階層的分類法は, さらに, 凝集型 (agglomerative type) と分枝型 (divisible type) に分けられる.

1. 非階層的分類法

　予め定めたクラスター数$<math>p\, </math>$に対して, 最適な分割を求める方法. 最適な分割を求めるのは, 組み合わせ最適化問題の一種であるから, 0-1変数の整数計画問題に定式化すれば, そのアルゴリズムが利用できる.

2. 階層的分類法

　クラスター数$<math>p\, </math>$が予め定められない場合や分類が段階的にクラスターの併合または細分によって変化することが考えられる場合には, 階層的分類が望まれる.

　(1) 凝集型階層的分類法

　対象が一つずつ分かれている状態から出発して, 最も近い二つのクラスターを併合することを繰り返して, クラスター数$<math>p\, </math>$を1ずつ減少させていく方法である. 予め, 二つのクラスター$<math>A,\ B\, </math>$間の距離$<math>\delta(A,\ B)\, </math>$を定めておく必要がある. 手順の概要は, 次のとおりである. ここで, 対象の数を$<math>n\, </math>$とし, $<math>p\, </math>$の最終値を$<math>p_{\min}\, </math>$とする.

　手順1. $<math>p=n,\ \Gamma=\{\{1\}, \{2\}, \ldots, \{n\}\}\, </math>$ とし, すべての$<math>i, \ j\, </math>$ に対して, $<math>\delta(\{i\},\ \{j\})\, </math>$ を計算する.

　手順2. $<math>\Gamma\, </math>$に含まれるクラスターの対の中で, 距離が最小であるものを求めて, それらを結合し, $<math>p\, </math>$ の値を1だけ小さくする. $<math>p=p_{\min}\, </math>$ であれば, 終了する.

　手順3. 結合してできたクラスターと他のクラスターの間の距離を計算して手順2にもどる.

　クラスター間の距離の定義は, いろいろ考えられているが, 対象$<math>i\, </math>$と対象$<math>j\, </math>$の間の距離$<math>d_{ij}\, </math>$を予め定めておいて, それを用いて表すことが多い. 対象間距離は, 対象のいくつかの特性の測定値から計算される. 特性の単位がすべて揃っているときは, ユークリッド距離が使えるが, 一般には, 重み付きユークリッド距離を用いる. 類似度やアンケートの回答の一致の程度から, 距離を定めることもある. このときは, 類似度などが大きくなるほど, 距離が小さくなるようにする.

　対象間距離を用いるクラスター間の距離の定義の代表的なものを挙げる.

\delta(A,\ B)=\min\{d_{ij}|i\in A,\ j\in B\}
\delta(A,\ B)=\max\{d_{ij}|i\in A,\ j\in B\}
\delta(A,\ B)=\sum_{i\in A, j\in B} d_{ij}/({\rm car}(A)\times {\rm car}(B))

ここで, $<math>{\rm car}(S)\, </math>$は, 集合$<math>S\, </math>$の要素数を表す. 上から順に, 最短距離, 最長距離, 群間平均距離という. 手順1で, $<math>\delta(\{i\}, \{j\})\, </math>$を計算しなければいけないが, 対象間距離を用いるときは, $<math>\delta(\{i\}, \{j\})= d_{ij}\, </math>$となる.

　凝集型方法では, クラスター間の距離の定義によって, 分類結果が異なる可能性がある. そこで, クラスター間の距離の定義に対応して, 方法に名称が付けられている. 最短距離, 最長距離, 群間平均距離を用いるときは, それぞれ最短距離法, 最長距離法, 群間平均距離法という. 最短距離法の別名としては, 最近隣法, 単連結法などがあり, 最長距離法の別名には, 最遠隣法, 完全連結法などがある. なお, 最短距離法は, 最小木問題のクラスカル法に当たる. 多くのクラスター間の距離を統一的に表わす距離が定義されていて, それを用いる凝集型方法を組み合わせ的方法(combinatorial method)と呼んでいる [6].

　凝集型方法は, ある一つの$<math>p\, </math>$の値に対する分割を求める場合でも, 非常に少ない計算量でよい解を求めるアルゴリズムである. 一般的には, 与えられた目的関数に対して, いつも良い分割を与えるクラスター間の距離の定義は存在しないから, 定義を変えていろいろな分割を求めて, それらの中から最も良いものを選べばよいが, 異なるクラスターに属する2対象間の距離の最小値, すなわち, 最短距離を最大にする場合は, 最短距離法で常に最適解が得られる. 結合していく過程と結合する二つのクラスター間の距離は, 樹形図 (dendrogram) で示される.

　(2) 分枝型階層的分類法

　凝集型とは逆に, 全対象を一つのクラスターにした状態から出発して, クラスターの分割を繰り返すことにより, トップダウンに階層分類を行う. 逐次二分割方式が多いが, 三つ以上に分割できる方式もある. 時間経過とともに進化して分岐してきたものの分類には適しているが, 凝集型に比べると, はるかに計算量が増える.

----
'''参考文献'''

[1] 奥野忠一, 久米均, 芳賀敏郎, 吉澤正, 『多変量解析法(改訂版)』, 日科技連出版, 1981.

[2] 大隅昇, L. ルバール他, 『記述的多変量解析法』, 日科技連出版社, 1994.

[3] M. R. Anderberg, ''Cluster Analysis for Applications'', Academic Press, 1973.

[4] T. S. Arthanari and Y. Dodge, ''Mathematical Programming in Statistics'', John-Wiley and Sons, 1981.

[5] B. Everitt, ''Cluster Analysis'', 3rd edn., Edward Arnold, 1993.

[6] G. N. Lance and W. T. Williams, "A General Theory of Classificatory Sorting Strategies 1 - Hierarchical System," ''Computer Journal'', '''9''' (1967), 373-380.

《回帰分析》

2007-07-08T17:21:07Z

219.161.35.37:

'''【かいきぶんせき (regression analysis) 】'''

　分析の対象に対して, 複数の間隔尺度変数についての値(長さ, 時間などのいわゆる計量値)が得られているとする. 変数は, 一つの目的変数といくつかの説明変数に分かれていて, 目的変数とできるだけ近い値をとる説明変数の関数を求めるのを回帰分析という. 説明変数が一つである場合を単回帰分析, 二つ以上である場合を重回帰分析という.

[回帰式]

　説明変数の関数を回帰式という. 説明変数を$<math>x_i$($i$=1, 2, $\cdots$, $m$)\, </math>,目的変数を$<math>y\, </math>$とする. 回帰式には, 通常, 次のような線形式が用いられる.

　y=b_0+b_1x_1+b_2x_2+\cdots+b_mx_m

$<math>b_i$($i$=0, 1, 2, $\cdots$, $m$)\, </math>を回帰係数といい, これを求めるのが目的である. なお, ここでの線形式は, 値を求める係数$<math>b_i\, </math>$に関して線形であることを示している. したがって, 説明変数の間には, たとえば, $<math>x_2=x_1^2\, </math>$のように, 線形以外の関係があってもよい. 非線形回帰式 [4] が用いられることもあるが, ここでは, 線形回帰式に限ることにする.

[残差]

　分析の対象の数を$<math>n\, </math>$とし, $<math>k\, </math>$番目 (<math>$k$=1, 2, $\cdots$, $n$\, </math>) の対象の$<math>x_i\, </math>$, $<math>y\, </math>$の値, いわゆるデータを$<math>x_{ik}\, </math>$, $<math>y_k\, </math>$とする. 変数$<math>x_i\, </math>$に$<math>k\, </math>$番目の対象の値$<math>x_{ik}\, </math>$を代入したときの回帰式の値を$<math>\eta_k\, </math>$, すなわち,

　\eta_k=b_0+b_1x_{1k}+b_2x_{2k}+\cdots+b_mx_{mk}

とすると,

　e_k=y_k-\eta_k

を残差または回帰からの偏差という.

[最適な回帰式]

　回帰式の評価は, 残差の関数を用いて行われる. 代表的な評価関数を以下に挙げる.
　
(1) 残差平方和(偏差平方和)

　　\mbox{SSD}=\sum_{k=1}^{n}\eta_k^2

(2) 絶対偏差の和

　　\mbox{SAD}=\sum_{k=1}^{n}|\eta_k|

(3) 絶対偏差の最大値

　　\mbox{MAD}=\max\{|\eta_1|, |\eta_2|, \cdots, |\eta_n|\}

いずれの評価関数も, 小さい方がよいので, 最小にする回帰式を最適とする.

[最適な回帰式の求め方]

　SSDを最小にする回帰式(回帰係数)を求めるのを最小二乗法という.
SSDは, $<math>b_i$($i$=0, 1, 2, $\cdots$, $m$)\, </math>に関する
凸二次関数であるから, これらで偏微分した式を0とおいて得られる連立一次方程式を解けばよい.
この連立一次方程式を正規方程式という.

　線形式の絶対値の和を最小にすることも, 線形式の絶対値の最大値を最小にする
ことも, 線形計画問題に変形できることにより, SADを最小にする回帰式も, MAD
を最小にする回帰式も, 線形計画問題を解くことによって得られる [2]. とくに, 一対比較の結果によるデータである場合は, ネットワーク計画問題に変形できる[3].

[推測統計における回帰分析]

　回帰分析は, 狭い意味では, 推測統計における解析法である. 説明変数$<math>y\, </math>$が確率変数$<math>Y\, </math>$の実現値であって, $<math>Y\, </math>$の期待値$<math>E[Y]\, </math>$が次のように説明変数の関数で表されるとする.

　E[Y]=\beta_0+\beta_1 x_1+\beta_2 x_2+\cdots+\beta_m x_m

このとき, 回帰係数を求めることは, 未知定数$<math>\beta_i$($i$=0, 1, 2,$\cdots$, $m$)\, </math>を推定することに当たる. $<math>y_k\, </math>$に対応する確率変数を$<math>Y_k\, </math>$とする, すなわち, $<math>y_k\, </math>$が確率変数$<math>Y_k\, </math>$の実現値と考えられるとき, $<math>Y_k\, </math>$の分布について, 分散が一定などの前提条件をおくと, 最小二乗法は, 望ましい推定法であることが証明されている [1].

----
'''参考文献'''

[1] C. R. Rao, ''Linear Statistical Inference and Its Applications'', John Wiley & Sons, 1973.

[2] T. S. Arthanari and Y. Dodge, ''Mathematical Programming in Statistics'', John Wiley & Sons, 1981.

[3] 古林隆, 佐藤俊之, 鈴木政志, 「一対比較データのネットワーク計画法的解析」, 『日本オペレーションズ・リサーチ学会1991年度春季研究発表会アブストラクト集』, 112-113, 1991.

[4] N. R. Draper and H. Smith, ''Applied Regression Analysis'', John Wiley & Sons, 1966. 　

《マルコフ連鎖の数値解法》

2007-07-08T17:17:04Z

219.161.35.37:

【まるこふれんさとまちぎょうれつのすうちかいほう (numerical methods for Markov chain and queue) 】

'''マルコフ連鎖の数値解法'''　[[マルコフ連鎖]]をマルコフ連鎖の[[数値的]]に解析する際の中心的な対象は[[定常分布]]である. [[有限状態空間]] $<math>{\mathcal S}=\{ 1, 2, \ldots, N \}\, </math>$ 上の[[既約]]で非周期的な (つまり[[エルゴード的]]) マルコフ連鎖を考え, その[[推移確率行列]]を$<math>\mbox{\boldmath$P$}=(p_{ij})\, </math>$, 定常分布を $<math>\mbox{\boldmath$\pi$}=(\pi_1, \pi_2,\ldots,\pi_N)\, </math>$ とする. [[一様化]]により, 連続時間マルコフ連鎖の定常分布は, 離散時間マルコフ連鎖の定常分布として計算できるので, 以下では離散時間マルコフ連鎖に限定して考える.

　エルゴード的なマルコフ連鎖では, 定常分布は

\begin{eqnarray}
\mbox{(平衡方程式)} \qquad & &
\pi_j = \sum_{i=1}^N \pi_i p_{ij}, \quad j=1, 2, \ldots,N,
\label{B-D-07-eq1} \\
\mbox{(正規化条件)} \qquad & &
\sum_{j=1}^N \pi_j = 1
\label{B-D-07-eq2}
\end{eqnarray}

を満たす一意の解として与えられる (式(1)) の解は定数倍に関して一意でないため, 式 (2) で正規化する). したがって, 定常分布の計算は, 原理的には線形方程式系を数値的に解く問題に帰着される. 状態数 $<math>N\, </math>$ が大きくなければ, 消去法や[[状態縮約法]]などの直接法 (反復計算を伴わない方法) でも解を求めることは可能だが, 一般にマルコフ連鎖によるモデル化はモデルが複雑になるに従って状態数が急激に増加する傾向があるため, そのような場合は計算精度などを考慮して反復法を用いることが多い.

'''ガウス・ザイデル法'''　反復法では, 反復回数 $<math>k \to \infty\, </math>$ のときに定常分布 $<math>\mbox{\boldmath$\pi$}\, </math>$ に収束するような近似値の列 $<math>\mbox{\boldmath$\pi$}^{(k)} = (\pi_1^{(k)}, \pi_2^{(k)}, \ldots,\pi_N^{(k)})\, </math>$ を構成する. 例えば, ヤコビ法 (Jacobi method) では, 適当な初期分布 $<math>\mbox{\boldmath$\pi$}^{(0)}\, </math>$ からスタートして

\pi_j^{(k)} = \sum_{i=1}^N \pi_i^{(k-1)} p_{ij}, \quad
j=1, 2, \ldots,N

によって分布列 $<math>\mbox{\boldmath$\pi$}^{(k)}\, </math>$ を構成し, $<math>\mbox{\boldmath$\pi$}^{(k-1)}\, </math>$ と $<math>\mbox{\boldmath$\pi$}^{(k)}\, </math>$ が十分近くなった時点で収束したと判断する. エルゴード的なマルコフ連鎖に対しては, ヤコビ法は計算誤差を除けば必ず収束するが, 一般に大きな $<math>N\, </math>$ に対してはあまり収束は速くない. これに対して, [[ガウス・ザイデル法]] (Gauss-Seidel method) では

\pi_j^{(k)} = \frac{ \sum_{i=1}^{j-1} \pi_i^{(k)} p_{ij}
+ \sum_{i=j+1}^{N} \pi_i^{(k-1)} p_{ij} }{1-p_{jj}},
\quad j=1, 2, \ldots,N

によって分布列を構成する. この方法では, $<math>k\, </math>$ 回目の反復で既に更新されている値を逐次利用するため, ヤコビ反復法に比べると一般に収束が速くなることが多い. また, 推移確率行列がブロック構造を持つ場合には, ブロックごとに更新された値を利用する[[ブロックガウス・ザイデル法]] (block Gauss-Seidel method) も有効である. さらに収束を加速する手段として[[過剰緩和法]] (overrelaxation method) の利用がある. 過剰緩和法では, 緩和 (または加速) 係数を $<math>\omega\, </math>$ として

\pi_j^{(k)} = \frac{ \omega \sum_{i=1}^{j-1} \pi_i^{(k)} p_{ij}
+ (1-\omega) \pi_j^{(k-1)} p_{jj}
+ \omega \sum_{i=j+1}^{N} \pi_i^{(k-1)} p_{ij} }{1-p_{jj}},
\quad j=1, 2, \ldots,N

によって $<math>\mbox{\boldmath$\pi$}^{(k)}\, </math>$ を計算する. $<math>\omega>1\, </math>$ のときには, 外挿により $<math>\mbox{\boldmath$\pi$}^{(k-1)}\, </math>$ から $<math>\mbox{\boldmath$\pi$}^{(k)}\, </math>$ を計算しており, 適切な $<math>\omega\, </math>$ を選ぶことで収束を加速することが可能となる. なお, ガウス・ザイデル系の方法では, 初期分布 $<math>\mbox{\boldmath$\pi$}^{(0)}\, </math>$ が (2) を満たしていても, 途中の計算でこの制約が満たされなくなるため, 計算の最後に (2) が満たされるよう正規化することが必要である.

'''状態縮約/非縮約法'''　一方, 複数の状態をまとめて1つの状態と見なした状態数の少ない確率過程に対して反復計算を行う方法に[[状態縮約/非縮約法]] (aggre\-ga\-tion/dis\-aggre\-ga\-tion method: AD法) がある. 例えば, 状態空間を $<math>L\, </math>$ 個の部分空間 $<math>{\mathcal S}_1, \ldots, {\mathcal S}_L\, </math>$ に分割し, $<math>{\mathcal S}_{\alpha}\, </math>$ には $<math>d_\alpha\, </math>$ 個の状態 $<math>(\alpha,1), \ldots, (\alpha,d_\alpha)\, </math>$ が含まれる場合を考え, 推移確率を $<math>\mbox{\boldmath$P$}=( p_{(\alpha,i)(\beta,j)} )\, </math>$, 状態 $<math>(\alpha,i)\, </math>$ の定常確率を $<math>\pi_{\alpha,i}\, </math>$, 部分空間 $<math>{\mathcal S}_\alpha\, </math>$ の定常確率を$<math>\tau_\alpha=\sum_{i=1}^{d_\alpha} \pi_{\alpha,i}\, </math>$ とする. いま, $<math>k-1\, </math>$ 回の反復で近似値 $<math>\pi_{\alpha,i}^{(k-1)}\, </math>$, $<math>\tau_\alpha^{(k-1)}\, </math>$ が求められているとしよう. $<math>k\, </math>$ 回目の反復計算のうち, まず縮約フェーズでは, 部分空間 $<math>{\mathcal S}_\alpha,\; \alpha = 1,\ldots,L\, </math>$ をそれぞれ1つの状態 $<math>s_\alpha\, </math>$ に縮約した $<math>L\, </math>$ 状態の確率過程を考え, それをマルコフ連鎖と見なして (特殊なケースを除いて縮約した確率過程はマルコフ連鎖とならない) 推移確率, 例えば $<math>s_\alpha\, </math>$ から $<math>s_\beta\, </math>$ への推移確率を$<math>q_{\alpha,\beta}^{(k)}=\sum_{i=1}^{d_\alpha} \sum_{j=1}^{d_\beta}\pi_{\alpha,i}^{(k-1)} p_{(\alpha,i)(\beta,j)} / \tau_\alpha^{(k-1)}\, </math>$ によって定める. このマルコフ連鎖 $<math>\mbox{\boldmath$Q$}^{(k)}=(q_{\alpha,\beta}^{(k)})\, </math>$ の平衡方程式を解いて, 更新された定常確率 $<math>\tau_\alpha^{(k)},\; \alpha=1,\ldots,L\, </math>$ を求める. 次に非縮約フェーズでは, 1つの着目した部分空間はそのままで他のすべての部分空間を1つの状態に縮約した確率過程を近似的にマルコフ連鎖と考える. 例えば, 部分空間 $<math>{\mathcal S}_\alpha\, </math>$ に注目した場合には, $<math>{\mathcal S}_\alpha\, </math>$ 内の推移確率は元のままで, $<math>{\mathcal S}_\alpha\, </math>$ 内の状態 $<math>(\alpha,i)\, </math>$ から縮約された状態への推移確率は $<math>\sum_{\beta \ne \alpha}\sum_{j=1}^{d_\beta} p_{(\alpha,i)(\beta,j)}\, </math>$, 逆に縮約された状態から $<math>(\alpha,i)\, </math>$ への推移確率は $<math>\sum_{\beta \ne \alpha} \sum_{j=1}^{d_\beta}\pi_{\beta,j}^{(k-1)} p_{(\beta,j)(\alpha,i)}/(1-\tau_{\alpha}^{(k)})\, </math>$ で与えられるマルコフ連鎖を考え, その定常分布を計算し $<math>\pi_{\alpha,i}^{(k)}, \; i=1,\cdots,d_\alpha\, </math>$ を得る. この計算を, 注目する部分空間を $<math>{\mathcal S}_1\, </math>$ から $<math>{\mathcal S}_L\, </math>$ まで変えながら行えば, 更新された定常確率を求めることができる. この縮約/非縮約の手続きを, 値が収束するまで反復すればよい.

'''無限状態と過渡的分布'''　状態数が無限のマルコフ連鎖に対しては, 状態空間を適当な有限サイズで打ち切って数値計算を行うが, 打ち切るサイズによって計算時間と計算精度の間にトレードオフが生じるので注意が必要である. 構造が入っている場合 (後述) は, 上の方法を用いるにしてもその構造をうまく利用することによって, 少ない計算量で精度良い解が計算できることが多い.

　定常分布に比べると, 過渡的分布 (各時点における推移確率) の計算方法はそれほど多くないが, 離散時間マルコフ連鎖に対してはべき乗法, 連続時間マルコフ連鎖に対してはランダム化を利用する方法などが知られている.

'''構造化されたマルコフ連鎖'''　確率モデル, 特に待ち行列モデルから派生するマルコフ連鎖には, 何らかの構造を持つものが多いため, その構造を利用した数値計算法が開発されている. 代表例として, [[相型待ち行列]]に対する[[行列幾何形式解]]を考えよう. [[到着過程]]や[[サービス過程]]}に[[マルコフ型到着過程]]や[[相型分布]]を導入することで, 広い範囲の待ち行列モデルは準出生死滅過程 (quasi-birth-and-death process) を含むGI/M/1型, あるいはM/G/1型マルコフ過程などの構造化されたマルコフ連鎖で表現することができる. このうち, GI/M/1型マルコフ連鎖は, レベル $<math>n\; (=0,1,\ldots)\, </math>$ と相 $<math>i\;(=1,\ldots,d)\, </math>$ の組 $<math>(n,i)\, </math>$ によって状態が表されるマルコフ連鎖で, 1回の[[推移]]では高々1つ上のレベルまでしか推移せず, またレベル $<math>n\, </math>$ の状態からレベル $<math>m\; (m\le n+1)\, </math>$ の状態への推移確率 (または推移速度) がレベルの差 $<math>m-n\, </math>$ と各状態の相によって決まる性質を持っている. レベル $<math>n\, </math>$ の状態の定常確率ベクトルを $<math>\mbox{\boldmath$\pi$}_n=(\pi_{n,1}, \ldots, \pi_{n,d})\, </math>$ で表すと, 行列幾何形式解より, [[公比行列]] $<math>\mbox{\boldmath$R$}$\, </math> を用いて

\begin{equation}\label{B-D-07-eq6}
\mbox{\boldmath$\pi$}_n = \mbox{\boldmath$\pi$}_{0}
\mbox{\boldmath$R$}^n, \quad n=1,2,\ldots
\end{equation}

と表される. $<math>\mbox{\boldmath$R$}$\, </math> は推移確率行列の要素を係数とする非線形行列方程式の非負最小解として与えられ, 逐次代入法などで計算することができる. また $<math>\mbox{\boldmath$\pi$}_{0}\, </math>$ は境界条件に相当する線形方程式を解いて求められる [2]. この方法は, 本来無限次元の定常分布を有限次元のベクトルと行列で表せるという特徴を持つが, 高速化のためには $<math>\mbox{\boldmath$R$}$\, </math> の計算方法がポイントとなる.

　なお, M/G/1型マルコフ連鎖は行列幾何形式解を持たないが, やはりその構造を利用したさまざまな方法が考えられている [2].

----
'''参考文献'''

[1] D. P. Heyman and M. J. Sobel (eds.), 伊理, 今野, 刀根監訳, 『確率モデルハンドブック』, 朝倉書店, 1995.

[2] M. F. Neuts, ''Matrix Goemtric Solutions in Stochastic Models - An Algorithmic Approach'', Johns Hopkins Univ. Press, 1981.

[3] M. F. Neuts, ''Structured Stochastic Matrices of {rm M/G/1} Type and Their Applications'', Marcel Dekker, 1989.

[4] W. J. Stewart (ed.), ''Numerical Solution of Markov Chains'', Marcel Dekker, 1991.

[5] W. K. Grassmann (ed.), ''Computational Probability'', Kluwer Academic Publishers, 2000.

《マルコフ決定過程》

2007-07-08T17:08:03Z

219.161.35.37:

'''【まるこふけっていかてい (Markov decision process) 】'''

　[[マルコフ決定過程]] (Markov Decision Process: MDP) は, [[待ち行列システム]]の制御, [[在庫管理]]や, [[信頼性]]システムの保全など, 確率システムの動的な最適化問題を定式化する能力に優れた数学モデルであり, 制御マルコフ過程 (controlled Markov process) とも呼ばれる. MDP は 1960 年にハワード (R. A. Howard) による名著 [3] が出版されたことにより, 広く知られるようになり, その後, 理論・応用・アルゴリズムの各面で膨大な数の多様な研究がなされてきている.

'''有限マルコフ決定過程'''　ここでは, 簡単のため, 離散時間の有限 MDP, すなわち状態数およびアクション数が有限のMDP を考える. 有限 MDP$<math>\{ {X}_{t} \}\, </math>$ は以下の要素で構成される:

i)　$<math>S := \{ 1, 2, \cdots ,M \}\, </math>$: 有限状態空間,

ii)　$<math>A(i)$, $i \in S\, </math>$: 状態 $<math>i\, </math>$ でとり得るアクションの有限集合, $<math>A := \bigcup_{i \in S} A(i)\, </math>$: 有限アクション空間,

iii)　<math>$p(j | i,a)\, </math>$, $<math>i \in S\, </math>$; $<math>a \in A(i)\, </math>$: 状態 $<math>i\, </math>$ でアクション $<math>a\, </math>$をとったとき, つぎの時刻で状態 $<math>j\, </math>$ に遷移する確率,

iv)　$<math>c(i,a)\, </math>$, $<math>i \in S\, </math>$; $<math>a \in A(i)\, </math>$: 状態 $<math>i\, </math>$ でアクション $<math>a\, </math>$ をとったときの期待即時コスト.

　各状態でとるべきアクションを規定する規則, すなわち $<math>S\, </math>$ から $<math>A\, </math>$ への写像 $<math>f\, </math>$ で $<math>f(i) \in A(i)\, </math>$, $<math>i \in S\, </math>$ を満たすもの, を政策という. ここでは定常政策, すなわち写像 $<math>f\, </math>$ が時刻 <math>$t\, </math>$ に依存しないもの, だけを考えるが, 下で述べる最適政策は非定常な政策を含む全ての政策の中で最適なものである. 定常政策の全体を $<math>F\, </math>$ で表す.

　最適化すべき[[計画期間]]には, 有限計画期間と無限計画期間の2種類があるが, ここでは無限計画期間を考える. また, 政策の評価規範として最も多く採用され, よく研究されているのは, 下で定義される[[割引き]]コストと平均コストの 2 種類である. 以下で, $<math>X_{t}$, $A_{t}\, </math>$, $<math>t = 0, 1, 2, \cdots\, </math>$ はそれぞれ時刻 $<math>t\, </math>$ における状態とアクションを表す確率変数とし, $<math>\mathrm{E}_{i, f}[\cdot]\, </math>$ は初期状態 $<math>i \in S\, </math>$, 政策 $<math>f \in F$\, </math> のもとでの期待値を表すものとする.

'''割引きコスト問題'''　割引き因子を $<math>\beta \in [0,1)\, </math>$ とする無限計画期間上の期待総割引きコスト ($<math>\beta\, </math>$-割引きコスト) :

u_{\beta,f}(i)
:= \mathrm{E}_{i, f} \left[ \sum_{t=0}^{\infty} \beta^{t}c(X_{t},A_{t}) \right],
\quad i \in S

を, すべての初期状態 $<math>i \in S\, </math>$ に対し, 最小化する政策 $<math>f \in F\, </math>$ ($<math>\beta\, </math>$-割引き最適政策) を求めよ.

'''平均コスト問題'''　無限計画期間における長時間平均の単位時間当り期待コスト (平均コスト) :

g_{f}(i)
:= \limsup_{T \to +\infty}
\frac{1}{T+1} \mathrm{E}_{i, f} \left[ \sum_{t=0}^{T} c(X_{t}, A_{t}) \right]

を, すべての初期状態 $<math>i \in S\, </math>$ に対し, 最小化する政策 $<math>f \in F\, </math>$ (平均最適政策) を求めよ.

　以下では, 割引きコスト問題において, よく知られている結果を概説しよう. いま最適 $<math>\beta\, </math>$-割引きコスト関数を

u_{\beta}^{*}(i)
:= \min_{f \in F} u_{\beta,f}(i), \quad i \in S

と定義すると, これは最適性方程式と呼ばれるつぎの関数方程式の一意的な解である:

\begin{equation} \label{B-D-06+OE}
u_{\beta}^{*}(i) = \min_{a \in A(i)} \left\{ c(i,a)
+ \beta \sum_{j \in S} p(j | i,a) u_{\beta}^{*}(j) \right\},
\quad i \in S.
\end{equation}

各状態 <math>$i \in S\, </math>$ に対して, 最適性方程式 (\ref{B-D-06+OE}) の右辺の $<math>\min\, </math>$ を達成する (任意の) アクションを $<math>f^{*}(i) \in A(i)\, </math>$ で表すと, それらで構成される政策 $<math>f^{*} := (f^{*}(i); i \in S) \in F\, </math>$ は $<math>\beta\, </math>$-割引き最適政策である.

　最適性方程式 (1) の標準的な数値解法としては, a. ハワードの提案による[[政策反復アルゴリズム]] (policy iteration method), b. 値反復アルゴリズム (逐次近似アルゴリズム), c. [[線形計画]]による解法, などが挙げられる. 割引きコスト問題に対する政策反復アルゴリズムは以下の通りである.

'''[政策反復アルゴリズム]'''

'''ステップ 0 (初期化)''' :　初期政策 $<math>f_{0} \in F\, </math>$ を与える.

'''ステップ 1 (政策評価)''' :　現在の政策 $<math>f_{n} \in F\, </math>$ のもとでの $<math>\beta\, </math>$-割引きコスト関数 $<math>u_{\beta,f_{n}} = (u_{\beta,f_{n}}(i); i \in S)\, </math>$ を, つぎの線形方程式系を解くことで計算する:

\begin{equation} \label{B-D-06+PI1}
u_{\beta,f_{n}}(i) = c(i,f_{n}(i))
+ \beta \sum_{j \in S} p(j | i,f_{n}(i))
u_{\beta,f_{n}}(j), \quad i \in S.
\end{equation}

'''ステップ 2 (政策改良)''' :　不等式

\begin{equation} \label{B-D-06+PI2}
u_{\beta,f_{n}}(i) \geq c(i,f(i))
+ \beta \sum_{j \in S} p(j | i,f(i)) u_{\beta,f_{n}}(j)
\end{equation}

を, すべての状態 $<math>i \in S\, </math>$ に対して成立させ, なおかつ, 少なくとも 1 つの状態では狭義の不等号で成立させる政策 $<math>f \in F\, </math>$ があれば, $<math>f_{n+1} \leftarrow f\, </math>$, $<math>n \leftarrow n+1\, </math>$ としてステップ 1 へ, さもなくば停止. 停止したとき, 最終の $<math>f_{n}\, </math>$ は $<math>\beta\, </math>$-割引き最適な政策である.

　通常, ステップ 2 (政策改良) では, 各状態 $<math>i \in S\, </math>$ において式 (3) の右辺を最小化するアクションをとる政策が新しい政策 $<math>f_{n+1}\, </math>$ として選ばれる.

　政策反復アルゴリズムは高速な解法として広く認められており, その収束に要する反復回数は, 経験的に, 問題の規模にあまり依存しない. この性質は非線形方程式系に対する数値解法であるニュートン・ラフソン法 (Newton-Raphson method) と共通のものであり, この政策反復アルゴリズムはニュートン・ラフソン法を適用することと等価であることが示されている. 政策反復アルゴリズムの弱点はステップ 1 (政策評価) において状態数だけの変数を持つ線形方程式系を解かなければならないことにある. したがって問題の規模が大きくなるにつれてその実行が負担となる. その弱点を克服するため, ステップ 1 を有限回の反復の逐次近似で代用する方法 (修正政策反復アルゴリズム) も提案されている.

　ここでは離散時間の有限 MDP の割引きコスト問題のみを概説したが, a) 他の様々な評価規範, b) 状態空間/アクション空間の一般化, c) 状態遷移の時間間隔が確率的な[[セミマルコフ決定過程]], についても多くの研究がなされている. 実際問題への適用の際に現れる情報の不完全性を明示的に考慮した, d) 不完全観測マルコフ決定過程, e) 遷移確率が未知パラメータを含む適応マルコフ決定過程, に関する研究も歴史が長い. また最近, 複数の評価規範を考慮し, f) すべての評価規範を[[目的関数]]として同時に最適化する多目的マルコフ決定過程, g) 一部の評価規範を制約条件に取り入れた制約付きマルコフ決定過程, なども関心を集め, 理論・応用・アルゴリズムの各面に関する活発な研究がなされている.

----
'''参考文献'''

[1] D. P. Bertsekas, ''Dynamic Programming and Optimal Control'', Vols. I, II, Athena Scientific, Belmont, Massachusetts, 1995.

[2] O. Hernández-Lerma and J. B. Lasserre, ''Discrete-Time Markov Control Processes, Basic Optimality Criteria'', Springer-Verlag, New York, 1995.

[3] R. A. Howard, ''Dynamic Programming and Markov Processes'', The MIT Press, Cambridge, Massachusetts, 1960.

[4] M. L. Puterman, ''Markov Decision Processes'', John Wiley & Sons, New York, 1994.

[5] S. M. Ross, ''Introduction to Stochastic Dynamic Programming'', Academic Press, New York, 1983.

[6] P. Whittle, ''Optimization over Times: Dynamic Programming and Stochastic Control'', Vols. I, II, John Wiley & Sons, New York, 1983.

《ランダム・ウォークとブラウン運動》

2007-07-08T17:01:21Z

219.161.35.37:

'''【らんだむ・うぉーくとぶらうんうんどう (random walk and Brownian motion) 】'''

　[[ランダム・ウォーク]] (random walk) とその連続化であるブラウン運動は, でたらめな動きを表現する最も基本的な[[確率過程]]で, 幅広い応用がある.

'''ランダム・ウォーク'''　$<math>\{X_n\}_{n=1}^\infty\, </math>$ を互いに独立で同一の分布に従う確率変数の列とするとき,

\begin{equation}\label{B-D-05+RW}
S_0=s~\mbox{(定数),}\qquad
S_n = s + \sum_{i=1}^n X_i
\end{equation}

によって定義される確率過程~$<math>\{S_n\}_{n=0}^\infty\, </math>$ をランダム・ウォークと呼ぶ. 特に, ある $<math>d>0\, </math>$ およびすべての $<math>n\, </math>$ に対して, $<math>\mathrm{P}(X_n=d)=p$, $\mathrm{P}(X_n=-d)=q=1-p\, </math>$ であるとき, $<math>\{S_n\}_{n=0}^\infty\, </math>$ は (1次元の) 単純ランダム・ウォークであるといい, さらに $<math>p=q=1/2\, </math>$ のとき, 単純ランダム・ウォークは対称であるという. また, 「壁」によって動きが止められたり, 動く範囲が制限されるランダム・ウォークを考えることもできる. $<math>X_n\, </math>$ の独立性より, ランダム・ウォークは[[マルコフ過程]]となる.

　初期値~$<math>s=0\, </math>$ のランダム・ウォークにおいて, $<math>n\, </math>$~ステップ後の位置の[[期待値]]と[[分散]]は, それぞれ $<math>\mathrm{E}(S_n)=n\,\mathrm{E}(X_1)\, </math>$, $<math>\mathrm{V}(S_n)=n\,\mathrm{V}(X_1)\, </math>$ となり, 時間の経過に比例する. 分散が時間の経過に比例することから, ランダム・ウォークは時間が経つにつれて次第に拡散していくことが分かる.

　$<math>d=1\, </math>$, $<math>0<p<1\, </math>$ として得られる単純ランダム・ウォーク $<math>\{S_n\}_{n=0}^\infty\, </math>$ は, 整数を[[状態空間]]とする周期2の[[既約]]な[[マルコフ連鎖]]である. このマルコフ連鎖は $<math>p\ne1/2\, </math>$ のとき一時的であり, $<math>p=q=1/2\, </math>$ ならば零再帰的となる. たとえば $<math>p>1/2\, </math>$ ならば $<math>S_n\, </math>$ はだんだん大きくなっていく傾向があり, 正の方へドリフトする. このため出発点に戻ることは保証できなくなり一時的となるのである.

　2次元の対称な単純ランダム・ウォーク~(2次元格子点空間上の4つの隣接点にそれぞれ確率~$<math>1/4\, </math>$ で推移する) は零再帰的, 3次元以上の単純ランダム・ウォークはすべて一時的であることも知られている [1].

'''単純ランダム・ウォークからブラウン運動へ'''　$<math>\{S_n\}_{n=0}^\infty\, </math>$ を初期値~$<math>s=0$\, </math> の対称な単純ランダム・ウォークとする. このランダム・ウォークが1ステップ進むのに $<math>T$\, </math> だけ時間がかかるとして, $<math>T\, </math>$ と $<math>d\, </math>$ を同時に0に近づけることを考える. $<math>t=n\,T\, </math>$ に対して, 時刻~$<math>t\, </math>$ にランダム・ウォークが $<math>x\, </math>$ にいる確率を $<math>v(x,t)\, </math>$ と表すと, $<math>v(x,t)\, </math>$ は差分方程式 $<math>v(x,t+T) = \{ v(x-d,t) + v(x+d,t) \}/2\, </math>$ を満たすので,

\frac{v(x,t+T) - v(x,t)}{T}
= \frac{1}{2}\,\frac{d^2}{T}\,
\frac{v(x+d,t) - 2\,v(x,t) + v(x-d,t)}{d^2}

が得られる. $<math>d^2/T=\sigma^2\, </math>$~(定数) を保ったまま $<math>T\to0$ ($d\to0$)\, </math> とすれば

\begin{equation}\label{B-D-05+Diffusion}
\frac{\partial v(x,t)}{\partial t}
= \frac{\sigma^2}{2}\,\frac{\partial^2 v(x,t)}{\partial x^2}
\end{equation}

を得る. 式 (2) は[[拡散方程式]] (diffusion equation) と呼ばれ, その解は初期条件~$<math>v(0,0)=1\, </math>$, $<math>v(x,0)=0$ ($x\ne0$)\, </math> のもとで, [[正規分布]] $<math>N(0,\sigma^2\,t)\, </math>$ の[[密度関数]]となる. より一般的には, 初期値が0の (必ずしも対称でない) 単純ランダム・ウォークにおいて, $<math>d^2/T=\sigma^2\, </math>$, $<math>(p-q)/d=\mu/\sigma^2\, </math>$ を保ったまま $<math>T\to0\, </math>$ とすると, 時刻~$<math>t$\, </math> での位置が正規分布~$<math>N(\mu\,t,\sigma^2\,t)\, </math>$ に従う確率過程が得られる [1].

'''ブラウン運動'''　イギリスの植物学者ブラウン (R. Brown) は, 水面に浮く花粉中の微粒子が極めて不規則な動きをすることを見いだした. アインシュタイン (A. Einstein) は, この運動が拡散方程式 (2) によって特徴づけられることを示し, その後ウィナー (N. Wiener) らによって確率過程としての基盤が築かれた. この確率過程を[[ブラウン運動]] (Brownian motion) または[[ウィーナー過程]] (Wiener process) と呼ぶ.

　(1次元の) ブラウン運動~$<math>\{B(t)\}_{t\ge0}\, </math>$ は次の性質を満たす実数値確率過程である:

1. [[独立増分過程]]である.

2. 任意の $<math>s$\, </math>, $<math>t>0\, </math>$ に対して $<math>B(s+t)-B(s)\, </math>$ は正規分布~$<math>N(0,\sigma^2\,t)\, </math>$ に従う.

3. $<math>B(0)=0\, </math>$ かつ $<math>B(t)\, </math>$ は $<math>t=0\, </math>$ で連続.

1. より, 時刻 $<math>s\, </math>$ 以降の $<math>\{B(t)\}_{t\ge s}\, </math>$ の振る舞いは $<math>s\, </math>$ までの履歴には依存しないため, ブラウン運動はマルコフ過程である. さらに, ブラウン運動が[[強マルコフ性]]を持つこと, 標本路が連続となることも知られている [2].

　$<math>\sigma^2\, </math>$ を拡散係数と呼び, 特に $<math>\sigma^2=1\, </math>$ のブラウン運動を標準ブラウン運動と呼ぶ. また, $<math>B_d(t) = \mu\,t + B(t)\, </math>$ によって定まる $<math>\{B_d(t)\}_{t\ge0}\, </math>$ をドリフトを持つブラウン運動と呼び, $<math>\mu\, </math>$ をドリフト係数と呼ぶ.

'''鏡像原理''' ドリフトのないブラウン運動 $<math>\{B(t)\}_{t\ge0}\, </math>$ に対して $<math>\tau_a\, </math>$ を $<math>\{B(t)\}_{t\ge0}\, </math>$ が初めて $<math>a\, </math>$ を横切る時刻とすると, $<math>\tau_a\, </math>$ は[[停止時]] (stopping time) となる. $<math>t\ge\tau_a\, </math>$ において $<math>\{B(t)\}_{t\ge\tau_a}\, </math>$ と $<math>a\, </math>$ に関して対称な標本路を持つ確率過程~$<math>\{\bar{B}(t)\}_{t\ge0}\, </math>$ を

\bar{B}(t) = \left\{\begin{array}{ll}
B(t), &\quad t<\tau_a, \\
2\,a - B(t), &\quad t\ge\tau_a,
\end{array}\right.

で定める. $<math>\{B(t)\}_{t\ge0}\, </math>$ が強マルコフ性を持つことと, $<math>\{B(t)\}\, </math>$ と $<math>\{\bar{B}(t)\}\, </math>$ の対称性から, $<math>\{B(t)\}\, </math>$ と $<math>\{\bar{B}(t)\}\, </math>$ は同じ確率法則に従うことがわかる. 一般にこのような性質を[[鏡像原理]] (reflection principle) と呼び, 初到達時間の分布などを求める際に利用される.

'''拡散過程''' ドリフト係数や拡散係数が位置~$<math>x\, </math>$ や時刻~$<math>t\, </math>$ に依存した値~$<math>\mu(x,t)\, </math>$, $<math>\sigma^2(x,t)\, </math>$ をとるように一般化して得られる確率過程~$<math>\{D(t)\}_{t\ge0}\, </math>$ を[[拡散過程]] (diffusion process) と呼び, $<math>\mu(x,t)\, </math>$ と $<math>\sigma^2(x,t)\, </math>$ を, それぞれドリフト関数, 拡散関数と呼ぶ. 拡散過程は強マルコフ性を持ち, その標本路は連続である. 逆に, 連続な標本路を持つマルコフ過程は拡散過程となることが知られている.

　ブラウン運動や拡散過程の標本路は, 連続であるがいたるところで微分不可能という性質を持っている. このため拡散過程の解析においては, [[確率積分]]や[[確率微分方程式]]といった通常の微分や積分とは異なる概念が必要となる [3, 4].

----
'''参考文献'''

[1] W. Feller,　''An Introduction to Probability Theory and Its Applications, Volume 1, 2nd Ed.'', John Wiley & Sons, 1957. 河田龍夫監訳, 『確率論とその応用 I』, 紀伊国屋書店, 1960 (上巻), 1961 (下巻).

[2] K. Itô and H. P. McKean, ''Diffusion Processes and Their Sample Paths'', Second Printing, Springer-Verlag, 1996.

[3] 木島正明, 『ファイナンス工学入門第I部ランダムウォークとブラウン運動』, 日科技連, 1994.

[4] 渡辺信三, 『確率微分方程式』, 産業図書, 1975.

《ポアソン過程と出生死滅過程》

2007-07-08T16:54:27Z

219.161.35.37:

'''【ぽあそんかていとしゅっせいしめつかてい (Poisson process and birth and death process) 】'''

　[[ポアソン過程]] (Poisson process) は, ランダムに生起する事象を表す基本的な[[確率過程]]で, 客の到着や故障の発生, 個体の出生など様々な現象のモデル化に使われる. 一方, [[出生死滅過程]]は個体の出生だけでなくランダムな死滅も考慮した確率過程で, [[待ち行列理論]]をはじめ広く利用されている.

'''ポアソン過程'''　事象の生起時点列を $<math>0 \le T_1 \le T_2 \le ...\, </math>$ とし, $<math>N(t)\, </math>$ を区間 $<math>[0, t]\, </math>$ における事象の生起数, $<math>N(u,v) = N(v) - N(u)\, </math>$ を区間 $<math>(u, v]\, </math>$ での生起数とする. このような確率過程$<math>\{N(t), t\ge 0\}\, </math>$ は一般に計数過程と呼ばれる. 計数過程 $<math>\{N(t)\}\, </math>$ がポアソン過程であるとは, 正の実数 $<math>\lambda\, </math>$ が存在して任意の $<math>t\ge 0\, </math>$ および $<math>h>0\, </math>$ に対して

\begin{eqnarray}
\mathrm{P}(N(t,t+h) = 1 \, | \, T_1,...,T_{N(t)}) &=& \lambda h + o(h),
\label{B-D-04+def11} \\
\mathrm{P}(N(t,t+h) \geq 2 \, | \, T_1,...,T_{N(t)}) &=& o(h). \label{B-D-04+def12}
\end{eqnarray}

が成り立つことである.

　(1), (2) はランダムな事象の生起を3つの点で特徴付けている. 第1は, 微小区間 $<math>(t, t+h]\, </math>$ に事象が生起する確率は時刻 $<math>t\, </math>$ 以前の挙動に独立であるという点, 第2は, 微小区間に2つ以上の事象が生起する確率は無視できるという点, 第3は, 微小区間に事象の生起する確率が時刻によらない点である. 式 (1) の $<math>\lambda\, </math>$ を強度 (intensity) または生起率と呼ぶ. これは単位時間あたりの平均生起数を表す. 強度を時間の関数 $\<math>lambda(t)\, </math>$ に拡張したものは[[非定常ポアソン過程]]と呼ばれる. 以下はポアソン過程の性質であり, それぞれがポアソン過程の同値な定義でもある.

'''性質1'''　ポアソン過程 $<math>\{N(t)\}\, </math>$ において,事象の生起間隔の列 $<math>U_i =T_{i+1} - T_i\, </math>$ は互いに独立で平均 $<math>1/\lambda\, </math>$ の
[[指数分布]]に従う.
\medskip

'''性質2'''　ポアソン過程 $<math>\{N(t)\}\, </math>$ は[[独立増分過程]]で, 任意の $<math>s<t\, </math>$ に対して $<math>N(s,t)\, </math>$ は平均 $<math>\lambda (t-s)\, </math>$ の[[ポアソン分布]]に従う.

　性質1は[[指数分布の無記憶性 (指数分布の)|指数分布の無記憶性]]から自然に導かれる. また, 性質2より複数の独立なポアソン過程の重ね合わせは, それぞれの強度の和を強度に持つポアソン過程となることが分かる. また, 次の定理は確率変数の和に対する[[少数の法則]]の確率過程版である.

'''定理1'''　各 $<math>k\, </math>$ に対して $<math>\ell_k\, </math>$ 個の計数過程 $<math>\{N_{k1}(t)\}, \cdots, \{N_{k\ell_k}(t)\}\, </math>$ を考え, その重ね合わせを $<math>N_k(t) =N_{k1}(t)+ \cdots +N_{k\ell_k}(t)\, </math>$ とする. $<math>\lim_{k\to\infty} \ell_k=\infty\, </math>$ で, かつ (a) $<math>\{N_{ki}(t)\}, \, i=1, \ldots , \ell_k\, </math>$ は互いに独立, (b) 任意の $<math>u<v\, </math>$ に対して $<math>\lim_{k\to\infty} \sup_{1\le i \le \ell_k} \mathrm{P}(N_{ki}(u,v) \ge 1) = 0\, </math>$ が成り立つとすると, $<math>k\to\infty\, </math>$ のとき $<math>\{N_k(t)\}\, </math>$ が[[平均測度]] $<math>\{\Lambda(t)\}\, </math>$ の (非定常) ポアソン過程に収束するための必要十分条件は, 任意の $<math>u<v\, </math>$ に対して, $<math>\lim_{k\to\infty} \sum_{i=1}^{\ell_k} \mathrm{P}(N_{ki}(u,v)=1) =\Lambda(v) - \Lambda(u)\, </math>$ および $<math>\lim_{k\to\infty} \sum_{i=1}^{\ell_k} \mathrm{P}(N_{ki}(u,v)>1) = 0\, </math>$が成り立つことである. なお, $<math>\Lambda(t)\, </math>$ が微分可能ならば強度は $<math>\lambda(t) = \mbox{d}\Lambda(t)/\mbox{d}t\, </math>$ となる.

　定理1は, 実際に起こる様々な現象をポアソン過程を用いて表わすことの妥当性を示唆している. 例えば, 電話網のある回線群への接続要求 (呼) は非常に多くの電話機からかかってくる呼の重ね合わせとみなせる. この場合, 各電話機は独立に使われており (仮定 (a)), その頻度は十分小さい (仮定 (b)) と考えられるため, この回線群への呼の発生はポアソン過程としてモデル化できるであろう. この他にも, [[マルチンゲール]]によるポアソン過程の特徴付けや, 事象平均と時間平均の同等性を示す[[PASTA]] (Poisson arrivals see time averages) など, ポアソン過程には興味深い性質が多い.

'''ポアソン過程の一般化'''　ポアソン過程を特徴付ける3つの条件のうち第2の条件を緩め, 事象の生起時点列はポアソン過程であるが, 各生起時点で同時に発生する事象の数は独立で同一の分布に従う確率変数である場合, $<math>N(t)\, </math>$ は複合ポアソン過程と呼ばれる. また, 非定常ポアソン過程の強度 $<math>\lambda(t)\, </math>$ を確率過程に拡張したものは2重確率ポアソン過程 (doubly stochastic Poisson process) と呼ばれる. 例えば, [[マルコフ変調ポアソン過程]]は $<math>\lambda(t)\, </math>$ が連続時間マルコフ連鎖に従う例である.

'''出生過程'''　性質1より, ポアソン過程は[[状態空間]] $<math>\{0, 1, ...\}\, </math>$ 上の[[連続時間マルコフ連鎖]]であることがわかる. [[推移速度行列]]を $<math>\mbox{\boldmath$Q$} =(q_{ij})\, </math>$ とすると, 性質1から $<math>q_{i,i+1} = -q_{ii} = \lambda, \, i\ge 0\, </math>$ でその他の $<math>\mbox{\boldmath$Q$}\, </math>$ の要素は全て0となる. これを一般化して, $<math>i\, </math>$ から $<math>i+1\, </math>$ への推移速度が $<math>i\, </math>$ に依存して $<math>\lambda_i\, </math>$ で定まるマルコフ連鎖を[[出生過程]] (birth process)と呼ぶ. 出生過程の推移速度行列は$<math>q_{i,i+1} = -q_{ii} = \lambda_i, \, i\ge 0\, </math>$ で, その他の要素は0である.

'''出生死滅過程'''　出生過程では, 状態は $<math>i\, </math>$ から <math>$i+1\, </math>$ というように1ずつ進んでいくが, $<math>i\, </math>$ から $<math>i-1\, </math>$ へ戻ることも許すように一般化すると, $<math>q_{i,i+1} = \lambda_i, \, q_{i+1,i} = \mu_{i+1}, \, i\ge 0\, </math>$ かつ $<math>q_{00} =-\lambda_0, \, q_{ii} = -(\lambda_i + \mu_i), \, i\ge 1\, </math>$ で, その他の要素は0の推移速度行列が得られる. このような3重対角の推移速度行列に従う連続時間マルコフ連鎖を[[出生死滅過程]] (birth and death process) という. また, $<math>\lambda_i\, </math>$, $<math>\mu_i\, </math>$ はそれぞれ状態 $<math>i\, </math>$ での出生率, 死滅率と呼ばれる. 出生死滅過程では, 状態 $<math>i\; (\ge 1)\, </math>$ に滞在する時間の長さはパラメータ $<math>\lambda_i+\mu_i\, </math>$ の指数分布に従い, 滞在時間を終えると確率 $<math>\lambda_i/(\lambda_i+\mu_i)\, </math>$ で状態 $<math>i+1\, </math>$ へ, 確率 $<math>\mu_i/(\lambda_i+\mu_i)\, </math>$ で状態 $<math>i-1\, </math>$ へ推移する.

　出生死滅過程は隣り合う状態間でのみ[[推移]]が起きるという特徴を持つため, [[定常分布]]などの特性量が陽な形で得られる. 例えば, 応用上重要な $<math>\lambda_i=\lambda\, </math>$, $<math>\mu_i=\mu\, </math>$ の出生死滅過程は, $<math>\lambda < \mu\, </math>$ のとき[[正再帰的]]で, $<math>\rho=\lambda/\mu\, </math>$ とすると状態 $<math>j$\, </math> にいる定常確率は $<math>\pi_j = (1 - \rho)\rho^j, \; j=0,1,\ldots\, </math>$ という[[幾何分布]]となる. なお, $<math>\lambda = \mu\, </math>$ のときは零再帰的, $<math>\lambda > \mu$\, </math> のときは一時的となり定常分布は存在しない. この例は[[M/M/1 待ち行列モデル]]に相当する出生死滅過程であるが, 出生死滅過程はより一般的な[[M/M/c 待ち行列モデル]] (M/M/<math>$c$\, </math> 待ち行列モデル) などのマルコフ型の待ち行列モデルや, [[機械修理モデル]]を解析する上でも重要な確率過程となっている.

----
'''参考文献'''

[1] P. Brémaud, ''Point Processes and Queues'', Springer-Verlag, 1981.

[2] D. R. Cox and V. Isham, ''Point Processes'', Chapman and Hall, 1980.

[3] R. W. Wolff, ''Stochastic Modeling and the Theory of Queues'', Prentice-Hall, 1989.

[4] 宮沢政清, 『確率と確率過程』, 近代科学社, 1993.

《マルコフ連鎖》

2007-07-08T16:46:05Z

219.161.35.37:

'''【まるこふれんさ (Markov chain) 】'''

'''マルコフ過程'''　quad独立性を緩めた性質である[[マルコフ性]]を持つ確率過程のことを[[マルコフ過程]]と呼び, その中で状態が離散的なものを一般にマルコフ連鎖と呼ぶ. マルコフ連鎖は最も基本的で応用範囲の広い\[[確率過程]]の一つである.

'''離散時間マルコフ連鎖'''　離散的な[[状態空間]] $<math>{\mathcal S}\, </math>$ 上の確率過程 $<math>\{ X_n; \; n = 0,1,2,\cdots \}\, </math>$ が, 任意の時点 $<math>n\, </math>$, $<math>m\, </math>$ と任意の状態 $<math>i_0, \cdots, i_m, j \in {\mathcal S}\, </math>$ に対して

\begin{equation}\label{B-D-03+eq1}
\mathrm{P}(X_{m+n}=j|X_k=i_k, k=m,m-1,\cdots,0)
=\mathrm{P}(X_{m+n}=j|X_m=i_m)
\end{equation}

を満たすとき, $<math>\{ X_n \}\, </math>$ を離散時間[[マルコフ連鎖]]と呼ぶ. (1) は, 将来の分布が現在の状態のみで定まり, 過去の状態には依存しない性質を表しており, マルコフ性と呼ばれる.賭けの問題における所持金の推移や, [[在庫理論]]における各期の在庫量の変化など, マルコフ性を持つと考えられる例は多い.

　(1) の推移確率が, 時点 $<math>m\, </math>$ に依存しない場合, マルコフ連鎖は[[斉時的]]であるという. 斉時的な離散時間マルコフ連鎖 $<math>\{ X_n \}\, </math>$ に対して, $<math>p_{ij}(n)=\mathrm{P}(X_{m+n}=j|X_m=i)\, </math>$ を $<math>n\, </math>$ ステップ[[推移確率]], $<math>\mbox{\boldmath$P$}(n)=(p_{ij}(n))\, </math>$ を $<math>n\, </math>$ ステップ[[推移確率行列]]と呼ぶ. 特に 1ステップ推移確率を $<math>p_{ij}\, </math>$ で表し, $<math>\mbox{\boldmath$P$}=(p_{ij})\, </math>$ を推移確率行列と呼ぶ. [[チャップマン・コルモゴロフの等式]] (Chapman-Kolmogorov equation) $\mbox{\boldmath$P$}(m+n)=\mbox{\boldmath$P$}(m) \mbox{\boldmath$P$}(n)$ から $\mbox{\boldmath$P$}(n)=\mbox{\boldmath$P$}^n$ が成り立つので, 1 ステップ推移確率行列 $\mbox{\boldmath$P$}$ が与えられれば, 任意のステップの推移確率を計算することができる.

'''既約なマルコフ連鎖と吸収的マルコフ連鎖'''　状態の組 $<math>i, j\, </math>$ に対して, 適当な $<math>n\, </math>$ で $<math>p_{ij}(n)>0\, </math> $ となる場合, $<math>i\, </math>$ から $<math>j\, </math>$ へ到達可能であるという. 任意の状態から他のどの状態へも到達可能であるマルコフ連鎖は[[既約]]であるという. 一方, $<math>p_{ii}=1\, </math>$ である状態 $<math>i\, </math>$ は, 一度入ると他の状態へ推移できないため吸収状態と呼ばれる. 任意の状態から出発したとき確率1でいつかはいずれかの吸収状態に到達するマルコフ連鎖を[[吸収的]]という. 後述するように, 既約なマルコフ連鎖では長期間観察したときに各状態に滞在する時間の割合が主な分析対象となる. これに対し, 吸収的マルコフ連鎖では, 吸収されるまでの挙動, 例えば吸収時間の分布, 吸収までに各状態に滞在する平均ステップ数, 複数の吸収状態がある場合に各状態への吸収確率, などが分析の対象となる.

　$<math>p_{ii}(n)>0\, </math>$ となるすべての $<math>n \geq 1\, </math>$ の最大公約数を, 状態 $<math>i\, </math>$ の周期と定める. 既約なマルコフ連鎖では, すべての状態は同じ周期を持つことが知られている. また, 周期 1 のマルコフ連鎖を非周期的という.

　$<math>i\, </math>$ から $<math>j\, </math>$ への[[初到達時間]]を $<math>T_{ij}\, </math>$ とすると, マルコフ連鎖の各状態 ($<math>i\, </math>$ とする) はその状態への[[再帰確率]]} $<math>\mathrm{P}(T_{ii}<\infty)\, </math>$ と平均再帰時間 $<math>\mathrm{E}(T_{ii})\, </math>$ により以下のように分類される.

\left\{
\begin{array}{ll}
\mathrm{一時的} & \mathrm{P}(T_{ii}<\infty)<1 \\
\mathrm{再帰的} & \mathrm{P}(T_{ii}<\infty)=1 \quad
\left\{
\begin{array}{ll}
\mathrm{零再帰的} & \mathrm{E}(T_{ii}) = \infty \\
\mathrm{正再帰的} & \mathrm{E}(T_{ii}) < \infty
\end{array}
\right.
\end{array}
\right.

なお, 既約なマルコフ連鎖ではすべての状態は同じ分類に属するので, これらはマルコフ連鎖自身の分類でもある. 特に, 既約で非周期的かつ正再帰的なマルコフ連鎖は, [[エルゴード的マルコフ連鎖]]と呼ばれる.

'''定常分布'''　$<math>n \rightarrow \infty\, </math>$ のとき $<math>p_{ij}(n)\, </math>$ が初期状態 $<math>i\, </math>$ に無関係な正定数 $<math>\pi_j\, </math>$ に収束し, 正規化条件 $<math>\sum_{j \in {\mathcal S}} \pi_j = 1\, </math>$ を満たす場合, $<math>\mbox{\boldmath$\pi$}=(\pi_j)\, </math>$ を[[極限分布]]と呼ぶ. 極限分布は[[平衡方程式]] $<math>\mbox{\boldmath$\pi$}=\mbox{\boldmath$\pi$}\mbox{\boldmath$P$}\, </math>$ を満たすため, この方程式と正規化条件から求めることができる. 極限分布に対して, 平衡方程式を満たす確率分布を[[定常分布]]と呼ぶ. 極限分布は定常分布であるが, 周期的なマルコフ連鎖のように定常分布は必ずしも極限分布とならない. 既約で非周期的なマルコフ連鎖に対しては, (1) 正再帰的であること, (2) 極限分布が存在すること, (3) 平衡方程式と正規化条件が一意の解を持つこと, の3条件は同値となる. 実際, エルゴード的なマルコフ連鎖では $<math>\pi_j = 1/\mathrm{E}(T_{jj})$\, </math> となり, 極限分布は $<math>\{ X_n \}\, </math>$ を長時間観測したときに各状態に滞在する時間の割合に一致する. なお, 有限状態のマルコフ連鎖が既約で非周期的であれば, 必ず正再帰的となる. 一方, 状態 $<math>j\, </math>$ が一時的もしくは零再帰的ならば, $<math>\lim_{n \rightarrow \infty} p_{ij}(n)=0\, </math>$ となり極限分布は存在しない.

'''連続時間マルコフ連鎖'''　離散状態空間上の連続時間確率過程 $<math>\{ X(t); \; t \geq 0 \}\, </math>$ が, 任意の時点 $<math>s\, </math>$, $<math>t\, </math>$ と状態 $<math>i, j\, </math>$, および履歴 $<math>x(u)\, </math>$ に対して

\begin{equation}\label{B-D-03+eq2}
\mathrm{P}(X(s+t)=j|X(u)=x(u), 0 \leq u \leq s)
=\mathrm{P}(X(s+t)=j|X(s)=x(s))
\end{equation}

を満たすとき, 連続時間マルコフ連鎖と呼ぶ. [[ポアソン過程]]や[[出生死滅過程]]などは, 代表的な連続時間マルコフ連鎖である.

　離散時間の場合と同様に, (\ref{B-D-03+eq2}) が $<math>s\, </math>$ に依存しないマルコフ連鎖を斉時的といい, 推移確率を $<math>p_{ij}(t) = \mathrm{P}(X(s+t)=j|X(s)=i)\, </math>$, 推移確率行列を $<math>\mbox{\boldmath$P$}(t)\, </math>$ で表す. 異なる状態 $<math>i, j\, </math>$ に対して, $<math>q_{ij} = \lim_{h \downarrow 0} h^{-1} p_{ij}(h)\, </math>$ を状態 $<math>i$\, </math> から $<math>j\, </math>$ への推移速度といい, $<math>q_{ij}\, </math>$ を非対角要素, 対角要素を $<math>q_{ii}=-\sum_{j \neq i} q_{ij}\, </math>$ とする行列 $<math>\mbox{\boldmath$Q$}=(q_{ij})\, </math>$ を[[推移速度行列]]と呼ぶ. マルコフ性から, 連続時間マルコフ連鎖が状態 $<math>i\, </math>$ に滞在する時間はパラメータ $<math>-q_{ii}\, </math>$ の[[指数分布]]に従う. また, $<math>-q_{ij}/q_{ii}\, </math>$ は状態 $<math>i\, </math>$ での滞在が終了したという条件の下で, 推移先が <math>$j\, </math>$ である条件付き確率を与える. 推移速度行列 $<math>\mbox{\boldmath$Q$}\, </math>$ が与えられると, 推移確率は[[コルモゴロフの後退方程式]] $<math>\mbox{\boldmath$P$}'(t)=\mbox{\boldmath$Q$}\mbox{\boldmath$P$}(t)\, </math>$, あるいは[[コルモゴロフの前進方程式]] $<math>\mbox{\boldmath$P$}'(t)=\mbox{\boldmath$P$}(t)\mbox{\boldmath$Q$}\, </math>$によって特徴付けられる. この関係から, 応用上現れる多くのマルコフ連鎖では推移確率が$<math>\mbox{\boldmath$P$}(t) = \mbox{exp}( \mbox{\boldmath$Q$}t )\ (t \geq 0)\, </math>$で表される.

　離散時間マルコフ連鎖と同様に, 任意の状態から他のどの状態へも推移可能な場合, このマルコフ連鎖は既約であるという. また, 状態の分類 (一時的, 零再帰的, 正再帰的) も, 各状態への再帰時間 $<math>T_{ii}\, </math>$ の性質により離散時間マルコフ連鎖の場合と同様に定義される. 極限分布についても, 初期状態 $<math>i\, </math>$ に無関係に $<math>\lim_{t \rightarrow \infty}p_{ij}(t) = \pi_j>0\, </math>$ と収束し, $<math>\sum_{j \in {\mathcal S}} \pi_j = 1\, </math>$ が成り立つ場合, $<math>\mbox{\boldmath$\pi$}=(\pi_j)\, </math>$ を極限分布とよぶ. 極限分布は, 平衡方程式 $<math>\mbox{\boldmath$0$} = \mbox{\boldmath$\pi$}\mbox{\boldmath$Q$}\, </math>$と正規化条件 $<math>\sum_{i \in {\mathcal S}} \pi_i = 1\, </math>$ から求めることができる. 既約な連続時間マルコフ連鎖に対しては, 正再帰的であること, 極限分布が存在すること, 平衡方程式と正規化条件を満たす $<math>\pi_j\, </math>$ が存在すること, の3条件は同値である.

'''マルコフ連鎖の一般化'''　マルコフ性は独立性を少し緩めた概念だが, 適用範囲は広い. 例えば, 離散時間確率過程 $<math>\{ X_n \}\, </math>$ の将来の時点における分布が, 現在の状態 $<math>X_n\, </math>$ と過去の $<math>k\, </math>$ 状態 $<math>X_{n-1}, \cdots, X_{n-k}\, </math>$ に依存する場合, $<math>\{ X_n \}\, </math>$ 自身はマルコフ連鎖とならないが, $<math>Y_n=(X_{n-k}, \cdots, X_n)\, </math>$ はマルコフ連鎖となる. また, 状態の推移はマルコフ連鎖に従い, 各状態の滞在時間分布が一般分布に拡張された確率過程は[[セミマルコフ過程]]と呼ばれ, マルコフ連鎖による分析が援用できる.さらに, そのままではマルコフ性を持たない確率過程に対しても, [[隠れマルコフ連鎖法]]や[[補助変数法]]を利用することでマルコフ連鎖としてモデル化できる場合が少なくない. このようなモデル化における汎用性・柔軟性は, マルコフ連鎖が広く利用される大きな理由となっている.

----
'''参考文献'''

[1] K. L. Chang,　''Markov Chains with Stationary Transition Probabilities'',　Springer-Verlag, 1967.

[2] D. Freedman,　''Markov Chains'',　Springer, 1983.

[3] J. G. Kemenny and J. L. Snell,　''Finite Markov Chain'',　Van Nostrand, 1960.

[4] 森村英典, 高橋幸雄, 『マルコフ解析』, 日科技連, 1979.

《確率過程》

2007-07-08T16:36:26Z

219.161.35.37:

'''【かくりつかてい (stochastic process) 】'''

'''確率過程と標本路'''　確率変数がランダムな試行の結果で値の決まる変数であるのに対し, パラメータ集合 $<math>{\mathcal T}\, </math>$ によってインデックスを付けられた確率変数の集まり $<math>\{ X(t);\; t \in {\mathcal T} \}\, </math>$ を[[確率過程]]と呼ぶ. 一般にパラメータ集合 $<math>{\mathcal T}\, </math>$ は時間を表すため, 確率過程は時間の経過に従ってランダムに変化する値の系列と言える. 単に[[独立 (確率変数の)|独立]]な確率変数が並んだものも形式的には確率過程であるが, 我々が分析の対象とするのは, 異なる時点の確率変数間に何らかの相関関係がある場合である. 例えば $<math>X(t)\, </math>$ をある場所の $<math>t\, </math>$ 時の気温とすれば, $<math>X(10)\, </math>$と $<math>X(12)\, </math>$ の間には強い相関があるであろう. $<math>X(t)\, </math>$ を $<math>t\, </math>$ 期の在庫量とする場合も同様である. 確率過程の分析においては, このような変数間の関連性をどのように表現し, それをもとにしてどのように確率過程の振る舞いを調べていくかが重要となる.

確率過程 $<math>\{ X(t);\; t \in {\mathcal T} \}\, </math>$ は, 時点 $<math>t\, </math>$ を 1 つ固定すると根元事象 (確率空間 $<math>(\Omega, {\mathcal F}, \mathrm{P})\, </math>$ における標本空間 $<math>\Omega\, </math>$ の要素 $<math>\omega\, </math>$) によって値が変わる確率変数となり, 逆に根元事象を 1 つ固定して考えると, 時間パラメータ $<math>t\, </math>$ の関数となる. 根元事象を固定して得られる $<math>t\, </math>$ の関数を, 確率過程の標本路 (sample path) と呼ぶ. 確率変数の値が根元事象によって異なるように, 根元事象が異なれば確率過程の標本路も違ったものとなる.

'''離散と連続'''　$<math>{\mathcal T}\, </math>$ が可算集合である確率過程を離散時間確率過程といい, $<math>{\mathcal T}\, </math>$ が連続的な集合の場合を連続時間確率過程という. また, 確率過程 $<math>X(t)\, </math>$ がとる個々の値を状態, すべての状態からなる集合を[[状態空間]]と呼ぶ. 応用上は, 実数や整数, およびそれらの多次元空間が状態空間となることが多い. 時間パラメータの集合と同様に, 確率過程は状態空間の性質によって連続と離散に分類できる.

'''確率的構造の導入'''　確率過程を定めるには, その確率過程が従う確率法則を規定する必要がある. そのための方法の中で最も直接的なのは, 任意の $<math>n\, </math>$ と任意に選んだ $<math>n\, </math>$ 個の時点 $<math>t_1, \cdots, t_n\, </math>$ に対して, $<math>(X(t_1), \cdots, X(t_n))\, </math>$ の[[同時分布]]を与える方法である. 例えば, どのような時点の組に対しても $<math>(X(t_1), \cdots, X(t_n))\, </math>$ が$<math>n\, </math>$次元正規分布 ([[n次元正規分布]]) に従うとき, $<math>\{ X(t) \}\, </math>$ は[[ガウス過程]]と呼ばれる. また, どんな $<math>s\, </math>$ に対しても $<math>(X(t_1), \cdots, X(t_n))\, </math>$ と時点を $<math>s\, </math>$ ずらした $<math>(X(t_1+s), \cdots, X(t_n+s))\, </math>$ の分布が一致する確率過程は[[定常過程 (強)]]と呼ばれ, 時系列解析などの基礎となる.

　同時分布を定める代わりに, 確率過程の変化量の分布特性を与えることで確率過程を定めることもできる. 例えば, 重ならない区間での変化量が独立, すなわち任意に選んだ時点 $<math>t_1< t_2 < \cdots < t_{2n}\, </math>$ に対して各時間区間での変化量 $<math>X(t_{2i})-X(t_{2i-1})\ (i=1,\cdots,n)\, </math>$ が互いに独立である確率過程は, [[独立増分過程]]と呼ばれる. 例えば, ランダムな動きを表す確率過程である標準[[ブラウン運動]]は, 任意の時間区間 $<math>[t_1, t_2]\, </math>$ での変化量 $<math>X(t_2)-X(t_1)$\, </math> が正規分布 $<math>N(0, t_2-t_1)\, </math>$ に従う独立増分過程として特徴付けられる. また, [[再生過程]]は独立で同一の分布に従う間隔で事象が起こるとして, 時点 $<math>t\, </math>$ までに起きた事象の数 $<math>N(t)\, </math>$ で与えられる. $<math>N(t)\, </math>$ はランダムな間隔で値が1ずつ増加する確率過程で, [[待ち行列理論]]における客の到着や[[信頼性理論]]における故障の発生を表す際によく用いられる. 特に, 事象の生起間隔が[[指数分布]]に従う再生過程は[[ポアソン過程]]と呼ばれ, [[少数の法則]]から我々の身の回りでもよく観察される.

　この他に, 隣接する複数時点の変数の関係によって確率過程を定めることも可能である. 例えば, $<math>K\, </math>$ 次の[[自己回帰移動平均過程]]では, $<math>X(n)\, </math>$ は過去 $<math>K\, </math>$ 時点の値と白色雑音 $<math>\{ \epsilon(n) \}\, </math>$ の加重線形結合 $<math>X(n)=\sum_{i=1}^K a_i X(n-i) + \epsilon(n)\, </math>$ で表される. また, 離散時間[[マルコフ連鎖]]では, $<math>X(n)\, </math>$ から $<math>X(n+1)\, </math>$ への推移確率によって確率過程の変化の規則を定める. 例えば, 単純[[ランダムウォーク]] $<math>\{ X_n \}\, </math>$ は, 確率 $<math>p\, </math>$ で $<math>X_{n+1}=X_n+1\, </math>$, 確率 $<math>1-p$\, </math> で $<math>X_{n+1}=X_n-1\, </math>$ という規則で値が変化する. さらに, 任意の $<math>m\, </math>$ と $<math>n\, </math>$ に対して $<math>\mathrm{E}(X_{m+n} | X_1,\cdots,X_m)=X_m\, </math>$ が成り立つ, すなわち時点 $<math>m\, </math>$ までの履歴が与えられた条件付きでの将来の時点における期待値が $<math>m\, </math>$ での値に一致する確率過程は (離散時間) [[マルチンゲール]]と呼ばれる. マルチンゲールは平均が一定で, 公平な賭けのモデル化である.

'''特性量'''　確率過程を利用して何らかの現象をモデル化・分析する際には, その過程に付随する特性量を定量的に評価することが必要となる. 例えば, 広い範囲の待ち行列システムは[[マルコフ過程]]として定式化されるが, この場合はマルコフ過程の定常分布から待ち行列システムの平均待ち時間などを求めることができる. マルコフ過程に限らず, 定常状態が存在する確率過程の分析では, 時間平均の分布と定常分布を関連付ける[[エルゴード定理]]が重要な役割を果たす. 信頼性理論や[[在庫理論]]においても, 長期間における平均コストが分析の主な対象となるが, これらのモデルでは取り替えや発注によって区切られた区間が1つのサイクルをなすため, 再生過程によるモデル化と[[再生定理]]による評価が主に利用される. 一方, 自己回帰過程などを利用した時系列分析では, 過去のデータからモデルのパラメータを同定し, 将来の変化を予測するため, 過去のデータに最もよく適合する時系列モデルやパラメータの選択が重要となる. また, 数理ファイナンスにおける金融派生商品の価格評価理論においては, 原資産価格や金利の変動を[[確率微分方程式]]等を用いて記述し, それをもとにマルチンゲール理論などを援用して商品の価格評価を行う. そこでは, 実際の変動により忠実でなおかつ価格評価式の計算が容易なモデルの構築がポイントとなる.

----
'''参考文献'''

[1] J. L. Doob, ''Stochastic Processes'', John Wiley and Sons, 1953.

[2] S. Karlin and H. M. Taylor, ''An First Course in Stochastic Processes'', Academic Press, 1975.

[3] S. Karlin and H. M. Taylor, ''A Second Course in Stochastic Processes'', Academic Press, 1981.

[4] S. M. Ross, ''Stochastic Processes'', John Wiley, 1983.

[5] 宮沢政清, 『確率と確率過程』, 近代科学社, 1993.

《確率論》

2007-07-08T16:27:09Z

219.161.35.37:

'''【かくりつろん (probability theory) 】'''

　不確実な現象を表現する手段としての確率論は, コルモゴロフ (A. N. Kolmogorov) が測度論的確率論を打ち立ててから数学的基礎ができたと言えよう.その後の確率論の理論的深化と応用は目を見張るものがあり, オペレーションズ・リサーチへの応用に限っても, [[待ち行列理論]], [[在庫理論]], [[ファイナンス理論]], [[動的計画]], [[確率計画]], [[信頼性理論]], [[シミュレーション]]等多岐にわたっている. 特に, 数理統計学や待ち行列理論は理論的基礎の多くを確率論に置いており, 数学的な観点からも興味ある問題を提起し続けている.

'''確率空間と確率変数'''　確率論を考える上で基礎となるのは, 確率空間 $<math>(\Omega, {\mathcal F}, \mathrm{P})\, </math>$ である. ここで, 標本空間 $<math>\Omega\, </math>$ は起こり得る結果 (根元事象) $<math>\omega\, </math>$ の集合, $<math>{\mathcal F}\, </math>$ は $<math>\Omega\, </math>$ 上の $<math>\sigma\, </math>$--集合体, $<math>\mathrm{P}\, </math>$ は確率を表す. しかし, 確率モデルに対して確率空間を明示するのは煩雑なため, 通常は $<math>(\Omega, {\mathcal F}, \mathrm{P})\, </math>$ を抽象的な基礎空間と捉え, $<math>\Omega\, </math>$ から観察される現象の空間 $<math>{\mathcal S}\, </math>$ への写像である確率変数を中心に考える.

　以下では, $<math>{\mathcal S}\, </math>$ として実数や整数, あるいはこれらの多次元空間を考え, 確率変数を $<math>X(\omega)\, </math>$ あるいは単に $<math>X\, </math>$ で表す. 例えば, サイコロを投げる試行では $<math>X\, </math>$ は1から6のどれかの値をとり, $<math>X\, </math>$ が測定誤差を表すならば実数全体をとる. また, $<math>K\, </math>$ 個の離散的時系列ならば $<math>X=\{ X_1, \ldots, X_K \}$\, </math> となり, 連続時間上の変動ならば $<math>X=\{ X_t \; : \; t \in \mbox{R} \}\, </math>$ と表現される. 一般に, 時間パラメーターを伴う確率変数の集まりは[[確率過程]]と呼ばれる.

'''確率分布'''　確率変数を特徴付ける主な要素は確率分布である. $<math>X\, </math>$ が実数値確率変数のとき, $<math>\mbox{R}\, </math>$ の部分集合 $<math>A\, </math>$ (正確には $<math>\mbox{R}\, </math>$ 上のボレル集合体 $<math>{\mathcal B}_1\, </math>$ の要素 $<math>A\, </math>$) に対し, $<math>X \in A\, </math>$ となる確率は $<math>\mathrm{P}(\{\omega : X(\omega) \in A \})\, </math>$ で与えられる. このように, 集合 $<math>A\, </math>$ に対して $<math>X \in A\, </math>$ となる確率を対応させたものを $<math>X\, </math>$ の[[確率分布]], あるいは単に分布と呼ぶ. 特に, $<math>A=(-\infty, x]\, </math>$ としたときの確率$<math>F(x)=\mathrm{P}(X \leq x)\; (=\mathrm{P}(\{\omega : X(\omega) \leq x\}))\, </math>$ を $<math>x\, </math>$ の関数と考えて $<math>X\, </math>$ の[[確率分布関数]]または分布関数と呼ぶ. $<math>F(x)\, </math>$ は単調非減少な右連続関数で, $<math>F(-\infty)=0\, </math>$, $<math>F(+\infty)=1\, </math>$ を満たす.

　分布の中で, とり得る値が高々可算個である確率分布を[[離散型分布]]と呼ぶ. $<math>X\, </math>$ が $<math>\{ \ldots, x_{-1}, x_0, x_1, \ldots \}\, </math>$ の値をとる離散型分布であれば, [[確率関数]] $<math>p(k) = \mathrm{P}(X=x_k)$\, </math> によって分布を表すことができる. 離散型分布に対し, $<math>F(x)\, </math>$ が連続な分布を[[連続型分布]]という. 実際に用いられるほとんどの連続型分布は $<math>F(x)\, </math>$ が微分可能であり, [[確率密度関数]] $<math>f(x)=\mathrm{d}F(x)/\mathrm{d}x\, </math>$によって分布を表現できる. $<math>f(x)\, </math>$ は単に密度関数とも呼ばれる. 密度関数を持つ分布は絶対連続型分布, あるいは単に連続型分布と呼ばれることもある.

　離散分布の例としては, [[2項分布]], [[ポアソン分布]], [[幾何分布]]などがあり, 密度関数をもつ分布の例としては[[正規分布]], [[指数分布]], [[一様分布]]などがある.

'''期待値と分散'''　確率関数や密度関数では, 一目で分布の性質を捉えたり分布を比較することが難しい場合もあるため, 確率分布の特徴を少数の数値で表現できると都合がよい. その代表は分布の中心を表す[[期待値]] (あるいは[[平均]]) $<math>\mathrm{E}(X)=\int x \mathrm{d} F(x)\, </math>$ と分布の散らばり具合を表す[[分散]] $<math>\mathrm{V}(X) =\int (x-\mathrm{E}(X))^2 \mathrm{d}F(x)\, </math>$, もしくは分散の平方根の標準偏差である. なお, $<math>\int g(x) \mathrm{d} F(x)\, </math>$ の形の積分は, $<math>F(x)\, </math>$ が離散型分布の場合は $<math>\sum g(x_i) \mathrm{P}(X=x_i)\, </math>$, 密度関数 $<math>f(x)\, </math>$ を持つ場合は $<math>\int g(x) f(x) \mathrm{d} x\, </math>$ と理解してよい. 平均や分散のように $<math>\mu_j=\int (x-a)^j \mathrm{d} F(x)\, </math>$ の形で表される数値を一般に $<math>j\, </math>$ 次の積率 (moment) と呼ぶ. 特に, $<math>a=0\, </math>$ のときは原点周りの積率, $<math>a=\mathrm{E}(X)\, </math>$ のときは平均周り積率となる. $<math>j\, </math>$ が高次になるにつれて $<math>\mu_j\, </math>$ の表現が複雑になる傾向があるため, [[特性関数 (確率変数の)|特性関数]] $<math>\phi(t)=\int \mathrm{e}^{\mathrm{i}tx} \mathrm{d} F(x)\, </math>$ ($<math>t\, </math>$ は実数パラメータ, $<math>\mathrm{i}\, </math>$ は虚数単位), あるいは[[積率母関数]] $<math>M(\theta)=\int \mathrm{e}^{\theta x} \mathrm{d}F(x)\, </math>$ を利用して$<math>\mu_j\, </math>$ を求める方法が考えられている. 例えば, 積率母関数 $<math>M(\theta)\, </math>$ が陽に求まれば, 原点周りのモーメントは $<math>\mu_j = \mathrm{d}^j M(\theta) / \mathrm{d} \theta^j |_{\theta=0}\, </math>$ で計算される. また, 非負の値をとる確率変数に対しては, [[ラプラス変換]]を利用してもよい. これらの変換は, 元の分布関数と1対1に対応しており, 原理的には逆変換によって元の分布を求めることができる. また, 変換を利用することで, たたみこみなど分布に関する演算が簡単になることも多い.

'''多次元分布'''　1次元の場合の自然な拡張として, $<math>n\, </math>$ 個の実数値確率変数 $<math>X_1, \ldots, X_n\, </math>$ に対しても, [[多次元分布関数]] $<math>\mathrm{P}(X_1 \leq x_1, \ldots, X_n \leq x_n)\, </math>$ によって分布を定めることができる. 代表的な多次元分布としては, 多変量解析などの基礎となる[[多次元正規分布]]がある. 多次元分布では, 複数の確率変数の関係に興味がある場合が多い. そのような関係を表す指標として, 2つの確率変数 $<math>X\, </math>$ と $<math>Y\, </math>$ の[[共分散]] $<math>\mathrm{Cov}(X,Y)=\mathrm{E}(\{X-\mathrm{E}(X)\}\{Y-\mathrm{E}(Y)\})\, </math>$ や, [[相関係数]] $<math>r(X,Y)=\mathrm{Cov}(X,Y)/\sqrt{\mathrm{V}(X)\mathrm{V}(Y)}\, </math>$ がある. 相関係数は $<math>-1 \leq r(X,Y) \leq 1\, </math>$ の範囲の値をとり, $<math>r(X,Y)\, </math>$ が1に近い場合は, 一方の値が大きいと他方も大きな値を, 一方の値が小さいと他方も小さな値をとる傾向が強い. $<math>r(X,Y)\, </math>$ が $<math>-1\, </math>$ に近いときは, 反対の傾向となる. また, $<math>r(X,Y)=0$\, </math> のとき $<math>X\, </math>$ と $<math>Y\, </math>$ は無相関と呼ばれる.

'''確率変数の独立性'''　$<math>n\, </math>$ 個の確率変数 $<math>X_1, \ldots, X_n\, </math>$ が, 任意の $<math>x_1,\ldots,x_n\, </math>$ に対して

:<math>\mathrm{P}(X_1 \leq x_1, \ldots, X_n \leq x_n)
= \prod_{i=1}^n \mathrm{P}(X_i \leq x_i)\, </math>

を満たすとき, $<math>X_1, \ldots, X_n\, </math>$ は[[独立 (確率変数の)|独立]]であるという. 直観的には, 各確率変数の値が他の確率変数の値と無関係に決まることを意味する. なお, $<math>X\, </math>$ と $<math>Y\, </math>$ が独立であれば無相関となるが, その逆は一般に成立しない. 独立な確率変数 $<math>X\, </math>$ と $<math>Y\, </math>$ の確率分布関数を $<math>F_X(x)$, $F_Y(x)\, </math>$ とするとき, その和 $<math>S = X+Y\, </math>$ の確率分布関数は, $<math>F_S(x)= \int F_X(x-y) \mathrm{d} F_Y(y)\, </math>$ によって計算できる. 同様に, 整数値をとる離散型分布に対しては $<math>\mathrm{P}(S=k)=\sum_i \mathrm{P}(X=k-i)\mathrm{P}(Y=i)\, </math>$ によって $<math>S\, </math>$ の確率関数を, また, $<math>X\, </math>$, $<math>Y\, </math>$ が密度関数をもつ場合は, $<math>f_S(x)=\int f_X(x-y)f_Y(y) \mathrm{d}y\, </math>$ によって <math>$S\, </math>$ の密度関数を求めることができる. [[たたみ込み]]と呼ばれるこれらの方法から, 2つの指数分布の和はガンマ分布になり, 2つの正規分布の和はやはり正規分布になる, といったことがわかる.

'''$<math>n\, </math>$個の確率変数の和'''　$<math>n\, </math>$個の確率変数の和 $<math>S_n=X_1+\ldots+X_n\, </math>$ は理論と応用のいずれにおいても重要な問題を提起してきた. $<math>S_n/n\, </math>$ は算術平均であるから統計処理上頻繁に使われる. $<math>X_1, \ldots, X_n\, </math>$ が互いに独立で同一の分布に従い, 平均 $<math>\mu$\, </math>, 分散 $<math>\sigma^2\, </math>$ をもてば, $<math>S_n/n\, </math>$ の平均は $<math>\mu\, </math>$, 分散は $<math>\sigma^2/n\, </math>$ であるから, $<math>n\rightarrow\infty\, </math>$ のとき $<math>S_n/n\, </math>$ は $<math>\mu\, </math>$ に収束する. このように $<math>S_n/n\, </math>$ が平均に収束することを[[大数の法則]]といい, 収束が概収束か確率収束かに応じて, それぞれ大数の強法則, 大数の弱法則と呼ばれる. 大数の強法則は[[エルゴード理論]]と密接に関係しており, ある種の条件を満たせば $<math>X_1, \ldots, X_n\, </math>$ が独立でなくとも $<math>S_n/n\, </math>$ は $<math>\mu\, </math>$ に収束することが知られている. 独立確率変数列 $<math>X_1, X_2, \ldots\, </math>$ がそれぞれ平均 $<math>\mu\, </math>$, 分散 $<math>\sigma^2\, </math>$ の同じ分布に従う場合, 元の分布が何であっても $<math>\sum_{i=1}^n (X_i-\mu) / \sigma \sqrt{n}\, </math>$ は $<math>n\rightarrow \infty\, </math>$ のとき平均0, 分散1の正規分布に近づく. これを[[中心極限定理]]といい, 確率論における正規分布の重要性の根拠となっている.

----
'''参考文献'''

[1] H. Bauer, ''Probability Theory and Elements of Measure Theory'', 2nd ed., Academic Press, 1983.

[2] M. Loéve, ''Probability Theory I'', 4th ed., Springer, 1977, ''Probability Theory II'', 4th ed., Springer, 1978.

[3] 伊藤清, 『確率論』, 岩波書店, 1991.

[4] 伏見正則, 『確率と確率過程』, 講談社, 1987.

《生物学における進化ゲーム理論》

2007-07-08T16:12:11Z

219.161.35.37:

'''【せいぶつがくにおけるしんかげーむりろん (evolutionary game theory in biology) 】'''

　メーナード・スミス（J. Maynard Smith）はゲーム理論をもとに生物学における進化ゲーム理論を発展させた[1]。最近では社会科学の分野でも進化ゲーム理論は注目を浴びつつあり、社会科学上未解決だった問題を生物学における自然選択のアナロジーを用いて解決しようとしている。

　生物学における進化ゲーム理論では自然選択説による進化が前提となる。まずは重要な指標である「適応度」の定義をしよう。適応度とは、繁殖齢の個体が出産する子供の数にその子供が繁殖齢になるまでの生存率をかけたものである。適応度は生物の置かれた自然環境や生物自身が作り出す社会環境からも影響を受ける。生物個体同士の種内・種間相互作用が適応度に影響を与える時に進化ゲーム理論が適用可能となり、ゲーム理論での利得や効用に当たる尺度として適応度が用いられる。

　自然選択による進化のためには、選択（あるいは淘汰）、変異、遺伝の３つの要素が必要であり、基本的には１つでも欠けると進化は生じない[2][3][4]。例として、集団をある形質A が占めていて、形質Aが「変異」して形質Bが生じる場合を考えてみる。「形質」とは、進化生物学における専門用語であり、各個体に備わっている形や性質である。形質Aを野生型（wild type）、形質Bを突然変異型と呼ぶ。子供へ形質Bが「遺伝」し、形質Aよりも適応度が高ければ、つまり、「選択」（あるいは「淘汰」）が生じれば、形質Bは自然選択によって進化する。もし、形質Aが形質B に取って代わられることがなければ、形質Aは進化的に安定な戦略（ESS: evolutionarily stable strategy）であるという。一般のゲーム理論では、戦略とは各プレイヤーが意思を持って選択する行動計画であるが、進化ゲーム理論ではそうでなく、各個体に備わっている形質そのもの，ないしは形質によって定まる行動を戦略と呼ぶ。

　メイナード・スミスとプライス（J. Maynard Smith and G. R. Price）によると、

:<math>E[A, A] > E[B, A]\, </math>

あるいは、

:<math>E[A, A] = E[B, A] \, </math>かつ<math>E[A, B] > E[B, B]\, </math>

が成り立つときに、戦略Aは進化的に安定であるという[1]。ただし、<math>E[A, B]\, </math>は形質Aと形質Bがゲームをしたときの形質Aの利得（適応度）である。

　以下では、資源を巡る競争を表すタカハトゲームを例に挙げる[1]。各プレーヤーはタカ戦略とハト戦略のどちらかを採る形質を備えている。タカは資源を巡って実際に戦う攻撃的な戦略であり、ハトは平和的に解決する戦略である。両方ハト戦略の場合には資源量<math>V\, </math>を等分する。一方がハトで一方がタカであれば、タカがすべての資源量<math>V\, </math>を得、ハトは何も得られない。両方タカの場合には実際に対戦し体力消耗などのコスト<math>C\, </math>を被るため、平均利得は<math>(V-C)/2\, </math>となる。資源量が対戦コストより大きく<math>V > C\, </math>であれば、進化的に安定な純粋戦略はタカ戦略である。もし資源量より対戦コストが大きく<math>V < C\, </math>であれば、タカもハトも進化的に安定な戦略ではなくなる。混合戦略<math>(p,1-p)\, </math>（<math>p,1-p\, </math>はそれぞれタカ戦略，ハト戦略を用いる確率）まで考えると、混合戦略が進化的安定になる条件を与えるBishop & Cannings(1978) の定理を用いることにより[1]、

:<math>E[\, </math>タカ<math>, ~(p,1-p)] = E[\, </math>ハト<math>, ~(p,1-p)],\, </math>

が成り立たなければならない。この式から<math>p = V/C\, </math> が得られ、<math>(V/C, 1-V/C)\, </math>が進化的に安定な混合戦略となる。

　以上の例では、利得が戦略のみに依存する対称ゲームであったが、性別や年齢、社会的立場によって利得が異なる非対称ゲームとなることもある。例えば、親の性別による子の世話を考えると、父親と母親では適応度が異なってくる。オスの場合は、子育てよりも他のメスと交尾した方が適応度が上昇するかもしれない。メスも世話をするより、沢山の卵を産みっぱなしにして子育てを放棄するという戦略もあり得る。また、子育てによって子供の生存率は上がるならば子育てに専念した方がよいであろう。メーナード・スミス[1]によると、子育てする場合としない場合とでオスが別のメスに出会う確率があまり変わらない場合や、片親で育てた時の子供の生存率が両親で育てた時の生存率よりかなり低いという場合には、両親が子育てすることがESSとなる。また、両親とも子育てしない時の子の生存率がどちらかが子育てする時の生存率よりかなり低い時には片親による子育てが進化的に安定になるが、オスにとって子育てしない方が次の交尾相手に出会う確率が高ければオスが子育てを放棄しメスのみが子育てをする、というような結果が得られている。

　以上ではゲームの利得行列をもとに進化的に安定な戦略を説明したが、各戦略を採用するプレーヤーの頻度の時間変化や進化的に安定な戦略へ収束するまでの集団動態を知るには、リプリケーターダイナミクスが有効である[5]（「進化と学習のゲーム理論」を参照）。ただ、リプリケーターダイナミクスでは、高い利得を得た戦略が世代毎に増えていくことを前提としているが、生物学的に現実に忠実にモデル化しようとすると、このような前提のみでは不十分な場合があるので注意しなければならない[6]。

　以上では形質が離散的に異なる場合であったが、形質が連続量であり突然変異によって形質が徐々に変化していく場合もある。樹高を例に取ると、周囲の木との光を巡る競争ではできるだけ高いほうがよいが、逆に高すぎると維持コストがかかるというトレードオフがあり、進化ゲーム理論によって最適な樹高を計算することができる[7]。

　以下では連続形質の進化的に安定な戦略の定義を説明する。形質<math>x\, </math> (<math>x\, </math>は形質の連続量。たとえば樹高など) の占めている集団へ突然変異型<math>y\, </math>が侵入したときの、突然変異型<math>y\, </math>の適応度関数を<math>\phi (y,x)\, </math>と定義する。ESSである形質を<math>x^*\, </math>とすると、<math>y\, </math>が<math>x^*\, </math>の近傍である時、

:<math>\frac{\partial \phi (y,x)}{\partial y}\Bigg|_{y=x=x^*} =0
\ \ and \ \ \frac{\partial^2 \phi (y,x)}{\partial y^2} \Bigg|_{y=x=x^*} <0\, </math>

つまり<math>\phi (y,x)\, </math>が極大値となる <math>y=x=x^*\, </math>が ESSとなる。連続形質の進化のいま１つの例として性比を考える。多くの生物ではオスメス比が<math>1:1\, </math>であり、これが当たり前のようであるが、オスを少なく産んでメスを多く産んだ方が子孫が多くなるのではないであろうか。そうだとすると何故<math>1:1\, </math>なのであろうか。フィッシャー（R. A. Fisher）は、子供の数だけでなく、孫の数に着目して適応度を定義した上で進化ゲーム理論による解析を行い、任意交配で集団サイズが十分大きな時には性比が<math>1:1\, </math>の状態が進化的に安定であることを示した [2][3][4][7]。

　上記のESSの定義だけでは、いかなる変異型も<math>x^*\, </math>には侵入できないというだけであり、集団の形質値が<math>x^*\, </math> から少しずれただけで安定性が崩れる可能性もある。集団の形質値<math>x\, </math>がESSである<math>x^*\, </math>からずれている時、変異体<math>y\, </math>（ただし、<math>x\, </math>より<math>x^*\, </math>に近い形質値。<math>x < y < x^*\, </math> あるいは <math>x^* < y < x\, </math>）に侵入される場合を連続進化可能な戦略（CSS: continuously stable strategy)という[8]。つまり<math>x^*\, </math>がCSSの時は、変異によって野生型が<math>x^*\, </math>からずれて<math>x\, </math>となっても、時間が経つとまた<math>x^*\, </math>へ戻るのである。

　以上の進化ゲームによる分析では、適応度関数を定義しなければならない。一方、アダプティブ・ダイナミクス（adaptive dynamics）では個体群動態の式（集団中のある形質の頻度の時間変化）から適応度関数<math>\phi (y,x)\, </math>に相当するある関数（invasion fitness）を導出するだけで、ESSやCSSだけではなく共存可能な条件や分岐（branching）条件を得る事が可能となる[9]。

　以上、生物の進化ゲームの紹介をしてきたが、人間も生物の一員である以上は、ある形質に関しては生物進化の観点からの進化ゲーム研究も可能であろう。たとえば言語能力や文化、規範、道徳、制度などについて生物進化の観点からの数理モデル解析が進められている[10][11][12][13]。これらの分析は、従来の研究にはなかった全く新たな視点を与えるものであり、これからの発展が大いに期待されている。

----
'''参考文献'''

[1] J. Maynard Smith, "Evolution and the Theory of Games," Cambridge University Pres, 1982. 寺本英, 梯正之訳, 『進化とゲーム理論』, 産業図書, 1985.

[2] 粕谷英一, 『行動生態学入門』, 東海大学出版会, 1990.

[3] 酒井聡樹, 高田壮則, 近雅博, 『生き物の進化ゲーム』, 共立出版, 1999.

[4] 嶋田正和, 山村則男, 粕谷英一, 伊藤嘉昭, 『動物生態学新版』, 海游舎, 2005.

[5] J. Hofbauer, K. Sigmund, "Evolutionary Games and Population Dynamics," Cambridge University Press, 1998. 竹内康博, 佐藤一憲, 宮崎倫子訳, 『進化ゲームと微分方程式』, 現代数学社, 2001.

[6] M. Nakamaru and Y. Iwasa, "The evolution of altruism by costly punishment in the lattice structured population: score-dependent viability versus score-dependent fertility," ''Evolutionary Ecology Research'', '''7''' (2005), 853-870.

[7] 巌佐庸, 『数理生物学入門』, 共立出版, 1992.

[8] I. Eshel, "Evolutionary and Continuous Stability," ''Journal of Theoretical Biology'', '''103''' (1983), 99-111.

[9] O. Diekmann, ''A Beginner's Guide to Adaptive Dynamics, Mathematical Modelling of Population Dynamics, Banach Center Publications'', Vol. 63, Institute of Mathematics Polish Academy of Sciences, Warszawa, 2004.

[10] L. L. Cavalli-Sforza, M. W. Feldman, ''Cultural Transimission and Evolution: A Quantitative Approach'', Princeton University Press, 1981.

[11] R. Boyd, P. J. Richerson, ''Culture and the Evolutionary Process'', Chicago University Press, 1985.

[12] F. J. Odling-Smee, K. L. Laland, M. W. Feldman, ''Niche construction'', Princeton University Press, 2003.

[13] A. Cangelosi, D. Parisi (Eds), ''Simulating the Evolution of Language'', Springer-Verlag, 2002.

《ゲームの解の計算》

2007-07-08T16:02:28Z

219.161.35.37:

'''【ゲームのかいのけいさん (computation of solutions of games) 】'''

1. 2人ゼロ和ゲームのマックスミニ戦略の計算

　次のような[[利得行列 (ゲームの)|利得行列]]をもつ[[2人ゼロ和ゲーム]]を考える.

:<math>\begin{array}{c|ccc}
& 1 & \ldots & n \\ \hline
1 & a_{11} & \ldots & a_{1n} \\
\vdots & \vdots & \ddots & \vdots \\
m & a_{m1} & \ldots & a_{mn}
\end{array}\, </math>

[[プレイヤー]]1の[[混合戦略]]を<math>p = (p_1, p_2, \ldots, p_m)\, </math>, プレイヤー2の混合戦略を<math>q = (q_1, q_2, \ldots, q_n)\, </math>, <math> 0 \leq p_i, q_j \leq 1 \, </math>, <math>\textstyle \sum_{i=1}^{m} p_i = 1\, </math>, <math>\textstyle \sum_{j=1}^{n} q_j = 1\, </math> とするとき, プレイヤー1の[[マックスミニ戦略]]は, 次の線形計画問題の最適解として得られ, 最適値が[[マックスミニ値]]となる.

:<math>\begin{array}{ll}
\mbox{maximize} & v \\
\mbox{subject to} & a_{1j}p_1 + a_{2j}p_2 + \ldots + a_{mj}p_m \geq v \ (j = 1, 2, \ldots, n), \\
& p_1 + p_2 + \ldots + p_m = 1,\;\; p_1, p_2, \ldots, p_m \geq 0.
\end{array}\, </math>

プレイヤー2の[[ミニマックス戦略]]はこの問題の[[双対問題 (線形計画の)|双対問題]]を解いて求められる. 少なくとも一方のプレイヤーの[[純戦略]]が2個だけである場合には, マックスミニ戦略, ミニマックス戦略はより簡単に計算することができる. 例えば, <math>m=2\, </math>とすると, プレイヤー1のマックスミニ戦略は,

:<math>\max_{0 \leq p_1 \leq 1} \min
\{a_{11}p_1 + a_{21}(1-p_1), a_{12}p_1 + a_{22}(1-p_1),
\ldots , a_{1n}p_1 + a_{2n}(1-p_1) \}\, </math>

の解となる. いま, 各jについて <math>a_{1j}p_1 + a_{2j}(1-p_1)\, </math> のグラフを描き, <math>n\, </math>個のグラフの最小の部分をたどるグラフ (図１(a)の太線) を描く. このグラフの最大値を与える<math>p_1\, </math>を<math>p^*\, </math>とすると, プレイヤー1のマックスミニ戦略は<math>(p^*, 1-p^*)\, </math>で与えられる. 図１(a)は<math>n=3\, </math>の場合である. プレイヤー2については, <math>p^*\, </math>を与える2つの戦略<math>j, j'\, </math>について同様の計算を行ってミニマックス戦略を求めることができる. 詳しくは, 例えば [4] を参照.

2. 非ゼロ和ゲームのナッシュ均衡の計算

　次のような <math>2 \times 2\, </math> の[[利得双行列 (ゲームの)|利得双行列]]をもつ2人[[非ゼロ和ゲーム]]を考える.

:<math>\begin{array}{c|cc}
& 1 & 2 \\ \hline
1 & a_{11}, b_{11} & a_{12}, b_{12} \\
2 & a_{21}, b_{21} & a_{22}, b_{22} \\
\end{array}\, </math>

プレイヤー1, 2の混合戦略を各々 <math>(p, 1-p)\, </math>, <math>(q, 1-q)\, </math>, <math>0 \leq p, q \leq 1\, </math>とする.

　<math>A_1 \equiv a_{11}q+a_{12}(1-q), A_2 \equiv a_{21}q+a_{22}(1-q) \, </math> とおくと, プレイヤー1の利得の期待値 (期待利得) は <math>p A_1 + (1-p) A_2\, </math> となるから, [[最適反応 (ゲーム理論における)|最適反応]]は <math>A_1 > A_2\, </math> のとき <math>p=1\, </math> , <math>A_1 = A_2\, </math> のとき <math>0 \leq p \leq 1\, </math> , <math>A_1 < A_2\, </math> のとき <math>p=0\, </math> となる. 同様にプレイヤー2の最適反応は, <math>B_1 = b_{11}p+b_{21}(1-p), B_2 = b_{12}p+b_{22}(1-p)\, </math> とおいて, <math>B_1 > B_2\, </math> のとき <math>q=1\, </math> , <math>B_1 = B_2\, </math> のとき <math>0 \leq q \leq 1 , B_1 < B_2\, </math> のとき <math>q=0\, </math> となる. 従って, 両者の最適反応は, もし, <math>a_{11}>a_{21}, a_{12}<a_{22}, b_{11}>b_{12}, b_{21}<b_{22}\, </math> であれば, 図１(b) のように表現される.

図１：2人ゲームのマックスミニ戦略およびナッシュ均衡の計算

　[[ナッシュ均衡]]は両者の最適反応の交点 (図１(b)の3つの交点) で与えられるから, この場合には, 純戦略に対応する <math>p=q=1\, </math> と <math>p=q=0\, </math> および, <math>A_1 = A_2\, </math> かつ <math>B_1 = B_2\, </math> を満たす混合戦略に対応する <math>p=(b_{22}-b_{21})/(b_{11}-b_{12} + b_{22}-b_{21})\, </math> , <math>q=(a_{12}-a_{22})/(a_{21}-a_{11} + a_{12}-a_{22})\, </math> の合計3通りのナッシュ均衡が存在する. <math>a_{11}>a_{21}, a_{12}<a_{22}, b_{11}>b_{12}, b_{21}<b_{22}\, </math>以外の場合など, 詳しくは, 例えば [4] を参照.

　<math>2 \times 2\, </math> よりも大きな利得行列をもつ2人非ゼロ和ゲームのナッシュ均衡を求める方法としては, [[シャープレイ(L. S. Shapley)のラベル法シャープレイのラベル法|シャープレイ(L. S. Shapley)のラベル法シャープレイのラベル法]](Shapley's labelling method) [6] がある. <math>3\, </math>人以上のプレイヤーからなる[[戦略形ゲーム]]においては, [[不動点アルゴリズム]]を用いて, ナッシュ均衡の近似値を計算することができる. [7] を参照.

　[[展開形ゲーム]]における[[部分ゲーム完全均衡]], [[完全均衡]], [[逐次均衡]]などの計算については, [4] を参照.

3. 提携形 (特性関数形) ゲームの解の計算

　[[提携形ゲーム]]<math>(N, v)\, </math>の[[コア]]の配分 <math>(x_i)_{i \in N }\, </math>を計算するために, まず <math>2^n-1\, </math> 本の制約式をもつ次の線形計画問題<math>P_1\, </math>を考える (<math>\textstyle |N|=n, x(S)=\sum_{i \in S} x_i \, </math>).

:<math>\begin{array}{lll}
\mbox{minimize} & e \\
\mbox{subject to} & x(S) + e \geq v(S) &
(S \subset N, \ S \neq N, \emptyset), \\
& x(N) = v(N).
\end{array}\, </math>

問題<math>P_1\, </math>の最適解において, <math>e \leq 0\, </math> となっているならば, ゲーム<math>(N, v)\, </math>のコアは空集合ではなく, <math>e \leq 0\, </math> を満たす実行可能解すべてからなる集合がコアとなる. また, コアが空であろうと非空であろうと, 問題<math>P_1\, </math>の最適解の全体はゲーム<math>(N, v)\, \, </math>の[[最小コア (ゲーム理論の)|最小コア]]になる.

　[[仁]]は, 線形計画問題を繰り返し解く[[コペロウィッツ (A. Kopelowitz)のアルゴリズム]] (Kopelowitz' algorithm) [2] によって求められる. まず, 問題<math>P_1\, </math>の最適解における<math>e\, </math>の値を<math>e_1\, </math>とする. もしも最適解が唯一でない場合は, すべての最適解を求め, 不等式制約条件がその全最適解において等号で成立しているような<math>S\, </math>の族を<math>A_1\, </math>とおく. さらに, <math>A_1\, </math>に含まれるすべての<math>S\, </math>に対して問題<math>P_1\, </math>の制約式 <math>x(S) + e \geq v(S)\, </math> を <math>x(S) + e_1 = v(S)\, </math> に置き換えて新たな問題<math>P_2\, </math>をつくり, その最適解を求める. このプロセスを繰り返し, あるステップで, 最適解が唯一であればそれが仁の配分である. このアルゴリズムは<math>n-1\, </math>回以内の繰り返しで必ず終了する. ただし, 1回の繰り返しの中での計算量は膨大になることがある. 仁のより効率的な計算方法については, [1], [5] を参照.

　[[シャープレイ値]]の計算方法については, [3] を参照.

----
'''参考文献'''

[1] G. Bruyneel, "Computation of the Nucleolus of a Game by Means of Minimal Balanced Sets," ''Operations Research Verfahren'', '''34''' (1979), 35-51.

[2] A. Kopelowitz, "Computation of the Kernels of Simple Games and the Nucleolus of n-Person Games," "Research Program in Game Theory and Mathematical Economics", RM 31, The Hebrew University of Jerusalem, 1967.

[3] 武藤滋夫, 小野理恵, 「投票システムのゲーム分析」, 日科技連出版社, 1998.

[4] 岡田章, 「ゲーム理論」, 有斐閣, 1996.

[5] J. K. Sankaran, "On Finding the Nucleolus of an n-Person Cooperative Game," ''International Journal of Game Theory'', '''19''' (1991), 329-338.

[6] L. S. Shapley, "A Note on the Lemke-Howson Algorithm," ''Mathematical Programming Study'', '''1''' (1974), 175-189.

[7] Z. -F. Yang, ''Computing Equilibria and Fixed Points'', Kluwer Academic Publishers, 1999.

《ゲーム理論の応用》

2007-07-08T15:41:48Z

219.161.35.37:

'''【げーむりろんのおうよう (applications of game theory to OR) 】'''

　[[ゲーム理論]]の応用分野は経済学・社会学・政治学・生物学と多岐にわたっているが, 現在もっとも応用が進んでいるのは経済学であると言ってよい. 多くの経済現象を個人の効用最大化に還元して説明しようとする現在の経済理論の方法論は, まさに非協力ゲームと共通している. このため経済学において, 寡占・独占の理論・情報経済学・環境経済学・国際経済学など多くの分野の基礎理論が[[非協力ゲーム理論]]によって説明されている.

　社会・経済現象の描写や叙述などゲーム理論の説明的な面をゲーム理論の応用の中心と考える経済学に比して, 現実の問題をモデル化し意思決定者に対して問題解決のための有益な情報を提供することが目的であるオペレーションズリサーチでは, 「良い解を薦める」というゲーム理論の規範的な面も重視されている. したがって, 規範的な面を持つ[[協力ゲーム理論]]もORでは広く応用されている. 以下, 経済学よりもORの文献等でよく見られるゲーム理論の応用を中心として述べる.

　ゲーム理論の応用としてかなり早い時期に研究が進められたものに[[市場ゲーム]] (market game) がある. 市場ゲームとは各個人が初期財としていくつかの財を保有し, それぞれが財から得られる効用の最大化を求めて財の交換を行うという交換経済を表現した協力ゲームである. もっとも典型的な市場ゲームは細かく分けることのできる分割財の取引を扱う譲渡可能効用を持つ市場ゲームで, この時の[[特性関数 (ゲーム理論の)|特性関数]]の値は, 提携に属する各個人の利得の和が最大になるように財が配分されたときの利得の和の値である. (譲渡可能効用を持たない市場ゲームの特性関数は各提携において実現可能な財の配分の集合である. ) 効用関数における通常の仮定のもとで, このゲームには[[コア]]が存在する. 市場ゲームは財に対する価格を導入することで, 理論経済学における交換経済モデルとして表現できる. この時, 参加する個人を増加(正確には初期保有財など特性が同じである個人を2倍, 3倍, . . . と複製)させたときに, [[競争均衡]] (competitive equilibrium) の配分の集合に収束することが知られている. これを[[極限定理 (ゲームのコアの)|極限定理]] (limit theorem of core) と呼ぶ.

　市場ゲームには家などのように分割できない非分割財を扱った非分割財の交換市場ゲームや, 売り手と買い手が分かれている[[割当て市場ゲーム]] (assignment game) などがある.

　譲渡可能効用を持つ市場ゲームには[[線形生産ゲーム]] (linear production game) と呼ばれるものがある. [3] を参照. これは各プレイヤーを生産者と考え, 各提携は最大限それに属するプレイヤーの持つ財の合計まで利用できると考えて, 線形計画法の生産計画問題で得られる最適値をその提携の特性関数の値と考えた市場ゲームである. 線形生産ゲームでは全員提携に関する線形計画問題の双対問題の解がコアとなる. また線形生産ゲームでは, プレイヤーの有限の複製でコアは競争均衡の配分と一致する. 市場ゲームについて詳しくは [4] を参照.

　[[費用分担ゲーム]] (cost allocation game) は, 何人かのプレイヤーが共同事業を行う場合に, 各プレイヤーがどれだけの費用を分担すべきかを考えるゲームである. 各提携の特性関数の値を, 各提携が単独で事業を行った場合の費用と考える場合と, 各プレイヤーが単独で事業を行った場合の和と提携で行った場合との費用の差として考える場合(節約ゲーム)とがある. 水資源共同開発における費用分担, 大学内での電話料金の分担, 飛行場の滑走路補修費用の機種別分担などの問題を, 仁やシャープレイ値を用いて分析した例が知られている.

　費用分担ゲームの中でも, 各プレイヤーがネットワーク上のグラフ上の点に存在し, グラフ上に費用最小木を張る時に, 各プレイヤーがいかに費用を配分するかの費用分担ゲームは最小木ゲームと呼ばれる. また同様に巡回セールスマン問題で各プレイヤーがグラフ上の点に位置すると考えたときに, 費用をいかに分担するかというゲームは巡回セールスマンゲームと呼ばれる. これらORで良く知られている最適化手法をゲームの状況に拡大した理論は多くあり, 他にも[[探索ゲーム]]や最少費用流ゲームなどが知られている. 線形生産ゲームもその1 つである.

　[[投票ゲーム]] (voting game) は, 議案の可決・否決や候補者の当選・落選など, 「2 つの結果に対する投票」を表現した協力ゲームである. プレイヤーの提携が, 結果を左右することができる場合にその提携を勝利提携と呼び, そうでないものを敗北提携と呼ぶ. 投票ゲームは, 勝利提携に1 , 敗北提携に0 を与えるような[[提携形ゲーム]]としても表現できる. 投票ゲームにおいて投票者の持つパワーを表現する指数を[[パワー指数]]と呼ぶ. シャープレイ・シュービック指数やバンザフ指数などの指数が考えられている. [2] を参照.

　[[仲裁ゲーム]] (arbitration game) は, 報酬契約などの2 人の交渉に仲裁者が存在しているゲームである. まず仲裁者が双方からどのような要求を出させ, どの場合にどのように仲裁するかを決める. 交渉する2人は要求を提出し, 決められたルールに従って利得の受け取り, 支払いを行う. [5] を参照.

　[[入札ゲーム]] (auction game) は, 各プレイヤーが入札対象に持つ事前価値について, その確率分布の情報が事前にプレイヤー間で共有されている状況で, 自分の事後の期待利益が最大になるように入札を行うような非協力ゲームである. プレイヤーの持つ価値がプレイヤーごとに独立で, かつ各プレイヤーはリスク中立である, という仮定をおいた場合には, 最も代表的な入札方法である最高の価格を付けたプレイヤーがその価格で落札するファーストプライス競売と, 最高の価格を付けたプレイヤーが2 番目に高い価格で落札するセカンドプライス競売が, 主催者にもたらす期待利益は等価であることが知られている. これを利潤等価定理という. [1] を参照.

　このようにゲーム理論の適用例は多岐にわたっているが, 最近では, スポーツへの適用も盛んになってきている. たとえば, サッカーのペナルティー・キックにおけるキッカーとゴールキーパーの実際の行動がゲーム理論の均衡概念による理論値ときわめて類似しているという興味ある結果も報告されている [1].

　ゲーム理論の応用例については, 本稿中に挙げたもののほか, [2], [3], [4], [5], [6], [9] などを参照していただきたい.

----
'''参考文献'''

[1] P. A. Chiappori, S. Levitt and T. Groseclose, "Testing Mixed-Strategy Equilibria When Playe.rs are Heterogeneous: The Case of Penalty Kicks in Soccer", ''American Economic Review'', '''92''' (2002), 1138-1151.

[2] A. Dixit and B. Nalebuff, ''Thinking Strategically'', N. W. Norton, 1991. 菅野隆, 嶋津祐一, 『戦略的思考とは何か』, TBSブリタニカ, 1991.

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

[4] 今井晴雄, 岡田章, 『ゲーム理論の新展開』, 勁草書房, 2002.

[5] 今井晴雄, 岡田章, 『ゲーム理論の応用』, 勁草書房, 2005.

[6] 梶井厚志, 松井彰彦, 『ミクロ経済学戦略的アプローチ』, 日本評論社, 2000.

[7] P. Milgrom and R. J. Weber, "The Theory of Auctions and Competitive Bidding", ''Econometrica'', '''50''', (1982), 1089-1122.

[8] 武藤滋夫, 小野理恵, 「投票システムのゲーム分析」, 日科技連出版社, 1998.

[9] 中山幹夫, 武藤滋夫, 船木由喜彦, 『ゲーム理論で解く』, 有斐閣, 2000.

[10] G. Owen, "On the Core of Linear Production Games", ''Mathematical Programming'', '''9''', (1975), 358-370.

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

[12] D. -Z. Zeng, S. Nakamura and T. Ibaraki, "Double-offer Arbitration," ''Mathematical Social Sciences'', '''31''', (1996), 147-170.

《提携形ゲーム》

2007-07-08T15:40:14Z

219.161.35.37:

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

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

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

　[[優加法性 (ゲーム理論における)|優加法性]] (superadditivity) をみたすゲームにおいてはプレイヤー全体による提携Nが形成されると考えられるので<math>v(N)\, </math>の値をどのようにプレイヤー間で分配すべきかが問題となる. このとき, ゲームの解の基本的な条件としては[[全体合理性]] (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) である [12]. 安定集合は[[フォンノイマン・モルゲンシュテルン解]] (von Neumann-Morgenstern solution) とよばれることもある. 安定集合は存在しない場合もあるし, 複数存在する場合もあるが, 存在すればコアを含む. また, コア自身が安定集合であれば, コア以外に安定集合は存在しない.

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

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

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

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

　なお, 提携形ゲーム全般の詳しい解説は [10], [7] などを参照されたい. また, [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] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

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

[9] 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.

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

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

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

《提携形ゲーム》

2007-07-08T07:10:41Z

219.161.35.37:

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

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

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

　[[優加法性 (ゲーム理論における)|優加法性]] (superadditivity) をみたすゲームにおいてはプレイヤー全体による提携Nが形成されると考えられるので<math>v(N)\, </math>の値をどのようにプレイヤー間で分配すべきかが問題となる. このとき, ゲームの解の基本的な条件としては[[全体合理性]] (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) である [12]. 安定集合は[[フォンノイマン・モルゲンシュテルン解]] (von Neumann-Morgenstern solution) とよばれることもある. 安定集合は存在しない場合もあるし, 複数存在する場合もあるが, 存在すればコアを含む. また, コア自身が安定集合であれば, コア以外に安定集合は存在しない.

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

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

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

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

　なお, 提携形ゲーム全般の詳しい解説は [10], [7] などを参照されたい. また, [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] 岡田章, 『ゲーム理論』, 有斐閣, 1996.

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

[9] 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.

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

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

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

《交渉ゲーム》

2007-07-08T07:07:21Z

219.161.35.37:

'''【こうしょうげーむ (bargaining game) 】'''

　交渉は, 複数の当事者が協力の条件を協議する状況であり, 各自が相互依存関係の中で意思決定をするゲームの状況である. [[交渉ゲーム]] (bargaining game) の研究は, ナッシュ (J. F. Nash)による[[2人交渉問題]]の交渉解に始まり, 近年では, ルビンシュタイン (A. Rubinstein) の[[交互オファーゲーム]]による交渉過程の分析が代表的である.

'''1　2人交渉問題と交渉解'''　交渉の結果は, 妥結して協力するか決裂するかであり, 交渉の妥結点は交渉決裂時の状態に依存する. 2人交渉問題は, 2人のプレイヤー間の交渉を, 協力実現可能集合 <math>S\, </math> と交渉の基準点 <math>d\in S\, </math> の組 <math>(S, d)\, </math> として記述する. <math>S\, </math>は２次元実数ベクトル空間の部分集合である. 以下では, ベクトル間の不等号は要素ごとの不等号を意味する.

　協力実現可能集合 <math>S\, </math> は2人が協力して実現可能な[[利得 (ゲームの)|利得]]ベクトル集合であり, 妥結点の候補を表す. 厳密には, 2人のプレイヤーの[[相関戦略]]により実現可能な[[フォンノイマン・モルゲンシュテルン期待効用]]ベクトル <math>(u_{1}, u_{2})\, </math> の集合が <math>S\, </math> である. 交渉問題では, 交渉決裂時は, 各プレイヤーは予め想定された行動を独立に実行し, 交渉の基準点 <math>d=(d_{1}, d_{2})\, </math> の利得を得るとする. 集合 <math>I(S, d)=\{u \in S|u \ge d\}\, </math> を (個人合理的) 交渉領域と呼ぶ. 通常, (1) 集合 <math>S\, </math> がコンパクト凸であり, (2) <math>x>d\, </math> なる点 <math>x \in S\, </math> が存在する, という2条件を満たす交渉問題が考察対象とされ, その集合を <math>B_{0}\, </math> とする. また, (1), (2)に加えて, 「<math>x \in S\, </math> かつ <math>x\ge y\ge d\, </math> ならば, <math>y\in S\, </math>」であり, 「交渉領域の[[弱パレート最適]]な境界線が水平, 垂直部分を持たない」交渉問題の集合を <math>B_{E}\, </math> とする.

　交渉問題の集合 <math>B\, </math> に属す任意の交渉問題 <math>(S, d)\, </math> に, 妥結点 <math>a\in S\, </math> を与える関数 <math>f:B \to {\mathbf{ R}}^{2}\, </math> を, (<math>B\, </math> 上の)[[交渉解]] (bargaining solution) <math>f\, </math> という. 交渉解は妥結方法を示す概念である. ナッシュは合理的妥結方法が満たすべき4つの公理を挙げて, それらを満たす交渉解を分析した.

'''公理1'''　(正アフィン変換からの独立性). 交渉問題 <math>(S, d)\, </math> と <math>(S^{\prime}, d^{\prime})\, </math> が, ある正アフィン変換 <math>y=(c_{1}x_{1}+b_{1}, c_{2}x_{2}+b_{2}), c_{1}, c_{2}>0\, </math>, により一致するとき, 交渉解が両問題に与える妥結点もその変換の下で一致する.

'''公理2'''　(パレート最適性). 交渉解は[[パレート最適]]な妥結点を与える.

'''公理3'''　(対称性). 交渉問題 <math>(S, d)\, </math> が対称的で, <math>(x, y)\in S\Leftrightarrow(y, x)\in S\, </math>, かつ, <math>d_{1}=d_{2}\, </math> ならば, 交渉解の与える妥結点 <math>(a_{1}, a_{2})\, </math> も対称的で, <math>a_{1}=a_{2}\, </math>.

'''公理4'''　(無関連な代替案からの独立性). 基準点が等しい交渉問題 <math>(S, d)\, </math> と <math>(T, d)\, </math> について, <math>T\subseteq S\, </math> かつ <math>f(S, d)\in T\, </math> ならば, <math>f(T, d)=f(S, d)\, </math>.

　公理1は利得の高低やその変化分の大小をプレイヤー間で比較する「個人間効用比較」の排除を求める公理であり, フォンノイマン・モルゲンシュテルン効用が正アフィン変換の下で同値なことからも仮定される. 公理2は交渉結果の効率性を求め, 公理3は, 交渉状況が対称的ならば妥結点も対称的であることを求めている. 公理4は, 妥結点とならなかった代替案を除いて, 再び交渉し直しても妥結点は変わらないことを求める公理である. ナッシュは, 交渉問題の集合 <math>B_{0}\, </math> 上で, 公理1-4を満たす交渉解が一意に定まることを証明した. [[ナッシュ解]]と呼ばれるその交渉解 <math>f^{{\rm N}}\, </math> は, 交渉領域内で2人のプレイヤーの基準点からの利得増加分の積を最大化する点を妥結点とし, <math>f^{\rm N}(S, d)= {\rm argmax}_{u\in I(S, d)}(u_{1}-d_{1})(u_{2}-d_{2})\, </math> で与えられる [3].

図1：交渉問題の妥結点

　ナッシュ解の妥結点は, 公理系では仮定されないが, 個人合理的である. 図1は, ナッシュ解の妥結点と各公理の関係を示している. まず, 対称的交渉問題では, 公理2, 3から, <math>f^{{\rm N}}(S^{0}, d)=C^{\prime}\, </math>, <math>f^{{\rm N}}(S^{1}, d)=A\, </math> となる. 次に, <math>f^{{\rm N}}(S^{0}, d)=C^{\prime}\, </math> ならば, 公理1から, <math>f^{{\rm N}}(S^{3}, d)=C\, </math> となる. そして公理4から, <math>f^{{\rm N}}(S^{2}, d)=f^{{\rm N}}(S^{3}, d)=C\, </math> となる. 問題 <math>(S^{2}, d)\, </math> は問題 <math>(S^{1}, d)\, </math> よりも交渉領域が広いが, プレイヤー2の妥結点利得は減少している. よって, ナッシュ解の妥結点は単調的には推移しない.

　個人間効用比較を排除する公理1の下で, 妥結点の単調性を求めた交渉解として, [[カライ・スモルディンスキー解]] (Kalai-Smorodinsky solution, 以下<math>{\rm KS}\, </math>解と略す) がある. <math>{\rm KS}\, </math>解では, 基準点に加え, 交渉の理想点 (各プレイヤー <math>i\, </math> が交渉領域で獲得できる最大利得 <math>m_{i}={\rm max}\{u_{i}|u\in I(S, d)\}\, </math> の組 <math>M=(m_{1}, m_{2})\, </math>) が考慮される. いま, 「基準点と理想点が共に等しい問題 <math>(S, d)\, </math> と <math>(T, d)\, </math> について, <math>T\subseteq S\, </math> ならば, <math>f(S, d) \ge f(T, d)\, </math>」という条件を限定単調性の公理と呼ぶと, 交渉問題の集合 <math>B_{0}\, </math> 上で, 公理1-3, かつ, 限定単調性を満たす交渉解が一意に定まる [2]. この解が<math>{\rm KS}\, </math>解であり, 基準点と理想点を結ぶ線分と交渉領域のパレート最適な境界線との交点を妥結点とする. 以下, <math>{\rm KS}\, </math>解を <math>f^{{\rm KS}}\, </math> で表す.

　ナッシュ解と <math>{\rm KS}\, </math> 解の一意性から, 公理4と限定単調性の公理は両立しない. これは, ナッシュ解と<math>{\rm KS}\, </math>解が, 異なる観点から各々合理的な妥結方法であることを示す. 先の問題 <math>(S^{2}, d)\, </math> の理想点は <math>{\rm M}^{1}\, </math> なので, <math>f^{{\rm KS}}(S^{2}, d)=B\, </math> となる. しかし交渉領域が <math>S^{3}\, </math> に広がると, <math>f^{{\rm KS}}(S^{3}, d)=C\, </math> となり, 再びプレイヤー2の妥結点利得は減少する. これは公理1のためで, <math>f^{{\rm KS}}(S^{0}, d)=C^{\prime}\, </math> 故に, <math>f^{{\rm KS}}(S^{3}, d)=C\, </math> となるのである.

\begin{table}[t]
表１：各交渉解とその妥結点 (図１参照)} \label{a-g-07-t1}
\begin{center}
\begin{tabular}{cccc}
\hline\hline
交渉問題 & ナッシュ解 & {\rm KS}解 & 均等解\cr\hline\hline
(S^{1}, d) & {\rm A} & {\rm A} & {\rm A}\cr\hline
(S^{2}, d) & {\rm C} & {\rm B} & {\rm B}\cr\hline
(S^{3}, d) & {\rm C} & {\rm C} & {\rm B}\cr\hline\hline
\end{tabular}
\end{center}
\end{table}

　個人間効用比較が可能な交渉状況を考え, 公理1を要件としなければ, より強い単調性を満たす[[均等解]] (egalitarian solution) が公理化される. 条件「基準点が等しい交渉問題 <math>(S, d)\, </math> と <math>(T, d)\, </math> について, <math>T\subseteq S\, </math> ならば, <math>f(T, d)\le f(S, d)\, </math>」を単調性の公理と呼ぶと, 交渉問題の集合 <math>B_{E}\, </math> 上で, 公理2, 3, かつ, 単調性を満たす交渉解が一意に定まる. その交渉解は交渉領域内で各プレイヤーの基準点からの利得増加分を等しく最大化する点であり, 均等解と呼ばれる [2]. ただし, 考察する集合を<math>B_0\, </math>とすると, 均等解は必ずしもパレート最適ではない. 以上3つの交渉解を図1の例によって整理すると, 表1のようになる.

'''2　交互オファーゲーム'''　[[交互オファーゲーム]]は, 2人のプレイヤーが所与の価値の分配, 例えば, 分割可能な財1単位の分配について, 相手が了承するまで, 繰り返し交互に分配案を提示しあっていくゲームである.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.8, bb=68pt 590pt 266pt 722pt, clip]{0075-a-g-07f2-mof.eps}
\end{center}

図２：財分配の実現可能集合

\end{figure}

　いま, 各プレイヤー <math>i\, </math> は, <math>x\, </math> 単位の財から利得 <math>U_{i}(x)\, </math> を得て, 利得関数 <math>U_{i}\, </math> は連続狭義単調増加で凹, かつ, <math>U_{i}(0)=0\, </math> とする. すると, 2人に実現可能な利得の集合は, <math>P=\{(U_{1}(x), U_{2}(1-x))|1\ge x\ge 0\}\, </math> となり, 図2の曲線 <math>AB\, </math> のようになる.

　ゲームは次のように進行する. まず第1期に, プレイヤー1が, 分配案として, 集合 <math>P\, </math> 上の1点 <math>(u_{1}, u_{2})\, </math> をプレイヤー2に提示する. プレイヤー2が了承すれば, 分配案が実現してゲームは終了し, 却下した場合には, 第2期に入る. 以下, 次の期に入る毎にプレイヤーの役割が交代されて, 第1期と同様な手番でゲームが進行する.

　2人は共通の割引率 <math>\delta\in(0, 1)\, </math> を持つとし, プレイヤー <math>i\, </math> が, 第 <math>t\, </math> 期に利得 <math>u_{i}\, </math> を得た場合の現在利得は, <math>\delta^{t-1}u_{i}\, </math> であるとする. そして, これを交互オファーゲームの利得とする. 2人が永久に分配案を了承しない場合のゲームの利得は0とする.

　ルビンシュタインは, この交互オファーゲームの[[部分ゲーム完全均衡]]利得<math>u^*=(u_1^*, u_2^*)\, </math>は一意に定まり, <math>\delta\rightarrow 1\, </math>のとき, <math>u^*\, </math>は<math>P\, </math>の上で<math>u_1u_2\, </math>を最大にする点に収束することを証明した [1].

　この結果から, 割引率が1に収束するとき, 均衡利得 <math>u^{*}\, </math> は, 集合 <math>P\, </math> をパレート最適集合に持つ協力実現可能集合と基準点が <math>d=0\, </math> である交渉問題の, ナッシュ解の妥結点となることが分かる. つまり, 合意遅延のコストが十分小さい場合, 交互オファーゲームは, ナッシュ解の具体的交渉過程モデルの1つとなる. [[ナッシュプログラム]]参照)

　ナッシュ解のみでなく, <math>{\rm KS}\, </math>解や均等解についても, その非協力ゲームモデルを与える研究が行われている. そして, <math>n\, </math> 人交渉問題の交渉解や情報不完備な非協力交渉ゲームの研究も進んでいる [1], [2].

----
'''参考文献'''

[1] M. Osborne and A. Rubinstein, ''Bargaining and Markets'', Academic Press, 1990.

[2] W. Thomson, "Cooperative Models of Bargaining," in ''Handbook of Game Theory with Economic Applications'' ed. by R. Aumann et al, 1992, vol. 2, 1238-1284.

[3] J. Nash, "The Bargaining Problem," ''Econometrica'', '''18''' (1950), 155-162.

《協力ゲーム理論》

2007-07-08T06:49:24Z

219.161.35.37:

'''【きょうりょくげーむりろん (cooperative game theory) 】'''

1　協力ゲーム理論

　[[プレイヤー]]間で話し合いが行われ, 話し合いの結果到達した合意に拘束力がある状況を協力ゲームといい, このような状況を扱う理論を

　[[協力ゲーム理論]] (cooperative game theory) という. 協力ゲームは, プレイヤーの数が2人か3人以上かによって大きく状況が異なり, それぞれ別々に理論が発展してきている.

2　2人協力ゲーム

　プレイヤーが2人の場合には, 2人のプレイヤーが話し合いの結果協力して行動するかどうか, また, 協力した場合には, その結果得られる利得をどのように分配するかの交渉が問題になる. 従って, 2人協力ゲームを[[2人交渉問題]] と呼ぶこともある.

　2人協力ゲームの主たる解は, ナッシュ (J. F. Nash) によって与えられたもので, [[ナッシュ解]] ないしはナッシュ交渉解と呼ばれている. ナッシュは, 公理論的なアプローチによりナッシュ解を導いた. まず, 2人のプレイヤーが協力して実現できる [[利得 (ゲームの)|利得]]の対の全体と, 交渉が決裂したときに2人のプレイヤーが得る利得を明らかにし, これによって2人のプレイヤーの交渉の場を定めた. 前者を実現可能集合, 後者を交渉の基準点という. ついで, 交渉の妥結点が満たすべき性質を4つあげ, その4つの性質をすべて満たす解は, 交渉の場の中の唯1つの利得の対に定まり, 交渉の基準点からの2人のプレイヤーの利得の増分の積を最大にする点で与えられることを示した. これがナッシュ解である.

　ナッシュは, 1つの交渉のプロセスとして, 2人のプレイヤーがそれぞれの獲得したい利得を同時に言い合う非協力ゲームを考え, そのナッシュ均衡によってナッシュ解を達成できないかと考えた. ナッシュのこの試みは, 協力ゲームの解を非協力ゲームの均衡点として分析しようとする[[ナッシュプログラム]] の始まりであった. 後に, ルビンシュタイン(A. Rubinstein) が, 2人のプレイヤーが交互に2人の取り分を提示しあい, 提示された方がそれに同意すればゲームは終了し, 同意しなければそのプレイヤーが新たな提示を行うという[[交互オファーゲーム]]を提案し, 将来の利得がそれほど割り引かれない場合には, その[[部分ゲーム完全均衡]] としてナッシュ解が達成されることを示した.

　ナッシュ解は, 労使の賃金交渉, 商品の売り手と買い手の交渉, 2国間の交渉など, 様々な交渉の分析に用いられている.

3　多人数協力ゲーム

　3人以上の協力ゲームになると, 単に全員が協力するかどうかだけではなく, 部分的な協力関係を考える必要が生じ, 状況は2人協力ゲームに比べ複雑になる. 3人以上の協力ゲームは, 一般に<math>n\, </math>人協力ゲームと呼ばれる. 協力ゲームにおける関心は, プレイヤー間でどのような協力関係が結ばれ, その結果得られた利得をプレイヤー間でどのように分け合うか, ないしは分け合うべきかということである.

　フォンノイマン (J. von Neumann) とモルゲンシュテルン (O. Morgenstern) は, <math>n\, </math>人協力ゲームにおいて, 協力関係を結んだプレイヤーのグループを[[提携]] と呼び, 提携それぞれに対して, それが獲得できる利得を与える関数を [[特性関数 (ゲーム理論の)|特性関数]]と呼んだ. [6] 特性関数によって表現された<math>n\, </math>人協力ゲームを[[提携形ゲーム]]ないしは特性関数形ゲームという.

　提携形ゲームでは, 特性関数の[[優加法性 (ゲーム理論における)|優加法性]]からプレイヤー全員の提携が形成されることは前提とし, 全員が協力したときに得られる利得をどのように分配すればよいかということがこれまでの主たる研究のテーマであった.

　提携形ゲームにおける最初の解は, フォンノイマンとモルゲンシュテルンによるものであり, [[安定集合]]ないしはフォンノイマン・モルゲンシュテルン解と呼ばれている. 提携形ゲームにおいては, プレイヤー間の利得分配の基準をどのように与えるかによって, これ以外にも, [[コア]], [[交渉集合]], [[カーネル (ゲーム理論における)|カーネル]], [[仁]], [[シャープレイ値]]など,

　様々な解が提案されてきている. 安定集合, コア, 交渉集合, カーネルは一般に集合として与えられる解であり, 仁, シャープレイ値は唯1点からなる解である.

　これらの解のうち, 適用例が多いのは, どの提携にも不満を持たせない利得の分配であって, その考え方が受け入れられやすいコア, および1点からなる解である仁, シャープレイ値である. コアは, 経済学において, 市場における取引の分析など様々な分野で用いられており, 経済学における1つの重要な解概念となっている.

　仁, シャープレイ値は費用分担, 便益分配などの計画問題の解決案としてよく用いられている. よく知られた例としては, 水資源共同開発における費用分担, 大学内の電話料金の分担, 飛行場の滑走路補修費用の機種別分担などがある. また, シャープレイ値はプレイヤーの力関係を反映する解であるため, 議会における政党の影響力を評価するパワー指数としても用いられている.

4　協力ゲームの最近の発展

　協力ゲームにおける最近の理論的発展の主たるものは, 提携形成の分析であろう. これまでの提携形ゲームの研究では, プレイヤーの交渉を通してどのような提携が形成されるかという問題はほとんど分析されてこなかったが, 最近になって, ようやく提携形成の研究が盛んに行われるようになってきている. 協力ゲームの様々な解を用いるもの, 非協力ゲームからのアプローチを試みるもの, など様々なアプローチがある.

　いま1つの研究の方向は, [[戦略形ゲーム]], [[展開形ゲーム]]を用いた協力行動の分析である. これまでの協力ゲームの分析は, 提携形ゲームを用いたものがほとんどであった. しかしながら, 戦略形ゲーム, 展開形ゲームにおいてプレイヤーが共同で戦略を選択することも考えられ, これによって, 協力行動を分析することもできる. このような分析はなにも新しいものではないが, 提携形では分析し得ないプレイヤー間の協力関係を分析する方法として重要なものとなるであろう.

　以上の2つの方向の研究を進める上ではもちろんのこと, 今後, 協力ゲーム理論と[[非協力ゲーム理論]]の融合をはかることは, ゲーム理論の発展の上で非常に重要であると思われる.

5　協力ゲーム理論の文献

　協力ゲーム理論を扱った日本語の文献としては [5], また, 最近のものとしては [4], [3], [2] がある. 協力ゲームの解についてのこれまでの研究のサーベイは, [1] に詳しい.

----
'''参考文献'''

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

[2] 中山幹夫, 『はじめてのゲーム理論』, 有斐閣, 1997.

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

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

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

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

《進化と学習のゲーム理論》

2007-07-08T06:45:34Z

219.161.35.37:

'''【しんかとがくしゅうのげーむりろん (evolutionary game theory and learning in game theory) 】'''

　伝統的な[[ゲーム理論]]では, 他の[[プレイヤー]]の[[利得関数]]などゲームの構造を熟知した「合理的」なプレイヤー像を想定してきた. そして, [[非協力ゲーム理論]]における中心的な解である[[ナッシュ均衡]]は, このような合理的なプレイヤーの[[利得 (ゲームの)|利得]]最大化行動の結果達成されると考えられてきた. しかしながら, ゲーム理論の考察の対象は, 必ずしも合理的な意思決定主体に限られない. 実際, ゲームの構造を完全には知らず, ある一定の行動規則に従って行動する「[[限定合理的]]」なプレイヤーを想定し, 彼らの意思決定の過程を記述する様々な動学モデルが存在する. そして, これらの動学モデルの定常状態はナッシュ均衡と密接な関連があることが明らかになってきている. 本項目では, この種の動学モデルのうち代表的なものとして, 1　[[自己複製子動学]] (replicator dynamics), 2　[[確率的進化 (ゲーム理論における)|確率的進化]] (stochastic evolution), 3　[[仮想プレイ]] (fictitious play) の3つをとりあげて解説する.

1　自己複製子動学：<math>n\times n\, </math> 行列 <math>A\, </math> をプレイヤー1の利得行列とし, <math>A\, </math>の転置行列<math>A^{\top}\, </math>をプレイヤー2の利得行列とする2人ゲーム<math>G\, </math>(以下, 2人対称ゲームと呼ぶ)が, 非常に大きな母集団からその都度ランダムに選ばれた2人のプレイヤーによって, 繰り返しプレイされる状況を考える. 時点 <math>t\, </math> において, 母集団の中で[[純戦略]] <math>i\, </math> (<math>i=1, \dots, n\, </math>) をとるプレイヤーの比率を <math>x_i(t)\, </math>とする. <math>x(t)=(x_1(t), \dots, x_n(t))\, </math>の全体を<math>{\mathit\Delta}^n\, </math> とする. <math>{\mathit\Delta}^n=\{x(t)=(x_1(t), \dots, x_n(t)) | x_1(t)+\cdots+x_n(t)=1, x_1(t), \dots, x_n(t)\ge 0\}\, </math>である. このとき, <math>{\mathit\Delta}^n\, </math> 上の微分方程式系

:<math>\frac{\dot x_i}{x_i}=(Ax)_i-x\cdot Ax\, </math>

を自己複製子動学という. ここで, "<math>\cdot\, </math>" は内積を, <math>(Ax)_i\, </math> は <math>Ax\, </math> の第 <math>i\, </math> 成分をあらわす. これは, 純戦略 <math>i\, </math> を使うプレイヤーの成長率が, その戦略を使ったときの利得とすべての戦略の利得の平均値との差であるというモデルである. このモデルは, 数理生物学においてダーウィン的自然選択の自然なモデル化とみなされている.

　いま, もとの2人対称ゲームにおいて, [[混合戦略]]の組<math>(x, x), x\in{\mathit\Delta}^n\, </math>, がナッシュ均衡, 即ち, 任意の<math>y\in{\mathit\Delta}^n\, </math>に対して, <math>x\cdot Ax \ge y\cdot Ax\, </math> であり, さらに, <math>x\cdot Ax=y\cdot Ax\, </math> である任意の <math>y\in{\mathit\Delta}^n\, </math>に対して, <math>x\cdot Ay >y\cdot Ay\, </math> となるとき, 戦略<math>x\, </math>を[[進化的安定戦略]] (evolutionarily stable strategy) という. 進化的安定戦略であるための条件は, 十分小さな<math>\epsilon >0\, </math>に対して, <math>x\cdot Az>y\cdot Az\, </math>, ただし<math>z=(1-\epsilon)x+\epsilon y\, </math>, と書き変えることができ, 他の戦略yの進入に対して<math>x\, </math>が安定であることを表している. 進化的安定戦略<math>x\, </math>は自己複製子動学において漸近安定である, つまり, <math>x\, </math>においてどのような小さな摂動を受けたとしても, それが十分小さければまた<math>x\, </math> に戻る動きが導かれる, ことが示されている. 自己複製子動学とナッシュ均衡の関係などより詳しくは, [3], [9] を参照.

2　確率的進化：前項と同様, <math>n\times n\, </math> 行列 <math>A\, </math>をプレイヤー1の利得行列とし, <math>A\, </math>の転置行列<math>A^{\top}\, </math>をプレイヤー2の利得行列とする2人対称ゲーム <math>G\, </math> を考え, このゲーム<math>G\, </math>が, <math>N\, </math>人 (<math>N>2\, </math>)の母集団からその都度ランダムに選ばれた2人のプレイヤーによって繰り返しプレイされるとする.

　まず, 動学過程の状態集合として <math>\textstyle S=\{s=(s_1, \dots, s_n)|\sum_is_i=N, s_i\, </math>\ は自然数<math>\}\, </math> をとる. <math>s_i\, </math> は純戦略 <math>i\, </math> (<math>i=1, \ldots, n\, </math>) をとるプレイヤーの人数である. 任意の <math>s\in S\, </math> および <math>i\, </math> (<math>i=1, \ldots, n\, </math>)について, <math>\textstyle x_i(s)=\frac{1}{N-1}(s_1, \dots, s_i-1, \dots, s_n)\in{\mathit\Delta}^n\, </math> とする. <math>x_i(s)\, </math> は, プレイヤー <math>i\, </math> から見た状態 <math>s\, </math> における他者の戦略分布である. <math>t\, </math> 期の状態が <math>s\in S\, </math> とき, 戦略 <math>i\, </math> をとるプレイヤーは <math>t+1\, </math> 期に, 確率 <math>1-\epsilon\, </math>で<math>x_{i}(s)\, </math>に対する[[最適反応 (ゲーム理論における)|最適反応]]戦略<math>s\, </math>を選択し, 確率 <math>\epsilon\, </math> である外生的に与えられた確率分布 <math>q=(q_1, \dots, q_n)\, </math>にしたがって戦略を選択するものとする. ここで, <math>\epsilon>0\, </math> かつ <math>q_1, \dots, q_n>0\, </math> である. これは, 戦略の選択にあたって確率 <math>\epsilon\, </math> で「ミス」または「突然変異」が起こることを表している.

　このモデルは状態の集合 <math>S\, </math> 上の唯1つの定常確率分布 <math>\mu_\epsilon\, </math>を持つ有限マルコフ連鎖を導く. いま, <math>\epsilon\to 0\, </math> としたときの極限分布<math>\textstyle \mu^*=\lim_{\epsilon\to 0}\mu_\epsilon\, </math> について, <math>\mu^*(s)>0\, </math> となる状態<math>s\, </math>を確率的安定状態という. 確率的安定状態に対応するゲーム <math>G\, </math>の戦略分布は, この動学過程を十分長期に観察した場合に, 最も頻繁に観察される戦略分布である. 確率的安定状態の集合は, <math>\epsilon=0\, </math>の場合のこの過程の再帰集合の1つとなる. <math>\epsilon=0\, </math>の場合の再帰集合は一般に複数個存在するので, 確率的安定性は複数の再帰集合から「もっとも起こりやすい」ものを1つ特定することとなる. 特に, <math>G\, </math>が[[狭義ナッシュ均衡]]を複数個持つ場合, 一般にこの中の唯1つが確率的安定状態に対応する. 従って, 確率的安定性により複数個の狭義ナッシュ均衡から1つを選び出すことができる. 確率的安定な状態に対応するナッシュ均衡を, [[確率的安定均衡 (ゲーム理論の)|確率的安定均衡]] (stochastically stable equilibrium)という. 確率的進化については, [2], [7], [8], [10] が詳しい.

3　仮想プレイ：<math>n\, </math> 人[[戦略形ゲーム]] <math>G=(N=\{1, \ldots, n\}, S_1, \ldots, S_n, u_1, \ldots, u_n)\, </math> が <math>t=1, 2, \ldots\, </math>の各期にプレイされる状況を考える. <math>t\, </math> 期に実現した戦略の組を <math>x^t=(x^t_1, \dots, x^t_n)\, </math> とすると, <math>t\, </math> 期までにとられた戦略の組の列 <math>h^t=(x^1, \dots, x^t)\, </math> によってプレイヤー <math>j\, </math> が戦略集合 <math>S_j\, </math> の各戦略を<math>t\, </math>期までにとった頻度の分布が定まる. これを<math>p_j^t\, </math>で表す.

　<math>p_{-i}^t\, </math> を <math>i\, </math>以外のプレイヤー<math>j\, </math>に関する <math>p_j^t\, </math> の直積分布とする. 各プレイヤー <math>i\, </math> が, <math>t+1\, </math> 期において <math>p_{-i}^t\, </math> に対する最適反応戦略 <math>x^{t+1}_i\, </math> をプレイすることにより, <math>x^{t+1}=(x^{t+1}_1, \dots, x^{t+1}_n)\, </math> が定まる. <math>t=1\, </math> 期の戦略は初期状態として外生的に与えられるとする. 以上のように戦略が選択されていく動学過程を仮想プレイとよぶ.

　任意の <math>i\, </math> について <math>\textstyle p_{i}^*=\lim_{t\to\infty}p_{i}^t\, </math> が存在するとき, 仮想プレイは収束するという. 仮想プレイが収束するならば, <math>(p_{1}^*, \dots, p_{n}^*)\, </math> はゲーム <math>G\, </math> のナッシュ均衡である. 2人ゼロ和ゲームや2人のプレイヤーがそれぞれ2つの純戦略を持つ <math>2\times 2\, </math> ゲームにおいては, 仮想プレイは収束することが知られているが, 一般には仮想プレイは収束するとは限らない. 仮想プレイが収束しないゲームの例として, シャープレイ(L. S. Shapley)の <math>3\times 3\, </math> ゲームの例が有名である. 仮想プレイの詳細および一般化については, [1], [2], [6]が詳しい.

　なお, 他のプレイヤーの戦略などに対する予想を, ゲームの繰り返しを通じて逐次ベイズ的に更新していく合理的なプレイヤーを想定した学習モデルもある. [4] および [5] を参照されたい.

----
'''参考文献'''

[1] D. Fudenberg and D. Kreps, "Learning Mixed Equilibria," ''Games and Economic Behavior'', '''5''' (1993), 320-367.

[2] D. Fudenberg and D. Levine, ''The Theory of Learning in Games'', MIT Press, 1998.

[3] J. Hofbauer and K. Sigmund, ''Evolutionary Games and Population Dynamics'', Cambridge University Press, 1988. 竹内康博, 「生物の進化と微分方程式」, 現代数学社, 1990.

[4] J. S. Jordan, "Bayesian Learning in Normal Form Games," ''Games and Economic Behavior'', '''3''' (1991), 60-81.

[5] E. Kalai and E. Lehrer, "Rational Learning Leads to Nash Equilibria," ''Econometrica'', '''61''' (1993), 1019-1046.

[6] P. Milgrom and J. Roberts, "Adaptive and Sophisticated Learning in Normal Form Games," ''Games and Economic Behavior'', '''3''' (1991), 82-100.

[7] L. Samuelson, ''Evolutionary Games and Equilibrium Selection'', MIT Press, 1997.

[8] F. Vega-Redondo, ''Evolution, Games, and Economic Behavior'', Oxford University Press, 1996.

[9] J. Weibull, ''Evolutionary Game Theory'', MIT Press, 1995. 大和瀬達二監訳, 「進化ゲームの理論」, 文化書房博文社, 1998.

[10] H. P. Young, ''Individual Strategy and Social Structure'', Princeton University Press, 1998.

《展開形ゲーム》

2007-07-08T06:24:48Z

219.161.35.37:

【てんかいけいげーむ (game in extensive form) 】

　[[展開形ゲーム]] (game in extensive form) はプレイヤーの手番の系列を[[ゲームの木]] (game tree) を用いて表現するモデルである. ゲームの木 <math>K\, </math> はグラフ理論でいう有向木で, 木の分岐点はプレイヤーが選択肢を選ぶ手番, 枝は[[プレイヤー]]の選択肢あるいは行動を表す. 木の始点から終点までの経路をゲームの1つのプレイという.

　プレイヤー分割 <math>P=[P_{0}, P_{1}. \cdots, P_{n}]\, </math> は, ゲームの木 <math>K\, </math> の分岐点の全体を <math>n+1\, </math> 個の部分集合に分割する. <math>P_{i}\ (i=1, 2, \cdots, n)\, </math> はプレイヤー <math>i\, </math> の手番の集合を表す. <math>P_{0}\, </math> に含まれる手番は偶然手番とよばれ, プレイヤーの意思とは無関係な偶然機構によって枝が選択される. 天候やトランプゲームでランダムにカードを配るなどは, 偶然手番の典型的な例である. 偶然手番に対しては枝の選択を行なう確率分布 <math>p\, </math> が付与される.

　ゲームの情報分割 <math>U=[U_{0}, U_{1}, \cdots, U_{n}]\, </math> は,プレイヤー分割<math>P\, </math> の細分割である.各 <math>i=1, 2, \cdots, n\, </math> に対して <math>U_{i}=[u_{i1}, u_{i2}, \cdots, u_{im_{i}}]\, </math>はプレイヤー <math>i\, </math> の手番の集合 <math>P_{i}\, </math> を <math>m_{i}\, </math> 個の非空な部分集合に分割する. <math>U_{i}\, </math> に属する部分集合 <math>u_{ij}\ (j=1, 2, \cdots, m_{i})\, </math> をプレイヤー <math>i\, </math> の[[情報集合]] (information set) という.プレイヤーは行動を選択するとき,自分の手番がどの情報集合に属するかは知っているが,情報集合の中のどの分岐点であるかは知らない.

　ゲームの[[利得関数]] <math>h\, </math> は,ゲームの木 <math>K\, </math> の各終点 <math>z\, </math> に対してプレイヤーの[[利得 (ゲームの)|利得]]ベクトル <math>h(z)=(h_{1}(z), h_{2}(z), \cdots, h_{n}(z))\, </math> を対応させる.

　形式的には, 展開形ゲーム <math>\Gamma\, </math> は以上の5つの要素の組 <math>(K, P, p, U, h)\, </math> によって定義される. これらの5つの構成要素をゲームのルールという.

図１：展開形ゲーム

　展開形ゲームの例として図1を考える.プレイヤー1と2の情報分割はそれぞれ <math>U_{1}=[u_{1}], U_{2}=[u_{21}, u_{22}]\, </math> である.図1では最初にプレイヤー1がRとLの2つの行動のうち1つを選択する. 次に, プレイヤー2はプレイヤー1の選択を知った上で, RとLのうちから1つの行動を選択する.ゲームは4つの終点をもち, 終点に付与されている利得ベクトルは上の数字がプレイヤー1の利得, 下の数字がプレイヤー2の利得を表す.

　図1のゲームのように, プレイヤーのすべての情報集合がただ1つの分岐点から成るゲームを[[完全情報ゲーム]] (game with perfect information) といい, そうでないゲームを不完全情報ゲーム (game with imperfect information) という. 完全情報ゲームでは, すべての手番においてプレイヤーはゲームの過去のプレイの経過を完全に知った上で行動を選択できる. チェスや将棋は完全情報ゲームである.

　展開形ゲームの部分木でそれ自身が展開形ゲームの構造をもつものを部分ゲームという. 図1のゲームは, 情報集合 <math>u_{21}\, </math> と <math>u_{22}\, </math> から始まる2つの部分ゲームをもつ.

　プレイヤー <math>i\, </math> の各情報集合 <math>u\in U_{1}\, </math> に対して <math>u\, </math> における選択肢の集合上の1つの確率分布 <math>b_{i}(u)\, </math> を対応させる関数 <math>b_{i}\, </math> をプレイヤー <math>i\, </math> の[[行動戦略]] (behavior strategy) という. 特に, すべての情報集合に対して1つの選択肢を確定的に対応させる行動戦略を[[純戦略]]という.

　例えば, 図1のゲームにおいて, プレイヤー1の純戦略 <math>\pi_{1}\, </math> はRとLの2通りであり, プレイヤー2の純戦略 <math>\pi_{2}\, </math> は, RR, RL, LR, LLの4通りである. ただし, 前の文字は情報集合 <math>u_{21}\, </math> でとる行動, 後の文字は情報集合 <math>u_{22}\, </math> でとる行動を表す. 図1の展開形ゲームから, プレイヤーの純戦略と利得の関係によって図2のような[[戦略形ゲーム]]を作ることができる.

図2：図1の展開形ゲームから作られた戦略形ゲーム

<math>\begin{figure}[ht]
\begin{center}
\begin{tabular}{|c|cccc|}
\hline
& LL & LR & RL & RR\\ \hline
R & 1, 1^{*} & 1, 1^{*} & -2, 0 & -2, 0\\ \hline
L & -1, 0 & 0, 1 & -1, 0 & 0, 1^{*}\\ \hline
\end{tabular}
\end{center}
\end{figure}\, </math>

　プレイヤーの行動分析のための最も基本的なゲームの解の概念は, ナッシュ (J. F. Nash) によって定義された非協力均衡点である. 一般に[[ナッシュ均衡]]と呼ばれている. 展開形ゲームの行動戦略の組 <math>b^{*}=(b_{1}^{*}, b_{2}^{*}, \cdots, b_{n}^{*})\, </math> がナッシュ均衡であるとは,すべてのプレイヤー <math>i=1, 2, \cdots, n\, </math> のすべての行動戦略 <math>b_{i}\, </math> に対して,

:<math>H_{i}(b^{*}) \ge H_{i}(b^{*}/b_{i})\, </math>
　

が成り立つことである. ただし, <math>b^{*}/b_{i}\, </math> は <math>b^{*}\, </math> からプレイヤー <math>i\, </math> だけが戦略を <math>b_{i}^{*}\, </math> から <math>b_{i}\, </math> に変更してできる行動戦略の組を表し, <math>H_{i}\, </math> はプレイヤー i の期待利得関数を表す.

　完全情報ゲームのナッシュ均衡は, 最初に, 終点に一番近い分岐点で, その手番のプレイヤーの利得を最大にする最適戦略を求め, 以下順次, ゲームの木を後向きに解くことによって計算できる. 例えば, 図1のゲームで情報集合 <math>u_{21}\, </math> と <math>u_{22}\, </math> におけるプレイヤー2の最適戦略はそれぞれLとRである. このとき, 情報集合 <math>u_{1}\, </math> におけるプレイヤー1の最適戦略はRであり, 純戦略の組 (R, LR) はゲームのナッシュ均衡である. このようなナッシュ均衡の計算方法を, ゲームの後向き帰納法という. キューン (H. Kuhn) は, <math>n\, </math> 人完全情報ゲームは純戦略の範囲で少なくとも1つのナッシュ均衡をもつことを証明した [1].

　図1のゲームは (R, LR) の他に図2の利得行列で＊をつけたナッシュ均衡をもつ. しかし, これらのナッシュ均衡は均衡プレイ上にない分岐点ではプレイヤーの最適戦略を導かないという欠点をもつ. ゼルテン (R. Selten) はナッシュ均衡のこのような欠点を解消するために, より強い均衡概念として, すべての部分ゲーム上にナッシュ均衡を導く[[部分ゲーム完全均衡]] (subgame perfect equilibrium) を定義した [3].

　ゼルテンの研究以後, 展開形ゲームの理論は大きく進展し, 現在, ゲーム状況におけるプレイヤーの戦略的行動を解明する基礎理論としてORや経済学を始め広範囲の分野に応用されている.

　展開形ゲームについて詳しくは, [2] を参照されたい.

----
'''参考文献'''

[1] H. W. Kuhn, "Extensive Games and the Problem of Information," in H. W. Kuhn and A. Tucker(eds.), ''Contributions to the Theory of Games'', Vol. II, Annals of Mathematics Studies 28, Princeton University Press, 1953, 193-216.

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

[3] R. Selten, "Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games," ''International Journal of Game Theory'', '''4''' (1975), 25-55.

《戦略形ゲーム》

2007-07-08T06:11:56Z

219.161.35.37:

'''【せんりゃくけいげーむ (game in strategic form) 】'''

　ゲームに参加する[[プレイヤー]]の集合を<math>N\, </math>, 各プレイヤー<math>i\, </math>のとりうる[[戦略 (ゲーム理論における)|戦略]]の全体を<math>S_i\, </math>, および<math>S=S_1 \times \cdots \times S_n\, </math> 上で定義された各プレイヤー<math>i\, </math> の[[フォンノイマン・モルゲンシュテルン効用関数]] (von Neumann-Morgenstern utility function) を<math>u_i\, </math> とするとき,

:<math>G=(N; S_1, \ldots , S_n; u_1, \ldots , u_n)\, </math>

を[[戦略形ゲーム]] (game in strategic form) または[[標準形ゲーム]] (game in normal form) という. <math>N\, </math> と<math>S_i\, </math> がすべて有限集合であるとき, <math>G\, </math> を有限ゲームという. 効用関数<math>u_i\, </math> は, また[[利得関数]] (payoff function) ともいい, その値を利得という.

　戦略形で書かれたゲームは, 特にことわらない限り[[非協力ゲーム]]である. 戦略の数が有限な2人ゲームは次のような[[利得双行列 (ゲームの)|利得双行列]] (payoff bimatrix) で表現することができるので, [[双行列ゲーム]] (bimatrix game) ということがある.

:<math>\begin{array}{@{\ }c|ccc@{\ }}
& 1 & \ldots & n \\ \hline
1 & a_{11}, b_{11} & \ldots & a_{1n}, b_{1n} \\
\vdots & \vdots & \ddots & \vdots \\
m & a_{m1}, b_{m1} & \ldots & a_{mn}, b_{mn}
\end{array}\, </math>

　ここに, 縦の<math>1, \ldots, m\, </math>はプレイヤー1の戦略, 横の<math>1, \ldots, n\, </math>はプレイヤー2の戦略であり, <math>a_{ij}, b_{ij}\, </math> は, プレイヤー1, 2が各々戦略<math>i, \ j\, </math>をとったときの, プレイヤー1, 2の利得である. <math>a_{ij}\, </math>を成分とする行列を<math>A\, </math>, <math>b_{ij}\, </math>を成分とする行列を<math>B\, </math>と表し, 利得双行列を簡単に<math>(A, B)\, </math>と表す. すべての<math>i, \ j\, </math>について, <math>a_{ij} + b_{ij} = 0\, </math>となる場合が[[2人ゼロ和ゲーム]] (two-person zerosum game) の戦略形である. 行列<math>B\, </math>は<math>A\, </math>の符号を変えたものであり, 行列<math>A\, </math>だけでゲームを記述できるので2人ゼロ和ゲームを[[行列ゲーム]] (matrix game) ということもある.

　双行列ゲーム<math>(A, B)\, </math>において, 各プレイヤーの[[混合戦略]] (mixed strategy) を各々<math>p=(p_1, \ldots , p_m)\, </math>, <math>q=( q_1, \ldots , q_n)\, </math> とすると, 各プレイヤーの利得の期待値 (期待利得) は各々 <math>pAq^{\top}\, </math> および <math>pBq^{\top}\, </math> で与えられる. <math>q^{\top}\, </math>は<math>q\, </math>の転置ベクトルを表す. また, 混合戦略に対してもとの戦略を[[純戦略]] (pure strategy) という. [[ナッシュ均衡]] <math>(p^*, q^*)\, </math>は, [[非協力ゲーム理論]]の項で述べた定義によって,

:<math>p^*Aq^{*\top} \ge pAq^{*\top}, \ p^*Bq^{*\top} \ge p^*Bq^{\top}, \ \mbox{ for all } p, \ q \, </math>

をみたす混合戦略の組である. とくに, ゼロ和ゲームでは, <math>B=-A\, </math>であるから

:<math>pAq^{*\top} \le p^*Aq^{*\top} \le p^*Aq^{\top} , \ \ \mbox{ for all } p, \ q \, </math>

となり, これから[[ミニマックス定理 (ゲーム理論における)|ミニマックス定理]] (minimax theorem)　

:<math>\mbox{max}_{p} \mbox{min}_{q} \ pAq^{\top} \ =\ \mbox{min}_{q}\mbox{max}_{p}\ \ pAq^{\top} \, </math>

が導かれ, さらにこの値は<math>p^*Aq^{*\top}\, </math>に等しい. 左辺の値をマックスミニ値 (maxmin value), 右辺の値をミニマックス値(minimax value), さらに, この共通の値を[[ゲームの値]] (value of a game) という. また, このときの戦略<math>p^*, \ q^*\, </math>を各々[[マックスミニ戦略]] (maxmin strategy), [[ミニマックス戦略]] (minimax strategy) という.
　次に示すのは, 左が囚人のジレンマ (prisoner's dilemma), 右が逢い引きのジレンマ (battle of the sexes) という名で知られる有名な双行列ゲームである.

:<math>\begin{array}{@{\ }c|ccc@{\ }}
& c & d \\ \hline
c & 3, 3 & 0, 4 \\
d & 4, 0 & 1, 1
\end{array}
\ \ \ \ \ \ \ \ \ \ \ \ \ \
\begin{array}{@{\ }c|ccc@{\ }}
& a & b \\ \hline
a & 2, 1 & 0, 0 \\
b & 0, 0 & 1, 2
\end{array}\, </math>

囚人のジレンマでは, 純戦略の組 <math>(d, \ d)\, </math>のみが, また, 逢い引きのジレンマでは, 純戦略の組 <math>(a, \ a)\, </math>および<math>(b, \ b)\, </math>と, 混合戦略の組 <math>((2/3, 1/3)\, </math>, <math>(1/3, 2/3))\, </math>がナッシュ均衡である. とくに, 囚人のジレンマのナッシュ均衡では, 戦略<math>d\, </math>は相手のすべての戦略に対する[[最適反応 (ゲーム理論における)|最適反応]] (best reply) となっている. このようなナッシュ均衡を, [[支配戦略]]均衡 (dominant strategy equilibrium) ということがある. 逢い引きのジレンマには支配戦略は存在しない. また, 逢い引きのジレンマでは, 混合戦略ナッシュ均衡における利得の組<math>(2/3, \ 2/3)\, </math>は, たとえば純粋戦略ナッシュ均衡<math>(a, \ a)\, </math>における利得の組<math>(2, \ 1)\, </math>に対して各プレイヤーについて劣っている. このとき, 利得の組<math>(2/3, \ 2/3)\, </math>は<math>(2, \ 1)\, </math>に[[パレート支配]] (Pareto dominate) されるという.

　戦略形ゲームにおいて, もし, 各プレイヤーが共通の偶然機構にもとづいて戦略を選ぶことが許されているならば, 各プレイヤーは互いに相関した行動をとることができる. このような戦略を[[相関戦略]] (correlated strategy) という. たとえば, 逢い引きのジレンマで, コインを投げて表が出たら戦略の組<math>(a, \ a)\, </math>, 裏が出たら<math>(b, \ b)\, </math>とすることに2人が合意したとしよう. つまり, 2人とも, 表が出たら<math>a\, </math>をとり, 裏が出たら<math>b\, </math>をとるという相関戦略をとるものとする. このような合意がナッシュ均衡になるとき, すなわち, 相関戦略の組がナッシュ均衡となっているとき, これを[[相関均衡]] (correlated equilibrium) という. 上に述べた相関戦略の組は相関均衡であり, 2人の期待利得はともに<math>3/2\, </math>となることが容易にわかる. また, 混合戦略均衡は互いに独立な相関戦略からなる相関均衡にほかならない. 相関均衡の正式な定義については, たとえば [3] など参照. 　

　以上のゲームでは, 戦略形<math>G\, </math>についての知識がすべてのプレイヤーの間で[[共有知識]] (common knowledge) であると仮定されており, これらは[[完備情報ゲーム]] (game with complete information) といわれている. 他方, 不完備情報ゲームはハルサーニ(J. C. Harsanyi) [2] の定式化によって分析できるようになった. たとえば, 利得関数<math>u_i\, </math>に関する情報が不完備な場合は, まず有限個のパラメター<math>t_{i1}, t_{i2}, \ldots, t_{ik} \in T_i\, </math>を導入し, プレイヤー<math>i\, </math>の利得関数は, そのタイプによって, 有限個の利得関数<math>u_i(\cdot|t_{i1}), u_i(\cdot| t_{i2}), \ldots, u_i(\cdot| t_{ik})\, </math> (以下, まとめて<math>u_{i}(\cdot|t_{i})\, </math>と表す. )のうちのどれか1つに定まる, と定式化し直すことにより, <math>u_{i}\, </math>に関する不完備情報を表現する. この<math>t_i \in T_i\, </math>をプレイヤー<math>i\, </math>のタイプという. 各プレイヤー<math>i\, </math>は自分はどのタイプであるかを知っているが, 他のプレイヤーのタイプは知らない. ただし, 他のすべてのプレイヤーのタイプ<math>t_{-i} = (t_1 , \ldots, t_{i-1}, t_{i+1}, \ldots , t_n )\, </math>について条件付き確率<math>p_i(t_{-i}|t_i)\, </math>によって<math>t_{-i}\, </math>を推測することができるとする. こうして, 新たな戦略形ゲーム

:<math>G'= (N, S_1, \ldots , S_n;
p_1, \ldots , p_n; T_1, \ldots, T_n;
u_1(\cdot|t_1), \ldots , u_n(\cdot|t_n))\, </math>

がえられる. これを[[ベイジアンゲーム]] (Bayesian game) という. また, 関数<math>s_i : T_i \rightarrow S_i\, </math>をベイジアンゲームの戦略という. すなわち, プレイヤー<math>i\, </math>は, 自分のタイプを知ってはいるが, どのタイプであったとしてもそのもとでの行動を指定しておくことがこの場合の戦略である. するとナッシュ均衡は, すべてのプレイヤー<math>i\, </math>とタイプ<math>t_i\, </math>および<math>a_{i} \in S_{i}\, </math> について次の条件をみたす戦略の組<math>s^*=(s^*_1, \ldots , s^*_n)\, </math>である. この戦略の組を, [[ベイジアンナッシュ均衡]] (Bayesian Nash equilibrium) という.

:<math>\sum_{t_{-i} \in T_{-i}} u_i(s^*(t)|t_i)p_i(t_{-i}|t_i)
\ \ge\ \sum_{t_{-i} \in T_{-i}} u_i(s^*_{-i}(t_{-i}), a_i
| t_i)p_i(t_{-i}|t_i)\, </math>

ただし, <math>s^*(t)=(s^*_{-i}(t_{-i}), s^*_i(t_i))=(s^*_1(t_1), \ldots, s^*_n(t_n))\, </math>である. ベイジアンゲームは, 80年代以降, 情報経済学や産業組織論などの新しい分野の発展に大きく貢献している. これについてはたとえば, [1] を参照.

----
'''参考文献'''

[1] R. Gibbons, ''Game Theory for Applied Economists'', Princeton University Press, 1992.

[2] J. C. Harsanyi, "Games with Incomplete Information Played by `Bayesian' Players, parts I, II and III", ''Management Science'', '''14''' (1967-8), 159-182, 320-334, 486-502.

[3] M. J. Osborne and A. Rubinstein, ''A Course in Game Theory'', MIT Press, 1994.

《非協力ゲーム理論》

2007-07-08T05:46:07Z

219.161.35.37:

'''【ひきょうりょくげーむりろん (noncooperative game theory) 】'''

　[[プレイヤー]]間で拘束的な協定をむすぶことが可能なゲームを[[協力ゲーム]], そうでないゲームを非協力ゲームといい, 非協力ゲームを扱う理論を[[非協力ゲーム理論]] (noncooperative game theory) という. 拘束的協定とは, ゲームの外部から付与された拘束力をともなう協定であって, たとえば違反した場合にしかるべきペナルティが課せられるために従わざるをえないような協定である. それゆえ, 協力ゲームでは拘束的協定のもとでプレイヤーたちは提携}{提携} を組んで行動することができるが, 非協力ゲームではプレイヤーたちは個々独立に意思決定し, 束縛されずに自由なコミュニケーションや取り決めをすることが許されている. これらのことは普通モデルに明記されないので注意が必要である.

　フォンノイマン (J. von Neumann) が1928年に[[ミニマックス定理 (ゲーム理論における)|ミニマックス定理]]を証明することによって解決した, ゲーム理論の出発点に位置する[[2人ゼロ和ゲーム]]は最もよく知られた非協力ゲームであり, 勝つか負けるかという完全な利害対立状況を記述するものである([8]). これに対して, ナッシュ (J. F. Nash) が1950年に創始した一般の非協力ゲームでは, 有名な[[囚人のジレンマ]]などにみられるように, 利害は完全に対立するとはかぎらない. そのためゼロ和という条件に縛られないので, 今日, 経済学を中心とする社会科学や生物学などに広く応用されている. 非協力ゲーム理論とは, 普通, このナッシュの理論をいう([5]).

　ナッシュはさらに, 合理的主体間の交渉や契約などの協力行動, つまり, 協力ゲームは, 一般に適切な非協力ゲームに還元して分析するべきであるという方法論上の提案をしたが, これは現在[[ナッシュプログラム]] (Nash program) として知られている([5]). 1994年のノーベル経済学賞は, あとで述べるようにこの方法論が経済分析に果たした貢献が評価されて, ナッシュ, ハルサーニ (J. C. Harsanyi) およびゼルテン (R.Selten) に対して与えられたものである.

　非協力ゲームは, <math>G=(N; S_1,\ldots ,S_n; u_1,\ldots ,u_n)\, </math> のように形式的に表現することができる. このように表現されたゲームを[[戦略形ゲーム]]という. ここに<math>N\, </math>はプレイヤーの集合, <math>S_i\, </math>はプレイヤー<math>i\, </math>の[[戦略 (ゲーム理論における)|戦略]]の集合, <math>u_i\, </math>は<math>S=S_1 \times \cdots \times S_n\, </math>上で定義されたプレイヤー<math>i\, </math>の[[フォンノイマン・モルゲンシュテルン効用関数]]である. <math>N\, </math>とすべての<math>S_i\, </math>が有限集合であるとき, ゲーム<math>G\, </math>を有限ゲーム, そうでないとき無限ゲームという. また, <math>N=\{1,2\}, \ u_1 (s)+u_2 (s) = 0\ \mbox{ for all } s=(s_1, s_2) \in S_1 \times S_2\, \, </math> , が成り立つゲーム<math>G\, </math>が[[2人ゼロ和ゲーム]]である.

　非協力ゲームの[[ナッシュ均衡]] (Nash equilibrium) とは, 次のような[[混合戦略]]の組である. <math>\Delta S_i\, </math>でプレイヤー<math>i\, </math>の混合戦略の集合をあらわし, 混合戦略の組<math>x=(x_1, \ldots , x_n) \in \Delta S= \Delta S_1 \times\cdots \times \Delta S_n\, </math> のもとでのプレイヤー<math>i\, </math>の効用の期待値（期待効用）を<math>U_i(x)\, </math>であらわそう. このとき, 混合戦略の組<math>x^*=(x^{*}_{1}, \ldots , x^*_n ) \in \Delta S\, </math>がナッシュ均衡であるとは, すべてのプレイヤーiに対して

:<math>U_i (x^*) \ge U_i (x^*_1 ,\ldots , x^*_{i-1}, x_i, x^*_{i+1},\ldots , x^*_n )\ \mbox{ for all } x_i \in \Delta S_i\, </math>

となることである. このように, ナッシュ均衡においては, 各プレイヤーの戦略は他のすべてのプレイヤーの戦略に対する最適な反応であり, 独立に行動する各プレイヤーは, 外的な拘束力がなくても, 他の戦略に切り替えることなくそこに留まることになる.

　混合戦略まで考えた有限ゲームや, 各<math>S_i\, </math> がコンパクト凸集合で, 各効用関数<math>u_i\, </math> が連続かつ<math>x_i\, </math>に関して準凹であるような無限ゲームがナッシュ均衡をもつことは, ブラウワーや角谷の不動点定理によって証明することができる. また, 2人ゼロ和ゲームのナッシュ均衡は, [[マックスミニ戦略]]と[[ミニマックス戦略]]の組であることも容易に確かめることができる. こうして, ナッシュによる均衡の存在定理は, [[ミニマックス定理 (ゲーム理論における)|ミニマックス定理]]の拡張になっていることがわかる.

　非協力ゲームの研究はその後, シャープレイ (L. S. Shapley) の[[確率ゲーム]] (stochastic game) ([7])やキューン (H. W. Kuhn)の[[展開形ゲーム]] ([4]), 無限回[[繰り返しゲーム]] (repeated game) の[[フォーク定理]] (folk theorem) ([1]), 連続時間上の動学を考える[[微分ゲーム]] (differential game) などの理論展開に続いて, ハルサーニによる[[不完備情報ゲーム]] (game with incomplete information) への拡張([2])やゼルテンの[[完全均衡]] (perfect equilibrium) ([6])などを産出した. さらに80年代に入ってからの[[逐次均衡]] (sequential equilibrium) ([3])という技術的展開も加わって, 産業組織論や情報経済学などの経済学の分野に新しい分析方法を確立し, 重要な研究領域を切り開くことになった.

　また, [[進化的安定戦略]]の名で知られる戦略は, 進化生物学においてナッシュ均衡のひとつの精緻化として生まれたものであり, 逆にこれに影響されて80年代に発展したのが[[進化ゲーム理論]]と呼ばれる非協力ゲーム理論である. 進化ゲーム理論におけるプレイヤーは, 通常のゲームにおけるように, 完全な合理性を備えた意思決定主体ではなく, むしろ思考せずにあらかじめ決められた行動のみを一定の手順でとるオートマトン, ないしアルゴリズムである. 自然界において, 特定の遺伝子が淘汰されずに優勢になっていくように, 進化ゲームでは進化的に安定なアルゴリズム（戦略）が動学的な均衡点になることが知られている. このように, 進化ゲームは合理的推論によらない均衡選択の可能性を示しており, これがきっかけとなって, 90年代以降, プレイヤーの[[限定合理性]] (bounded rationality) と, プレイヤーの[[学習 (ゲーム理論における)|学習]]による均衡選択の研究が精力的になされるようになった. この限定合理的な行動による均衡選択というアイディアの原型は, 実はナッシュ自身が彼の最初の論文の削除された章で述べていたことが知られている.

----
'''参考文献'''

[1] R. Axcelrod, ''The Evolution of Cooperation'', Basic Books, 1984.

[2] J. C. Harsanyi, "Games with Incomplete Information Played by `Bayesian' Players, parts I,II and III," ''Management Science'', '''14''' (1967-8), 159-182, 320-334, 486-502.

[3] D. M. Kreps and R. Wilson, "Sequential Equilibria," ''Econometrica'', '''50''' (1982), 863-894.

[4] H. W. Kuhn, "Extensive Games and the Problem of Information," in ''Contributions to the Theory of Games II, Annals of Mathematics Studies'', '''28''', H. W. Kuhn and A. W. Tucker, eds., Princeton University Press, 1953.

[5] J. F. Nash, Jr, ''Essays on Game Theory'', Edward Elgar, 1996

[6] R. C. Selten, "Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games," ''International Journal of Game Theory'', '''4''' (1975), 25-55.

[7] L. S. Shapley, "Stochastic Games," ''Proceedings of the National Academy of Sciences of the United States''}, '''39''' (1953), 1095-1100.

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

《ゲーム理論》

2007-07-08T05:37:24Z

219.161.35.37:

'''【げーむりろん (game theory) 】'''

1　ゲーム理論とは

　[[ゲーム理論]] (game theory) は, 複数意思決定主体の存在する状況における決定理論であり, フォンノイマン (J. von Neumann) とモルゲンシュテルン (O. Morgenstern) による大著"Theory of Games and Economic Behavior"([9])をその出発点とする. 複数の主体が存在するから, 主体間で利害の対立がある場合もあるし, 利害を共にする場合もある. このような状況において, 各意思決定主体はどのような行動をとるか, ないしは, とるべきかを数理的に分析することがゲーム理論の目的である. ゲーム理論では, 意思決定主体を[[プレイヤー]] (player), 各プレイヤーが持つ行動の計画を[[戦略 (ゲーム理論における)|戦略]] (strategy), プレイヤーがそれぞれの戦略をとった時に, 各プレイヤーが得られるもの, ないしは, それに対する評価値を[[利得 (ゲームの)|利得]] (payoff) と呼ぶ.

　ゲーム理論は, 想定するプレイヤーの行動様式の違いによって, [[非協力ゲーム理論]], [[協力ゲーム理論]]の2つに分かれて発展してきている. 非協力ゲーム理論は, プレイヤー間の話し合いはなく各プレイヤーがそれぞれ独立に戦略を決定する状況か, ないしは, たとえ話し合いがあったとしてもその結果得られた合意に拘束力のない状況を扱う. それに対して, 協力ゲーム理論は, プレイヤー間に話し合いのあることを前提とし, 話し合いの結果得られた合意に拘束力がある状況を扱う. 非協力ゲーム理論の扱うゲームを非協力ゲーム, 協力ゲーム理論の扱うゲームを協力ゲームと呼ぶ.

2　非協力ゲーム理論

　非協力ゲームは, 各プレイヤーの戦略と利得を用いて表現する[[戦略形ゲーム]]と, プレイヤーの意思決定を時間の流れと共に[[ゲームの木]]を用いて詳しく表現する[[展開形ゲーム]]に分かれる.

　非協力ゲーム理論における主要な解は, ナッシュ (J. F. Nash) によって与えられた[[ナッシュ均衡]]である. ナッシュ均衡とは, 各プレイヤーの戦略が他のプレイヤーの戦略の組に対する[[最適反応 (ゲーム理論における)|最適反応]]戦略になっているような戦略の組である. 戦略形ゲームにおいて, もともとの戦略が有限個である場合には, それらを確率混合して用いる[[混合戦略]]まで考えれば, ナッシュ均衡は必ず少なくとも1つ存在することが知られている.

　展開形ゲームは, プレイヤーの意思決定の順序, プレイヤーが意思決定の際に持っている情報などを詳細に表現できるものである. また, 展開形ゲームを考えると, ナッシュ均衡のうちのいくつかはその合理性に問題のあることが明らかになる. そのため, [[部分ゲーム完全均衡]], [[逐次均衡]], [[完全均衡]]などのナッシュ均衡の精緻化が展開形ゲームにおいて提唱されてきている.

3　協力ゲーム理論

　協力ゲームは, プレイヤーが2人の場合と3人以上の場合では, 状況が大きく異なり, それぞれ別々に理論が発達してきている.

　2人の協力ゲームでは, プレイヤーが話し合いの結果, 協力して行動するかどうか, また, 協力した場合には, その結果得られる利得をどのように分配するかの交渉が, 問題になる. 従って, 2人の協力ゲームを[[2人交渉問題]]と呼ぶこともある. 2人協力ゲームの主たる解もナッシュによって与えられたもので, [[ナッシュ解]]ないしはナッシュ交渉解と呼ばれている.

　3人以上の協力ゲームになると, 単に全員が協力するかどうかだけでなく, 部分的な協力関係を考える必要が生じ, 分析が難しくなる. 3人以上の協力ゲームは, 一般に<math>n\, </math>人協力ゲームと呼ばれる. フォンノイマンとモルゲンシュテルンは, <math>n\, </math>人協力ゲームにおいて, 協力関係を結んだプレイヤーのグループを[[提携]]と呼び, 提携それぞれに対して, それが獲得できる利得を与える関数を[[特性関数 (ゲーム理論の)|特性関数]]と呼んだ. 特性関数による<math>n\, </math>人協力ゲームの表現を[[提携形ゲーム]]ないしは特性関数形ゲームという. 提携形ゲームにおいては, プレイヤー間の利得分配の基準をどのように与えるかによって, [[安定集合]], [[コア]], [[交渉集合]], [[カーネル (ゲーム理論における)|カーネル]], [[仁]], [[シャープレイ値]]など, 様々な解が提案されてきている.

4　ゲーム理論の応用

　ゲーム理論がこれまで最大の貢献をなした分野は経済学であろう. 最初は, 交換市場や生産市場の[[競争均衡]]のコアによる新たな特徴付けなど, 協力ゲームの応用が中心であった. ついで, 産業組織論などにおいて企業競争の非協力ゲーム理論による分析が進み, 1980年代に入って爆発的な勢いで情報経済学をはじめ, ミクロ経済学の様々な分野に非協力ゲーム理論が浸透していった. いまでは, 経済学だけでなく, 政治学, 社会学などにおいてもゲーム理論は大きな貢献をなすものとなっている.

　ＯＲにおいても, 第2次世界大戦の軍事研究に始まり, 企業など組織における意思決定, 社会的, 公共的意思決定など, 非協力ゲーム, 協力ゲームが用いられているところは多い. 最も多い適用例は, 費用分担, 便益分配などの計画問題に対するものであろう. また, 投票による意思決定システムの協力ゲーム, 非協力ゲームによる分析もよく行われている.

5　最近のゲーム理論の発展

　最近のゲーム理論の発展で最も重要なものは, [[進化ゲーム理論]]とゲームにおける[[学習 (ゲーム理論における)|学習]]であろう. ナッシュ均衡と部分ゲーム完全均衡などその精緻化は, プレイヤーの合理性を追求した結果得られた解であったが, これらの解が, 必ずしもわれわれが現実に経験する結果を導かないことが, 様々なゲーム的状況の分析から明らかになってきた.

　そこで出てきたのが, プレイヤーは必ずしも完全には合理的ではないとする[[限定合理性]]の考え方である. 限定合理性に対する１つのアプローチが, 進化ゲーム理論と学習であり, これらの理論によって, 社会における慣習, 制度などの形成過程が明らかにされるのではないかと期待されている.

　いま1つの重要なアプローチが, 実際に人間を使った[[実験 (ゲーム理論における)|実験]]によるゲーム理論の再検証である. これも, 人間の合理性の限界を認識することからスタートしている. 様々なゲームにおける実験が行われており, われわれ人間は, ゲーム理論の解が導く行動を必ずしもとらないことが明らかにされ, 実験結果を基に, 新たな理論の構築が模索されている.

6　ゲーム理論の文献

　ゲーム理論の最近の一般的なテキストとしては, 和書では, [4], [5], [8] が, 洋書では, [1], [2], [3], [6], [7] がある.

----
'''参考文献'''

[1] A. Dixit and B. Nalebuff, ''Thinking Strategically'', N.W.Norton, 1991. 菅野隆, 嶋津祐一, 『戦略的思考とは何か』, TBSブリタニカ, 1991.

[2] D. Fudenberg and J. Tirole, ''Game Theory'', MIT Press, 1991.

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

[4] R.Gibbons, ''Game Theory for Applied Economists'', Princeton University Press, 1992. 福岡正夫, 須田伸一, 『経済学のためのゲーム理論入門』, 創文社, 1995.

[5] 今井晴雄, 岡田章, 『ゲーム理論の新展開』, 勁草書房, 2002.

[6] 今井晴雄, 岡田章, 『ゲーム理論の応用』, 勁草書房, 2005.

[7] 梶井厚志, 松井彰彦, 『ミクロ経済学戦略的アプローチ』, 日本評論社, 2000.

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

[9] R.B.Myerson, ''Game Theory'', Harvard University Press, 1991.

[10] 中山幹夫, 『はじめてのゲーム理論』, 有斐閣, 1997.

[11] 中山幹夫, 武藤滋夫, 船木由喜彦, 『ゲーム理論で解く』, 有斐閣, 2000.

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

[13] M.J.Osborne and A.Rubinstein, ''A Course in Game Theory'', MIT Press, 1994.

[14] G.Owen, ''Game Theory, 3rd ed''., Academic Press, 1996.

[15] 佐々木宏夫, 『入門ゲーム理論』, 日本評論社, 2003.

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

[17] J.vonNeumann and O.Morgenstern, ''Theory of Games and Economic Behavior, 3rd ed.'', Princeton University Press, 1953.