Envelopes!

[irchans]

Two envelope questions to think about:

1) A kind man tells you that he has two envelopes each with money in them. He says that you can choose either envelope, open it, and keep the money in that envelope, or trade the contents of the opened envelope for the unopened one. Is there any strategy that has a higher expectation than randomly choosing, opening, and not trading?

2) A millionaire is funding a game between you and another person. The other person is given 1000 one dollar bills and two identical envelopes. He is instructed to put any integral dollar amount up to $333 in the first envelope and put exactly twice that amount into the second envelope. He shuffles the envelopes and presents them to you. As in 1) you get to choose one envelope, open it, and then decide whether to trade for the unopened envelope. If you end up with the envelope containing less money, he gets $100. If you end up with the envelope containing more $, he gets nothing. What is a good strategy for you? What is a good strategy for him? What is his worst strategy?

I'm confused? Does anybody end up with the 1000 one dollar dollars? It sounds like the 1000 $1 bills are just the instruments of the game (not unlike a deck of cards in poker). I want more information. The rules (as I see them) state that the other guy gets either $100 or nothing -- I don't understand. Define the problem better.

What's in it for me? Please explain my possible gain in this game -- not his.

I have no stragety before hand -- I'm not putting any money in the envelopes -- he is....
I think his worse stragety would be to but $333 in one of the envelopes (also if he is above the age of reason, he should not use any odd integer amounts in the envelopes). I think his best stragery would be to put $2 & $4 in the envelopes or maybe $124 & $248. (any two even integers where their sum is less than 372).

[lorinda]

I'll not post all my conclusions yet (partly because they are still incomplete) but i believe in case 2, that if we get to keep the money in the envelope we end up with (which is what i believe is the case) then we should always switch, except in some very obvious situations.
I also believe the opponent (who has motivation to win $100) needs a variable strategy.

As to case one, well, Im always going to switch if there's $1 in the envelope...
..now Im off to consider, and to give others a chance to do this one, I like this puzzle a lot

[irchans]

Carl,

For game 2, the $1000 is just the maximum amount that can be put into the envelopes. You want to do your best to guess which envelope has the most money because you get to keep the money in the envelope that you choose. The other guy wants you to choose the envelope with less money because he then gets $100. If you choose the envelope with more money, then he wins nothing.

Example of game # 2: The other guy puts $3 into envelope A and $6 into envelope B. You choose randomly between A and B. Let' say you choose envelope A. You open it and find $3. You say a-ha! The other envelope must contain either $1.50 or $6 and $1.50 is not allowed because game #2 specifies that the envelopes must contain whole dollar amounts. Therefore, the other envelope must contain $6. You switch and get $6. The other guy gets nothing because you ended up with the richer envelope.

Another example of game # 2: Other guy puts $30 into envelope A and $60 into envelope B. You choose randomly between A and B. Let' say you choose envelope A. You open it and find $30. You reason that the other envelope must contain either $15 or $60. Suppose you decide to keep the $30 envelope rather than risking the $15 loss. The other guy now gets $100 because you ended up with the poorer envelope.

Did that make the game clear?

irchans

yes you made it clear.

[irchans]

Carl wins the ribbon for finding the worst envelope stuffer strategy for game #2. If the stuffer puts $333 in one envelope and $666 in the other, then you always win $666. The stuffer wins nothing.

The best strategy for the envelope stuffer:

- Tell the picker that you will put $333 in one envelope and $666 in the other if he agrees to split the money with you ($200 / $466). If he doesn't agree, you'll put $1 and $2 in.

- If he agrees to split, hoorah! That's a guaranteed $200 instead of a 50/50 $100. The picker also gets more money this way, since it's pretty obvious that if you were playing 'correctly' you would never put more than $332 in the larger envelope.

- If he doesn't agree to split the money, actually put $2 and $4 in the envelopes...that way if he chooses the $2 envelope, he'll stay (netting you $100), plus if he chooses the $4 envelope he might switch just because you double-crossed him and he's confused / out-thinking himself.

PP

[irchans]

Pseudo,

If the two players in game #2 (stuffer and guesser) are permitted to collaborate, then their combined expectation is $666 as in your solution.

If no communication is permitted between the stuffer and the guesser, what strategy would you recomend?

[Mike Haven]

2 is a good problem, irchans

i'm having difficulty getting beyond random even number stuffing and random choosing unless i am lucky and hit an envelope with $2 or $334 or more in it - but that's not my final guess! /forums/images/icons/confused.gif

That's a lot less fun. Here goes:

As the picker:
- If I see an odd number, I switch (it's got to be the low).
- If I see a number over $333, I stay (it's got to be the high).

- If I see a number that's not a multiple of 4, it's probably the low, so I switch. (If it is the high, that means the stuffer put an odd number of bills in the other envelope, which is an odd strategy.)
- If I see a number that's over $166, I stay. (If it is the low, that means the stuffer put over $332 in the high envelope, which is an odd strategy.)

- If I see a multiple of $4 between $4 and $164, it's trickier. I pick X. The envelopes contain either (X and 2X) or (X/2 and X).
-- For (X and 2X) to be a good stuffing choice, 2X should be $164 or less (and thus 'ambiguous' whether it's the high or low value)...otherwise, if I had picked 2X instead of X, I'd be pretty sure it was the high value and stay. So if 2X is over $164, then X is probably not the low value.
-- For (X/2 and X) to be a good stuffing choice, X/2 should be a multiple of $4...otherwise, if I had picked X/2 instead of X, I'd be pretty sure it was the low value and switch. So if X is not a multiple of 8, it's probably not the high value.
-- So, if X is over $82, I stay. If X is not a multiple of $8, I swap.

- What if X is a multiple of $8 between $8 and $80? Here we go:
-- Again, the stuffing choices are (X and 2X) and (X/2 and X).
-- If it's (X and 2X), the stuffer would have to be worried about me choosing (2X) and thinking it might be either (X and 2X) or (2X and 4X). Thus 4X should be an ambiguous choice as well...so 4X must be under $164. So if X is a multiple of 8 over $41, X is probably not the low value, and I'll stay.
-- Likewise, if it's (X/2 and X), the stuffer would have to worried about me choosing (X/2) and considering the pair (X/4 and X/2). So X/4 should be a multiple of 4 as well. Thus, if X is not a multiple of 16, it's probably the low value, and I'll switch.
-- So, if X is over $41, I'll switch. If X is not a multiple of 16, I'll stay.

- So, what do I do with 16 and 32 (the multiples of 16 under $41)? It depends on my read of the stuffer:
-- If the stuffer (a) did not think out the problem or (b) thought out the problem only to the point of figuring out the (16, 32) is the most 'ambiguous' pairing, then I would stay on 32, swap on 16.
-- If the stuffer (a) figured out that (16, 32) is the most 'ambiguous' pair and (b) realizes that I, the picker, also would figure that out, then I would probably stay on 16, swap on 32...since he's probably counting on me to figure him for (16, 32) and make the appropriate move based on that.

- On the other hand, you could think about it this way: since I don't care about what happens to the picker, I just have to choose some value Y so that for all X > Y I'm equally happy and all X < Y I'm equally sad.
-- If X > Y, then I stay -- no regrets if it's high or low.
-- If X < Y but 2X > Y, then I swap -- I'm happy if I get 2X and would have been equally unhappy with either X or X/2.
-- If 2X < Y, it doesn't matter if I swap or not -- I'm not happy no matter what I do.
-- And, of course...this is FREE MONEY! Who cares if it's the most free money you could have gotten or not? It's FREE!

- The way NOT to look at this problem is this: I have X. If I swap, I'll either get 2X or X/2...so I'm risking X/2 to gain X with a 50% chance of winning. That's a 2:1 bet on even odds. Of course I'll swap! (Stupid paradoxes.)

As the stuffer:
- It depends on what I know of the picker.
-- Against a dunce I'd choose (16, 32).
-- Against anyone else, I'd probably go with (8, 16). If I get lucky and he chooses 16, he'll probably swap, since he reasoned that (16, 32) is a likely choice for me. If I get unlucky and he gets 8, well, maybe he'll get confused and outsmart himself by staying on 8. (I think this is better than choosing a combo like (19, 38), where you definitely lose on (19) and only probably win on (38).)

That's my mostly-muddled thinking on the problem.

Of course, depending on the exact interpretation of the rules, the stuffer's best strategy for X and 2X might be X = 0.
- 0 is an interger, after all...so both envelopes would be empty.
- If the rule is that you get paid off if the pick ends up with the least amount of money, then this is an automatic win.
- Even if not, if you really hate the picker, you can screw him over this way.

PP

For question #1:

I can't see any way to maximize your expectation, unless you can make some kind of reasonable assumption about the range/distribution of possible values.

For me personally, I'd probably choose some value Y which I'd be satisfied with. If the envelope I pick has more than Y, I stick, otherwise I swap -- no regrets either way.

Unless, of course, he's kind enough to tell you how much money's in the unopened enveloped. That would make your choice much easier.

PP

[Inthacup]

If I was dividing the envelopes this is what I would consider. First any number than ends in a 1,3,5,7,9 MUST be the low, so you can always chose the other envelope. Any number over 333 must be the high. So if I were to be dividing these up I would make sure that if I divided the Big by 2 I wouldn't get an odd #. For instance 100/200, not 98/49.

If I was chosing I would take those things into consideration as well as a few miscellaneous thoughts. If I get certain even numbers I know they're most likely low as well. For instance if I get an envelope with $26 then a logical guess would be that the $26 is low. This is because I know that the dealer knows that odds must be low, therefore he wouldn't chose $26 to be the high w/ $13 being the low. So I can make reasonable guesses on any odd number as well as about half of the even ones.

The only real numbers that are problematic the ones that are divided by 4 and still give an even number. For instance, 48/4 is 12, therefore you have no hints on your 48 options. This makes since to me, but if I'm unclear or just wrong feel free to correct me. Great question.

[Mike Haven]

whilst you have done a huge amount of work and your answer makes extremely interesting reading i think that your opponent's tactics might work only for the "first" game

i assume there are an infinite number of envelopes being proffered and although i may be wrong it seems to me that after the first few thousand or so with such a set strategy your opponent may not have to think too much to improve his chances of winning as he will know what you are going to
do in any given situation, and therefore will he not just do the "opposite" for a time?

I was reading it as more of a one-time thing...make your best choice in this game, because you won't get another shot at it.

Thinking about this problem reminded me of that scene in The Princess Bride ("And you'd have KNOWN that I knew iocaine powder comes from Australia, so I can clearly not choose the glass in front of me...").

PP

OK, my solution to #2:

pick a random number from the set {1,2,4,8,16,32,64,128,256} and put it in the low envelope.

Your opponent has a 1 in 9 chance of winning for certain after picking and 8/9 of being 50/50. That gives you a EV of $44.44.

OK.... thought about it for a few minutes... in my answer the other player should always switch, since that would greater EV. It may be possible to exploit this. I could give greater weighting to the lower numbers, so opponent still favors switching (possibly just barely favors it), but now is more likely to switch to a lower number. The down side of that is that I now have greatly increased the chances of randomly picking 1 from the set, which gives me an automatic loss. I still like my set of numbers, but I don't know what the magic balancing point is for their probablility distribution. Anyone more mathematically inclined than me (and there should be a bunch of you on this forum) want to take a shot at it?

Why not just pare your set down to {8, 16, 32}? It seems to me that including possibilities that might give the picker a sure win can only be bad. Just so long as your opponent doesn't know these three are your only possibilities for the low number, it's a 50/50 proposition.

PP

[Inthacup]

I would not put 256 in the low envelope. The large would have to be 512, and if he picked that one, then he has an automatic win. But if he happened to pick 256, he would most likely think that 256 was the high, because no one would put money in a envelope where they gave the choser a guarenteed winner. I would advise against putting either 256 or 128 in the envelopes as the low for the specified reasons above.

[irchans]

>pick a random number from the set {1, 2, 4, 8, 16, 32, 64, 128, 256} and put it in the low envelope.

Many people had very interesting stuffer and guesser strategies. I don't have time right now to comment on all of them, so I will only comment on Manhattan Jac's strategy.

Let's assume that Manhattan Jac publishes his strategy and then plays the stuffer role. What is his expectation?

The selector will always switch unless he chooses the 512 envelope. (For this stuffer strategy, if the selector picks an envelope containing x dollars and x is neither 1 nor 512, then his expectation for switching is 0.5*0.5*x + 0.5*2*x = 1.25 x, so he must switch.)

So if the selector picks an envelope with

$1 in it, the suffers expectation is 0
$2 in it, the suffers expectation is 50
$4 in it, the suffers expectation is 50
$8 in it, the suffers expectation is 50
$16 in it, the suffers expectation is 50
$32 in it, the suffers expectation is 50
$64 in it, the suffers expectation is 50
$128 in it, the suffers expectation is 50
$256 in it, the suffers expectation is 50.
$512 in it, the suffers expectation is 0.

So Jac's stuffing expectation is 50*8/9 = $44.44 against a smart opponent with that strategy if the selector knows the stuffers strategy.

Could someone check my reasoning here?

My solution is different but it has exactly the same stuffer expectation.

The picker gets to know the stuffer's strategy? That hardly seems fair /forums/images/icons/smile.gif

PP

[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 /forums/images/icons/laugh.gif

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.

[lorinda]

Please note a couple of things about my solution.

1. These numbers are ratios that you would use a random number generator to provide if you could

2. In a medium term game you could "cheat" your opponent by not putting enough $2 envelopes in, however, when his envelope tracker/envelope stat program found this out, he would stop switching when he opened $4 envelopes and you would lose out in the long term, it is to be considered as a pure solution for millions of trials.

[heihojin]

The main problem is that I find it nonsensical to discuss unbounded probability distributions. It may just be because I haven't yet encountered such in my math education, but I've always considered expectation to be incalculable for such problems.

While I can understand how both of your strategies marginally increase your expectation by an infinitesimal amount, I'm not sure that you could calculate that amount given an unbounded probability distribution.

Furthermore, there doesn't seem to be anything inherently magical about those two strategies; you obtain the same results by switching with probability f(x), where f is any function such that the following are true for all x in [1, infinity):

1. 0 &lt;= f(x) &lt;= 1
2. f(L) &gt;= f(H) when L &lt; H
3. there is some number a such that f(L) &gt; f(H) when L &lt; a &lt; H.


heihojin

[irchans]

Heihojin,

Great observations. Any monotonically increasing switching function beats random. (i.e. 0 &lt;= f(L) &lt; f(H) &lt; 1 when L &lt; H).

[irchans]

Lorinda,

I believe that your solution is the best possible stuffer strategy! /forums/images/icons/ooo.gif (i.e. That is the highest expectation that the stuffer can get if she tells the selector her strategy first.) Your solution has interesting properties:

1) If you open the randomly selected first envelope and it contains more than $2, then there is a 66.6664% chance that it is the larger envelope. (It seems very weird to me that when you open this "randomly" selected envelope, it is more likely to be the larger of the two envelopes! )

2) Even though there is a 66.6664% chance that it is the larger envelope, the guesser is forced to switch because he gets a 2 to 1 pay off on the amount risked.

It is neat that you force the switcher to switch even though is it more likely that he has the larger envelope.


Now, what is the best switching strategy?

(PS: I think you can get just a tiny tiny bit more expectation by going down to $1.)

Just a nitpicking note:
You lose nothing by adding a $1 low envelope, I think, since you right now have the same affect with your $2 envelope. Now you can get even closer to 50%

[lorinda]

Irchans wrote:
(PS: I think you can get just a tiny tiny bit more expectation by going down to $1.)

Damn! Damn! Damn! I missed that.
/forums/images/icons/laugh.gif

[lorinda]

Ive thought about it again and I'm not certain you should include the $1.
Even though the strategy works if you tell the picker, it also works (assuming a reasonably intelligent picker)if you don't.
Including the $1 takes away some of the edge made by picker error....That's my lame defence Im afraid.

(Okay Okay, you're right, and I'm real annoyed at myself)