Optimal replacement of GMC bus engines: An empirical model of Harold Zurcher

Optimal replacement of GMC bus engines: An empirical model of Harold Zurcher
J Rust - Econometrica 1987

Single Agentの動学最適化問題。バスのエンジンというアプリケーションで推定している。
エンジンの交換という離散的な意思決定をどう分析し、推定するかというのがテーマになっている。

イントロダクション

各期の効用をuとすると、各主体は将来の効用の割引現在価値を最大化するように行動する。具体的には、 $\Pi=(f_0, f_1, ...)$ を意思決定ルールとすると、Agentは以下のValue Functionを最大化するように意思決定ルールを決める。
$V_{\theta} (x_t)= \sup _{\Pi} E \Bigg( \sum \beta ^{j-t} u(x_j, f_j, \theta _1) \Bigg)$
各期の効用は以下のようにかける。（メンテナンスコスト、故障の期待コストを含む。それらは個別には識別できない）
エンジンを交換すると、エンジン代−スクラップバリューを得て、その気はマイレージ０のメンテナンスコストがかかる。
$u(x,f,\theta_1) = c(x,\theta_1)$ if f=0 and $u(x,f,\theta_1)= P^u -P^l +c(0, \theta_1)$ if f=1
今期のマイレージを所与としたときの、来期のマイレージは以下のような分布に従っているとする。
$p(x_{t+1}| x_t, \theta_2, f)= \theta_2 \exp \{ \theta_2(x_{t+1}-x_t \}$
そうすると、普通のValue Functionと同じに以下のようなRepresentationが可能になる。
$V(x_t) =max_{f_t} \{ c(x_t,i, \theta_1) +\beta E_{\theta|x_t,i} V(x_{t+1}) \}$
ここまでだと、（ほとんど）全てがDeterministicなので、Threshold Valueが一意に決まり、それを超えたらエンジン交換、そうじゃなかったらそのままという意思決定ルールが最適になる。しかし、それは明らかにデータからRejectできる。

そこで、どこかにRandomnessを入れる必要がある。最後の結果にAdditiveな項を入れるのが一番簡単だが、いまいちカッコよくないし、誠実な感じがしない。
やっぱりカッコよくて真摯な研究姿勢が見られるのは各期の効用の部分に誤差項を入れるのだろう。

セットアップ

$C(x_t)$ 選択肢の集合
$\epsilon_t=\{ \epsilon _t(i) | i\in C(x_t)$ 各選択肢ごとの誤差項
$u(x_t,i,\theta_1) =-c(x_t, i, \theta_1)+\epsilon_t(i)$ 各期の効用
$p(x_{t+1}, \epsilon_{t+1} | x_t,\epsilon_t, i, \theta_2, \theta_3)$ マルコフ移行確率
$\theta=(\beta, \theta_1,\theta_2,\theta_3)$ 推定したいパラメータ
を定義する。バリューファンクションは似たように書けるけど、今度はXの動きだけでなく、誤差項の分布に関しても積分したり、色々めんどくさくなる。

マルコフという仮定はあるものの、このまま一般的に進めていくのは難しい。そこで、以下の仮定を置く。

メインの仮定

Conditional Independence
$p(x_{t+1}, \epsilon_{t+1} | x_t , \epsilon _t,i,\theta_2,\theta_3 )=q(\epsilon_{t+1} | x_{t+1},\theta_2)p(x_{t+1}|x_t,i,\theta_3)$
CIがあると、２個の状態変数に依存しているバリューファンクションを誤差項に関して積分して、１個の状態変数にしか依存しない期待値的なバリューファンクションを定義しなおすことができて便利。まぁ、以下参照。
まず素直にValue Functionを書いちゃうと、
$V(x_t,\epsilon_t) =\max \{ u(x,i)+\epsilon(i) +\beta EV(x_{t+1},\epsilon_{t+1} |x_t, i, \epsilon_t) \}$
ってなるんだけど、ベータがかかってるバリューファンクションの期待値がすごい複雑になってしまう。
しかし、CIを使うことで上手いこと積分しちゃって期待値の部分の誤差項を消すことができる。

定理１

CIの仮定の下では、
$V^*(x_t)=\int max\{u(x_t,i,\theta)+\epsilon_t(i)+\beta E_{|i}V(x_{t+1}, \epsilon_{t+1} ) \} q(\epsilon_{t}|x_{t},\theta_2)$
を定義すると、以下で定義するMappingはContraction Mappingになっており、V^*はFixed Pointになっている！
$V^*(x_t)=\int max\{u(x_t,i,\theta)+\epsilon_t(i)+\beta E_{|i,x_t}V^*(x_{t+1} ) \} q(\epsilon_{t}|x_{t},\theta_2)$

注：ここまで論文のNotationにできるだけ忠実にやるつもりだったんだけど、あまりにNotationが分かりにくいのでちょっと変えていきます。

CIの仮定から、次期の誤差項は次期の状態変数が分かれば分布が完全にわかる。一方次期の状態変数の分布は今期の選択と今期の状態変数の分布からわかる。つまり、今期の状態変数がわかれば、次期のVFの期待値は今期の誤差項とは無関係に求められる。
ざっくばらんに言うと、定理１はそういうことを言っている。もちろんCIを使ってるからこれが言える。

結論

（パラメータが与えられれば）V^*はIterationで求まるわけだが、そうすると、Staticなモデルの離散選択問題と全く同じ問題になる。
なので、Likelihoodを書くなり、Observed ProbabilityとImplied ProbabilityのDistanceを最小化するなりして、パラメータを求めることができる。
そこまで解いたらMLEを使うものだと思う。フルにバリューファンクションを解いたらMLEで推定できるってのがRustの方法の利点だと思う。効率的に推定できる一方、フルに解くために計算時間が多くなる。

V(x,e)っていうバリューファンクションの不動点を探す問題の中に、V^*(x)っていう小さな問題が入れ子型に入っているからNested Fixed Pointアルゴリズムとか言われるんだと思う。・・・
と思っていたんだけど、実はどうやら、
Inner Roop：V^*(x)をFixed Pointとして見つける
Outer Roop：V^*を使ってChoice Probabilityを導出してMLEで推定する
っていう構造が入れ子になってるからNested Fixed Pointアルゴリズムっていうっぽいです。

疑問

誤差項の（条件付の）Time IndependenceはどれぐらいCrucialな仮定なんだろう。