Envelopes!

[Mike Haven]

if it was a one off thing the best strategy would be to put say $32 and $64 in the two envelopes - surely it would be purely a 50%/50% bet - and not a problem worthy of all your effort?

and we wouldn't have needed our altruistic millionaire - it has to be a series of games

[Mike Haven]

yes it is - which is why i read it as an ongoing game

otherwise you might as well toss a coin and ask if it landed heads or tails

[irchans]

Often the game theory will answer the following question:

In a particular game, what is the best strategy I can have if my opponent knows or guesses my strategy?

For example in rock, paper, scissors, the best strategy that you can have if you opponent knows your strategy is 1/3 rock, 1/3 paper, 1/3 scissors.

[irchans]

Picking any number Y before opening the first envelope and switching whenever the envelope contains less than Y has a higher expectation than random as long as there is any chance that the stuffer can put $x and $z into envelopes where x < Y < z. This is the best "solution" to this problem that I have seen in the past.

Here is an interesting alternate solution. Open the first envelope. Say it contains d$. Generate a random number x between 0 and 1. If x < Exp(-d), then switch. This alternate strategy is guaranteed to have a higher expectation than the random strategy for any stuffer probability distribution.

[heihojin]

To expound on irchans's reply, to calculate optimal strategy you are assuming that your opponent knows the rules of the game, and that your opponent is attempting to maximize his or her expected game. Although this isn't a zero-sum game, it is a competitive game in the sense that one player's payoff is reduced by the other player "winning." Because of this, minimizing your opponent's expected gain is a vital part of computing your own optimal strategy.

Think of it like this: if you and I were playing the game, would strategy would you choose so as to minimize my expected gain no matter what strategy I chose?


heihojin

[heihojin]

irchans,

Could you explain your reasoning for both of these solutions?

In the first case, I can understand how one might think that given an amount Y in the first envelope, that the probability that the second envelope contains more money is infinite. Logically, however, it doesn't make sense that you the envelope containing the greater amount of money will always be the second one you choose, even when the probability distribution is unbounded. I can't justify it mathematically, either (although I haven't yet had a calculus-based probability class).

Your second solution I just don't get at all.


heihojin

[irchans]

Heihojin,

The value of Pseudo's Y solution is easy to explain. Assume that the stuffer has a probability distribution for stuffing envelopes. For example, suppose his distribution is

<pre><font class="small">code:</font><hr>
1) 25% Low envelope = $5 Hi envelope = $20
2) 50% Low envelope = $1 Hi envelope = $6
3) 25% Low envelope = $10 Hi envelope = $11.
</pre><hr>

If the guesser knew this probability distribution, then the optimal strategy is easy to figure out. If he knew the distribution, the guesser would keep the first envelope if it contained 6, 11, or 20 dollars and switch otherwise. But let's suppose that the guesser is Pseudo and he does not know the stuffer's distribution. He now picks a satisfactory $ amount Y. If the first envelope contains Y or more, he keeps it and if it contains less, he switches.

Suppose Pseudo picks Y=$1000. Then he will always switch and that is no better than random. His expectation would be (12.50 *.25 + 3.50 * .50 + .25 * 10.50) = $7.50.

Suppose he picks Y=$7. Then he will always switch if the first envelope had $1, $5, or $6. In case 1) he always wins. In the other two cases, the Y strategy has the same expectation as random switching. His expectation would be (20 *.25 + 3.50 * .50 + .25 * 10.50) = $9.38. Psuedo will do better than random whenever there is a chance that low &lt; Y &lt; hi. In this example, there is a 25% chance that low &lt; Y &lt; hi.

As far as I can tell there is no "optimal strategy" for the guesser if he does not know the probability distribution of the stuffer. But, there are strategies that always do better than random. In my previous post, I proposed switching with probability exp(-d) where d is the dollar amount in the first envelope you open. The expectation for that strategy with the example distribution is

<pre><font class="small">code:</font><hr>
.25*.5* exp(-5 )* 20 + .25*.5* (1- exp(-5 ))* 5 +
.25*.5* exp(-20)* 5 + .25*.5* (1- exp(-20))* 20 +
.50*.5* exp(-1 )* 6 + .50*.5* (1- exp(-1 ))* 1 +
.50*.5* exp(-6 )* 1 + .50*.5* (1- exp(-6 ))* 6 +
.25*.5* exp(-10)* 11 + .25*.5* (1- exp(-10 ))*10 +
.25*.5* exp(-11)* 10 + .25*.5* (1- exp(-11))* 11
= $7.97
</pre><hr>

I claim that the exp(-d) strategy always does better than the three strategies: always switch, always keep the first envelope, and random.

When you have a infinite discrete stuffer probability distribution, the math gets a bit harder. Suppose the stuffer will put L(i) in the lower envelope and H(i) in the higher envelope with probability P(i) where i = 1,2,3, .... Then the expectation is

expectation = Sum[ P(i) * E(i) , {i, 1, Infinity}]

where

E(i) = (L(i) + H(i))/2 for the random strategy, always switch, or always keep the first,

E(i) = H(i) if L(i)&lt;Y&lt;= H(i) and (L(i) + H(i))/2 otherwise for the Y strategy, and

<pre><font class="small">code:</font><hr>
E(i) = 1/2 exp(-L(i))*H(i) + 1/2 (1-exp(-L(i)))* L(i) +
1/2 exp(-H(i))*L(i) + 1/2 (1-exp(-H(i))) *H(i)
</pre><hr>
for the exp strategy.



The Y strategy is simple and always does as well or better than random. The exp strategy always does better than random. I expect there are strategies that always do worse than random also.

Good point, Mike.

PP

Nifty.

For each H and L pair, the expectation for the random strategy is:

E = (H+L)/2

The expectation for the exp(-d) strategy is, after reducing:

E = (H+L)/2 + (exp(-L) - exp(-H))(H-L)/2

Since the second term is always positive, the exp(-d) strategy is always better than random. And switching on x&gt;exp(-d) would swap exp(-L) and exp(-H) in that second term, which would make that always worse than random. How...nifty.

Any other nifty problems for us, irchans?

PP

[lorinda]

My strategy gives higher EV even if the guesser knows my strategy [img]/forums/images/icons/laugh.gif[/img]

I put low envelope as
$2......128 times
$4.......64 times
$8.......32 times
$16......16 times
$32.......8 times
$64.......4 times
$128......2 times
$256......1 time

I actually multiply by 1.9999 not 2 so the guesser knows he can change with an edge (in case he screws me on level game)

So what happens, guesser opens envelope with $32 in it.
He knows this is the low envelope 4 times, and the high envelope 7.9999 times.
He gets 2-1 his money on a swap and he is getting favourable odds, so he should swap.
So on a non-$2, non $512 envelope, he swaps.

$2 envelope will be opened 64 times from the 255 games.
0 EV 25.1% of the time

$512 envelope will be opened 1 time in 510 games.
0 EV 0.2% of the time

The other times we have a $66.67 EV, which is 74.7% of the time = $49.80
I think this tends towards $50.00 the more envelopes we are allowed (Maximum stuffing of 1,000,000 say)
This would make logical sense as we have the difficult end of this bet so near 50% would be our best result.