Application Center - Maplesoft

App Preview:

Game Theory is AMAZING !

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application


 

 

 

 

 

 

 

Image 

 

 

 


Game Theory is AMAZING!
 

 

 

The following was implemented in Maple by Marcus Davidsson (2009)

davidsson_marcus@hotmail.com and is based upon the solution provided by

Joe Riel who is very generous with his knowledge which this author is very grateful for.
 

 

 

 

 

 

 

 

 

IBM research runs a series called "Ponder This". In the February 2007 challenge which can be found at 

 

 

http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/February2007.html 

 

 

 

they outline the following problem: 

 

 

 

 

Consider the following two person game. Each person is given a random number generated from a standard

uniform distribution with boundaries 0 and 1. The goal is to get a number that is as large as possible.
 


Now each person is given the option to discard his allocated number and receive a new random number.
 

 

This choice is made without knowing the other players number or whether the other player chose to replace 

 

his number. After each player has had an opportunity to replace his number the numbers are compared and  

 

the player with the higher number wins. What strategy should a player follow to ensure he will win at  

 

least 50% of the time? 

 

 

 

 

 

We now assume that player-1 discard his first allocated number if it is lower than a specified threshold denoted by .

We also denote player-1's first allocated numbers with and the second allocated number with

 

We can calculate the expected value for player-1 as follows: 

 

 

 

 

 

 

 

which says that the expected value for player-1 given a certain threshold is given by the probability that he will

get a value of that is less than the threshold multiplied by the outcome in such scenario plus the

probability that he will get a value of that is larger than the threshold multiplied by the outcome in such scenario  

   

 

 

We now note that since n1 is which means that

 

We should also note that since the allocation is completely random. The only term that is left to 

 

explain is . We know that the expected value is simply given by the arithmetic mean when the outcomes are 

 

symmetric. This means that the expected value of for example is . Now is the outcome  

 

that he will get a value of that is large than but smaller than 1 (not a value between 0 and 1). This means that  

 

the expected value is . A very nice mathematical trick indeed :-)  

 

 

 

These definitions means that we can write our previous equation as: 

 

 

 

EP(x) = `+`(`*`(.5, `*`(x)), `*`(`+`(1, `-`(x)), `*`(`+`(`*`(.5, `*`(x)), .5)))) (1)
 

 

Which can be written as: 

 

 

 

Typesetting:-mprintslash([`assign`(EPx, `+`(`*`(.5, `*`(x)), .5, `-`(`*`(.5, `*`(`^`(x, 2))))))], [`+`(`*`(.5, `*`(x)), .5, `-`(`*`(.5, `*`(`^`(x, 2)))))]) (2)
 

 

 

 

Which is simply a concave function which can be maximized to find a "optimal value" of as follows: 

 

 

 

x = .50 (3)
 

 

   
 

 

We will soon see that this not an optimal value at all. Which means that this is one example of a game where

maximizing the expected value does not result in an optimal outcome. 

 

 

 

We can now plug in such an "optimal value" into our equation for as follows: 

 

 

 

EP(.5) = .625 (4)
 

 

 

 

Which means that if player-1 choice a threshold of his expected value will be  

 

 

 

 

 

Now lets say player-2 enter into the game. What is the optimal threshold for player two ? 

 

 

 

 

In order for Player-2 to win against player-1 he has to make sure that his threshold is equal to the

expected value of player-1 which means that otherwise he will lose on average against

player-1. This means that player-2 optimal threshold is given by:  

 

 

 

 











 

 

 

 

 

 

 

Typesetting:-mprintslash([`assign`(EPxx, `+`(`*`(`/`(1, 2), `*`(x)), `/`(1, 2), `-`(`*`(`/`(1, 2), `*`(`^`(x, 2))))))], [`+`(`*`(`/`(1, 2), `*`(x)), `/`(1, 2), `-`(`*`(`/`(1, 2), `*`(`^`(x, 2)))))])
`+`(`-`(`/`(1, 2)), `*`(`/`(1, 2), `*`(`^`(5, `/`(1, 2)))))
.6180339880
.6180339887 (5)
 

 

 

 

We can also see that the optimal threshold is equal to the inverse of the golden mean. 

 

 

 

 

 

 

 

 

We can now run some simulations to confirm such findings. 

 

 

 

 

 

 

We assume that player-2 selects an optimal threshold which corresponds to the inverse of the Golden Mean. 

 

We can now analyze what happens to the expected percentage wins for player-1 by changing the

threshold for player-1 between 0 and 1 as seen below.   

 

 

 

 





























































 

Plot_2d  
 

 

 

 

 

We can see that when player-1 threshold is equal to the inverse of the golden mean then  

 

player-1's expected percentage wins will become 0.5. Any deviation from such an value will 

 

results in a significant decrease in the expected percentage wins for player-1. 

 

 

 

 

 

 

 

 

We again assume that player-2 selects an optimal threshold which corresponds to the inverse of the Golden Mean. 

 

We can now analyze what happens to the expected percentage wins for player-2 by again changing the

threshold for player-1 between 0 and 1 as seen below.   

 

 

 





























































 

Plot_2d  
 

 

 

 

 

 

We can see that when player-1 threshold is equal to the inverse of the golden mean then  

 

player-2's expected percentage wins will become 0.5. Any deviation from such an value will 

 

results in a significant increase in the expected percentage wins for player-2. 

 

 

 

 

 

 

The conclusion therefore becomes that a player should always select a threshold equal to the inverse of the

golden mean. If you select such a threshold then you will win more than 50% unless the other player 

 

also selects such a threshold then you will win exactly 50% of the time on average. 

 

 

 

 

 

 

The End !