DiscreteDP Example: Job Search

Daisuke Oyama

Faculty of Economics, University of Tokyo

We study an optimal stopping problem, in the context of job search as discussed in http://quant-econ.net/py/lake_model.html.


In [1]:
using QuantEcon
import QuantEcon: solve
using Distributions
using PyPlot
using Roots

Optimal solution

We skip the description of the model, just writing down the Bellman equation: $$ \begin{aligned} U &= u(c) + \beta \left[(1 - \gamma) U + \gamma E[V_s]\right], \\ V_s &= \max\left\{U, u(w_s) + \beta \left[(1 - \alpha) V_s + \alpha U\right] \right\}. \end{aligned} $$ For this class of problem, we can characterize the solution analytically.

The optimal policy $\sigma^*$ is monotone; it is characterized by a threshold $s^*$, for which $\sigma^*(s) = 1$ if and only if $s \geq s^*$, where actions $0$ and $1$ represent "reject" and "accept", respectively. The threshold is defined as follows: Let $$ \begin{aligned} g(s) &= u(w_s) - u(c), \\ h(s) &= \frac{\beta \gamma}{1 - \beta (1 - \alpha)} \sum_{s' \geq s} p_s u(w_s). \end{aligned} $$ It is easy to see that $g$ is increasing and $h$ is decreasing. Then the threshold $s^*$ is such that $s \geq s^*$ if and only if $g(s) > h(s)$.

Given $s^*$, the optimal values can be computed as follows: $$ \begin{aligned} U &= \frac{\{1 - (1 - \alpha) \beta\} u(c) + \beta \gamma \sum_{s \geq s^*} p_s u(w_s)} {(1 - \beta) \left[\{1 - (1 - \alpha) \beta\} + \beta \gamma \sum_{s \geq s^*} p_s\right]}, \\ V_s &= \begin{cases} U & \text{if $s < s^*$} \\ \dfrac{u(w_s) + \alpha \beta U}{1 - (1 - \alpha) \beta} & \text{if $s \geq s^*$}. \end{cases} \end{aligned} $$

The optimal policy defines a Markov chain over $\{\text{unemployed}, \text{employed}\}$. Its stationary distribution is $\pi = \left(\frac{\alpha}{\alpha + \lambda}, \frac{\lambda}{\alpha + \lambda}\right)$, where $\lambda = \gamma \sum_{s \geq s^*} p(w_s)$; note that the flow from unemployed to employed is $\lambda$, while the flow from employed to unemployed is $\alpha$.

The expected value at the stationary distribution is $$ \pi_0 U + \pi_1 \frac{\sum_{s \geq s^*} p_s V_s}{\sum_{s \geq s^*} p_s}. $$

The above analytical solution aside, we solve the job search problem using the DiscreteDP type:


In [2]:
type JobSearchModel
    # Parameters
    w::Vector{Float64}
    w_pdf::Vector{Float64}
    beta::Float64
    alpha::Float64
    gamma::Float64
    rho::Float64
    # Internal variables
    u::Function
    ddp::DiscreteDP
    num_states::Integer
    num_actions::Integer
    rej::Integer
    acc::Integer
    
    function JobSearchModel(w::Vector, w_pdf::Vector, beta::Float64;
                            alpha::Float64=0., gamma::Float64=1., rho::Float64=0.)
        # Utility function
        function u(y::Vector{Float64})
            small_number = -9999999
            nonpositive = (y .<= 0)
            if rho == 1
                util = log(y)
            else
                util = (y.^(1 - rho) - 1)/(1 - rho)
            end
            util[nonpositive] = small_number
            return util
        end
        u_w = u(w)
        
        num_states = length(w) + 1
        num_actions = 2
        rej, acc = 1, 2
        
        # Reward array
        R0 = zeros(num_states, num_actions)
        R0[1:end-1, acc] = u_w
        
        # Transition probability array
        Q = zeros(num_states, num_actions, num_states)
        # Reject
        for s in 1:num_states
            Q[s, rej, 1:end-1] = w_pdf * gamma
            Q[s, rej, end] = 1 - gamma
        end
        # Accept
        for s in 1:num_states-1
            Q[s, acc, s] = 1 - alpha
            Q[s, acc, end] = alpha
        end
        Q[end, acc, 1:end-1] = w_pdf
        
        ddp = DiscreteDP(R0, Q, beta)
        
        js = new(w, w_pdf, beta, alpha, gamma, rho, u, ddp,
                 num_states, num_actions, rej, acc)
        return js
    end
end;

In [3]:
function solve(js::JobSearchModel, c::Float64)
    n, m = js.num_states, js.num_actions
    rej = js.rej
    js.ddp.R[:, rej] = js.u([c])[1]
    js.ddp.R[end, :] = js.u([c])[1]
    
    res = solve(js.ddp, PFI)
    V::Vector{Float64} = res.v[1:end-1]  # Values of jobs
    U::Float64 = res.v[end]  # Value of unemployed
    C::Vector{Int64} = res.sigma[1:end-1] - 1  # Optimal policy

    lamb::Float64 = dot(js.w_pdf, C) * js.gamma
    pi::Vector{Float64} = [js.alpha, lamb]
    pi /= sum(pi)  # Stationary distribution
    
    return V, U, C, pi
end;

The following paramter values are from lakemodel_example.py.


In [4]:
w = linspace(0, 175, 201)  # wage grid

# compute probability of each wage level 
logw_dist = Normal(log(20), 1)
logw_dist_cdf = cdf(logw_dist, log(w))
logw_dist_pdf = logw_dist_cdf[2:end] - logw_dist_cdf[1:end-1]
logw_dist_pdf /= sum(logw_dist_pdf)
w = Array((w[2:end] + w[1:end-1])/2);

In [5]:
gamma = 1.
alpha = 0.013  # Monthly
alpha_q = (1-(1-alpha)^3)  # Quarterly
beta = 0.99
rho = 2.  # risk-aversion;

In [6]:
js = JobSearchModel(w, logw_dist_pdf, beta, alpha=alpha_q, gamma=gamma, rho=rho);

Take a look at the optimal solution for $c = 40$ for example:


In [7]:
c = 40.
V, U, C, pi = solve(js, c);

In [8]:
s_star = length(w) - sum(C) + 1
println("Optimal policy: Accept if and only if w >= $(w[s_star])")


Optimal policy: Accept if and only if w >= 65.1875

In [9]:
fig, ax = subplots(figsize=(6, 4))
ax[:plot](w, V, label=L"$V$")
ax[:plot]((w[1], w[end]), (U, U), "r--", label=L"$U$")
ax[:set_title]("Optimal value function")
ax[:set_xlabel]("Wage")
ax[:set_ylabel]("Value")
legend(loc=2)
show()


Optimal unemployment insurance policy

We compute the optimal level of unemployment insurance as in the lecture, mimicking lakemodel_example.py.


In [10]:
type UnemploymentInsurancePolicy
    w::Vector{Float64}
    w_pdf::Vector{Float64}
    beta::Float64
    alpha::Float64
    gamma::Float64
    rho::Float64
    
    function UnemploymentInsurancePolicy(w::Vector, w_pdf::Vector, beta::Float64;
                                         alpha::Float64=0., gamma::Float64=1., rho::Float64=0.)
        uip = new(w, w_pdf, beta, alpha_q, gamma, rho)
        return uip
    end
end;

In [11]:
function solve_job_search_model(uip::UnemploymentInsurancePolicy,
                                c::Float64, T::Float64)
    js = JobSearchModel(uip.w-T, uip.w_pdf, uip.beta,
                        alpha=uip.alpha, gamma=uip.gamma, rho=uip.rho)
    V, U, C, pi = solve(js, c-T)
    return V, U, C, pi
end;

In [12]:
function budget_balance(uip::UnemploymentInsurancePolicy, c::Float64, T::Float64)
    V, U, C, pi = solve_job_search_model(uip, c, T)
    return T - pi[1]*c
end;

In [13]:
function implement(uip::UnemploymentInsurancePolicy, c::Float64)
    # Budget balancing tax given c
    T = fzero(T -> budget_balance(uip, c, T), 0., c, xtolrel=1e-3)
    
    V, U, C, pi = solve_job_search_model(uip, c, T)
    
    EV = dot(C .* V, uip.w_pdf) / (dot(C, uip.w_pdf))
    W = pi[1] * U + pi[2] * EV
    
    return T, W, pi
end;

In [14]:
uip = UnemploymentInsurancePolicy(w, logw_dist_pdf, beta,
                                  alpha=alpha_q, gamma=gamma, rho=rho);

In [15]:
grid_size = 26
cvec = linspace(5, 135, grid_size)
Ts, Ws = Array(Float64, grid_size), Array(Float64, grid_size)
pis = Array(Float64, 2, grid_size)

for (i, c) in enumerate(cvec)
    T, W, pi = implement(uip, c)
    Ts[i], Ws[i], pis[:, i] = T, W, pi
end
i_max = indmax(Ws)
println("Optimal unemployment benefit: $(cvec[i_max])")


Optimal unemployment benefit: 67.4

In [16]:
function plot(ax, y_vec, title)
    ax[:plot](cvec, y_vec)
    ax[:set_xlabel](L"$c$")
    ax[:vlines](cvec[i_max], ax[:get_ylim]()[1], y_vec[i_max], "k", "-.")
    ax[:set_title](title)
end

fig, axes = subplots(2, 2)
plot(axes[1, 1], Ws, "Welfare")
plot(axes[1, 2], Ts, "Taxes")
plot(axes[2, 1], vec(pis[2, :]), "Employment Rate")
plot(axes[2, 2], vec(pis[1, :]), "Unemployment Rate")

tight_layout()
show()



In [17]:
fig, ax = subplots(figsize=(6, 4))
plot(ax, cvec-Ts, "Net Compensation")
show()



In [ ]: