How to eat a cake?

The simple cake eating problem

Suppose that you have a cake of size $K$. You can eat today the whole cake, but you will be hungry in the future. Or you can eat small pieces every day. The question is: how much of the cake would you eat each day?

Of course, preferences play an important role, we assume that you like eating cake, and that when you are eating it in any given day first slices seems tastier than the latter, which can be generalized in a instantaneous utility function which $u'(c)>0$ and $u''(c)<0$. Also, you are impatient, therefore we can assume that your intetemporal utility function is given by $U(\{c\}_{t=0}^\infty)=\sum_{t=0}^\infty \beta^t u(c_t)$.

The unit of time are days represented by $t \in \{1;2;3;...T\}$. The cake does not spoil or grow, so $K_t=K_{t-1}-c_{t-1}$. So what to do?

If $T=2$ the problem is quite simple, we can use real analysis, that is we want to find $c^*\in R^2$ that maximices the utility. If $T=\infty$ we have a problem, we are in a diferent space, no longer in $R^n$. We are not looking for a vector we are looking for a sequence $\{c\}_{t=0}^\infty$, we can think about it as an infinite dimension vector, or as a function (that's why function analysis is used).

What would you do if you know that tomorrows the world ends?

It is a dramatic way to think the above problem with (a finete $T$) as if you were at time $T-1$. Let's write the problem a little more Bellman:

$$ V_{T-1}(K_{T-1})=max_{c_{T-1},c_T} \{ u(c_{T-1})+\beta u(c_T) \} \text{ subject to: }K_{T-1}=c_{T-1}+c_T \} $$

With an easier notation, and knowing that the last period consumption will be $c_T=K_T$, so the value function of last period would be $V_T(K')=u(K')$

$$ V_{T-1}(K)=max_{c} \{ u(c)+\beta V(K') \} \text{ subject to: } K'=K-c $$

Suppose $u(c)=ln(c)$. It is easy to solve it with pen and paper. How to solve it with Julia?

Let put some numbers: $\beta=0.9$ $K_{T-1}=100$

A not very efficent Algorithm

I think it is useful to understand a simple method of how to find a maximun. It could give some intuition on how is a computer approach to optimization rather than the typical derivative equals 0 with pen and paper.

The mian idea is to try a lot of values for $c$ and take the one that gives the greatest value.

We know that $c\in [0,K]$, but there are infinite many options, so we discretizise the space. For example, since $K=100$ we can define $C=\{0,1,2,...,100\}$

Then we evaluate the function in everý point.

Finally we choose the greatest.

Using a solver

The solver Optim.jl works fine for us

What if the cake would have been different?

We didn't find a function $V_{T-1}(K_{T-1})$. We found an specific value of its image given an specific value of $K_{T-1}$.

What is a function? For now, let's say it is set of order pairs, e.g. $f=\{(x,y):y=f(x)\}$, this is convinient for a computational perspective. Although, Julia can deal with closed form functions as we usually think of them, a more general approach is to discretize the domain and think of the function as a collection of points, the graph of the function.

So now we have to find $V_{T-1}(K_{T-1})$ for $K_{T-1}\in(0,100]$ for example. It is useful to read the notebook on Interpolation.

What if there is another day before the end of the world?

Instead of thinking in a sequential way like this:

$$ V_{T-2}(K_{T-2})=max_{c_{T-2},c_{T-1},c_T} \big\{ u(c_{T-2})+\beta u(c_{T-1}) + \beta^2 u(c_T) \big\} \text{ subject to: }K_{T-1}=K_{T-2}+c_{T-1}+c_T $$

We can build on previous work. That is: $$ V_{T-2}(K_{T-2})=max_{c_{T-2}} \big\{ u(c_{T-2}) + \beta V_{T-1}(K_{T-1}) \big\} \text{ subject to: } K_{T-2}=K_{T-1}+c_{T-2} $$

We already know the function $V_{T-1}(K)$. In fact, in orther to get the function $V_{T-2}(K)$ the process is almost the same. Again we have to find the value of $c$ that maximices that objective function for a grid of $K$.

It is very helpful to read the notebook about Interpolation. In a hurry, linear interpolation is taking dots in a plane and conecting them with a straight line. If we are working with a grid as domain and the image of a function in those points of the grid, linear interpolation makes the function continuos

What happens n days before T?

We simply have to repeat the process. This process that goes backwards a day is called a mapping, which is another way to say function. For convention we will use mapping for something that eats functions and spits functions (instead of numbers).

So we have:

$$ V_{T-n}=T(V_{T-(n-1)}) $$

For simplicity, we can write:

$$ V_n=T(V_{n-1}) $$

What if the world never ends?

One remarkable thing about the above Bellman operator us that this mapping is a contraction, that is to say that in each step $V_n$ and $V_{n-1}$ are less different. In fact, there is a fixed point, in other words a value of $n$ so big that $V_n=V_{n-1}$ (or almost equals). Why does it matter? Because if the problem is infinitely long, we still can find $V$ at time $0$, we do not need to do infinite steps, just some steps.

Was that enough?

In the previous code I iterated $n$ times. But was that enough? The idea is to get a fixed point (or loosly speaking a fixed function). However, it is not necessary that $V_n$ and $V_{n+1}$ to be exactly the same, maybe some mesurement of how similar they are would be useful. Actually, it is better to measure how different they are, because we can think about the difference as some number that if it is 0 then they are the same, but it grows as the two funcrions became more differents, so the rule is the closer to 0 the better. Tinking in how similar two things are it is a little more tricky, what is exactly the same in this context? $\infty$?.

So we have to measure difference between two functions, it may be easier to think in an easier space first. Let's go back to real analysis: How can you measure difference between two real numbers? $|x-y|$ this difference is better known as distance. How can we measure distance in a plane? Pitagoras already told us that. There are many ways of measuring the difference of two things, that is to say of calculating the distance between them. This concept of distance it is key in Calculus, and it is key in functional analysis (Calculus in bigger spaces).

One last comment, there are two closely related concepts distance and norm, the mian difference is you calculate the distance of two things, while you calculate the norm of a single element. For example, let's think in $R$, $|\;|$ is a norm, so we now that $|-5|=5$; that norm induce a distance (a way of measuring how differents two things are) that is $d(x,y)=|x-y|$, so the distance between 2 and 5 is $d(2,5)=|2-5|=|-3|=3$. In Julia with the LinearAlgebra.jl package we are provided with a function called norm, that do what the name says, so we can use ir to induce a distance.

Let's suppose $a$ is a real vector (or iterable) such that $a=[a_1,a_2,a_3,...a_N]$. Julia's LinearAlgebra default norm is: $$ `norm(a)`=\sqrt{\sum_{i=1}^N a_i^2} $$ Which induce de Pitagora's distance distance_pitagoras(a,b)=norm(a-b).

Since we are actually working with vectors, that aproximate functions, things are relatively simple. However, I hope these very informal lines motivates you to actually study some introductory text about functional analysis.

So... How to eat a cake? The value function doesn't tell us directly how to eat it. The policy function tell us how much you should eat today given a cake. That is $c^*_t=g(K_t)$. Using the law of motion of the cake ($K_t=K_{t-1}-c_t)$ and an initial condition $K_0=\bar{K}$, we can compute the evolution of the cake. For example, let's compute it for $K_0=90$.

And the fixed point? It is over the space of value functions, not over consumption. The function is the same, although the point in the domain where it is calculated change. There is no stationary equilibrium in this example. We didn't look for a point (a value of k and c) we looked for a sequence of k and c.