Problem 691152 · medium · Economics · Level 06 Dynamics and General Equilibrium

A Rainy-Day Jar for the Ferry Pilot

precautionary saving · borrowing constraint · expected utility · dynamic programming · memoisation

Pavo pilots a ferry. His pay depends on the weather, so he keeps a jar of coins. The jar pays no interest, coins are whole, and he cannot borrow.

The periods are t = 0, 1, \ldots, T-1. At the start of period 0 he has m0 coins of cash. In each period with cash m he eats c coins and puts the rest, s = m - c, in the jar, with c \ge 1 and s \ge 0, both whole numbers. At the start of the next period he is paid an income y, drawn at random: incomes[i] with probability probs[i], independently every period, so his cash becomes m' = s + y. In the last period, t = T-1, he eats all his cash (coins left after it are worth nothing).

A period in which he eats c coins gives him \ln c. He chooses his savings to make the expected value of

\sum_{t=0}^{T-1} \beta^t \ln c_t

as large as possible, where \beta is beta (0 < \beta \le 1) and each choice may depend on the cash he has at that time.

Write rainy_day(m0, incomes, probs, beta, T) that returns a tuple (s0, value): the best saving in period 0 and the largest expected value. If several savings in some period come within 1e-9 of the best value, he takes the smallest.

Examples

Input:  m0 = 6, incomes = [1, 9], probs = [0.5, 0.5], beta = 1, T = 2
Output: (2, 3.13454814)
Explanation: saving 2 gives ln 4 + 0.5 ln 3 + 0.5 ln 11 = 3.1345, the best of s = 0..5.

Input:  m0 = 6, incomes = [5], probs = [1], beta = 1, T = 2
Output: (0, 3.40119738)
Explanation: the same average income for sure: saving 0 and saving 1 both give
ln 6 + ln 5, so he takes 0. The risk alone made him save 2 coins more.

Input:  m0 = 10, incomes = [20], probs = [1], beta = 0.95, T = 3
Output: (0, 7.85217913)
Explanation: he would like to borrow against his large future pay, but cannot.

Constraints

  • incomes are whole numbers from 1 to 20 (so cash is always at least 1); probs has the same length and adds up to 1
  • value is compared with a tolerance of 1e-6, s0 exactly

Goals

  • Maximise expected discounted utility when next period's income is random
  • Respect a borrowing limit: savings can never go below zero
  • See that a riskier income with the same average makes a prudent saver put more aside
Starting Python…