Category Archives: Games

Promesse et rationalité économique (à court terme)

Non, je vais pas faire une analyse des promesses en cette année électorale (bien que le sujet pourrait être amusant, on peut penser aux propos du candidat Newt Gingrich qui veut que la lune devienne un état américain, ici ou ). Non, en fait je voulais faire un billet sur le sujet les assureurs sont-ils vraiment des voleurs ? En effet, lorsqu’en classe on présente le fonctionnement d’un contrat d’assurance – en particulier lorsque l’on parle de tarification et de l’inversion du cycle de production, ou du provisionnement – on explique que l’assuré achète une promesse: celle de se faire indemniser les sinistres survenus pendant la période dite de couverture. Car formellement, c’est bien de cela qu’il s’agit. Sauf qu’il y a toujours quelqu’un pour faire noter que ce n’est peut-être pas aussi simple et que l’assureur, souvent, rechigne à payer.

En fait, il est parfaitement rationnel – d’un point de vue économique (on s’entend) – que l’assureur négocie. En tous les cas si l’assureur a une vision à très court terme… Et c’est ce que justifient Briegleb & Lemaire (1982), sur l’analyse du marchandage ou Lemaire (1982) (dont sera très largement inspiré ce billet).
Considérons un cas très simple: un assuré a subit une perte http://freakonometrics.blog.free.fr/public/perso5/tribunal33.gif (connue, de l’assuré comme de l’assureur). Mais l’assureur refuse de payer. Et l’assuré envisage d’aller au tribunal. Afin de voir s’il s’agit d’une décision rationnelle, on suppose que l’assuré (http://freakonometrics.blog.free.fr/public/perso5/tribunal18.gif) avait une richesse  avant que le sinistre ne survienne, qu’aller en justice lui coûte , et qu’il estime que sa probabilité de gagner le procès est http://freakonometrics.blog.free.fr/public/perso5/tribunal05.gif. De son coté, la compagnie (http://freakonometrics.blog.free.fr/public/perso5/tribunal19.gif) d’assurance a une richesse , qu’aller en justice lui coute http://freakonometrics.blog.free.fr/public/perso5/tribunal04.gif, et que la probabilité que la compagnie perde le procès est – selon la compagnie – http://freakonometrics.blog.free.fr/public/perso5/tribunal06.gif (les http://freakonometrics.blog.free.fr/public/perso5/tribunal.gif sont alors les probabilités que l’assuré gagne son procès, mais vu des deux cotés). Au tribunal, on suppose que le juge rend un verdict du genre tout ou rien (on n’autorise pas ici de compensation plus importantes que le cout réel du sinistre, et on ne parle pas non plus de remboursement des frais d’avocat en cas de victoire du procès).
L’espérance d’utilité de l’assuré est

http://freakonometrics.blog.free.fr/public/perso5/tribunal07.gif

alors que pour la compagnie d’assurance, son espérance d’utilité est

http://freakonometrics.blog.free.fr/public/perso5/tribunal08.gif

La situation est Pareto optimale si

http://freakonometrics.blog.free.fr/public/perso5/tribunal09.gif

Si on suppose que les agents sont risquophobe (i.e. http://freakonometrics.blog.free.fr/public/perso5/tribunal10.gifdécroissante), alors

http://freakonometrics.blog.free.fr/public/perso5/tribunal11.gif

alors que

http://freakonometrics.blog.free.fr/public/perso5/tribunal12.gif

Aussi, une condition nécessaire pour que la situation soit Pareto-optimale est que

http://freakonometrics.blog.free.fr/public/perso5/tribunal14.gif

i.e. http://freakonometrics.blog.free.fr/public/perso5/tribuanl16.gif. Aller au tribunal n’est pas Pareto optimal si http://freakonometrics.blog.free.fr/public/perso5/tribunal18.gif croit plus en ses raisons de gagner que http://freakonometrics.blog.free.fr/public/perso5/tribunal19.gif. Si http://freakonometrics.blog.free.fr/public/perso5/tribunal17.gif, il peut alors être optimal de ne pas aller au tribunal…. On ne dit pas ici qu’il faut que la compagnie indemnise (intégralement) l’assuré, mais que l’assureur et l’assuré peuvent avoir intérêt a trouver une solution amiable…
Si http://freakonometrics.blog.free.fr/public/perso5/tribuanl16.gif, il peut être intéressant d’aller au tribunal… mais pas forcément… Du point de vue de l’assureur, on peut supposer que sa richesse lui permet de ne pas être risquophobe, ou au moins d’être risque neutre (face a cette assuré au moins). Elle est donc indifférente entre aller au tribunal (et avoir un rendement incertain) et verser un règlement amiable si le versement correspond à son espérance de perte si elle va au procès. Autrement dit http://freakonometrics.blog.free.fr/public/perso5/tribunal20.gif. L’assuré acceptera cette somme si l’utilité qu’il en tire est plus grande que l’espérance d’utilité qu’il aura en allant au tribunal,

http://freakonometrics.blog.free.fr/public/perso5/tribunal21.gif

La différence entre le terme de gauche et le terme de droite est une fonction http://freakonometrics.blog.free.fr/public/perso5/tribunal22.gif. Si l’agent a une utilité exponentielle

http://freakonometrics.blog.free.fr/public/perso5/tribunal23.gif

alors

http://freakonometrics.blog.free.fr/public/perso5/tribunal25.gif

doit être une fonction positive. Un calcul rapide de dérivées montre que cette fonction est convexe, avec un minimum atteint en

http://freakonometrics.blog.free.fr/public/perso5/tribunal26.gif

Moralité ?

  • pour les petits et pour les gros sinistres, il est normal que l’assureur et l’assuré cherchent une solution amiable (transaction)
  • en revanche, pour les sinistres de cout intermédiaire, il peut être légitime d’aller au tribunal (procès).

Maintenant, si on a les grandes directions… peut-être peut-on essayer de mieux comprendre quelle serait le montant de la transaction dans le cas ou une solution amiable est envisagée. Nash (1950) a envisagé un jeu non-coopératif afin de décrire le marchandage. La transaction optimale est la quantité http://freakonometrics.blog.free.fr/public/perso5/tribunal28.gif qui maximise le produit des deux gains d’utilité (cf Nash (1950) ou Roth (1979))

http://freakonometrics.blog.free.fr/public/perso5/tribunal30.gif

La condition du premier ordre donne l’équation suivante

http://freakonometrics.blog.free.fr/public/perso5/tribunal27.gif

Si on fait un peu de calcul numérique, on note que la solution http://freakonometrics.blog.free.fr/public/perso5/tribunal32.gif est décroissante en http://freakonometrics.blog.free.fr/public/perso5/tribunal31.gif: plus l’assuré est risquophobe, plus faible sera la montant de la transaction…. Ce qui n’est pas surprenant, on retrouve ici un résultat noté dans Peeters (1981), Roth (1982) ou ecnore Osbourne (1985). Maintenant, sur le modèle théorique on pourrait bien entendu argumenter que le tribunal fonctionne selon une règle trop simple du tout ou rien, et qu’un procès peut couter beaucoup cher que le simple remboursement du cout du sinistre. Ou qu’il pourrait créer une jurisprudence. On pourrait aussi regarder économétriquement le lien entre le cout des sinistres et les montants des ententes amiables (c’est ce que fait Ayusoa, Bermúdezb & Santolinoc (2012)) mais c’est une autre histoire…. ou ça pourrait être le sujet pour une autre histoire… à suivre donc.

Que signifie “utiliser de l’information” ?

Considérons un simple jeu de pile ou face. On suppose que l’on tombe sur pile avec une probabilité http://freakonometrics.blog.free.fr/public/perso3/pf-20.gif (histoire de formaliser un peu). Le but du jeu est dedeviner sur quelle face la pièce va tomber: si on devine bien, on gagne, sinon on perd. Et le but de mon billet est de comprendre quelle est la stratégie qu’il convient de mettre en œuvrer si on connaît, ou si on estime http://freakonometrics.blog.free.fr/public/perso3/pf-20.gif.

  • Connaissance parfaite des probabilités

Supposons que l’on connaisse parfaitement http://freakonometrics.blog.free.fr/public/perso3/pf-20.gif. A priori deux stratégies sont possibles:

  • jouer au hasard, en utilisant les différentes probabilités: on prédit pile avec probabilité http://freakonometrics.blog.free.fr/public/perso3/pf-20.gif et face avec probabilité http://freakonometrics.blog.free.fr/public/perso3/pf-21.gif.
  • ne pas jouer au hasard, et prédire la valeur la plus probable, autrement dit si http://freakonometrics.blog.free.fr/public/perso3/pf-22.gif, on prédit pile, sinon on prédit face (à chaque lancer si on fait plusieurs lancers consécutifs).

Notons http://freakonometrics.blog.free.fr/public/perso3/pf-24.gif la variable correspondant à la valeur prise au lancer, disons 1 si on tomber sur pile et 0 sur face. Et notons http://freakonometrics.blog.free.fr/public/perso3/pf-23.gif la valeur prédite. On gagne si http://freakonometrics.blog.free.fr/public/perso3/pf-25.gif, et la probabilité de gagner est alors

http://freakonometrics.blog.free.fr/public/perso3/pf-26.gif

i.e. pour la première stratégie

http://freakonometrics.blog.free.fr/public/perso3/pf-27.gif

En revanche pour la seconde, la probabilité de gagner est

http://freakonometrics.blog.free.fr/public/perso3/pf-28.gif

Graphiquement, on peut représenter en ligne la prédiction que l’on fait, et en colonne la face obtenue. En bleu, on gagne, et en rouge on perd,

Supposons que http://freakonometrics.blog.free.fr/public/perso3/pf-29.gif. Considérons le polynôme http://freakonometrics.blog.free.fr/public/perso3/pf-30.gif, dont les racines sont http://freakonometrics.blog.free.fr/public/perso3/pf-31.gif et http://freakonometrics.blog.free.fr/public/perso3/pf-32.gif, i.e sur http://freakonometrics.blog.free.fr/public/perso3/pf-33.gif,
http://freakonometrics.blog.free.fr/public/perso3/pf-34.gif

ou encore

http://freakonometrics.blog.free.fr/public/perso3/pf-35.gif

i.e.

http://freakonometrics.blog.free.fr/public/perso3/pf-36.gif

(avec une inégalité stricte si http://freakonometrics.blog.free.fr/public/perso3/pf-20.gif est strictement inférieur à 1). Bref, il est toujoursplus intéressant de parier toujours la même chose (et de ne pas essayer de jouer au plus malin).

  • Connaissance imparfaite des probabilités

Supposons maintenant que la probabilité http://freakonometrics.blog.free.fr/public/perso3/pf-20.gif soit inconnue, mais estimable. Autrement dit, on a assisté à http://freakonometrics.blog.free.fr/public/perso3/pf-03.gif lancers, on a un échantillon http://freakonometrics.blog.free.fr/public/perso3/pf-01.gif et on estime la probabilité de tomber sur pile par

http://freakonometrics.blog.free.fr/public/perso3/pf-05.gif

Comme auparavant pour la première stratégie, on utilise un générateur de nombre aléatoire http://freakonometrics.blog.free.fr/public/perso3/pf-04.gif (qui tire une loi uniforme sur le segment unité), pour la prochaine valeur, on prédit

http://freakonometrics.blog.free.fr/public/perso3/pf-06.gif

Pour la seconde stratégie

http://freakonometrics.blog.free.fr/public/perso3/pf-07.gif

Autrement dit, si on estime que la probabilité de tomber sur pile dépasse 50%, on prédit pile, et sinon on prédit face.
On gagne si http://freakonometrics.blog.free.fr/public/perso3/pf-08.gif, et la probabilité de gagner est alors

http://freakonometrics.blog.free.fr/public/perso3/pf-09.gif

Dans le premier cas, la probabilité de gagner est

http://freakonometrics.blog.free.fr/public/perso3/pf-11.gif
dont l’espérance est http://freakonometrics.blog.free.fr/public/perso3/pf-12.gif (comme auparavant). En revanche, dans le second cas, le calcul de la probabilité de gagner est

http://freakonometrics.blog.free.fr/public/perso3/pf-13.gif

Graphiquement, on obtient, cette fois,

Si on se place au bout de 20 lancers, on obtient la courbe rouge ci-dessous pour le cas d’information imparfaite, et verte dans le cas de l’information parfaite, pour le ratio de la probabilité de gagner avec le second cas divisé par le premier cas (nous avions vu auparavant que le ratio été inférieur à 1)

à partir du code suivant

> p=seq(.5,1,by=.01)
> q=(p^2+(1-p)^2)/(p*(1-pbinom(10,20,p))+
+ (1-p)*pbinom(10,20,p))
> plot(p,q)
  • Répétons le jeu plusieurs fois et apprentissage des probabilités

Supposons que l’on répète le jeu un certain nombre de fois, avec un apprentissage au fur et à mesure que les tirages avancent, i.e. l’algorithme s’écrit

> n=10
> p=.64
> X=sample(c("a","b"),size=100,prob=c(p,1-p),replace=TRUE)
> S1=S2=rep(NA,100)
> for(s in (n+1):100){
+ P=c(mean(X[1:(s-1)]=="a"),mean(X[1:(s-1)]=="b"))
+ S1[s]=(sample(c("a","b"),size=1,prob=P)==X[s])
+ S2[s]=(names(sort(table(X[1:s])))[2]==X[s])
+ }
> sum(S1[(n+1):100])/sum(S2[(n+1):100])

Graphiquement, si on suppose que l’on apprend sur 10 tirages (et que l’on calcule le nombre moyen de victoires sur les 90 lancers suivants), on obtient un graphique assez proche de ce que l’on avait auparavant,

I.e. comme le ratio est inférieur à 1, la seconde stratégie l’emporte toujours.
Moralité, j’ai un peu l’impression qu’il est souvent inutile d’élaborer une stratégie trop complexe, car les stratégies les plus simples permettent de gagner le plus souvent…

Pourquoi frapper aussi fort la balle au service ?

Au tennis, il n’est pas rare de voir les joueurs servir très fort sur leur première balle, puis de se calmer sur la seconde. Est-ce pour se reposer un peu après le premier effort ou bien y-a-t-il une réelle logique derrière ?

Modélisons un peu tout ça (en reprenant une modélisation présentée par David Gale en 1971). Un joueur a un ensemble http://freakonometrics.blog.free.fr/public/perso3/tennisserv01.gif de services possibles. A son premier service, il choisit le service http://freakonometrics.blog.free.fr/public/perso3/tennisserv02.gif. La première difficulté est que le service soit correct (ou passe le filet pour faire simple), et on note http://freakonometrics.blog.free.fr/public/perso3/tennisserv03.gif la probabilité qu’un tel service passe le filet. Si le service est passé, il a une certaine probabilité de gagner le point, que l’on notera http://freakonometrics.blog.free.fr/public/perso3/tennisserv05.gif. Bien que ne connaissant pas vraiment le tennis, il n’est pas absurde de supposer qu’il y ait une forme d’arbitrage,

  • un service puissant a peu de chance de passer (http://freakonometrics.blog.free.fr/public/perso3/tennisserv06.gif petit), mais s’il passe le filet le serveur sera à son avantage, et la probabilité de gagner le point sera élevée (http://freakonometrics.blog.free.fr/public/perso3/tennisserv05.gif grand)
  • un service faible a de grandes chances de passer (http://freakonometrics.blog.free.fr/public/perso3/tennisserv06.gif grand), mais la balle sera alors facile pour l’adversaire, et la probabilité de gagner le point sera faible (http://freakonometrics.blog.free.fr/public/perso3/tennisserv05.gif petit)

A un service http://freakonometrics.blog.free.fr/public/perso3/tennisserv07.gif donné, la probabilité de gagner le point (sur ce premier service) est alors http://freakonometrics.blog.free.fr/public/perso3/tennisserv08.gif.

Supposons que http://freakonometrics.blog.free.fr/public/perso3/tennisserv01.gif soit “ordonné” au sens où http://freakonometrics.blog.free.fr/public/perso3/tennisserv06.gif peut être supposée strictement croissante.
Compte tenu de la remarque que nous avions faite initialement, il n’est pas absurde de supposer que la fonction

http://freakonometrics.blog.free.fr/public/perso3/tennisserv09.gif

soit à valeur dans http://freakonometrics.blog.free.fr/public/perso3/tennisserv10.gif, avec une fonction croissante pour http://freakonometrics.blog.free.fr/public/perso3/tennisserv.gif, puis décroissante pour http://freakonometrics.blog.free.fr/public/perso3/tennisserv12.gif.

Le joueur cherche à maximiser sa probabilité de gagner le point.

Mais au tennis, si le premier service ne passe pas, le serveur a le droit a une deuxième chance. Le serveur choisi alors en réalité un couple http://freakonometrics.blog.free.fr/public/perso3/tennisserv15.gif correspondant à son premier et second service, respectivement. La probabilité de gagner le point, à stratégie http://freakonometrics.blog.free.fr/public/perso3/tennisserv16.gif donnée, est alors

http://freakonometrics.blog.free.fr/public/perso3/tennisserv17.gif

On peut noter que la stratégie optimale pour la seconde balle est indépendante de ce qui a été fait pour la première. En effet, si on cherche à résoudre, à http://freakonometrics.blog.free.fr/public/perso3/tennisserv18.gif donné

http://freakonometrics.blog.free.fr/public/perso3/tennisserv20.gif

la condition du premier ordre est

http://freakonometrics.blog.free.fr/public/perso3/tennisser21.gif

i.e

http://freakonometrics.blog.free.fr/public/perso3/tennisserv22.gif

Autrement dit, le second service doit être celui qui maximise sa probabilité de gagner le point, i.e. http://freakonometrics.blog.free.fr/public/perso3/tennisserv23.gif.
Mais si on sait qu’il est optimal de jouer http://freakonometrics.blog.free.fr/public/perso3/tennisserv23.gif, dans ce cas, pour le premier service, le joueur cherche à résoudre

http://freakonometrics.blog.free.fr/public/perso3/tennissserv24.gif

dont la condition du premier ordre est

http://freakonometrics.blog.free.fr/public/perso3/tennisserv25.gif

i.e.

http://freakonometrics.blog.free.fr/public/perso3/tennisserv26.gif

Le point s_1 qui vérifie cette condition peut se visualiser sur la figure ci-dessous, car http://freakonometrics.blog.free.fr/public/perso3/tennisserv27.gif s’interprète comme http://freakonometrics.blog.free.fr/public/perso3/tennisserv28.gif, i.e. la tangente de la fonction rouge, et on veut que cette tangente soit de pente http://freakonometrics.blog.free.fr/public/perso3/tennisserv29.gif, qui est la pente de la courbe bleue (comme l’avait noté David Gale),

Autrement dit, il est optimal de servir plus fort la première fois que la seconde… Comme quoi finalement tout peut se démontrer avec un joli modèle…

When should I optimally shoot at my son ? (part 2)

Following my previous post of yesterday, online here, assume now that I do not know if my son came when I turned my back at time, and missed me… Then the payoff function is the one propose by Vincent, i.e.

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

In that particular case,

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

becomes

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

i.e.

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

If we draw those functions, on [0,1], the optimal value is solution of https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel103.png

i.e. https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel104.png (we focus only on solutions in [0,1]). Because here the game is symmetric, my son should also shoot at time https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel105.png
Thus, the payoff is then

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

Since we consider here a  zero-sum game, this cannot be a solution of the game. So the game does not have pure strategy solution.

Assume that now I have a mixed strategy, i.e. a distribution of the optimal time to shot. My strategy has distribution https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel110.png, with density https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel111.png (we assume here that the density exists, or we seek only solution that are differentiable). Assume further that there exists https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel112.png>0 such that the support of my optimal shooting time (the time to shoot is now a random variable) is (https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel112.png,1] (or [https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel112.png,1] since we assume that https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel110.png is differentiable). There is a discussion at the end of Vincent’s post where he needs that assumption, at the end. Actually, I think we can make it now, since we can rationally assume that
I will not shot at time 0 (even on a neighborhood of 0 since I have zero chance to hit my son).
The expected payoff function, assuming that my son shoots at time y is

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

Since the zero-sum game is symmetric, again, the expected payoff should be zero. It comes that necessarily,

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

if https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel121.png. Hence, if we differentiate (with respect to y), we have

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

and if we differentiate one more time, it comes

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

i.e. a general solution should be of the form https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel130.png.
Here, we have the same solution as the one considered in Vincent’s blog. His solution is obtained as follows (with slightly different expressions) conditional to https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png, my expected payoff is

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

i.e.

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

With a simple integration by parts,

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

where https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel134.png, i.e.

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

Thus,

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

So, if we want to be indifferent to https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png‘s strategy, https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel141.png, where

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

with https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel143.png,

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

Consider solutions https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel150.png, then https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel151.png=1, i.e. either https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel152.png=1 and then https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel153.png is constant, or https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel152.png=-1. This means that https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel154.png is in proportional to https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel155.png.
If we substitute in the equation we had, initially, it comes that

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

i.e.

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

If we consider https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png=a and https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png=1, it comes that https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel112.png=1/3 while https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel162.png=1/4 (but we don’t really care about that normalizing constant).
It means that we should not start shooting before 1/3 of the tank is fulled. Actually, it makes sense, since

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

if https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png<1/3 (while https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel164.png=0 if  https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png>1/3).

When should I optimally shoot at my son ? (part 1)

when playing with water guns ! It is not a reverse oedipal fantasy, it is simply a (stochastic) game. Actually, that game was mentioned here, in the context of a duel with laser guns, and the answer is there. Vincent (alias @Vicnent) presented the problem this way: consider a single combat between two single warriors (a duel) with laser guns. The probability to kill the other one is proportional to time https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png (duel started at time 0). Initially, the have no chance to kill the other one, and after one hour, they are certain to kill the other one. At time https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png, they kill the other one with probability https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png (and miss him with probability https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel04.png). What is the optimal time to shot ?

An alternative can be the following (yes, I prefer personal experience to science fiction): consider two warriors playing with water gun. We start with empty guns, and assume that both warriors fill their guns at two different tap water. The more water we have in guns, the more likely the other one will be wet. What is my optimal strategy to stop filling the gun, and start shooting at the other player ?
In order to formalize the game, assume that I will win 1 point if my son gets wet (and not me), I’ll get -1 if I am wet, and not him, and 0 if we are both wet (in Vincent’s game, we have the same payoff matrix, but I find odd to say that I have -1 if I die).
Let https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel02.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png denote time where players shoot. Vincent derived the following expected payoff function: for me (I shoot at time https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel02.png) the payoff is

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

If we know that the other player shoot us, but missed us, it should be different: if I shot first, but missed my son, then he should wait until the end, and so, the payoff should be (thanks Jérôme)

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

Actually, we can consider a more general game, where probabilities are not proportional to https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png, but functions https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel10.png for me (https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel13.png stands for dad), and https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel11.png for the other player (here my son https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel12.png). The expected payoff becomes,

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

Thus my best strategy is obtained by solving

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

that is

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

Let

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

If https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel11.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel10.png are assumed to be continuous (we assume that water goes continuously into the tank of the gun), then there is https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel26.png such that

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

If https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel30.png, then https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel32.png and

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

and so https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel35.png. So

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

Similarly, if https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel31.png, then https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel33.png and

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

and so https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel40.png. So

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

So finally, the optimal strategy is to shoot at the same time, https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png.
In the game considered initially by Vincent, https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel43.png. Hence, https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png=1/2.
But it is also possible that I did not hear my son coming, shooting at me (and missing me). So in that case, the payoff is different, and closer to what Vincent proposed… but that will be in another post…

Quand il est optimal de ne rien faire…

Tous les bloggers d’économie se sentent régulièrement obligés de parler de ce film culte… et je n’y couperais par aujourd’hui.
Ce week end, en sortant de l’exposition sur les mammouths à Rennes avec mon fils, on est passé à la fête de la science, voir si on pouvait faire quelques casses têtes à un stand tenu par des collègues de Beaulieu. Et là, un petit problème de théorie des jeux m’a été soumis, et je ne pouvais pas passer à côté de l’occasion (surtout quand on connaît la morale) d’en parler ici.
Tout le monde connaît la scène du “duel à trois” où le bon, la brute et le truand se font face… Pour les besoin du jeu, on va faire quelques hypothèses (c’est le principe de base d’un jeu: il faut une règle),

  • tout d’abord, on suppose que l’ordre dans lequel ils tirent a été fixé (et qu’ils vont s’y tenir, sans tricher (même Tuco): le bon, puis le truand, et enfin la brute,
  • ils peuvent tirer (et doivent tirer) tant qu’ils ont des balles, et tant qu’ils sont en vie, le jeu s’arrêtant quand plus personne n’a de balle, ou qu’il n’y a qu’un survivant1
  • on connaît les probabilités que chacun rate sa cible:  le bon (alias Blondin) est un peu nul (oui, il faut un peu d’imagination) car il a 1 chance sur 3 d’atteindre sa cible; le truand (Tuco) est un peu moins mauvais car il a 1 chance sur 2; enfin la brute (Sentenza) est super fort car il ne rate jamais sa cible.
  • ah oui, et les personnages ne sont pas rancuniers… ce n’est pas parce que quelqu’un nous tire dessus qu’on voudra se venger quand ça sera notre tour (et si on a la chance d’être en vie)

..La question est simple “que doit faire Clint, alias Blondin ?“. Raisonnons simplement en étudiant les scénarios,

  • s’il tire sur Tuco, il a 1 chance sur 3 de le tuer. S’il est chanceux, il le tue. Alors on retrouve avec un duel entre la brute et le bon. Et comme c’est à la brute de tirer et qu’il ne rate jamais son coup… ce n’est pas franchement malin,
  • s’il tire sur la brute, supposons qu’il le tue. Alors c’est au truand de tirer, et il a 1 chance sur 2 de gagner le dual, alors que le bon a 1 chance sur 3… Bref, les probas ne sont pas franchement en sa faveur…

mais on a regarder ce qui se passait si, par malheur, Blondin tuait quelqu’un… peut être devrait on se demander ce qu’il se passait s’il rate son coup

  • dans ce cas, peu importe qui a été visé car personne n’est rancunier. Dans ce cas, c’est à Tuco de tirer.S’il tire sur Clint, et qu’il le tue, ça sera à la brute de tirer, et alors il n’a aucune chance de s’en sortir vivant. Il est donc impératif que Tuco tire sur Sentenza.
  • si Tuco rate son coup, alors la brute a tout intérêt à tuer d’abord le truand. En effet, il risque plus de mourir s’il laisse le truand en vie que la brute. Donc, le truand meurt car Sentenza est super fort….
  • Moralité, après un tour, c’est au bon de tirer, il ne peut que tirer sur la brute et espérer réussir son coup. Sinon, c’en est fait de lui…

Bref, en ratant son premier tir, il augmente ses chances de gagner…. je laisse les personnes intéressées faire les maths, mais ce petite exemple montre clairement que, dans la vie, il est parfois optimal de ne rien faire !
1 a priori on peut supposer aussi un jeu à la roulette russe, avec une balle chacun, qui doit arriver à la même conclusion…

Jeu de mains, jeu de malins ?

Ce week-end – merci à Serge qui m’a raconté cette histoire – beaucoup de mes illusions de jeunesse se sont envolées…. Mais gardons un peu de suspens pour que mes lecteurs lisent le billet en entier….

  • Pierre, ciseaux ou feuille

Le jeu “pierre, ciseaux, feuille” semble être né en Chine (soit sous le joli nom 五雜俎, alias wuzazu, datant de la fin de période Ming, soit 手勢令 i.e.shoushiling) ou au Japon (soit sous la forme 一二三 , i.e. Hi-fu-mu, c’est à dire un, deux, trois,soit じゃんけんぽん ou plus simplement じゃんけん, alias janken  , lui même basé sur deux anciens jeux, 数拳 – su ken – et 三すくみ拳 -saan sukumi ken). Pour rappel, la pierre (ぐう) bat les ciseaux (ちょき) qui bat à la feuille (ぱあ) qui à son tour bat la pierre. Bref, ce jeux vient d’orient !
Pour preuve, en avril 2005, Takashi Hashiyama, alors président de Maspro Denkoh Corporation, une entreprise d’électronique située à Nagoya, au Japon, n’arrivait pas à savoir chez qui (entre Christie’s et Sotheby’s) il allait vendre sa collection d’art (estimée à plus de 20 millions de dollars). N’arrivant pas à choisir, le choix s’est fait par “pierre, ciseaux, feuille” (ici).

  • Le théorème min-max

Pour comprendre ce jeu, il faut revenir un peu sur des résultats classiques de théorie des jeux. La matrice de gain pour le joueur X est ici

GAINS
X joue « pierre »
X joue « feuille »
X joue « ciseaux »
Y joue « pierre »
0
1
-1
Y joue « feuille »
-1
0
1
Y joue « ciseaux »
1
-1
0

et de manière symétrique, on peut définir la matrice de gain pour le joueur Y. Notons que l’on suppose ici un “jeu à somme nulle” (i.e. ce que perd X,  Y le gagne, et réciproquement). Cette seconde matrice de gains est alors l’opposé de celle-ci.
La stratégie de base du jeu a été énoncée par Italo Calvino sous la forme suivante, “tu sais que ce que tu peux espérer de mieux est d’éviter le pire”.
Intuitivement, supposons que X souhaite jouer “pierre” on peut penser que Y reconstitue les anticipations de X, et donc joue “feuille”, mais à son tour X doit modifier ses anticipations et donc jouer “ciseaux”, plutôt que “feuille”, etc. Bref, rien ne se stabilise et aucune stratégie pure ne s’impose.
Mais s’il n’y a pas de stratégie pure, tentons des stratégies mixtes, i.e. choisissons intelligemment une mesure de probabilités sur l’ensemble des stratégies pures. En pratique, on jouera alors aléatoirement, en pondérant chaque tirage suivant la mesure de probas choisie. Une stratégie mixte (pour X) est alors caractérisée par un vecteur du simplexe,

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

La  stratégie mixte

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

consiste à décider au  hasard quel coup on jouera avec équiprobabilité.
Formellement, notons que le tirage équiprobable – par les deux joueurs – est un équilibre de Nash. En effet, si A désigne la matrice de gain pour X (on est sur des jeux à somme nulle), John von Neumann a montré ce que l’on appelle aujourd’hui le théorème du minimax (en fait, Emile Borel avait également obtenu ce résultat) en 1926, sous la forme suivante: il y a un équilibre de Nash associé à A si et seulement si

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

L’intuition est assez évidente (mais la preuve de ce théorème du point fixe est un peu technique): https://blogperso.univ-rennes1.fr/arthur.charpentier/public/perso2/minimax-4.png est un équilibre de Nash si aucun des jours n’a intérêt de dévier dans sa stratégie, i.e.

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

et

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

On recherche alors un point selle dans la matrice des gains.
Dans le cas de notre jeu de “pierre, ciseaux, feuille“, notons que si

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

alors  https://blogperso.univ-rennes1.fr/arthur.charpentier/public/perso2/minimax-8.png, et on note que  https://blogperso.univ-rennes1.fr/arthur.charpentier/public/perso2/minimax-9.png ainsi que https://blogperso.univ-rennes1.fr/arthur.charpentier/public/perso2/minimax-10.png. Aussi, pour toute  stratégie mixte,

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

et de même

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

Bref, cette stratégie est une équilibre de Nash.

  • Pierre, ciseaux, feuille, ou comment trouver une stratégie

Bref, comme on vient de le noter, la meilleure stratégie à adopter quand on jour à “pierre, caillou, feuille” c’est de ne pas avoir de stratégie… ce qui revient à dire que l’issue du jeu est purement aléatoire. Pour Kenneth Binmore (ici) la méthode du minimax consiste à dire que face à un “bon” joueur, il n’y a rien de mieux à faire de que choisir la stratégie mixte du théorème de von Neumann.
Bon, si on réfléchit deux minutes, on sait qu’on ne joue pas une fois à ce jeux, mais que l’on répète le jeux quelques fois (avant de se lasser). C’est ce qu’a décrit Julia Robinson en 1950. L’idée était d’avoir une approche que l’on peut qualifier de bayésienne, consistant à utiliser pour la stratégie de l’adversaire les probabilités observées.

  • Un champion du monde de “pierre, ciseaux, feuille” ?

Maintenant que j’ai fini avec les rappels de théorie, revenons à la discussion de samedi soir…. J’ai appris qu’il existait un champion du monde de “pierre, ciseaux, feuille” ! Serge prétendait – samedi soir – qu’un joueur avait été vainqueur deux années de suite (ce qui m’a vraiment fait douté sur le côté aléatoire du jeu… malheureusement pour mon histoire, ce n’est qu’une légende, car les champions du monde entre 2002 et 2008 ont été Peter Lovering, Rob Krueger, Lee Rammage, Andrew Bergel, Bob Cooper, Andrea Farina et Monica Martinez).
Comment peut-il y avoir un champion du monde à un jeu qui repose exclusivement sur du hasard ? C’est comme si on inventait un champion du monde de lancer de pièces (ou de dés), qui serait récompensé pour sa régularité1 !
En creusant un peu, j’ai aussi découvert qu’il existait un livre qui apprend à gagner au jeu (je ne l’ai encore lu, mais promis, si la BU le commande, je le dévorerais et ferais un compte rendu détaillé ici même).

Jeux noncoopératifs et assurance des catastrophes

Présentation d’un papier (pas encore complètement fini) lors de la réunion AST&Risk à Grenoble1, sur l’assurance des catastrophes naturelles. Les slides seront mis en ligne dès lors que le papier sera finalisé (encore quelques jours)…

En théorie de la décision, les agents prennent des décisions en fonction de leurs croyances, et de leur utilité. Un jeu est un cadre (formel) où les décisions des agents sont interdépendantes: la décision que je prends dépend de ce que font les autres. On parle alors de stratégie.
La notion d’équilibre dans les jeux à somme nulle découle du théorème minimax de John von Neumann (en 1926). Mais c’est John Nash qui a proposé la notion la plus générale en 1950 (je l’avais mentionné ici). Ce résultat est fondamentalement un théorème de point fixe.  Pour comprendre la notion d’équilibre de Nash, prenons l’exemple suivant (que j’ai trouvé ici): considérons un jeu avec deux joueurs (A et B) qui doivent choisir entre deux stratégies S1 et S2. Les gains des 2 joueurs (connus) sont représentés dans le tableau suivant sous la forme (Gain de A ; Gain de B).

On se demande simplement comment les agents doivent prendre une décision. Pour résoudre ce problème, on étudie toutes les stratégies possibles

  1. est-ce que (S1 ; S1) est une situation stable ? Non, car le joueur A aura plutôt intérêt à choisir S2 (afin d’augmenter son gain de 3 à 4), tandis que le joueur B voudra dévier en S2 (pour avoir un gain de 4 plutôt que de 3). Bref, les deux joueurs chercheront à dévier: ce n’est pas un équilibre.
  2. en (S1 ; S2), A aura intérêt à choisir la stratégie S2 afin de faire passer son gain de 0 à 1. B n’a pas intérêt à dévier dans cette situation. Si l’un des agents a intérêt à dévier, on se doute qu’on ne restera pas sur cette stratégie: ce n’est pas un équilibre.
  3. en (S2 ; S1), A n’a pas intérêt à dévier, mais B va préférer la stratégie S2 qui lui donne un gain de 2 plutôt que de 1.
  4. en (S2 ; S2), aucun des joueurs n’a intérêt à dévier, il s’agit d’un Équilibre de Nash. Aucun des joueurs ne peut faire mieux en modifiant unilatéralement sa stratégie.

On parle de jeux non-coopératif car les décisions sont prises unilatéralement. On peut alors schématiquement représenter ces déviations sur le schéma suivant

Notons également que l’on a un équilibre de Nash, mais aucunement une situation optimale: les joueurs gagnent respectivement 1 et 2, alors qu’ils pourraient gagner 3 (tous les deux) avec la stratégie (S1 ; S1)

1 Le groupe organise d’ailleurs un workshop Modélisation spatiale et temporelle de la dépendance & Applications au risque, qui se tiendra à Luminy du 26 au 30 avril 2010, ici.