Tag Archives: duel

Bayes is playing Russian roulette

There was (once again) a nice puzzle inhttp://www.futilitycloset.com/. Bayes and a good friend are playing Russian roulette. The revolver has six chambers. He puts two bullets in two adjacent chambers, spin the cylinder, hold the gun to his friend’s head, and pull the trigger. It clicks. So it is now Bayes’s turn: he can choose either to spin the cylinder again or leave it as it is. Which is better? Hopefully, Bayes knows his theorem: if he does spin it, the probability of getting killed is 2 out of 6 (four empty chambers out of six), but if he does not, since his friend is still alive, then the hammer should be next to one of the four cylinders in red, below


So here, there is 3 chance out of 4 to survive, i.e. the probability of getting killed is 1 out of 4 (while it was 1 out of 3 when spinning). So Bayes should not spin. And as always, it is possible to see it is a more general result: more generally, in a revolver with http://freakonometrics.blog.free.fr/public/perso5/bullet01.gif chambers, it there are http://freakonometrics.blog.free.fr/public/perso5/bullet02.gif bullets in http://freakonometrics.blog.free.fr/public/perso5/bullet02.gif adjacent chambers,  if the first player survives, the probability of getting killed is k over http://freakonometrics.blog.free.fr/public/perso5/bullet01.gif, when spinning, while it would be 1 over http://freakonometrics.blog.free.fr/public/perso5/bullet03.gif if we don’t. Not spinning is better if and only if

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

i.e.

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

So you’d better not spin, unless there was one bullet in the revolver, i.e. http://freakonometrics.blog.free.fr/public/perso5/bullet06.gif… or http://freakonometrics.blog.free.fr/public/perso5/bullet07.gif (in that case, it might not be a good idea actually to play the game).

Playing with fire (or water)

A few days ago,http://www.futilitycloset.com/published a short post based on the fourth problem of the 1987 Canadian Mathematical Olympiad (from on a problem from the 6th All Soviet Union Mathematical Competition in Voronezh, 1966). The problem is simple (as always). It is about water pistol duels (with an odd number of players)

The answer is nice, an can be read on the blog.

What puzzled me in this problem is the following: if we know, for sure, that at least one player won’t get wet, we don’t know exactly how many of them won’t get wet (assuming that if they shoot at the closest, they hit him for sure) ? It is simple to run simulations, e.g. assuming that players are uniformly distributed over a square,

NOTWET=function(n){
x=runif(n)
y=runif(n)
(d=as.matrix(dist(cbind(x,y), method = "euclidean",upper=TRUE)))
diag(d)=999999
dmin=apply(d,2,which.min)
notwet=n-length(table(dmin))
return(notwet)}

It is then rather simple to get the distribution of the number of player that did not get wet,

N25=Vectorize(NOTWET)(n=rep(25,NSim))
T=table(N25)
plot(as.numeric(names(T)),T/NSim,type="b")

The graph for different values for the total number of players is the following (based on 25,000 simulations)

If we investigate further, say with 51 players, we have a distribution for the total number of players that did not get wet which looks exactly like the Gaussian distribution,

NSim=25000
N51=Vectorize(NOTWET)(n=rep(51,NSim))
T=table(N51)
plot(as.numeric(names(T)),T/NSim,type="b",col="blue")
u=seq(0,51,by=.1)
lines(u,dnorm(u,mean(N51),sd(N51)),col="red",lty=2)

If anyone has an intuition (not to say a proof) for that, I’d be glad to hear it…

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…