Archive for game theory

bean bag win

Posted in Books, Kids, pictures, R with tags , , , , on May 19, 2021 by xi'an

A quick riddle from The Riddler, where a multiple step game sees a probability of a 3 point increase of .4 and a probability of a 1 point increase of .3 with a first strategy (A), versus a probability of a 3 point increase of .4 and a probability of a 1 point increase of .3 with a second strategy (B), and a sure miss third strategy (C). The goal is to optimise the probability of hitting exactly 3 points after 4 steps.

The optimal strategy is to follow A while the score is zero, C when the score is 3, and B otherwise. The corresponding winning probability is 0.8548, as checked by the following code

win=function(n=1,s=0){
  if(n==4)return((s==3)+.4*(!s)+.8*(s==2))
  else{return(max(c(
    .4*win(n+1,s+3)+.3*win(n+1,s+1)+.3*win(n+1,s),
    .1*win(n+1,s+3)+.8*win(n+1,s+1)+.1*win(n+1,s),
    win(n+1,s))))}}

asymmetric information

Posted in Kids, R with tags , , , , , on November 4, 2020 by xi'an

The Riddler of 16 October had the following puzzle:

Take a real number θ uniformly distributed over (0,100). Among three players, the winner is whoever guessed the closest price without going over θ. In the event all guesses exceeded θ, the contestant with the lowest (and therefore closest) guess is declared the winner. The second player knows the first player’s guess and the third player knows both other guesses. What is the optimal guess for the first player, assuming all players maximise their probability of winning?

Looking at the optimal solution z for the third player leads to six possible choices, depending on the connection between the other guesses, x and y. Which translates in the R code

topz=function(x,y){
  if((2*y>=x)&(y>=1-x))  z=y-.001
  if(max(4*y,1+y)<=2*x)  z=y+.001
  if((2*x<=1+y)&(x<=1-y))z=x+.001
  z}
  
third=function(x,y) ifelse(y<x,topz(x,y),topz(y,x))

For there, the optimal choice y for the second player follows and happens on a boundary of one of the six regions, which itself returns that the optimal choice for the first player is x=2/3, leading to equal chances of winning (although there is some uncertainty on the boundaries). It is thus feasible to beat the asymmetric information. The picture above was my attempt at representing the probabilities of gain for all three players, some of the six regions being clearly visible, with first axis being x and second being y [and z is one of x⁻,x⁺,y⁻,y⁺]. The R code is too pedestrian to be reproduced!

the biggest bluff [not a book review]

Posted in Books with tags , , , , , , , , , , , on August 14, 2020 by xi'an

It came as a surprise to me that the book reviewed in the book review section of Nature of 25 June was a personal account of a professional poker player, The Biggest Bluff by Maria Konnikova.  (Surprise enough to write a blog entry!) As I see very little scientific impetus in studying the psychology of poker players and the associated decision making. Obviously, this is not a book review, but a review of the book review. (Although the NYT published a rather extensive extract of the book, from which I cannot detect anything deep from a game-theory viewpoint. Apart from the maybe-not-so-deep message that psychology matters a lot in poker…) Which does not bring much incentive for those uninterested (or worse) in money games like poker. Even when “a heap of Bayesian model-building [is] thrown in”, as the review mixes randomness and luck, while seeing the book as teaching the reader “how to play the game of life”, a type of self-improvement vending line one hardly expects to read in a scientific journal. (But again I have never understood the point in playing poker…)

Covid’s game-of-life

Posted in Books, pictures, Travel, University life with tags , , , , , , , on May 7, 2020 by xi'an

A colleague from Paris Dauphine, Miquel Oliu-Barton made a proposal in Le Monde for an easing of quarantine that sounds somehow like Conway’s game of life. The notion is to define a partition of the country into geographical zones with green versus red labels, representing the absence versus presence of contagious individuals. With weekly updates depending on the observed cases or the absence thereof. While this is a nice construct that can be processed as a game theory problem, I am not so sure that it fits the specific dynamics of the coronavirus, which is not immediately detected while active, hence inducing a loss of efficiency in returning quickly enough to a red status. Not mentioning the unreliability and unavailability of tests at this scale. Or an open society (as opposed to China or Vietnam) where (a) people will resent local lockdown more than they do with global lockdown and (b) mostly operate outside the box for work or family interactions.

Le Monde puzzle [#1115]

Posted in Kids, R with tags , , , , , on October 28, 2019 by xi'an

A two-person game as Le weekly Monde current mathematical puzzle:

Two players Amaruq and Atiqtalik are in a game with n tokens where Amaruq chooses a number 1<A<10 and then Atiqtalik chooses a different 1<B<10, and then each in her turn takes either 1, A or B tokens out of the pile.The player taking the last token wins. If n=150, who between Amaruq and Atiqtalik win if both are acting in an optimal manner? Same question for n=210.

The run of a brute force R code like

B=rep(-1,200);B[1:9]=1
for (i in 10:200){
    v=matrix(-2,9,9)
    for (b in 2:9){
       for (a in (2:9)[-b+1])
       for (d in c(1,a,b)){
        e=i-d-c(1,a,b)
        if (max(!e)){v[a,b]=max(-1,v[a,b])}else{
         if (max(e)>0) v[a,b]=max(v[a,b],min(B[e[which(e>0)]]))}}
     B[i]=max(B[i],min(v[v[,b]>-2,b]))}

always produces 1’s in B, which means the first player wins no matter… I thus found out (from the published solution) that my interpretation of the game rules were wrong. The values A and B are fixed once for all and each player only has the choice between withdrawing 1, A, and B on her turn. With the following code showing that Amaruq looses both times.

B=rep(1,210)
for(b in(2:9))
 for(a in(2:9)[-b+1])
  for(i in(2:210)){
   be=-2
   for(d in c(1,a,b)){
    if (d==i){best=1}else{
      e=i-d-c(1,a,b)
      if (max(!e)){be=max(-1,be)}else{
       if (max(e)>0)be=max(be,min(B[e[which(e>0)]]))}}}
   B[i]=be}