13. Stochastic Dynamic Programming: Searching Problem
本章主题：随机动态规划的搜寻问题。 求职市场搜寻问题。§13.1 设定：agent 初始失业、活无限期；每期从分布 \(F(w)\)（\(w\in[0,B]\)，i.i.d.）抽工资 offer；贴现 \(\beta\)；无分离（匹配后永不离职）⟹ 被匹配价值 \(\frac{w}{1-\beta}\)；失业每期得 \(c\)。§13.2 值函数：\(V(w)=\max\{\frac{w}{1-\beta},\,c+\beta\int_0^B V(w')dF(w')\}\)；保留工资 \(\bar w\) 满足 \(\frac{\bar w}{1-\beta}=c+\beta\int_0^B V dF\)，化简得 \(\bar w-c=\frac{\beta}{1-\beta}\int_{\bar w}^B(w'-\bar w)dF(w')\equiv h(\bar w)\)。§13.3 比较静态：\(h'(\bar w)=-\frac{\beta}{1-\beta}(1-F(\bar w))<0\)、\(h''(\bar w)=\frac{\beta}{1-\beta}f(\bar w)>0\)；失业补偿 \(c\uparrow\) ⟹ \(\bar w\uparrow\)；更好的抽取分布（\(F_1\) 一阶随机占优 \(F_2\)，定义 13.1）⟹ \(h_1\ge h_2\) ⟹ \(\bar w_1\ge\bar w_2\)。
Chapter theme: the searching problem of stochastic dynamic programming. A job-market searching problem. §13.1 Set-up: the agent starts unemployed and lives infinite periods; each period draws a wage offer from \(F(w)\) (\(w\in[0,B]\), i.i.d.); discount \(\beta\); no separation (never resigns after matching) ⟹ value of being matched is \(\frac{w}{1-\beta}\); unemployment pays \(c\) per period. §13.2 Value function: \(V(w)=\max\{\frac{w}{1-\beta},\,c+\beta\int_0^B V(w')dF(w')\}\); the reservation wage \(\bar w\) satisfies \(\frac{\bar w}{1-\beta}=c+\beta\int_0^B V dF\), simplifying to \(\bar w-c=\frac{\beta}{1-\beta}\int_{\bar w}^B(w'-\bar w)dF(w')\equiv h(\bar w)\). §13.3 Comparative statics: \(h'(\bar w)=-\frac{\beta}{1-\beta}(1-F(\bar w))<0\), \(h''(\bar w)=\frac{\beta}{1-\beta}f(\bar w)>0\); higher unemployment compensation \(c\uparrow\) ⟹ \(\bar w\uparrow\); a better draw distribution (\(F_1\) first-order stochastically dominates \(F_2\), Definition 13.1) ⟹ \(h_1\ge h_2\) ⟹ \(\bar w_1\ge\bar w_2\).
本章用随机动态规划方法讨论一个具体的求职市场搜寻问题。
13.1 Set-up
- agent 起始时失业，可活无限期。
- 每期 agent 可从分布 \(F(w)\)（\(w\in[0,B]\)）抽取一个工资 offer。每期的抽取是 i.i.d. 的。
- 各取值的贴现因子为 \(\beta\in(0,1)\)。
- 为简便，匹配后不允许分离。这意味着收到 offer 后，agent 永不辞职或换工作；他必在所有剩余期工作以领取不变的 \(w\)。
- 故被匹配的价值为 \(\dfrac{w}{1-\beta}\)。
- 失业每期得 \(c\)。
13.2 Value Function
值函数可写为 $$V(w)=\max\left\{\frac{1}{1-\beta}c+\beta\int_0^B V(w')dF(w')\right\}$$
事实上更精确地， $$V(w)=\max\left\{\frac{w}{1-\beta},\ c+\beta\int_0^B V(w')dF(w')\right\}$$
图示（值函数图，已转述）： 横轴当前 offer \(w\)。一条直线 \(\dfrac{w}{1-\beta}\)（接受 offer 的价值）；一条水平线 \(c+\beta\int_0^B V(w')dF(w')\)（拒绝、继续搜寻的价值）。\(V(w)\) 取二者之大：在小 \(w\) 处为水平段、在大 \(w\) 处沿 \(\dfrac{w}{1-\beta}\) 上升；两者相交于保留工资 \(\bar w\)。
由保留工资 \(\bar w\) 的定义： $$\begin{aligned}\frac{\bar w}{1-\beta}&=c+\beta\int_0^B V(w')dF(w')\\\Rightarrow\frac{\bar w}{1-\beta}-\frac{\beta\bar w}{1-\beta}&=c+\beta\int_0^B V(w')dF(w')-\frac{\beta\bar w}{1-\beta}\\\Rightarrow\bar w-c&=\beta\int_0^B V(w')dF(w')-\frac{\beta\bar w}{1-\beta}\\\Rightarrow\bar w-c&=\beta\int_0^{\bar w}\frac{\bar w}{1-\beta}dF(w')+\beta\int_{\bar w}^B\frac{w'}{1-\beta}dF(w')-\frac{\beta\bar w}{1-\beta}\\\Rightarrow\bar w-c&=\beta\frac{\bar w}{1-\beta}F(\bar w)+\beta\int_{\bar w}^B\frac{w'}{1-\beta}dF(w')-\frac{\beta\bar w}{1-\beta}\\\Rightarrow\bar w-c&=\beta\frac{\bar w}{1-\beta}(F(\bar w)-1)+\frac{\beta}{1-\beta}\int_{\bar w}^B w'dF(w')\\\Rightarrow\bar w-c&=\underbrace{\frac{\beta}{1-\beta}\int_{\bar w}^B(w'-\bar w)dF(w')}_{\equiv h(\bar w)}\end{aligned}$$ 其中用到 \(V(w')=\dfrac{\bar w}{1-\beta}\)（\(w'<\bar w\)）、\(V(w')=\dfrac{w'}{1-\beta}\)（\(w'\ge\bar w\)）。
In this part, we will use the stochastic Dynamic Programming method to discuss a specific job market searching problem.
13.1 Set-up
- The agent starts with being unemployed. He can live for infinite periods.
- Each period, the agent can draw a wage offer from the distribution \(F(w)\) for \(w\in[0,B]\). Draws in each period are i.i.d..
- Discounting factor for values is \(\beta\in(0,1)\).
- For simplicity, no separation after matching is allowed. This means that after receiving the offer, the agent can never resign or switch jobs. Instead, he must be working in all the remaining periods to receive the unchanging \(w\).
- So, the value of being matched is \(\dfrac{w}{1-\beta}\).
- Unemployment for each period is \(c\).
13.2 Value Function
The value function can be written as $$V(w)=\max\left\{\frac{1}{1-\beta}c+\beta\int_0^B V(w')dF(w')\right\}$$
More precisely, $$V(w)=\max\left\{\frac{w}{1-\beta},\ c+\beta\int_0^B V(w')dF(w')\right\}$$
Figure (the value function graph, paraphrased): the horizontal axis is the current offer \(w\). There is a line \(\dfrac{w}{1-\beta}\) (the value of accepting the offer) and a horizontal line \(c+\beta\int_0^B V(w')dF(w')\) (the value of rejecting and keeping searching). \(V(w)\) takes the larger of the two: a flat segment for small \(w\) and then rising along \(\dfrac{w}{1-\beta}\) for large \(w\); the two cross at the reservation wage \(\bar w\).
By the definition of the reservation wage \(\bar w\): $$\begin{aligned}\frac{\bar w}{1-\beta}&=c+\beta\int_0^B V(w')dF(w')\\\Rightarrow\frac{\bar w}{1-\beta}-\frac{\beta\bar w}{1-\beta}&=c+\beta\int_0^B V(w')dF(w')-\frac{\beta\bar w}{1-\beta}\\\Rightarrow\bar w-c&=\beta\int_0^B V(w')dF(w')-\frac{\beta\bar w}{1-\beta}\\\Rightarrow\bar w-c&=\beta\int_0^{\bar w}\frac{\bar w}{1-\beta}dF(w')+\beta\int_{\bar w}^B\frac{w'}{1-\beta}dF(w')-\frac{\beta\bar w}{1-\beta}\\\Rightarrow\bar w-c&=\beta\frac{\bar w}{1-\beta}F(\bar w)+\beta\int_{\bar w}^B\frac{w'}{1-\beta}dF(w')-\frac{\beta\bar w}{1-\beta}\\\Rightarrow\bar w-c&=\beta\frac{\bar w}{1-\beta}(F(\bar w)-1)+\frac{\beta}{1-\beta}\int_{\bar w}^B w'dF(w')\\\Rightarrow\bar w-c&=\underbrace{\frac{\beta}{1-\beta}\int_{\bar w}^B(w'-\bar w)dF(w')}_{\equiv h(\bar w)}\end{aligned}$$ where we used \(V(w')=\dfrac{\bar w}{1-\beta}\) (for \(w'<\bar w\)) and \(V(w')=\dfrac{w'}{1-\beta}\) (for \(w'\ge\bar w\)).
13.3 Comparative Statics
13.3.1 \(h(\bar w)\) 的性质
为做比较静态，先考虑 \(h(\bar w)\) 的性质： $$h'(\bar w)=\frac{-\beta}{1-\beta}\int_{\bar w}^B dF(w')=\frac{-\beta}{1-\beta}(1-F(\bar w))<0$$ $$h''(\bar w)=\frac{\beta}{1-\beta}f(\bar w)>0$$ 其中 \(f\) 是 \(F\) 的密度函数。
13.3.2 比较静态：失业补偿增加
设 \(c_1 13.3.3 比较静态：更好的抽取 设工资抽取的分布从 \(F_2(w)\) 改善到 \(F_1(w)\)，意为 \(F_1(w)\) 一阶随机占优 \(F_2(w)\)。则
$$\begin{aligned}h(\bar w)&=\frac{\beta}{1-\beta}\int_{\bar w}^B(w'-\bar w)dF(w')\\[\text{integral by parts}]&=\frac{\beta}{1-\beta}\left([(w'-\bar w)F(w')]_{\bar w}^B-\int_{\bar w}^B F(w')dw'\right)\\&=\frac{\beta}{1-\beta}\left(B-\bar w-\int_{\bar w}^B F(w')dw'\right)\\&=\frac{\beta}{1-\beta}\left(\int_{\bar w}^B(1-F(w'))dw'\right)\end{aligned}$$ 定义 13.1（一阶随机占优 first order stochastic dominance）
称 \(F_1\) 一阶随机占优（FOSD） \(F_2\)，若 \(F_1(x)\le F_2(x)\) 对 \(\forall x\)。 由 \(F_1(w)\) FOSD \(F_2(w)\)：
$$\begin{aligned}F_1(w')&\le F_2(w')\ \text{for }\forall w'\\\Rightarrow1-F_1(w')&\ge1-F_2(w')\ \text{for }\forall w'\\\Rightarrow\frac{\beta}{1-\beta}\int_{\bar w}^B(1-F_1(w'))dw'&\ge\frac{\beta}{1-\beta}\int_{\bar w}^B(1-F_2(w'))dw'\\\Rightarrow h_1(\bar w)&\ge h_2(\bar w)\end{aligned}$$
图示（已转述）： \(h_1(\bar w)\) 整体位于 \(h_2(\bar w)\) 之上，与同一条 \(\bar w-c\) 线的交点满足 \(\bar w_1\ge\bar w_2\)。由此 \(h_1(\bar w)\ge h_2(\bar w)\Rightarrow\bar w_1\ge\bar w_2\)，即 \(\bar w\) 随抽取分布的改善而递增。这一结果合理：更好的工资抽取分布意味着等待会有更好的机会，故接受当前 offer 的保留价格应上升。
13.3.1 Properties of \(h(\bar w)\)
In order to do some comparative statics, let's first consider the property of \(h(\bar w)\): $$h'(\bar w)=\frac{-\beta}{1-\beta}\int_{\bar w}^B dF(w')=\frac{-\beta}{1-\beta}(1-F(\bar w))<0$$ $$h''(\bar w)=\frac{\beta}{1-\beta}f(\bar w)>0$$ where \(f\) is the density function of \(F\).
13.3.2 Comparative statics: increased unemployment compensation
Suppose \(c_1 13.3.3 Comparative statics: better draw Suppose the distribution of wage draws improves from \(F_2(w)\) to \(F_1(w)\) in the sense that \(F_1(w)\) first order stochastic dominates \(F_2(w)\). Then,
$$\begin{aligned}h(\bar w)&=\frac{\beta}{1-\beta}\int_{\bar w}^B(w'-\bar w)dF(w')\\[\text{integral by parts}]&=\frac{\beta}{1-\beta}\left([(w'-\bar w)F(w')]_{\bar w}^B-\int_{\bar w}^B F(w')dw'\right)\\&=\frac{\beta}{1-\beta}\left(B-\bar w-\int_{\bar w}^B F(w')dw'\right)\\&=\frac{\beta}{1-\beta}\left(\int_{\bar w}^B(1-F(w'))dw'\right)\end{aligned}$$ Definition 13.1 (first order stochastic dominance)
We say \(F_1\) first order stochastic dominance (FOSD) \(F_2\) if \(F_1(x)\le F_2(x)\) for \(\forall x\). Since \(F_1(w)\) FOSD \(F_2(w)\):
$$\begin{aligned}F_1(w')&\le F_2(w')\ \text{for }\forall w'\\\Rightarrow1-F_1(w')&\ge1-F_2(w')\ \text{for }\forall w'\\\Rightarrow\frac{\beta}{1-\beta}\int_{\bar w}^B(1-F_1(w'))dw'&\ge\frac{\beta}{1-\beta}\int_{\bar w}^B(1-F_2(w'))dw'\\\Rightarrow h_1(\bar w)&\ge h_2(\bar w)\end{aligned}$$
Figure (paraphrased): \(h_1(\bar w)\) lies above \(h_2(\bar w)\) everywhere, so their intersections with the same \(\bar w-c\) line satisfy \(\bar w_1\ge\bar w_2\). Hence \(h_1(\bar w)\ge h_2(\bar w)\Rightarrow\bar w_1\ge\bar w_2\), i.e. \(\bar w\) is increasing in the improvement of the draw distribution. This result makes sense because a better distribution of wage draws means better chances for waiting, so the reservation price for accepting the current offer should increase.