
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 player1 discard his first allocated number if it is lower than a specified threshold denoted by .
We also denote player1's first allocated numbers with and the second allocated number with .
We can calculate the expected value for player1 as follows:
which says that the expected value for player1 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:

(1) 
Which can be written as:

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

(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:

(4) 
Which means that if player1 choice a threshold of his expected value will be
Now lets say player2 enter into the game. What is the optimal threshold for player two ?
In order for Player2 to win against player1 he has to make sure that his threshold is equal to the
expected value of player1 which means that otherwise he will lose on average against
player1. This means that player2 optimal threshold is given by:
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 player2 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 player1 by changing the
threshold for player1 between 0 and 1 as seen below.
We can see that when player1 threshold is equal to the inverse of the golden mean then
player1'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 player1.
We again assume that player2 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 player2 by again changing the
threshold for player1 between 0 and 1 as seen below.
We can see that when player1 threshold is equal to the inverse of the golden mean then
player2'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 player2.
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 !