Optimal control, part 2

In the first part (here), we introduced Bellman’s idea of backward induction. But what if we consider now infinite time horizon ? Actually, the maths will be even more simple… and we will be able to use fixed pointed theorem to derive solutions.

  • The mathematical framework

Here, consider the following value function

https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-01.png

and define

https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-02.png

A sequence https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-04.png is said to be an admissible solution for starting point x,

https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-05.png

if https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-06.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-07.png. If we reformulate the dynamic programming idea, we obtain that if https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-04.png is a solution to problem https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-08.png, then for all https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-09.png, sequence https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-10.png is a solution to problem https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-11.png. It comes that function v is a solution of Bellman’s equation

https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-12.png

Note that is can be ssen as some fixed point resul, since

https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-13.png

i.e.

https://perso.univ-rennes1.fr/arthur.charpentier/latex/opt-contr-14.png

So far, it shouldn’t be so hard….

  • Frank Ramsey’s model (discrete version)

In 1928, Frank Ramsey wanted to understand the amount of savings in a dynamic perspective (in how much of its income should a nation save). Consider the following infinite horizon problem, where some planifier wants to maximize

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-01.png

subject to constraints https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-02.png https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-03.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-04.png.
Before looking at dynamic programming answers, we might start with standard Lagrangian optimization techniques.
Assuming concavity of utility function and production function, we should look only for interior solutions. Define the Lagrangian as

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-05.png

Thus, the first order conditions are then given by

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-06.png

and

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-088.png

Assume further some terminal condition, e.g.

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-08.png

(also called transversality condition). If we combine those two conditions, and assume that the first constraint is saturated, we obtain the so-called Euler equation,

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-09.png

It is also possible to use Bellman’s equation: given the dynamic of the capital

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-10.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-11.png

The first order condition states

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-12.png

But since v is unknown, so is its derivative. But from the enveloppe theroem, we obtain something like

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-13.png

where

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-14.png

We can then write

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-15.png

i.e.

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-16.png

and finally

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-17.png

which is, Euler’s equation.

  • A specified model, with calculations

As in the previous post (here), consider a log utility function, and a power production function,https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-18.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-19.png. The dynamic is then

 https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-20.pngand https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-21.png

Note that fixed points are here

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-22.png

and

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-23.png

Recall that the value function is defined as

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-24.png

A natural idea to derive the value function can be to iterate, i.e.

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-25.png

starting with a simple function, e.g the null function, at step 0. At step n=1

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-26.png

thus

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-27.png

At step n=2,

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-28.png

i.e.

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-29.png

The first order condition is then

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-30.png

and thus, we obtain

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-31.png

that can be plugged in the previous equation, i.e.

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-32.png

At step 3, we start from that new expression, derive the first order condition, and we get

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-33.png

and

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-34.png

and so on…
And finally, we can prove that

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-35.png

i.e. https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-36.png. Assuming that

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-37.png

actually, we can prove that

https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-38.png

(and https://perso.univ-rennes1.fr/arthur.charpentier/latex/co-opt-39.png has a form that can be explicited).

Market valuation des garanties des produits d’assurance

Pour le dernier cours d’actuariat 2, on parlera de market valuation, i.e. de valorisation financière. Je vais aussi en profiter pour éclairer Bruno (pour qui j’avais déjà commencé à poster des billets sur le contrôle optimal) sur “comment introduit-t-on la mesure risque neutre dans un passif ?” , sous-entendu en assurance-vie (en assurance non-vie c’est à mon avis plus compliqué, mais c’est la question que l’on se pose quand on valoriser des cat-bonds par exemple). Notons que ce problème s’est posé assez tôt dans la littérature économique, je renverrais par exemple au papier de Brennan et Schwartz en 1976.

  • Valorisation de produits financiers (en marché complet)

Je passerais un peu rapidement (en renvoyant ici ou là pour les grands principes), mais les techniques principales pour valoriser les actifs financiers sont les prix d’Arrow-Debreu, les probabilités risque-neutre, et les déflateurs. Mais auparavant, rappelons que le marché est composé de n actifs financiers (bien distincts) dont les prix et les payoffs sont parfaitement connus, et de n états de la natures, de telle sorte que la matrice des payoffs soit de plein rang. Introduisons le concept de portefeuillle de réplication. Compte tenu du fait que la matrice des payoffs est de plein rang, on a l’existence et l’unicité d’un tel portefeuille. Considérons un ensemble de payoff contingents aux états de la nature

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-17.png

Il est alors possible de créer un portefeuille (dit de réplication) qui permette de toucher précisément ces payoffs à la date 1. Le prix (à la date 0) d’un tel actif est alors le prix du portefeuille de réplication.
Considérons les actifs rapportant 1 dans un état de la nature, et 0 sinon, à la date 1, i.e.

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-16.png

appelés actifs d’Arrow-Debreu. On note https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-15.png le prix aujourd’hui d’un tel actif. Notons que le prix d’un actif sans risque, rapportant 1 demain dans tous les états du monde est https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-1.png. Aussi, si on note https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-14.png le taux sans risque, alors

https://perso.univ-rennes1.fr/arthur.charpentier/latex/correc.png

Le prix de l’actif rapportant https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-12.png à la date 1 est alors https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-10.png.
Posons https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-09.png tel que https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-08.png soit une distribution de probabilité. Alors

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-09.png

où l’espérance est prix sous la mesure de probabilité https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-pst.pngappelée probabilité risque-neutre.
Je renvoie ici (par exemple) pour l’introdution de cette probabilité via les arbres binomiaux. Bref, c’est ainsi que l’on arrive au théorème fondamental de la valorisation d’actif en marché complet: le prix d’un actif contingent l’espérance sous probabilité risque neutre, des payoff actualisés.
Aussi, prenons l’exemple d’un put européen, de maturité T et de strike K. Le prix (à la date 0) du put est donné par

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-01.png

Rappelons d’ailleurs que la formule de Black et Scholes donne un prix pour un tel produit financier (un put européen),

https://perso.univ-rennes1.fr/arthur.charpentier/latex/BSC01.png

https://perso.univ-rennes1.fr/arthur.charpentier/latex/BSC02.png

et

https://perso.univ-rennes1.fr/arthur.charpentier/latex/BSC03.png

Voilà rapidement comment on valorise un produit financier en marché complet, en calculant la valeur d’un portefeuille de réplication.

 

  • Valorisation de produits d’assurance

Pour valoriser les produits d’assurance, classiquement, on calcule des primes pures, ou des valeurs actuelles probables. Par exemple en assurance-vie (car c’est essentiellement de ça dont on parle non ?), considérons simplement une garantie plancher, où l’on s’engage à verser 1€ au décès d’un souscripteur. La valeur actuelle probable (que l’on calcule sous la  probabilité historique) est alors

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-02.png

que l’on pourrra réécrire

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-03.png

(où j’adopte une convention de temps continu pour les taux pour garder une analogie avec le cas financier, mais ça n’est pas vraiment important ici). Bref, par rapport à la valorisation financière on valorise toujours des flux futurs (payoffs) actualisés, mais en prenant l’espérance sous la probabilité historique. Et c’est généralement comme ça que l’on valorise un produit d’assurance: les risques ne sont pas échangés sur des marchés liquides, on n’a donc pas vraimentt de marché complet, et les assureurs espèrent simplement que la mutualisation (via la loi des grands nombres) leur permettra d’avoir égalité entre les flux entrants et les flux sortants.
Remarque: j’avais fait l’an dernier un rapide billet sur la transformée d’Esscher (ici) qui présentait une méthode conciliant les deux approches. Mais je suis toujours à la recherche du papier original (datant de 1932) pour proposer une nouvelle discussion sur ce sujet…

  • Valorisation des garanties planchers dans les contrats d’assurance vie, une approche heuristique

Là où les choses se compliquent c’est quand on mélange des garanties d’assurance (un décès) avec des garanties financières (sur des taux ou bien un actif financier pour des contats en unité de compte). Considérons pour cela un contrat décès, où l’assureur s’engage à payer, au moment du décès à la date https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-tau.png le maximum entre la somme investie en actif risqué à la signature du contrat, https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-07.png et le niveau atteint par l’actif lors du décès, https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-06.png. Autrement dit, l’assureur s’engage à verser https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-05.png. De manière plus général, disons qu’il existe une valeur plancher en dessous de laquelle on ne descendra pas, que l’on notera K.
Notons que l’on peut réécrire le payoff

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-04.png

Le terme de gauche est la valeur de l’actif, et le second terme peut être interprété comme la valeur de la garantie plancher. Par la suite, on ne s’intéressera qu’à la valeur de cette garantie. Le flux versé (pour cette garantie) à la date t, pour un individu d’âge x à la souscription est alors tout simplement

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-04.png

(les dates étant supposées discrètes ici). Si l’on cherche à calculer la valeur actuelle probable de l’ensemble des flux, on voit que deux espaces de probabilités intervienne: l’espace des probabilités actuarielles (sous lesquelles on couvre le risque de décès en supposant les risques mutualisables, i.e. l’univers historique https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-05.png) et l’espace des probabilités financières (sous lesquelles on couvre le risque financiers, i.e. l’univers risque neutre https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-06.png). Autrement dit, la valeur actuelle probable s’écrit

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-07.png

que l’on pourrrait réécrire

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-C-08.png

où le terme à droite est le prix d’un call de strike K de maturité t.
Notons que la commission de contrôle s’était penché sur le sujet il y a quelques années, via le mémoire d’actuariat de Sylvain Merlus et Olivier Pequeux (ici), et c’est ce genre de formule qui avait été proposé, à savoir de faire somme somme de prix de put. Et c’est cette approche que  la réglementation a imposé de valoriser cette garantie.
Pour aller plus loin, il avait aussi été précaunisé d’utiliser la formule de Black et Scholes pour valoriser ces puts, ce qui a donné la formule “standard

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-03.png

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-02.png

et

https://perso.univ-rennes1.fr/arthur.charpentier/latex/market-valuation-01.png

Voilà comment on valorise une telle garantie. Je n’ai parlé de la couverture, car on voit qu’elle ne serait pas parfaite, loin de là.
Comme toutes les formules standards, elle a l’avantage de la simplicité.
Bon formellement, si on veut faire ça proprement, ça risque d’êetre plus compliqué, et il faudrait parler des mesures risques neutre forward, mais on fera ça une autre fois. Sinon tout ça est repris dans une multitude de documents que l’on peut trouver ici, , voire ici ou encore . Et pour aller plus loin, il y a eu récemment pas mal de livres qui abordent ces sujets….

En complément, je pourrais aussi mettre des vieux transparents d’un cours donné il y a plusieurs années maintenant,

Nikkei’s past experience vs. SP500 (in euros)

Following Michael’s idea (here), I wanted to go further, based on his intuition (and dataset that he kindly sent me, there). If we consider the two series of Nikkei index and SP500 index in euros, we have to following graph,

the code is simply the following (the merging function is simply here to avoid problem with different trading days: since we look at the index and not the return, it is the simplest way to deal with it).

> library(RODBC)
> base = odbcConnectExcel(
+ "https://perso.univ-rennes1.fr/arthur.charpentier/spx_nky_eurusd.xls", 
+ readOnly = TRUE)
> series1 = sqlQuery(base,query="select * from [Tabelle1$A2:B8837]") # SPX
> series2 = sqlQuery(base,query="select * from [Tabelle1$D2:E8631]") # NKY
> series3 = sqlQuery(base,query="select * from [Tabelle1$G2:H8945]") # EURUSD
> odbcCloseAll()
> series4=merge(series1,series3)
> series4$SPEUR=series4$SPX/series4$EURUSD
> series5=merge(series4,series2)
> x=(as.Date(series5[,1])-as.Date("01/01/0000","%d/%m/%Y"))/365.25
> yl=range(series5[,4])
> xl=c(1975,2010)
> plot(x,series5[,4],axes=FALSE,xlab="",ylab="",type="l",
+ lwd=3,col="red",xlim=xl,ylim=yl)
> axis(1)
> axis(2, col="red")
> par(new=TRUE)
> yl=range(series5[,5])
> plot(x,series5[,5],axes=FALSE,xlab="",ylab="",type="l",
+ lwd=3,col="blue",xlim=xl,ylim=yl)
> axis(4, col="blue")
> mtext("SP500 in Euros", 2, line=2, col="red", cex=1.2)
> mtext("NKY", 4, line=2, col="blue", cex=1.2)

Those two series series seem to have a similar pattern, so an idea can be translate the SP500 on the left,

Interesting isn’t it ? Suppose that we want to forecast (or forsee ?) the SP500 in euro for the next 10 years…

People who enjoy charts would have here a nice tool…

Those two series are extremely correlated, with a correlation of 0.9572,

> X1=series5[2501:n,4]
> X2=series5[1:(n-2500),5]
> cor(X1,X2)
[1] 0.9572484

But are the two series cointegrated (see here, here or therefor material on cointegration) ? Well, using standard procedure, we first have to prove that the two series are integrated. First, let us look at the autocorrelograms,

At first sight, we confirm the economic intuition that those indices should be integrated. Standard tests confirm that intuition,

> acf(X2,lag=1000,col="light green")
> acf(X1,lag=1000,col="light green")
> library(tseries)
> adf.test(X1)
        Augmented Dickey-Fuller Test
data:  X1 
Dickey-Fuller = -1.0768, Lag order = 17, p-value = 0.9264
alternative hypothesis: stationary 
> adf.test(X2)
        Augmented Dickey-Fuller Test
data:  X2 
Dickey-Fuller = -1.2905, Lag order = 17, p-value = 0.8788
alternative hypothesis: stationary

But if we want to go further, we have to find the cointegration relationship between the two series. From an heuristic point of view, a linear regression should be a good proxy,

> reg=lm(X1~X2)
> plot(residuals(reg))

> acf(residuals(reg),lag=1000,col="light green")

> adf.test(residuals(reg))
        Augmented Dickey-Fuller Test
data:  residuals(reg) 
Dickey-Fuller = -5.176, Lag order = 17, p-value = 0.01
alternative hypothesis: stationary 
Message d'avis :
In adf.test(residuals(reg)) : p-value smaller than printed p-value
> pp.test(residuals(reg))
        Phillips-Perron Unit Root Test
data:  residuals(reg) 
Dickey-Fuller Z(alpha) = -46.9775, Truncation lag parameter = 11,
p-value = 0.01
alternative hypothesis: stationary 
Message d'avis :
In pp.test(residuals(reg)) : p-value smaller than printed p-value

When we look at the autocorrelation function, it looks like we do have a stationary series.
This idea is – more or less – the idea of Engle-Granger two step procedure. But actually, we can not directly use Dickey-Fuller’s test to see if residuals are integrated. This was proved in Phillips and Ouliaris (1990), who also proposed a test (see e.g. here),

> library(tseries); po.test(cbind(X1,X2))
        Phillips-Ouliaris Cointegration Test
data:  cbind(X1, X2) 
Phillips-Ouliaris demeaned = -53.1766, Truncation lag parameter = 57,
p-value = 0.01
Message d'avis :
In po.test(cbind(X1, X2)) : p-value smaller than printed p-value
Another similar function can be found in R
> library(urca)
> summary(ca.po(cbind(X1,X2)))
######################################## 
# Phillips and Ouliaris Unit Root Test # 
######################################## 
Test of type Pu 
detrending of series none 
Call:
lm(formula = z[, 1] ~ z[, -1] - 1)
Value of test-statistic is: 45.2032 
Critical values of Pu are:
                  10pct    5pct    1pct
critical values 20.3933 25.9711 38.3413

Thus, we has to admit that those series are cointegrated.

Based on that idea, it is possible to model the stationary component, and forecast it for the next ten years, based on the assumption that we know the behavior of one time series. Hence, if we add the confidence interval due to the stationary component uncertainty, we have the following graph,

 Of course, again, only uncertainty related to the stationary process is considered here….

Julien Prévieux, ou repenser l’économie

La période est aux pronostics de tous les économistes (pour l’année, voire la décennie 2010), et parfois une relecture de citations passées du style “mais je vous l’avais bien dit“. J’ai une passion pour les personnes qui arrivent à se relire eux-mêmes (en se trouvant d’ailleurs très éclairants).
Histoire de dire du bien de quelqu’un qui fait un travail admirable, j’ai rencontré avant les vacances – en vue de préparer la prochaine biennale d’art contemporain de Rennes – Julien Prévieux (ici pour son site). Julien s’est fait connaître il y a quelques années avec ses lettres de non motivation (dont on trouvera des extraits ), et il m’a fait découvrir des choses incroyables lors de nos discussions. Comme le fait que certains fabricants d’écrans tactiles déposaient des brevets sur les mouvements des doigts,

Mais surtout, Julien s’est amusé à utiliser le “code de la bible” (ici, qu’il doit être possible de voir comme la version textuelle de l’analyse chartiste pour les financiers) pour relire les grands économistes classiques. On y retrouve ainsi la crise de 1929 annoncé par Karl Marx,

https://blogperso.univ-rennes1.fr/arthur.charpentier/public/perso2/JULIEN3.png

ou encore le scandale Enron

https://blogperso.univ-rennes1.fr/arthur.charpentier/public/perso2/JULIEN4.png

Mais je pense que je referais des billets sur le travail que Julien qui apporte un regarde incroyablement neuf, pertinent et drôle sur l’économie !

Optimal control, part 1

Since I had recently a request (from Benoît) about optimal control, I will start here a series of posts on that topic. But first, let us start with a simple problem, with discrete timeno randomness, and with a finite horizon. This might be a too simple framework to model complex problem, but that should be interesting to derive heuristic intuitions (I will skip here the mathematical problems, that can be found in very good books… references will come soon).

  • An introduction to backward induction

Before starting seriously, let us consider the following example: we want to reach the red city on the right from the red city on the left, as fast as possible. There are some roads, and the number is the number of hours it takes. Let us prove that the optimal way is the red one,

The first idea can be to calculate all possible trajectories, but with a large number of roads, the number of possible ways can soon be extremely large. An alternative can be to look backwards (like any students facing a question where the answer is given: start from the end, and try to find a possible way to reach it).


Numbers are greens are the number of hours that we still need one we’ve reached that point. Let us move again one step backward, and consider the orange points,

In the middle, we had to chose either to go up (it will still take 9 hours) or go down (and then 14 hours are necessary). Thus, the optimal strategy, once we’ve reach that point, it to take the 9 hour road. This will be idea the idea proposed by Bellman. Let us go backward again, to the purple cities. Again, we have to chose the shorter way,

From the top, the fastest road will take 13 hours, and from the bottom, it will take 16 hours. Thus, since it takes 10 hours to reach the top city, this road is necessarily faster than taking the one below (since it takes 8 hours to reach the nearest city).
Any this is it. We now have an intuitive idea of what should be done to find optimal strategies.

  • The optimization problem, discrete with finite horizon

Let us consider the following optimization problem: we want to find the optimal strategy https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-01.png that maximizes the following function

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-02.png

with simple constraints, such as https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-03.png (a state space) and https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-04.png (i.e. some dynamic constraints). Assume further that the starting point is given, i.e.
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-05.png. In economic application, note that frequently https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-06.png i.e. we consider a discounted version of the value.

  • The idea of dynamic programming

The intuitive idea of dynamic programming is that if the optimal path from A to C goes throught B, then the path is optimal from B to C. Thus, it will be natural to consider backward induction techniques.
Thus, define
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-07.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-08.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-09.png

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-10.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-11.png
Then Bellman’s principle can be used to link those problems: if https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-12.png is a solution of the problem https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-13.png then, for all
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-14.png, https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-15.png is a solution of problem https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-16.png.
Note that, so far, we assume that such an optimal sequence does exist. Thus, we get that for all x

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-17.png

and more generally,

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-18.png

He
nce, from a practical point of view, we solve those equation using a backward approch. I.e. first,

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-20.png

and then

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-21.png

and so on

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-22.png

… etc. It can be proved that the sequence https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-23.png is solution of https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-24.png if and only if for all https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-25.png,  https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-15.png
is solution of

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-27.png

So far, it does not look so difficult….

  • A simple example

Let  https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-30.png denote the consumption at period t, and assume consumption yields utility

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-31.png

as long as the consumer lives. Assume the consumer is impatient, or has a stronger preference for present, so that he discounts future utility by a factor https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-32.png. Let https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-33.png be capital he got at time t. Assume that his initial capital is a given amount https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-34.png, and suppose that this period’s capital and consumption determine next period’s capital as

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-35.png

where https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-36.png is a positive constant and https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-37.png. Assume further that capital cannot be negative. Then the consumer’s problem is simply

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-38.png

given https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-39.png. Bellman’s equation is then

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-40B.png

whih leads us to a simplier problem than the initial one, since only two variables are involved here https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-41.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-42.png. And to solve that problem, we use backwards induction techniques.
Since https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-44.png is known, we can derive easily https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-45.png,  and so on until https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-46.png. More precisely, given https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-47.png, we can get https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-49.png which is the maximum of function

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-50.png

with https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-51.png. One can see that the following function is a possible solution

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-52.png

where each https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-53.png is a constant. Further, the optimal amount to consume at time https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-54.png is

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-55.png

i.e., if we explicit those expressions

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-60.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-61.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-62.png

…etc.

  • A reformulation of the optimisation problem

Another way of expressing the optimization problem is the following: https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-70.png was the variable of interest, https://perso.univ-rennes1.fr/arthur.charpenti<br />
er/latex/control-71.png was the control variable, and https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-72.png. Thus, the programm

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-73b.png

can be expressed as

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-74.png

Several extension can be considered,

  • consider an infinite sum
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-80.png
  • consider a random component
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-81.png
  • consider a continuous version
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-82.png

But those items will be for posts that I still have to write down….

Modeling dynamic incentives: application to basketball

La page des séminaires au CREM, à Rennes, est mise jour (ici). Je présenterais donc le février prochain le papier que nous écrivons avec Nathalie Colombier sur Modeling dynamic incentatives: application to basketball. Le résumé viendra rapidement. Pour comprendre la finalité du papier, je renvoie à cette phrase du grand philosophe Jean-Claude Dusse, “bon, dans 10 minutes je nous considère comme définitivement perdus“. Dans le contexte des matchs de baskets aux Etats-Unis, nous nous demanderons à partir de quand l’équipe pense que le match est “définitivement perdus“.