동적 이산 선택

동적 프로그래밍의 이산 선택 모델이라고도 알려진 동적 이산 선택(DDC) 모델은 미래의 함의가 있는 이산형 옵션에 대한 에이전트의 선택을 모델링한다.관측된 선택이 정적 효용 극대화의 결과라고 가정하기보다는, DDC 모델에서 관측된 선택은 이산 선택 모델의 기반이 되는 효용 이론을 일반화하면서 효용의 현재 가치를 에이전트로 극대화한 결과라고 가정한다.^[1]

DDC 방법의 목표는 대리인의 의사결정 과정의 구조적 매개변수를 추정하는 것이다.일단 이러한 매개변수가 알려지면, 연구자는 추정치를 사용하여 대리인이 세계의 반사실적 상태에서 어떻게 행동할 것인지 시뮬레이션할 수 있다. (예를 들어, 예비 대학생의 등록금 인상에 대한 결정이 어떻게 변경될 것인가)

수학적 표현

에이전트 $n{\displaystyle }$ ${\displaystylen}$의$$최대화 문제는 다음과 같이 수학적으로 작성할 수 있다.

${\displaystyle V\left(x_{n0}\right)=\max _{\left\{d_{nt}\right\}_{t=1}^{}T}}\mathb {E} \left(\sum _{t^{\premium }=t}^{{}}}^T}\sum _{i=1}^{J}\베타 ^{t'-t}\왼쪽(d_{nt}=i\right)U_{nit}\왼쪽(x_{nt},\varepsilon _{nit}\오른쪽),}$

어디에

• ${\displaystyle x_{}}$ ${\displaystyle n_{}}$ ${\displaystyle t_{}}$ ${\$은(는) 상태 변수로서, $x{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{n}}_{}}$ 0$${\$displaystyle x_{n0}$ 에이전트의$$ 초기 조건이다.
• ${\displaystyle {dn}_{}}$ ${\displaystyle t_{}}$ ${\$은(는$)$ J {\$displaystyle J}$ 이산형$$ 대안 중에서 $n{\displaystyle }$ ${\displaystyle n}$의$$결정을 나타낸다$$.
• ${\displaystyle \beta }$ ${\displaystyle \in }$( 0${\displaystyle }$, ${\displaystyle 1}$) ${\$이(가) 할인 요인임
• ${\displaystyle {Un}_{}}$ ${\displaystyle i_{}}$ ${\$은(는$)$ 기간 t {\$displaystyle t$의 $대안{\displaystyle }$ i {\$displaystyle i}$에서 수신하는 흐름 $n$${\$와 비관측 요인 ${\displaystyle {\epsilon n}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle t_{}}$ ${\$에 모두 의존한다.
• ${\displaystyle T}$ ${\displaystyle T}$은(는) 시간 범위임
• ${\displaystyle {\mathrm{기대<img\; alt="\{\backslash displaystyle\; \backslash mathbb\; \{E\}\; \backslash left(\backslash cdot\; \backslash right)\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/af404759c2b73e9984aefa48dee6bfee9b19c57a"\; style="vertical-align:\; -0.838ex;\; width:4.394ex;\; height:2.843ex;"\; papago-attr-id="60">}}_{}}$ $E{\displaystyle \mathbb{}}$ (${\displaystyle \cdot }$ ) ${\$$displaystyle$ $\mathb {E} \left(\cdot \right)}$은(는$)$ ${\displaystyle x_{}}$ n ${\displaystyle t_{}}$ ${\$s 및 ${\displaystyle {and}_{}}$ n ${\displaystyle i_{}}$ t ${\$ $_{nit}$에$$있다$.$즉, 에이전트는 주의 향후 전환에 대해 불확실하며, 또한 관찰되지 않은 요인의 향후 실현에 대해서도 불확실하다.

가정 및 표기법 단순화

동적 의사결정 문제의 다음과 같은 단순화된 가정과 표기법을 부과하는 것이 표준이다.

1. 흐름 효용은 추가적으로 분리할 수 있고 매개변수가 선형이다.

흐름 효용은 결정론적 요소와 확률적 요소로 구성되는 부가적인 합으로 작성할 수 있다.결정론적 구성요소는 구조 매개변수의 선형 함수로 작성할 수 있다.

${\displaystyle {\reasonedat}{5}U_{nit}\left(x_{nt},\varepsilon _{nit}\right)&&\;=\;&&u_{nit}&&\;+\;&&\varepsilon _{nit}\\&&\;=\;&&X_{nt}\alpha _{i}&&\;+\;&&\varepsilon _{nit}\end{alignedat}}}$

2. 최적화 문제는 Bellman 방정식으로 쓸 수 있다.

$\epsilon n{\displaystyle {}_{}}$ ${\displaystyle t_{}}${\$displaystyle n}$의 개별$n {\displaystyle$n$}$에 대한 ex ante 값 함수를$$${\displaystyle {\mathrm{nn}}_{}}$ t ${\$$displaystyle t}$에 따라 ${\displaystyle {}_{}}$하십시오. $definen{\displaystyle {}_{}}$ t {\$displaystyle \varepsilon _{nt}:$

${\displaystyle V_{nt}(x_{nt})=\mathbb {E} \max _{i}\left\{u_{nit}(x_{nt})+\varepsilon _{nit}+\beta \int _{x_{t+1}}V_{nt+1}(x_{nt+1})\,dF\left(x_{t+1}\mid x_{t}\right)\right\}}$

where the expectation operator ${\displaystyle \mathbb {E} }$ is over the ${\displaystyle \varepsilon }$'s, and where ${\displaystyle dF\left(x_{t+1}\mid x_{t}\right)}$ represents the probability distribution over ${\displaystyle x_{t+1}}$ conditional on ${\dis$$플레이스타일 x_{t}}$.상태 전환에 대한 기대는 이 확률 분포에 대한 적분을 취함으로써 달성된다.

$V{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle t_{}}$( x ${\displaystyle n_{}}$ ${\displaystyle t_{}}$) ${\displaystyle V_{nt}(x_{nt})$를 결정론적이고 확률론적인 구성 요소로 분해할 수 있다.

${\displaystyle V_{nt}(x_{nt})=\mathb {E}\max _{i}\left\{v_{nit}(x_{nt})+\varepsilon _{nit}\right\}}}}}}}}}$

여기서 ${\displaystyle {vn}_{}}$ ${\displaystyle i_{}}$ ${\$은(는) 시간 $t{\displaystyle }$ ${\displaystyle t}$에서 대체 $i{\displaystyle }$ ${\displaystyle i}$을(를) 선택하는 값이며 다음과$$$$ 같이 기록된다.

${\displaystyle v_{nit}(x_{nt})=u_{nit}\left(x_{nt}\right)+\beta \int _{x_{t+1}}\mathbb {E} \max _{j}\left\{v_{njt+1}(x_{nt+1})+\varepsilon _{njt+1}\right\}\,dF(x_{t+1}\mid x_{t})}$

여기서 이제 기대 $E{\displaystyle \mathbb{}}$ ${\$${\displaystyle {\mathrm{E}}_{}}$$}}$이(가) $\epsilon {\displaystyle {}_{}}$ ${\displaystyle n_{}}$ j ${\displaystyle t_{}}$+ 1 ${\$을(를) 인수한다$.$

3. 최적화 문제는 마르코프 의사결정 과정을 따른다.

상태 $x{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$는 마르코프 체인을 따른다$$.즉, $상태{\displaystyle {}_{}}$ ${\displaystyle x_{}}$ t ${\$의 달성은 $상태{\displaystyle {}_{}}$ x${\displaystyle t_{}}$ - ${\displaystyle 1_{}}${\$displaystyle x_{t-1}$에만 $의존$하며 ${\displaystyle x_{}}$- ${\displaystyle 2_{}}${\$displaystyle x_{t-2}$ 또는$$ 이전 상태가 아니다.

조건부 값 함수 및 선택 확률

이전 절의 값 함수는 $기간{\displaystyle }$ t ${\displaystyle t}$에서 대안 $i{\displaystyle }$ ${\displaystyle i}$를 선택하는 조건부 값 함수가 되기 때문에 조건부 값 함수를 이렇게 쓰는 것이 선택 확률에 대한 공식을 구성하는 데 유용하다$.$

선택 확률을 기록하려면, 연구자는$$${\displaystyle {\epsilon n}_{}}$ i ${\displaystyle t_{}}$ ${\$s의 분포에 대해 가정을 해야 한다.정적 이산 선택 모델에서와 같이, 이 분포는 iid Type I 극단값, 일반화된 극단값, 다항 프로빗 또는 혼합 로짓으로 가정할 수 있다.

${\displaystyle {\epsilon n}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle t_{}}$ ${\$이 다항 로짓(즉, 타입 I 극단값 분포에서 iid를 추출)인 경우, 선택 확률을 위한 공식은 다음과 같다.

${\displaystyle P_{nit}={\frac {\exp(v_{nit})}{\sum _{j=1}^{J}\exp(v_{njt})}}}$

추정

동적 이산 선택 모델의 추정은 연구자가 구조 매개변수의 각 추측에 대해 역반복 문제를 해결해야 하기 때문에 특히 어렵다.

구조 매개변수를 추정하는 데 사용되는 가장 일반적인 방법은 최대우도 추정과 시뮬레이션 모멘트의 방법이다.

추정 방법 외에도 해법도 있다.문제의 복잡성 때문에 다른 해결 방법을 사용할 수 있다.이것들은 풀솔루션 방식과 비솔루션 방식으로 나눌 수 있다.

풀솔루션 방법

풀솔루션 방식의 가장 중요한 예는 1987년 존 러스트(John Rust)^[2]가 개발한 중첩 고정점(NFXP) 알고리즘이다.NFXP 알고리즘은 설명서 매뉴얼에 자세히 설명되어 있다.^[3]

2012년^[4] Che-Lin Su와 Kenneth Judd의 최근 연구는 균형 제약이 있는 수학 프로그래밍의 특별한 경우인 우도함수의 제한된 최적화를 사용하는 또 다른 접근법 (1987년 Rust에 의해 난치될 수 있는 것으로 해석)을 시행한다.특히 우도함수는 모형이 부과하는 제약조건에 따라 극대화되며, 모형의 구조를 설명하는 추가 변수의 관점에서 표현된다.이 접근방식은 최적화 문제의 높은 차원성 때문에 Artelys Nitro와 같은 강력한 최적화 소프트웨어가 필요하다.일단 해결되면, 가능성을 최대화하는 구조적 매개변수와 모형의 해법이 모두 발견된다.

후기 기사^[5] 러스트와 공저자는 NFXP와 비교한 MPEEC의 속도 이점이 크지 않다는 것을 보여준다.그러나, MPEC에서 요구하는 연산들은 모델의 구조에 의존하지 않기 때문에, 그것의 구현은 훨씬 덜 노동 집약적이다.

수많은 경쟁자들에도 불구하고, NFXP 최대우도 추정기는 마르코프 의사결정 모델의 선도적인 추정 방법으로 남아 있다.^[5]

비솔루션 방법

풀솔루션 방법의 대안은 비솔루션 방법이다.이 경우 연구자는 각 모수 추측에 대해 역귀속 문제를 완전히 해결할 필요 없이 구조 매개변수를 추정할 수 있다.비솔루션 방법은 더 많은 가정을 요구하면서 일반적으로 더 빠르지만, 추가 가정은 많은 경우에 현실적이다.

대표적인 비솔루션 방법은 V가 개발한 조건부 선택 확률이다.조셉 핫즈와 로버트 A.밀러^[6]

예

버스 엔진 교체 모델

세미날 페이퍼 러스트(1987)에서 개발된 버스 엔진 교체 모델은 실제 데이터를 사용해 추정된 이산 선택의 최초의 동적 확률 모델 중 하나이며, 이러한 유형의 문제에 대한 고전적인 예로서 계속 기능하고 있다.^[4]

이 모델은 위스콘신주 매디슨 메트로폴리탄 버스 회사의 관리 감독인 해롤드 주셔가 직면한 단순 재생 최적 정지 확률론적 동적 문제다.각 기간 동안 운행 중인 모든 버스의 경우 해롤드 주셔는 엔진을 교체하고 관련 교체 비용을 부담할 것인지, 아니면 고장의 경우 보험과 승객 수송 손실 비용을 포함하여 계속 인상되는 운영 비용으로 버스를 계속 운행할 것인지를 결정해야 한다.

$let{\displaystyle {}_{}}$ x ${\displaystyle t_{}}${\$displaystyle x_{$t}}은(는) $기간{\displaystyle }$t {\$displaystyle$ t$\},$ $c{\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ,${\displaystyle {}_{}\theta }$)$${\$displaystyle c(x_{$t$\},\backslash$$ta$ $)$에서 주행 기록계 수치(마일리지)를$$ 나타내며, 이 값은 $매개{\displaystyle }$ 변수 $\$ {\$displaystate \ta$\}, 엔진 및 $RC}$의 벡터에 의존한다.${\displaystyle \beta }$ ${\displaystyle \$property$}$그러면 기간 유틸리티는 다음에 의해 주어진다.

${\displaystyle U(x_{t},\xi _{t},d,\theta )={\begin{cases}-c(x_{t},\theta )+\xi _{t,{\text{keep}}},&\\-RC-c(0,\theta )+\xi _{t,{\text{replace}}},&\end{cases}}=u(x_{t},d,\theta )+{\begin{cases}\xi _{t,{\text{keep}}},&{\textrm {if}}\;\;d={\text{keep}},\\\xi _{t,{\text{replace}}},&{\textrm {if}}\;\;d={\text{replace}},\end{cases}}}$

여기서 $d{\displaystyle }$ ${\displaystyle d}$은 결정(유지 또는 교체) 및 $\xi {\displaystyle {}_{}}$ ${\displaystyle t_{}}$를 나타내며$$${\displaystyle {,}_{}}$ ${\$은(는) 해롤드 주셔가 관찰한 유틸리티의 구성요소를 나타내며$$, 존 러스트가 아니다.It is assumed that ${\displaystyle \xi _{t,{\text{keep}}}}$ and ${\displaystyle \xi _{t,{\text{replace}}}}$ are independent and identically distributed with the Type I extreme value distribution, and that ${\displaystyle \xi _{t,\bullet }}$ are independent of ${\displaystyle {\xi }_{t-1,\bullet }}$${\$$displaystyle \xi _{t-1,\$$displaystyle x_{t}}$을(를) $조건$으로 한다$.$

그러면 최적의 결정은 Bellman 방정식을 만족시킨다.

${\displaystyle V(x,\xi ,\theta )=\max _{d={\text{keep}},{\text{replace}}}\left\{u(x,d,\theta )+\xi _{d}+\iint V(x',\xi ',\theta )q(d\xi '\mid x',\theta )p(dx'\mid x,d,\theta )\right\}}$

여기서 $p{\displaystyle (d}$ ${\displaystyle {}^{}}$ ${\displaystyle \prime }$ ${\displaystyle x}$, ${\displaystyle d}$, d ,${\displaystyle \theta }$ )$${\$displaystyle p($dx$'\$${\displaystyle {}^{}}$$x$,d$,\theta$ $)}$ $및{\displaystyle q}$(${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ′ ${\displaystyle \prime }$ x${\displaystyle {}^{}\prime ,\theta }$) {\$displaystyle q(d\$xi '\$mid$ x$',\ta$)은 관측되지 않은 상태 변수의 변환 밀도이다$$.벨만 방정식의 시간 지수는 모델이 무한 수평선 설정에서 공식화되고, 알 수 없는 최적 정책이 정지되어 있기 때문에, 즉 시간과 무관하게 떨어지게 된다.

$($ ${\displaystyle {}^{}}$ ${\displaystyle \prime }$ ${\displaystyle {}^{}}$ x ′${\displaystyle }$,${\displaystyle {}^{}}$θ${\displaystyle }$)에 대한 분포 가정을 고려할 때$,$ d ${\displaystyle$ $q(d\xi 'mid x',\theta$ )에 $의해$ 특정 선택 $확률$은 다음과$$ 같다$.$

${\displaystyle P(d\mid x,\theta )={\frac {\exp\{u(x,d,\theta )+\beta EV(x,d,\theta )\}}{\sum _{d'\in D(x)}\exp\{u(x,d',\theta )+\beta EV(x,d',\theta )\}}}}$

여기서 $E{\displaystyle }$ ${\displaystyle V(x}$, ${\displaystyle d}$ ,${\displaystyle \theta }$) ${\displaystyle EV(x,d,\theta )}$는 기능 방정식의 고유한 솔루션이다$$.

${\displaystyle EV(x,d,\theta )=\int \left[\log \left(\sum _{d={\text{keep}},{\text{replace}}}\exp\{u(x,d',\theta )+\beta EV(x',d',\theta )\}\right)\right]p(x'\mid x,d,\theta ).}$

후자의 기능 방정식은 상태 공간 x ${\displaystyle t_{}}$ ${\$가 경계된$$ 경우 수축 매핑을 정의하므로$,$ 어떤 $\theta {\displaystyle }$ ${\displaystyle \ta}$에 대해서도$$ 고유한 솔루션 $x,d,\teta$)가 있을 것이고$,$ 나아가 암묵적 함수 정리가 유지될 $것$이므로 ${\displaystyle \mathrm{EV}}$(${\displaystyle x}$${\displaystyle )}$는 X이다.${\displaystyle ,}$ ${\displaystyle d}$ ,${\displaystyle \theta }$) ${\displaystyle EV(x,d,\$$theta$ $)}$도 $각각$ ($x$ ,$$d$$${\displaystyle }$) $displaystyle$$\$theta$$$}$의 부드러운 기능이다$.$

내포 고정점 알고리즘을 사용한 추정

The contraction mapping above can be solved numerically for the fixed point ${\displaystyle EV(x,d,\theta )}$ that yields choice probabilities ${\displaystyle P(d\mid x,\theta )}$ for any given value of ${\displaystyle \theta }$. The log-likelihood function can then be formulated as

${\displaystyle L(\theta )=\sum _{i=1}^{{N}\sum _{t=1}^{{t=1}^{}}T_{i}}\log(P(d_{it}\mid x_{it},\theta )+\log(x_{it}\mid x_{it-1},d_{it-1},\ta )),}$

where ${\displaystyle x_{i,t}}$ and ${\displaystyle d_{i,t}}$ represent data on state variables (odometer readings) and decision (keep or replace) for ${\displaystyle i=1,\dots ,N}$ individual buses, each in ${\displaystyle t=1,\dots ,T_{i}}$ periods.

parameter {\$displaystyle \theta}$ 매개 변수 $\theta {\displaystyle }$ ${\$displaystyle $\the}$의 특정 값을 부여하고$$ $\theta {\displaystyle }$ ${\displaystyle$ $(\theta )$을 최대화하기 위한 고정점 문제의 공동 알고리즘은 존 러스트 내포 고정점 알고리즘(NFXP)에 의해 명명되었다$$.

내포된 고정점 알고리즘의 러스트의 구현은 확률 극대화를 위해 뉴턴-칸토로비치 반복을 사용하여 $P{\displaystyle (d}$ ${\displaystyle \mid }$ ${\displaystyle x}$ ,$){\displaystyle P(d\mid$ x,\$theta )}$와 준뉴턴 방법(예: Berndt-Hall-Hall-Hausman 알고리즘)을 계산하여 이 문제에 매우 최적화되어 있다.^[5]

엠펙을 사용한 추정

중첩 고정점 알고리즘에서 $P{\displaystyle (d}$∣ x ,${\displaystyle \theta }$ )${\displaystyle P(d\mid x,\theta )}$는 매개변수 θ의 각 추측에 대해 재계산된다$$.대신 MPEC 방법은 제한된 최적화 문제를 해결한다.^[4]

${\displaystyle {\begin{aligned}\max &\qquad L(\theta )&\\{\text{subject to}}&\qquad EV(x,d,\theta )=\int \left[\log \left(\sum _{d={\text{keep}},{\text{replace}}}\exp\{u(x,d',\theta )+\beta EV(x',d',\theta )\}\right)\right]p(x'\mid x,d,\theta )\end{aligned}}}$

이 방법은 중첩된 고정점 알고리즘의 최적화되지 않은 구현보다 계산이 빠르고, 고도로 최적화된 구현에 걸리는 시간이다.^[5]

비솔루션 방법을 사용한 추정

Hotz와 Miller의 조건부 선택 확률 방법을 이 설정에 적용할 수 있다.Hotz, Miller, Sanders, Smith는 이 방법의 계산적으로 더 간단한 버전을 제안했고, 버스 엔진 교체 문제에 대한 연구에서 그것을 테스트했다.이 방법은 시뮬레이션을 사용하여 조건부 선택 확률을 추정한 다음 값 함수의 내재적 차이를 배제하는 방식으로 작동한다.^[7][8]

참고 항목

• 역보강학습

참조

추가 읽기

• Aguirregabiria, Victor; Mira, Pedro (2010). "Dynamic discrete choice structural models: A survey" (PDF). Journal of Econometrics. Elsevier BV. 156 (1): 38–67. doi:10.1016/j.jeconom.2009.09.007. ISSN 0304-4076.
• Keane, Michael P.; Wolpin, Kenneth I. (2009). "Empirical applications of discrete choice dynamic programming models". Review of Economic Dynamics. 12 (1): 1–22. doi:10.1016/j.red.2008.07.001.
• Rust, John (1987). "Optimal Replacement of GMC Bus Engines: An Empirical Model of Harold Zurcher". Econometrica. 55 (5): 999–1033. doi:10.2307/1911259. ISSN 0012-9682. JSTOR 1911259.
• Rust, John (1994). "Chapter 51 Structural estimation of markov decision processes". Handbook of Econometrics. Vol. 4. Elsevier. pp. 3081–3143. doi:10.1016/s1573-4412(05)80020-0. ISBN 978-0-444-88766-5. ISSN 1573-4412.