多数エージェントの動学的離散選択行動モデルに対する定常均衡アプローチについて
A Stationary Equilibrium Approach for Dynamic Discrete Choice Modelswith Many Agents
東北大学大学院情報科学研究科
宮城俊彦*
Abstract
Stochastic game with dynamic programming gives a basic framework for modeling dynamic economic systems. The
standard solution concept for such games is Markov perfect equilibrium (MPE), but it is well known that MPE
computation becomes intractable as the number of players increases. Recently, a scheme for approximating MPE forsuch large scale game was proposed with a solution concept called oblivious equilibrium (OE). This paper tries tocombine a dynamic discrete choice model with OE and shows MEP can be solved as a DDC model with a singleagent.
Key Words: stochastic games, dynamic discrete choice model, learning algorithm, stationary Markov chain

１．はじめにShapley(1953)によって創設された確率ゲームは，エージェント間の相互作用をもつ動的経済システムをモデル化する基本枠組みを与える．確率ゲームでは，エージェントの行動はシステムの状態変数を変化させ，利得に影響を与える．こうした状態変化はマルコフ過程によって記述され，プレイヤーは無限計画時間軸上での割引期待利得を最大化する．Ericson and Pakes(1995) による動的寡占市場モデル以降，
EP モデルは特性の異なる企業で構成される産業組織構造を分析するモデルとして多くの応用が試みられてきている[Doraszelski and Pakes(2007)]．Rust(1987)，Hotz and Miller (1993)そして Aguirregabiriaand Mira (2002)（以降では AE モデルと略称する）は，市場における単一企業の選択に関するデータが与えられた場合の構造パラメータ推定法を提案し，また，Aguirregabiria and Mira (2007)は，これを複数企業が存在する場合の構造パラメータ推定法へと拡張している．こうした手法は紳士服やファーストフードなどの小売市場の分析あるいはオープンスカイによる我が国の航空市場の開放に伴う LCC の参入・退出分析そして空港経営改革の効果分析にも応用でき，今後の多様な発展が期待できる．
確率ゲームでは，あるプレイヤーの混合戦略は他のすべてのプレイヤーの混合戦略に依存して決定される，いわゆるマルコフ完全均衡(MPE)を求める必要がある．MPE は通常解析解を得ることはできず，動的計画法を用いた数値計算手法を用いる(Pakes and McGuire,1994). このため，プレイヤー数が増加すると計算量は指数的に増加する．この問題は“次元の呪い(curse of dimentionality)”として知られている．例えば，企業数 20，状態変数 40 の場合，2000 万 GB のコンピュータメモリーが必要になると言われている(Gabriel, Weintraub, Benkard and Van Roy,2010)．したがって，現時点では，寡占市場の構造変化を分析にするに留まり，多くの企業で構成される産業組織の構造変化を分析するまでには至っていない．
また，企業数が増加すると企業間の相互作用の影響が薄れ，いわゆる完全競争の状態に漸近するという特性を表現できない．こうした問題を克服するため，Jovanovic and Rosenthal(1988)や Hopenhayn(1992)はエー

ジェント数が無限の場合を想定し，他のプレイヤーの行動の影響は大数の法則によって平均化されるので，各プレイヤーはあたかも他のプレイヤーの状態変数が固定されているかのように見なして最適行動をとるモデルを提案した．この結果達成される均衡を Hopenhayn(1992)は定常均衡(stationary equilibrium:SE)と呼んでいる．
一方，Weintraub, Benkard and van Roy(2008)は，エージェント数が非常に大きい場合の MPE を近似する手法として oblivious equilibrium(OE)に基づく手法を提案している．OE は Ericson and Pakes モ
デルと SE の概念を統合したモデルとみることができる．すなわち，(1)競争企業の行動は平均的な行動に近い行動をとっている，(2) 平均的な行動を逸脱する企業が存在したとしても，それらの企業数が小さいならば，それらの企業が個別企業のコストに与える影響は無視できるほど小さい．OE アルゴリズムは，1次元の DP を解くだけで済むので企業数がかなり多い場合の産業構造分析に適している．
本研究の目的は，AE モデルと OE を統合することによって，任意の規模の企業を対象にした産業構造分析が可能なモデルを提案することにある．このため，AE モデルに Weintraub, Benkard and vanRoy(2008)が提案した産業構造の状態変数を加え，AE モデルと同様の枠組みで MPE の条件を誘導し，その特性を分析する．この場合，産業構造の推移をマルコフ連鎖で記述し，その定常確率を求めることにより，Weintraub, Benkard and van Roy(2008)とは異なるアプローチで MPE が single agent 問題として解けることを示す．
２．動的離散選択モデル
2.1 表記法と仮定
プレイヤー集合 I = {1,, i,, N } とおき，プレイヤー i の行動集合 Ai と置く，離散的時間 t = 0,1, を考え，ステージ t でのプレイヤー i の行動を ait ∈ Ai とおき，プレイヤー i 以外のプレイヤの行動を

a− it ∈ A− i と記す．行動プロファイルを at = ( ait , a− it ) で表わす．ステージ t でのプレイヤー i の特性を２つの状態ベクトル ( xit , ε it ) で記述する．状態 xit ∈ X i は各プレイヤーが共有する公的情報であり，ε it ∈Σ はプレイヤー i に固有の私的情報と定義する．例えば，参入・退出市場モデルでは X i = {0,1} とおき， xit = 1 ならば，プレイヤー i がステージ t で市場に参入することを表わし， xit = 0 ならば，参入していないことを表わす．X i は離散数の集合で，有限と仮定する．加えて，産業構造を表わすベクトル st を定義する． st は N プレイヤーの xt 上でどのように分布しているかを表わす産業状態ベクトルである．
Weintraub, Benkard and van Roy(2008)に従い，プレイヤー i の競争相手の状態 s− it を次のように定義する．すなわち，xit = x ならば，s− it=[ x ] st [ x ] − 1 であり，xit ≠ x ならば，s− it [ x ] = st [ x ] である．参入・退出市場モデルの例で言えば，=st ( N − m, m ) は x = 0 と x = 1 で表わされる状態空間上のプレイヤー数の分布であり， xit = 0 ならば， s− it = ( N − m − 1, m ) ，また， xit = 1 ならば， s− it =( N − m, m − 1) になる．
プレイヤー i の利得関数をπ i : Ai × X i × S − i × Σi →  で表わす．すなわち，ステージ t でプレイヤー iがとる行動 ait ，状態 ( xit , ε it ) そして競争相手の状態 s− it が与えられたときのプレイヤー i の実現利得を

π i ( ait , xit , s− t , ε it ) で記す．各プレイヤーは他のプレイヤーの現在および将来の行動そして共通情報の将来の値およびショックに関する不確実性に直面している．
プレイヤーが行動 ait を選択することによる状態間推移は確立法則 F ( xi ,t +1 , s− i ,t +1 , ε i ,t +1 | ait , xit , s− it , ε it ) にしたがうと仮定している．

このとき，次のような企業の割引期待利得最大化問題を考える．

∞max E  ∑ β t +τ π i ( ai ,t +τ , xi ,t +τ , s− i ,t +τ , ε i ,t +1 | ait , xit , s− it , ε it ) {at }t ≥0 τ =0(1)

ここに， β ∈ [0,1) は割引係数である．(1)式が AE モデルと異なる点は，他プレイヤーとの相互作用が行
動 a− it を介してではなく，産業状態 s− it によって認識されるとする点だけである．
以下の仮定をおく．
仮定１）（加法分離性） プレイヤー i の利得は私的情報 ε it と加法分離的である．

π i ( a=π i ( ait , xit , s− it ) + ε it ( ait )it , xit , s− it , ε it )

(2)

仮定２）
（条件付独立性） 推移確率は次式のように表わすことができる．

CDF ( xi ,t +1 , s− i ,t +1 , ε t +1 | at , xit , s− it , ε t ) = Gε (ε t +1 ) Fx ( xi ,t +1 | ait , s− it , xit ) H s ( s− i ,t +1 | ait , s− it , xit )(3)
この前提として，以下のことが仮定されている．
・私的情報は，公的情報の推移には影響を与えない．
・各プレイヤーの状態の変化は産業状態の変化と独立である．
・私的情報は時間依存性がなく，公的情報と独立であり，独立，同一分布（iid）にしたがう．なお，以降では各分布の添え字は省略する．
2.2 OE モデル
Weintraub, Benkard and van Roy(2008)に従い，各プレイヤーは産業状態は定常分布 s であると見なしていると仮定する．すなわち，各プレイヤーは競争企業の状態は変化せず，あたかも外生的に決定されていると見なし，また，自己の行動が他企業に与える影響は無視できると考える．このとき，(3)において産業状態の時間的推移 H s は考慮する必要がなくなる．その結果，(1)式は次のように書き改められる．

∞max E  ∑ β t +τ π i ( ai ,t +τ , xi ,t +τ , s , ε i ,t +τ | ait , xit , ε i ,t ) {at }t ≥0 τ =0(4)

Aguirregabiria and Mira (2002) がすなわち，(4)では他のプレイヤーとの相互作用 s− it の影響がないため，提案した single player 問題と類似した構造になる．唯一異なるのは， s が利得関数に含まれる点である．
2.3

産業構造の定常性を考慮した AE モデル

プレイヤー i の状態が sit = ( xt , ε it ) から si ,t +1 = ( x ', ε i ,t +1 ) に変化する場合を考える．私的情報は状態変化に依存しないので，以降においては，特に必要ない限り状態変化を x → x ' で表わす．状態 x におけるプレイヤー i の最適応答に伴う利得 Vi ( x, ε i , s− i ) は現在の利得そして状態変化 x → x ' を考慮した

forward looking 行動を考え，次の Bellman 方程式で与えられる．

Vi =( x, ε i , s− i ) max π i (bi , x, s− i ) + ε i (bi ) + β ∑  ∫ Vi ( x ', s− i ,ηi )dGi (ηi )  Fi ( x ' | bi , s− i , x )  (5)bi ∈A
x '∈X
ここで，Fi ( x ' | bi , x, s− i ) は，他のプレイヤーの混合戦略が s− i であるという確信の下でプレイヤー i が行動 ai をとるときの状態 x → x ' の推移確率である．このとき，プレイヤー i の最適応答に伴う利得Vi ( x, ε i , s− i ) の期待値（状態価値関数）はVi ( x, s− i ) = ∫ Vi ( x, ε i , s− i )dGi (ε i )(6)で与えられる．したがって，
Vi ( x, s− i ) max π i (bi , xi , s − i ) + β ∑ Vi ( x 'i , s− i ) Fi ( x 'i | bi , xi , s− i ) =bi ∈Ax 'i ∈X i(7)

右辺の括弧の中を次のように定義し，これを行動価値関数と呼ぶ．

v=π i ( ai , xi , s− i ) + β ∑ Vi ( x 'i , s− i ) Fi ( x 'i | ai , xi , s− i )i ( ai , xi , s− i )

(8)

x '∈X

式(8)を用いると，Bellman 方程式(5)は次のように書き改められる．

Vi ( xi , ε i , s− i ) = max  vi (bi , xi , s− i ) + ε i ( ai ) bi ∈A

したがって，(6)は次のように与えられる．

Vi ( xi , s− i )=∫ max {v (b , x , s ) + ε (b )}dG (ε )ibi ∈Ai−iiiii(9)i

このとき，プレイヤーの状態変数が xi という条件の下で行動 ai を選択する確率は，σ=i ( ai | xi , s− i )s ) + ε (b )) a }dG (ε )∫ 1{max(π (b , x,=bi ∈Aii−iiiii(10)⋅ は指示関数である．
で与えられる．ここに，1{}
2.4 マルコフ連鎖の定常分布2.3 では産業構造の定常性を前提に AE モデルの誘導が行なわれた．この節では，定常分布を与えるマルコフ連鎖モデルを提案する．議論を簡単にするため，ここでは意志決定行なう企業数を１ステージあた．この企業は他の企業り１企業とする（ポアソン参入分布を想定し，参入率 λ と拡張することもできる）
は t − 1 時点での状態を維持していると見なしている．意志決定を行なう企業はランダムに選択される．また，この企業が行動選択は(10)式で与えられる．企業の選択が最善応答である確率を ps ，そうでない場合(1 − ps ) で表わす．今，時刻 t で最善応答の状態にある企業数を s とおく．このとき，推移確率は次式で与えられる．

Pr [ st +1 = s + 1| st = s ] =n−s
ps , for 0 ≤ s ≤ n − 1n(11)他の推移確率については，図１に示す．

なお，図には表記されていないが次のことが仮定されている．

Pr [ st +1 = s ' | st = s ] = 0, for s ' ∉{s − 1, s, s + 1}
このマルコフ連鎖は，既約で非周期であり，定常分布に収束する．すなわち，推移確率の定常分布 ω は次式で与えられる．

ωs +1  n − s   ps = andωs  s + 1   1 − ps (12)n∑ω = 1s =0s

2.4 マルコフ完全均衡
ベルマン方程式(5)は次のように書き改めることができる．

∑ σ (a | x , s ) π (b , x , s ) + E[ε (a )] + β ∑ V ( x ' , s ) F ( x ' | b , x , s )  (13)Vi ( x, s− i )=ai ∈Aiii−i

iii−iiix 'i ∈X iii−iiiii−iHotz and Miller (1993)は，価値関数が選択確率の関数として表わすことができることを示した．
すなわち，

E[ε i ( ai )] = eiσ ( ai ) と置くことができ，したがって，(13)は与えられた{xi , s− i } に対して，
Viσˆ = ∑ σˆ i ( ai ) * π iσˆ ( ai ) + eiσˆ ( ai ) + β Fiσˆ ( ai )Viσˆ (14)ai ∈Ai

ここに，オペレータ「*」は Hadamard 積を表わす．これより，ˆ) ( I − β Fiσˆ ) −1 ∑ σˆ i ( ai ) * π iσˆ ( ai ) + eiσˆ ( ai ) Viσ=ϕ (σˆ=(15)ai ∈Aiσˆ

ここに， Fi は(12)で与えるマルコフ連鎖の推移確率の定常分布であり，次式を満足する．

Fiσˆ = ∑ σˆ i ( ai ) Fiσˆai ∈Ai3. 計算手法{xi , s− i } は変化するので(15)を満足する行動選択確率，状態価値は変化する．したがって，マルコフ連鎖のエルゴート性を仮定した AE モデルは不動点問題に帰着する．著者は，この問題は Miyagi andPeque(2012)によって提案された学習アルゴリズムで解くことをできると考えている．Miyagi andPeque(2012)のアルゴリズムは状態独立の確率ゲームに応用するために考案されたものであり，目的関数(1)を次のように変更したものに相当する．

1 T

max lim E  ∑π i ( ai ,t +τ , s− i ,t +τ , ε i ,t +1 ) {at }t ≥0 T →∞
 T τ =0

4. まとめ
本研究は，エージェントが多数の場合のマルコフ完全均衡を近似的に解くための手法を提案したもので
あ る ． Weintraub, Benkard, and Van Roy(2008,2009) の ア プ ロ ー チ と は 異 な り ， Aguirregabiria andMira(2002,2007)の NPL(Nested Pseudo-Likelifood)法が利用可能なように再構成した．また，新しい解法の可能性については，数値計算上は収束することを確認しているが，この段階では汎用性のある手法かどうかの保証はできていない．
参考文献
Aguirregabiria, V., Mira, P., (2002). Swapping the nested fixed point algorithm: A class of estimators for discreteMarkov decision models. Econometrica 70,1519-1543.
Aguirregabiria, V. and P. Mira (2007). Sequential Estimation of Dynamic Discrete Games, Econometrica,Vol.75,No.1,pp 1-53.
R. Ericson and A. Pakes, (1995). Markov-perfect industry dynamics: A framework for empirical work. Review ofEconomic Studies, 62(1):53 – 82.
Doraszelski, U., and A. Pakes, (2007). A framework for applied dynamic analysisin IO. Handbook of Industrial
Organization, Vol. 3. North-Holland, Amsterdam.
Hopenhayn, H. A., (1992). Entry, exit and firm dynamics in long run equilibrium. Econometrica, 60(5) 1127-1150.
Hotz, J., Miller, R.A., (1993). Conditional choice probabilities and the estimation of dynamic models. Review of
Economic Studies 60, 497-529.
Jovanovic, B. , R. W. Rosenthal, (1988) Anonymos sequential games. Journal of Mathematical Economics 17, 77-87.
Maskin, E., and J. Tirole,(1988). A theory of dynamic oligopoly, I and II. Econometrica, 56(3) , 549–570.
Miyagi, T. and G. Peque, Jr. (2012). Informed –user algorithms that converges to Nash equilibrium in traffic games,
Procedia-Social Behavioral Science, Elsevier. (in print).
Pakes, A., and P. McGuire, (1994). Computing Markov-perfect Nash equilibria: Numerical implications of a
dynamic differentiated product model. RAND J. Econom. 25(4), 555-589.
Pakes, A., and P. McGuire, (2001). Stochastic algorithms, symmetric Markov perfect equilibrium, and the “curse” ofdimensionality. Econometrica, 69(5) , 1261-1281.
Shapley, L. S. (1953). Stochastic games. Proceeding of the National Academy of Sciences 39 ,1095-1100.
Rust, J., (1987). Optimal replacement of GMC bus engines: An empirical model of Harold Zurcher. Econometrica 55,999-1033.
Weintraub, G. Y., C. L. Benkard, and B. Van Roy. (2008). Markov perfect industry dynamics with many firms.
Econometrica, 76(6), 1375-1411.
Weintraub, G. C.L Benkard and B. Van Roy, (2010): Computational Methods for Oblivious Equilibrium, Operations
Research, 58(4),1247-1265.