While this sounds like just a lazy intuitive explanation, it calls out the key component - a lack of information about the outcome - that can help avoid the paradox in more complex situations.

This is in contrast to the three-door problem where information is gained by opening the first door. https://en.wikipedia.org/wiki/Monty_Hall_problem

In imperfect information games you are in an information set, not a subgame. When the value is 2A and you have to make a keep or switch decision, the value A is still part of how you calculate the solution. When the value A is the game you are in, it doesn't matter, the value 2A is still part of how you calculate the solution. It has to be this way, because you don't have a way of discriminating between which game state you are in. This is one of the notable and counterintuitive (apparently) results of game theory and it really matters, because when you don't notice it you run into a contradiction.

Check out Noam's talk on solving imperfect information games at NIPS 2017 for a more detailed treatment of this subject. I'm going to handwave it to dive deeper into the exact logical contradiction.

So 2A and A both have to exist still for the correct calculation. The subgames are still connected. But notice what happens? What the failed solution does though is it creates two different subgames!

In one they set 2A. In another they have A/2. But its still two different subgames. Now why does this seem appropriate? Because this sort of reasoning is okay in perfect information games! You can reason about different subgames independently of each other.

But we're not in a perfect information game. We're in a null information set. So 2A and A coexist.

Since we can't state that we are in the 2A case or the A case, being in an information set that prevents us from discrimination between these two things, they error when they try to build their reasoning on the supposition they are able to do so. In particular, they create a logical contradiction.

The dependence means you are required to have the subgame from the 2A as the other side of the equation. Required, but they don't do that. Instead they evaluate one subgame as if they are in a perfect information context.

That is the missing equality symbol that people aren't seeing. That dependence. So what is really happening is this: They claim 2A=A; assuming A is not zero, they claim that 2=1. You can see this very clearly when you take the actual correct probabilities for expectation and place them beside the incorrect ones:

Observe.

    They said: 5/4A = (1/2)2A + (1/2)A/2
    Reality  : 3/2A = (1/2)2A + (1/2)A
    Equality : (1/2)2A + (1/2)A/2 = (1/2)2A + (1/2)A
                         (1/2)A/2  = (1/2)A
                              A/2  =  A
                              A    = 2A
                              1    = 2

The reward for the game is only defined for R(KEEP) and it is defined as {0.5: A, 0.5: 2A}. R(SWITCH) ends up getting its valuation according to a bellman equation: R(SWITCH) = R(SWITCH) * P(SWITCH) + R(KEEP) * P(KEEP). This is obviously an infinite sequence if P(SWITCH) = 1. We actually tend to use a discount factor here like 0.9999999999*R(some_choice) because for this infinite sequence it lets us use limits to claim the case is defined as 0.

But this is like, an extension of why this is wrong - because game theory with information sets already solves for probabilities over action space. It already acknowledges it. So when you point to the information set problem? You point to game theory. And you point to the root of why their calculations were wrong: in an imperfect information game, you play both the game you're in and the game you're not in at the same time.

But this omits (loses) the information of "both envelopes contain >= $MONEY". That is, as soon as you switch to the other envelope, the situation is still true, the previous envelope contains >= $MONEY.

So if you forget that your current envelope also contains >= $MONEY you're stuck in an infinite loop, which you break out of only because you can only do a single iteration.

The way that they fool you is by saying that you either double your money or you halve it, leading you to think that your expected ratio is 2.5/2. But that isn't correct. That ratio doesn't mean anything. That's the wrong step.

This is the key difference between perfect information and imperfect information. In perfect information you can do the assumption of just one subgame and it works because you know what game you are in - its the one you are in. So you are playing over states and actions. In imperfect information you have to assume you are in both at the same time - so you can't assume one subgame, because you don't know which one you are in. You are playing over information sets - every state contained within that information set, not just one state.

I have a feeling that saying it like this, in the general way, is a lot more confusing to people than your phrasing. So thanks for sharing your phrasing.

Which is why the problem as stated doesn't let you look in the envelope before deciding whether to switch or not. Then it's obvious switching makes no difference.

If you have a tree:

         0.5
         /  \
       A     2A
  

It is really counterintuitive, but the way I think about it is "you are playing every game at once" and "you are playing a game over information sets and strategy choices" not "state space and actions" so since you are playing every game at once already when they come in with that other game - well, you were already playing another game. They're overwriting that part of your solutions memory. Which in math terms declares an equality. In that case that equality is 2=1 because they say A = A/2 or that 2A=A depending on which framing you use to build the real game tree.

The actual recurrence relationship is obviously

    R(KEEP) = {0.5: A, 0.5: 2A} = 3/2A. 

    R(SWITCH) = P(KEEP)*R(KEEP) + P(SWITCH)*R(SWITCH)

`R(SWITCH)` becomes `R(KEEP)` because of the way the markov chain drains into it. Literally the only thing you can't pick is `P(SWITCH)=1`. Everything else is an equivalent EV solution. P(SWITCH) <= P(KEEP) because there exists one P(SWITCH=1) is undefined or else 0 (in practice we take the limit after a horizon by multiplying by some term like 0.9999999 to avoid the infinite regress).

And since the problem didn't make this clear, your policy __influences your expected value__ and so their reasoning process is just so broken at a fundamental level. They literally declared 2=1 and therefore undefined solution is the best answer despite infinite solutions that aren't undefined. Its... really bad reasoning. Don't listen to the idea that switching is better. It can't be. Look at the actual relationship. Look at the actual graph. They skip some really important steps, like using the same gametree for the entire calculation.

The actual solution is explained right there on the page, the expectation for both envelopes (one has x, one has 2x) is x*3/2, so switching changes nothing.

The "solution" demanded is supposed to be pointing out the specific logical error in the erroneous calculation that says switching should win. Citing the correct logic is not considered sufficient.

> Denote by A the amount in the player's selected envelope.

which is information that we have not actually gained.

I tell you "These two envelopes contain money. One of the envelopes contains twice as much money as the other one. Pick one.". You pick one. I tell you the one you picked contains $60. You've now determined the amount in your selected envelope -- should you switch?

1. Denote by A=60 the amount in the player's selected envelope.

2. The probability that A=60 is the smaller amount is 1/2, and that it is the larger amount is also 1/2.

3. The other envelope may contain either 2A=120 or A/2=30.

4. If A=60 is the smaller amount, then the other envelope contains 2A=120.

5. If A=60 is the larger amount, then the other envelope contains A/2=30.

6. Thus the other envelope contains 2A=120 with probability 1/2 and A/2=30 with probability 1/2.

7. So the expected value of the money in the other envelope is: 1/2(120) + 1/2(30) = 75

8. This is greater than A=60 so, on average, the person reasons that they stand to gain by swapping.

9. ...

edit: If anything, to me this obscures things further, because it makes it non-obvious that we are actually talking about ratios (i.e. 2A, 1/2A) rather than absolute numbers, and so the expectation calculated in step 7 is inappropriate - a geometric mean recovers the correct answer.

But these two worlds never exist together. They are different realities. We can't determine which of them we are in without more information.

Trying to do so is an error, because we are in multiple subgames simultaneously. In imperfect information games you are already in more than one world. You are in the reality A and counterfactual 2A and you are in the reality 2A and counterfactual A. You can't tell which. You're in both.

In perfect information, you're not in both, so you can do this case based reasoning and not run into as much trouble. But when you're already in both worlds? Well doing the case based reasoning implies that the counterfactual world = the case based world. Its overwriting that part of the equations. Which means you just accidentally declared that either A/2=A or that 2A=A. That 2=1. You do this because you're still in the counterfactual reality, but you're pretending you are not.

A and 2A are together, so you can't propose A/2 without violating the A and 2A codependency imposed by not knowing which subgame you are in.

There are multiple A when you get told 60. They are 30, 60, and 120. This leads to three potential solutions to the expected value: 3/2(30), 3/2(60), 3/2(120). You can't tell which of these solutions you are in, because you don't know. Regardless, since the terminating R(KEEP) condition is the only one that is defined P(SWITCH) = 1 still is either undetermined or 0 depending on how you solve the bellman equations. Your policy decides your expected value. So earlier I was a little loose when I claimed the 3/2A relationship.

Honestly, the wikipedia article is really terrible. It demands you stick in its formalism and declares you a no true scotssman if you don't, buts its approach is fundamentally wrong. Throw off its chains and consider the framing where you remove the requirement of thinking about imperfect information. People are bad at it and if this is confusing you then it is /because/ you are struggling with the imperfect information.

The way you convert between the two game types is this: Instead of states -> information sets. So you only have one move in this game. You always have the Null information set. You always have the same situation. So you're only allowed to have one choice and that is it every time forever. So you always have to make the same decision. Secondly instead of actions -> probability vectors over actions. To simplify and make it tractable assume [0.0, 0.1, 0.2, ... 1.0] so the action space is small. You are choosing 'an action' to take and its going to create multiple subgames. Focus on the recurrence relationship between those games. In particular look at the base case: R(KEEP) = {0.5: A, 0.5: 2A}.

Everything heads toward that base case except one thing: P(SWITCH)=1. It is a markov process and R(SWITCH) 'drains' so as to be R(KEEP) because any probability in it inevitably becomes R(KEEP) after enough iterations.

Notice that {0.5: A, 0.5: 2A} is always true! It is true for both you have A and you keep it and it is true for both you have 2A and you keep it, because notice - you never ever have A. You have the null information set. You can't ever see a difference between these two things.

The moment you force in the idea that you can actually define A to be a particular thing, you smash all over that recurrence relationship. You destroy the relationship. You claim there is no relationship between the policy function and the expected value even though /there is/. There is so much wrong with replacing R(SWITCH) with a fake reality where you can you know you're actually in 1/2A when you can't. And that is what the equations are doing. They're saying you can replace the dependence on each other with a subgame that exists in a different reality. Lets say 120 was when you got 60 - there is no 30 in existence, but your equation calls to replace the recurrence relationship with the idea there is one. It doesn't make sense.

A=60 is the amount in our chosen envelope - we are given this information in the variant in this thread. What we still don't know is if that is the larger amount (and thus the other envelope contains 30, and therefore x=30), or the smaller amount (and the other envelope contains 120, and therefore x=60).

The error is (in step 7) to calculate the arithmetic expectation of those absolute values, because they do not exist "together". The correct arithmetic mean can be obtained by considering the different conditions in which those values do exist, as described in [0]. However, the ratios do exist "together" - the other envelope contains either double or half of 60 - so we could instead calculate the geometric mean, of either the ratios or the corresponding absolute values, and obtain the correct result:

    (2 * 0.5) ** 0.5 = 1
    (120 * 30) ** 0.5 = 60

edit: changed “first envelope” to “chosen envelope” for clarity.

My correction is still valid though. You're not handling step ten properly. You didn't work over the information sets, didn't solve the actual graph that is the game, didn't handle the under-specified policy function.

To try and show you that your solution isn't the actual solution: well, both options have the same EV. So I choose switch every time, because why not. As you are no doubt aware I never get to have EV because I'm constantly swapping. The sixty is a mirage. For my policy choice, the answer was undefined or zero depending on how you write it down. But you told me they had the same EV. So if they did, why did my choice not produce that EV? Ergo, your solution only appears to be giving you the EV.

Think about that for a while and you'll start to realize why I honed in on specifying a recurrence relationship with the terminal keep node and why I'm so eager to escape the trap of their flawed problem model.

Lets take a step back and learn the important lesson for more complex situations. Your policy influences your expected value. Not keeping that in mind is going to destroy the ability to correctly calculate expected value. You aren't trying to search for the best thing to do on the basis of expected value. You are searching for the right policy to provoke a high expected value. The difference is subtle, but essential.

How do we correct it? Well, the right formalisms that allow you to search for the correct policy comes from several fields, but one of them is game theory. In game theory when dealing with imperfect information, it is considered incorrect to do state-based reasoning under imperfect information. This is because you aren't in a state - you are in an information set. When you are playing the game you have to consider every game you could be in, because you don't know which you are in.

This is a second problem with the analysis, but I think you corrected this one.

They ask to be able to translate this into more complex situation. So the general lesson here is about considering counterfactuals in your analysis. An example of this in practice is Jeff Bezo's talking about his decision to found Amazon on the basis of regret minimization on account of his theory about how he would feel in various counterfactual futures. He didn't consider one EV, the founding of Amazon, but also other EVs like founding Amazon and failing and also not founding Amazon and doing other things.

I think I get why you think I'm conflating A, but I'm actually trying to point out that the wikipedia article is conflating A and so its hard to have a productive discussion due to our inheritance of their misuse of terms. I don't want to conflate A, but the Wikipedia article defined A in their expected value calculation and in that equation it ends up taking on a different meaning to what it means when it is defined to be 60. And their meaning ends up claiming things like 1=2 in practice, because of the properties of the hidden counterfactual part of their equations - just because they neglect to show them, doesn't mean they don't exist in the correct mathematics. So the logical contradiction is there - which is exactly the thing the problem asks us to identify.

I[null] = {0.5: A, 0.5: 2A}

We get the expected change in EV for switching like this:

    (
        # The expected gain of switching if we are in subgame A
        (2A-A) * 0.5
    
        +

        # The expected loss of switching if we are in subgame 2A
        (A-2A) * 0.5
    )

You had to consider the benefit of switching from A to 2A and the cost of switching from 2A to A. You had to consider the factual reality you were in, but also the counterfactual reality you were not in.

Here is the reality of the first part of the game tree:

   ChanceNode(0.5)
  /           \ 
 A            2A

        0.5
      /    \
    I[nil] I[nil]

                      0.5
      /                                    \
    {Factually A, Counterfactually 2A}     {Factually 2A, Counterfactually A}

Look at the trouble they run into when they /do/ condition on A. I just showed you these counterfactuals exist, but when they condition they still exist. It treats the situation as if you can just deal with A and just deal with 2A. So they get a 2A case and a A/2 case both of which have their own counterfactuals. Notice what just happened when they did that.

In the A/2 case since we are in imperfect information there is a counterfactual associated with it. What is that counterfactual? It is A! So they don't just have A/2 they also have counterfactual A.

And now look at the other case. 2A has a counterfactual associated with it too. What is it? A.

So they have this:

[F: A, CF: 2A], [F: A/2 CF: A]

And what I'm trying to point out to you is that they just declared A=A/2 and 2A=A, because they neglected the counterfactual relationships.

You can't condition on A in the subgame; you don't have perfect information - you don't have A. You have I[null]. Even when you get told 60 you still have I[null].

/A/ isn't 60 and it can't be because you don't know which subgame you are in. A isn't given. If you knew A, if it was possible to know A, you wouldn't be in an imperfect information game. A is defined in point one yes - but it is also used in point seven and when it is used there we get the logical contradiction.

Select a power of 2 according to the probability

P(2^k) = 0.2 * 0.8^k

i.e. p(1) = 20%, p(2) = 16%, p(4) = 12.8%, etc.

Then place this amount in one envelope and twice that I'm the other envelope.

Then, randomly shuffle the envelopes and select one and open it. Say you see the number 16. It could have landed there in two ways: Either 16 was generated and the other envelope has 32. This happens with probability 0.2*0.8^4 ~ 8.192%. Alternatively 8 was generated and the envelope you have is already the largest one. This happens with probability 0.2*0.8^3 ~ 10.24%. Given that you see 16 already, the relative probability becomes 4/9 vs 5/9. In other words the chance that you have the largest envelope already is 5/9. The expected value of the other envelope is then 5/9*8 + 4/9*32 = 18.67 > 16 so you should switch.

In fact, try this for different initial envelopes and you'll see that you should always switch.

But, if you should always switch, why even look inside the envelope?

But, then you're back at the symmetry / no information argument.

Spherical cow problems often end in counterintuitive results.

That being said, even if you let k go negative I think it's still a paradox.

If you're curious the resolution to this is that before you look in the envelope the expected value of both envelopes is infinite. Only after you look inside one of them does that collapse to two finite values that you can subtract.

I assume you meant to use a exponential base <0.5 so that the mean is finite

I believe the problem you are trying to elicit is that you can almost show that either envelope is a priori better than the other. The problem with this is that the means are infinite so the math isn't sound. So there's not an actual contradiction; the strategy is to open either envelope and then switch to the other one. It's unintuitive but only because we're not used to reasoning about distributions with infinite means.

I still think it's quite unintuitive that one needs to open an envelope in order to regularize things this way. The fact that you will always decide to switch, regardless of what you see in the first envelope, yet you still have to open it is what I find paradoxical.

Once the probability gets around 7/9*.5X + 2/9*4X, then switching is no longer attractive.

- https://en.wikipedia.org/wiki/Boy_or_Girl_paradox

- https://en.wikipedia.org/wiki/Penney%27s_game

- Waiting time paradox

- Honorary mention: https://en.wikipedia.org/wiki/St._Petersburg_paradox

(feel free to add more)

This is in contrast to the earlier problem statement of Gardiner's wealthy men playing against each other as per the article, actually.

The right formula is changing either the 0.5A by A or the 2A by A.

Try with A being a real like 100 usd numbers to see it.

Basically you can't have "two realities" in the same equation. U havé to pick one.

No it's not, that's not how you make EV calculations. As I already said in my previous post, the parts in the EV calculation do NOT refer to the pair of envelopes. Both parts refer to the same object, not to different objects. You are trying to change the EV calculation such that the different parts refer to different envelopes. This does not make any sense.

> Try with A being a real like 100 usd numbers to see it.

...and that's not a way to prove / demonstrate the correctness of math. Yes, if you change these numbers in this way, you get EV 0, which is the correct answer. Just because the answer is correct does not mean the calculation is correct. In this case it isn't.

Since you seem to be making some authority arguments just know that I have a PhD in ML / stats and was top 30 in my country in olympiad level competitive maths so I DO know what I do and in this case with absolute certainty.

Look for the other guys answer if you want more details

Let's review what you're claiming with absolute certainty. This is the first claim that I'm contesting:

> they say "one envelope contains 2A and the other A/2".

When pointed out that they actually don't say this, you clarified your point:

> the "writing" doesn't say it but the written formula at bullet point 7 says it. That's the mistake, the formula is wrong and does not describe reality.

The second part of that quote is correct: bullet point 7 has the mistake, the formula is wrong and does not describe reality.

The first part of that quote is incorrect: the written formula at bullet point 7 does not claim that one envelope contains 2A and the other envelope contains A/2. It claims that the first envelope contains A and the second envelope has a 50% probability of containing 2A and a 50% probability of containing A/2.

You correctly identify where the mistake is, but you misidentify what the mistake is.

If you read bullet point 6, it is very clear: "the other envelope contains 2A with probability 1/2 and A/2 with probability 1/2". Notice that bullet point 6 does not claim "One envelope contains 2A and the other envelope contains A/2".

To illustrate my point, consider a simple coin toss game. If the coin comes up heads, you win $2. If it comes up tails, you win $0.50. How might we construct the EV calculation for this coin toss?

0.5 * $2 + 0.5 * $0.50

Notice how both parts of the formula refer to the same coin. They don't refer to different coins. You have one coin that you flip, and depending on how that one coin lands, there is some probability that you get $2, and some probability that you get $0.50. If you looked at that formula, you wouldn't think that the first part refers to different coin that the second part.

Similarly, here we have one envelope (similar to having one coin) and we have uncertainty about the what the envelope contains (similar to having uncertainty about how the coin will land). We have 50% chance that the envelope will contain 2A, and we have 50% chance that the envelope will contain A/2. Thus, we arrive at the (incorrect) formula:

0.5 * 2A + 0.5 * A/2

It's very obvious that both parts of the formula refer to the same envelope, just like in the coin toss formula both parts of the formula refer to the same coin. To be extremely clear, I am not claiming that the formula is correct. I am claiming that both parts of the formula refer to the same envelope, not to different envelopes. To be specific, I am refuting this claim that you made:

> they say "one envelope contains 2*A and the other A/2".

They don't say that.

Furthermore, you make an additional incorrect claim:

> The right formula is changing either the 0.5A by A or the 2A by A.

Here you are just randomly changing the formula in order to make it output 0EV (which is the correct answer). Just because you get a correct answer does not mean your computation was correct. In this case it is incorrect, because A was defined badly. In order to fix the formula you would have to fix the definition of A. If you keep the incorrect definition of A and just shuffle symbols around until you get the correct result, your computation is still incorrect.

But it's wrong! Try with literally any A.

> If you read bullet point 6, it is very clear: "the other envelope contains 2A with probability 1/2 and A/2 with probability 1/2". Notice that bullet point 6 does not claim "One envelope contains 2A and the other envelope contains A/2".

Sure but this bullet point is also dead wrong and possibly the start of the scam. If you say A is lowest value, Either it contain A with probability 1/2, or 2A.

Otherwise you are changing the reality of A midway through the sentence.

To meet you halfway, what you may actually want, or see in your head is the possibility that A (in the lowest value sense) may vary in the experiment, and try to compute the expectation of that new problem.

But that's a different problem. And if you want to compute the expectation of this problem with A varying in a range you have to write an integral over the p(A) around the (corrected) equation 7. But the equation 7, even in this integral, need to use the same consistency for A: either you have A being the lowest envelope value and you only write 2A ever, or the highest value and then you only write 0.5A

As I said, I agree that the formula is wrong. I disagree with you regarding where the mistake is and how to fix it.

> Sure but this bullet point is also dead wrong and possibly the start of the scam. If you say A is lowest value, Either it contain A with probability 1/2, or 2A.

I think maybe you have some typos here, because I don't understand what you're trying to say here. In any case our disagreement concerns whether the formula in Wikipedia refers to the same envelope in both parts of the formula, or different envelopes. You kept stating that it refers to different envelopes, and I wrote a long post to refute that. Now you came back saying that the bullet / formula / Wikipedia text is "wrong" and "possibly the start of the scam". Ok, sure, but the EV formula still clearly refers to the same envelope in both parts of the formula, despite the fact that you claimed otherwise with literally "absolute certainty". You were wrong about something that you claimed to know with "absolute certainty", so perhaps you should in the future adjust those estimates downwards with a bit of uncertainty added in?

> Otherwise you are changing the reality of A midway through the sentence.

Nope, A is defined as the "value of the firstly-chosen envelope" in the beginning of the sentence, and A is defined as the "value of the firstly-chosen envelope" in the end of the sentence. The definition for A does not change midway through the sentence.

> But that's a different problem. And if you want to compute the expectation of this problem with A varying in a range you have to write an integral over the p(A) around the (corrected) equation 7. But the equation 7, even in this integral, need to use the same consistency for A: either you have A being the lowest envelope value and you only write 2A ever, or the highest value and then you only write 0.5A

That's not the only way to compute the expectation for this problem. I actually ran some small simulations for this today, representing wagers on this problem. The simulations demonstrate the following claims:

- Steps 1 through 7 in the Wikipedia page are correct, in terms of calculating the "expected value in the other envelope, relative to the value in the firstly-chosen envelope". The expected value for the switch, relative to the firstly-chosen envelope's value, is in fact positive (+25%).

- At the same time, the "expected value for the switch in absolute terms" is zero.

- These claims do not contradict each other.

- The first error in Wikipedia's line of reasoning is step 8 that states "they stand to gain by swapping". This indicates that the player should try to maximize goal "expected value relative to firstly-chosen envelope", which is incorrect. The player should instead maximize goal "expected value in absolute terms".

If you disagree with any of these, let's formulate our disagreement in the form of a wager that can be simulated in code.

A man walks to a house with a ladder. He explains that ladders are climbing devices. He tries to set it up against the house, killing plants that he sets it on. The ladder falls over.

One person watches this happen and correctly explains that the ladder is a climbing device and says many very true things about the intentions and proves the genuine thoughtfulness of the ladder users approach. He isn't wrong.

Another person looks at everything from a different perspective. They are a time traveler and they experience the world in reverse chronological order. They say the ladder isn't a climbing device - it is a thing which falls on ground. They say it is a flower killing device. They claim that when the person explains that the ladder was for climbing, they were wrong, because it isn't. They fundamentally disagree about what the ladder is, because they viewed the ladder from a different perspective. He isn't wrong.

They start arguing about what the ladder is. The first person is trying to argue that the ladder isn't a falling device, because it isn't defined to be so. The other person is arguing - this is very critical by the way - not that it is a falling device, but that the way it got used meant it was one and that this disagrees with the statements about what the ladders purpose was. Now, because they aren't noticing this distinction, they argue and they try to prove that the ladder isn't what the other person is claiming it is. Perhaps they think they are winning the argument by pointing out the contradiction, but pointing out the contradiction is agreement that the contradiction exists.

You are using a programmatic understanding of what is happening. You are having to proceed forward from statements in order to get meaning. But there are different paradigms in programming type resolution which might help you understand why you get such sharp disagreement. In programmatic terms you can actually have this backward flow too. b [unknown]; foo(int); foo(b) -> b [int] is implied. You can propagate the type backwards from the function call.

Critically, this is extremely common in math. Mathematics has identities. The relationships between operations flow along those identities. When you let the identities flow backwards, the ladder you two are discussing stops being a ladder. When they make the choice to use a known algorithm, getting the expected value for a subgame under imperfect information, we know the relationships which flow backward from a correct usage. We know what was 'supposed to' be there. They had an incorrect usage. Their ladder wasn't intended to be for falling. But we're experiencing the world in a backwards direction. So we don't know that yet, like you know it. We're treating it as it was used, not as it ought to have been used - flowing what it is backwards from what they mean in the equations, not forward from how they are defined.

So he started trying to explain his thinking to you by moving backward and you noticed that he was saying the ladder was a falling over device, when the ladder maker told you it was something else. And you are right. He isn't wrong so much as his understanding of what the terms are was decided by a different process. And he agrees that you are right that the terms are defined differently!

You aren't really disagreeing about as much as you think you are, because you and him both already agree that the ladder maker said the ladder was for climbing and he said the ladder was for falling over. When you find the contradictions, well, I'm not sure you are actually proving him wrong so much as you are agreeing with each other that a contradiction exists.

On Wikipedia they created two trees one with 2A.

             -> Keep    -> 2A
          2A -> Switch  -> A
    0.5 ->
          A  -> Keep    -> A
             -> Switch  -> 2A

                -> Keep    -> A
          A     -> Switch  -> A/2
    0.5 ->
          A/2   -> Keep    -> A/2
                -> Switch  -> A

If you don't think this is the error, you're not thinking in imperfect information terms. You're thinking in perfect information terms. This sort of splitting action is allowed in perfect information games! In imperfect information games, you are in multiple subgames at the same time. A has to be the same A in both subgames, because you can't discriminate between which game you are in. So you're not allowed to do this. It is wrong!

This gets at the core of what the question is trying to make people notice. You can't do this with imperfect information. You can only do it with perfect information. You can't do it over information sets and strategy spaces. You can only do it over states and action spaces.

But they do it. And then they combine them back into the same analysis when they say 1/2(Game tree 1 switch case) + 1/2 (Game tree 2 keep case). And you can't do that, because game tree one depends on game tree ones keep case and game tree 2 depends on its switch case! You can't tell which you are in, so you are in both - not one or the other. You can't combine the two different subgames from two different trees like you could in perfect information! You have to stick with the same game tree.

And that is what the person you are mistakenly correcting is saying. Pick one or the other, you can't have both.

PS: There are other errors in the problem, like that when you solve it with an MDP or the Bellman equations you actually /do/ end up with 100% Switch having an expected value of zero. So if you spotted some other error, that doesn't mean that the person you are correcting is wrong in their correction. There are multiple issues with the way the wikipedia article approaches the conclusion.

PPS: This exact confusion that people are talking about is actually something that happened in practice in the solving of imperfect information games! IIRC the Pluribus paper author corrected a reasoning error of this type when he introduced sub game reach solving? I might be misremembering here, since its been a while since I listened to his talk, but my fuzzy memory suggests that confusion about subgames interacting with each other was the root cause of a failure in some of the poker research for subgame solving in a blueprint abstraction.

This game tree only makes sense if you change the definition of A. In particular, you need to change the definition to "A = 1/3 of the total amount of money in the envelopes". If you define A like this, then your game tree is correct, and it corresponds to the "simple resolution" described on the Wikipedia page (where they use x instead of A, for clarity). This is an unsatisfactory answer, because it provides an "alternate path" to the correct answer, without demonstrating which step went wrong in the "incorrect path" that leads to the wrong answer. It is not particularly difficult to construct these "alternate paths" that lead to the correct answer. The difficulty of the puzzle is in demonstrating what goes wrong in the incorrect path, as stated on the Wikipedia page:

The puzzle is to find the flaw in the very compelling line of reasoning above. This includes determining exactly why and under what conditions that step is not correct, in order to be sure not to make this mistake in a more complicated situation where the misstep may not be so obvious. In short, the problem is to solve the paradox. Thus, in particular, the puzzle is not solved by the very simple task of finding another way to calculate the probabilities that does not lead to a contradiction.

> Notice now that there is no game in which A is both 2A and A/2.

I have no idea what you are referring to here. I never claimed that A = 2A in any circumstance (there is nonzero amount of money in the envelopes).

> If you don't think this is the error, you're not thinking in imperfect information terms. You're thinking in perfect information terms. This sort of splitting action is allowed in perfect information games! In imperfect information games, you are in multiple subgames at the same time. A has to be the same A in both subgames, because you can't discriminate between which game you are in. So you're not allowed to do this. It is wrong!

I agree with you that the crux of the issue is in the definition of A. In particular, "mixing" "two different A's" within the same computation, even though they sort of mean different things. This is a fuzzy explanation that gives a feeling "something about this explains the issue", but it's not a complete explanation that precisely pinpoints what is wrong.

> This gets at the core of what the question is trying to make people notice. You can't do this with imperfect information. You can only do it with perfect information.

This is false. We can easily construct imperfect information games similar to this one, but tweak a few things in such a way that a "naively constructed EV calculation" yields the correct results.

> And that is what the person you are mistakenly correcting is saying. Pick one or the other, you can't have both.

Nope! I was very clear about which very specific claims I was refuting. They were unrelated to the topics you are bringing up here. I posted a long, clarifying comment to a sibling comment here, you can look that up if you want to refute specific claims.

> So if you spotted some other error, that doesn't mean that the person you are correcting is wrong in their correction. There are multiple issues with the way the wikipedia article approaches the conclusion.

I didn't say "I spotted error X in Wikipedia which explains Two Envelope problem", I said "I spotted error X in this other poster's Hacker News comment". Please read the very specific comments I made about very specific claims made by the person.

> This is an unsatisfactory answer, because it provides an "alternate path" to the correct answer, without demonstrating which step went wrong in the "incorrect path" that leads to the wrong answer.

Eh, I mean, I guess I'm cheating by claiming an interpretation they aren't trying to use. This is why I detest the "no true scottsman" setup to the question. We can create an identity that maps their wrong step into my formalism where what they did is wrong in the way I claim it is. Even though they didn't "try to do it" doesn't mean I can't see that they did do it. But apparently - even though game theory notation neatly avoids these pitfalls - we need to stick to the footgun notation. It just seems stupid to me. If you want to avoid the problem, use the notation that trivializes avoiding the error. I really like the other person's analogy to type errors, because it is such a similar idea to what I'm saying, but they just use a different part of math to assert it. There are ways you can just make this decision fail to typecheck. If you don't want to have these type of errors? Be stricter about your typing so at to prevent them.

Nobody makes this claim, directly or indirectly. If you got this result by formalizing the plain English statement into a proof assistant, then the error was introduced during the step where you interpret the plain English into a formal statement. If the claim "Z = 2Z" was inherent to the plain English version of the problem, then it wouldn't be possible to run the wager as a simulation, but it is. The entire Two Envelopes problem - including step 7 - is possible to simulate in code: https://pastebin.com/jPyZVrkx

What the simulation demonstrates is:

- It's perfectly possible to define "expected value of the final envelope in relation to the value of the firstly-chosen envelope", as the Wikipedia page describes. No contradiction exists that would prevent this computation.

- It's also perfectly possible to define "expected value of the final envelope in absolute terms".

- These are different goals to maximize. A rational actor should maximize goal 2 ("expected value of the final envelope in absolute terms") in this variant of the game. It's also possible to construct another variant where a rational actor should NOT maximize goal 2, but should instead maximize goal 1 ("expected value of the final envelope in relation to the value of the firstly-chosen envelope").

- The error in Wikipedia's "compelling line of reasoning" appears to be at step 8 where they conclude that "they stand to gain by swapping". This implies that a rational actor should maximize goal 1, when in fact a rational actor should maximize goal 2 instead. This is the error in Wikipedia's line of reasoning.

> When we get to step seven we do a calculation that reintroduces our uncertainty. We multiply by the probability of being in each case. However, we don't actually know we are in one case and we don't know we are in the other case. So combining these two situations leads to the counterfactual part of subgames emerging. So we have {A, 2A} and {A/2, A}. The sets aren't equal. We can choose some parts of this, like grabbing A and comparing it to 2A. So now we have an identity rule that just let us say 2A=A. 2=1. Our contradiction is found.

I'm not a mathematician, so I don't understand expressions like "counterfactual part of subgames emerging" or "there is an identity implied by being under imperfect information". I appreciate you writing back at length, but the majority of what you wrote went straight over my head. The impression I have is that you formalized the problem in a manner that lead to a contradiction. If this contradiction was inherent to the original English problem statement, it wouldn't have been possible for me to simulate the problem. But it is. So it seems to me that there is no inherent contradiction in the English problem statement, it seems that the contradiction was introduced during the formalization step.

> I detest the "no true scottsman" setup to the question [...] If you want to avoid the problem, use the notation that trivializes avoiding the error.

I wouldn't describe the setup as a "no true scottsman" scenario, because the setup describes what counts as a scottsman: determine which step in the line of reasoning is incorrect, why and under what conditions. I appreciate that you tried to do this when you identified step 7 and explained what was wrong with it in your opinion. This is also what I tried to do in my explanation, with regards to step 8 and the comparison between the two goals.

Besides, it's very trivial to conclude that nothing can possibly be gained by switching (in absolute money terms, which should be the goal a rational actor chooses to maximize). It would be boring and unsatisfying to accept a simple answer that explains how to get the "correct answer" without explaining what made it a paradox in the first place. It would be akin to looking at an illusion that displays a man or a cliff depending on how you look at it, then shouting "this is not an illusion! it's just a cliff! there is no man in this picture!"

Well, this is just a place where they do the math wrong. We can quibble about why, but it isn't a paradox. We both agree they do it wrong and we even have an overlap in the reason why - we both think they aren't comparing them relative to all the subgames they are in and we both think that this is required to reason correctly. So lets say we get to the correct relative EV of 0.

If both are worth the same, well, why not always switch? They are the same EV, right?

IMO this is the real paradox. We have a false equivocation. EV(policy, game) is not equal to EV(envelopes), because for the policy `ALWAYS_SWITCH` we get the logical contradiction that undefined = EV(envelope) or if you take the limit with a discount under a different formalism that 0 = EV(envelope)

When you tackle this problem starting there rather than at the other error the entire algorithm changes, because we need to modify the problem so that we can calculate EV with respect to policy. The algorithm changes enough so that it really annoys me, because I have this intuitive feeling that I'm changing the solution so much so that I'm no longer working within the spirit of the puzzle.

That is why I feel like "no true scottsman"; to use a metaphor, they gave me a coloring book and told me to color something beautiful but that I had to stay in the lines, but the lines of are a skunk and I want to draw a sunrise. I don't want to correct just the one particular step. I hate the framework that forces me into the confusion by falsely implying that if I get the right envelope EV, I know my EV.

I feel like this is a detour that we can avoid by adding a small cost to switching.

> I hate the framework that forces me into the confusion by falsely implying that if I get the right envelope EV, I know my EV.

I love it. I love it in the same way I love the trick of a magician who fools me. Also, the answer of "two EVs" is particularly satisfying for me, because it resembles a similar confusion in poker tournaments where you need to account for chip EV and dollar EV separately.

I don't think its a detour we actually want to avoid; the implications are really fascinating and help us to understand how to solve games more generally.

I agree with adding cost as a way to do it. Actually, that is why I've been saying it is zero or undefined. You know about dynamic programming right? Well, one of the reasons it was invented is kind of related to what we're talking about right now. There are these things called the bellman equations. They can look like this when you think of things in terms of a markov decision process.

https://wikimedia.org/api/rest_v1/media/math/render/svg/0e35...

Since they're recursively defined, you can compute them more quickly by caching the computation back to front then by computing them front to back. Anyways, putting aside that bit of trivia, do you see the symbol that looks a bit like a y? When we have an infinite sequence like we would if we kept switching you can set that term to be some constant, for example 0.9999999999999. That lets you take the limit, because the infinite sequence is obviously going to converge to zero.

Check out the formula again and notice one of the things that it does which the wikipedia article doesn't. Do you see the symbol for pi? That is talking about the concept of a policy function. A strategy, that way you compute what the agent would get if they played the game, rather than the envelope contents. Under this formalism we've doing an argmax over the policy function for the equation in order to get the policy that has the highest expected value.

> I love it. I love it in the same way I love the trick of a magician who fools me.

If you're actually interested in this sort of thing, I suggest checking out the poker research papers by Noam Brown. He had a talk at NIPS 2017 where he won best paper award. In 2019 he was runner up for best scientific advancement of the year. His work is about applying game simplification to poker to create a bluneprint of the game which is simpler, solving the blueprint using a modified form of counterfactual regret minimization, and then refining the solution during actual play with reach subgame solving. You might have heard of his work, because he was involved in the entire AI now better than humans at poker thing even in no limit breakthrough. I have some belief, but not certainty, that his paper contains a correction of someone who made this style of error. He mentions in the research paper that there was a mistake in another paper where they didn't account for the way subgames influence each other. I see that as the problem here, but I haven't read the other paper, so I don't know if it was the same category of error. Find the paper he referenced, read through it, and see if you're tricked. It is potentially a kind of real world two envelope problem to see if your tools for reasoning about these things is actually helping you to avoid the error in more complicated situations - though, since you disagree with me that this is about handling of imperfect information (or more precisely, the counterfactuals - there is a variant on wikipedia where they removed the probabilites, but counterfactual reasoning still applied to resolve the paradox) maybe you won't see it as related errors.

Yes, I've done dynamic programming in competitions. I'm not familiar with bellman equations, and the explanation you provided about convergence, policy functions, etc. went over my head, sorry.

> If you're actually interested in this sort of thing, I suggest checking out the poker research papers by Noam Brown [...] He mentions in the research paper that there was a mistake in another paper where they didn't account for the way subgames influence each other. I see that as the problem here, but I haven't read the other paper, so I don't know if it was the same category of error. Find the paper he referenced, read through it, and see if you're tricked. It is potentially a kind of real world two envelope problem to see if your tools for reasoning about these things is actually helping you to avoid the error in more complicated situations - though, since you disagree with me that this is about handling of imperfect information (or more precisely, the counterfactuals - there is a variant on wikipedia where they removed the probabilites, but counterfactual reasoning still applied to resolve the paradox) maybe you won't see it as related errors.

This sounds really interesting! It was a huge deal in the poker scene when the poker AI developed by Brown and Sandholm defeated pro human players. I read the first few pages of the paper now, but the paper becomes very math-heavy after that. I don't have the necessary background to understand the notation they use. That said, the "mistake" in the way "subgames influence each other" that you referenced, I suspect it was of a far simpler kind - the kind that Brown explains in chapter 2 which he concludes with:

This shows that a player’s optimal strategy in a subgame can depend on the strategies and outcomes in other parts of the game. Thus, one cannot solve a subgame using information about that subgame alone. This is the central challenge of imperfect-information games as opposed to perfect-information games.

Although Brown says "imperfect-information games" here, he actually means a specific type of imperfect-information games: the type where the opponent's strategy is not fixed. We're talking about games where your opponent can change their strategy in order to exploit weaknesses in your strategy. This property was a key requirement of the "coin toss" example game that he provided in chapter 2. If you modified the coin toss game such that the opponent's strategy was fixed, then the situation would change completely. Crucially, Two Envelopes Game is not one of those games where the "opponent" can adapt their strategy according to your strategy. The strategy of the opponent is fixed in Two Envelopes Game. That's why you can solve a single subgame in Two Envelopes game independently of other subgames, even though it's an imperfect-information game. If you are suspectful of this claim, we can verify it by simulations.

I was agreeing with you when I talked about convergence. You said that adding a cost would solve the problem and I agree that it does. I think you were probably thinking of a literal cost like "one cent". If you choose a cost like that then switching an infinite number of times has an infinite cost. You could instead think of the cost as a fraction of your expectation, the cost is 1% of whatever you end up getting back. Now if you switch an infinite number of times you end up having a cost of zero. That might seem counterintuitive, but recall that 1/3 is .3333 repeating. So when you sum 1/3 + 1/3 + 1/3 you get .9999 repeating. Yet 1/3 + 1/3 + 1/3 is equal to one. Infinitely close to something else is basically being the thing you are infinitely close to. Even though we never get the reward we know that the fraction is becoming infinitely close to zero. People call it "converging" when we have an infinite sequence we can sum to a real value. We know before ever seeing the value that we'll be multiplying it by zero. So we can refactor the equation to be 0*ev(switch) and then take advantage of the identity of 0x=0 to declare the result to be 0. Thus, the calculation converges to zero.

This isn't really the central problem of imperfect information. Consider that in a perfect information game, your opponent will also adjust their strategy to exploit weakness in your strategy. So if it was the central challenge, why does it happen in both? You can rule it out as what he was referring to, because it doesn't discriminate between the two types of games. The central challenge in imperfect information games is you have to play with respect to your information set, not the subgame you are in. So the policies and outcomes of other subgames influences the expected value of the subgame you are in. In perfect information, the only game in your information set is the subgame you are in. So you only have to play with respect to the subgame. That is what makes perfect information different from imperfect information. It discriminates between the two game types.

The type of issue I was referring does not occur in perfect information games.

As a practical example, consider the concept of "balancing your range" in poker. If you play poker without doing that - if you play with a purely exploitative strategy where you are only trying to maximize your EV for each hand - then your strategy will be very easily exploitable by an adaptive opponent. You will frequently end up in river situations where your opponent can deduce whether you have a strong or weak hand, so they can fold to your strong hands and bluff you out of weak hands. In contrast, if you attempt to "balance your range" - that is, consider all the subgames - then you won't end up in these situations as badly. For example, when you make a particular river bet, your opponent might deduce that you have a strong hand 70% of the time and a bluff 30% of the time (as opposed to 100% and 0%).

This issue does not exist in perfect information games. Yes, my definition of "adjusting your strategy to your opponent's strategy" was overly broad to define this issue. But if you think about the poker example, where a poker player will might make a decision like "I need to bluff with this part of my range, because I need to support my strong hands [other subgames] by having some bluffs in my range in this situation" - you won't find a corresponding example from perfect information games like chess. This class of problems is unique to imperfect-information games in which an opponent is allowed to adapt their strategy to yours. If you fix the opponent's strategy, the issue disappears. If you turn the game into a perfect-information game, the issue disappears. Both requirements must be present for this issue to exist.

I thought that Noam Brown was talking about this issue in chapter 2. He discussed a simple coin toss game where one player took a strategy, and then the other player adapted by taking the optimal (exploitative) strategy against them. Then the other player changed their strategy, and the other player again adapted their strategy. And then he described a balanced (GTO) strategy. Then he said this as a conclusion:

> This shows that a player’s optimal strategy in a subgame can depend on the strategies and outcomes in other parts of the game. Thus, one cannot solve a subgame using information about that subgame alone. This is the central challenge of imperfect-information games as opposed to perfect-information games.

I thought that this corresponds perfectly to my poker example. If it doesn't, and it means something completely different, ok, sure. I'm not a mathematician. I can't even read the notation that's used in subsequent part of the paper.

I think you understood his point very well. I just think you're making a mistake in trying to recast his claim from "imperfect information games" have this property to "this narrow subset of imperfect information games" has this property. Both imperfect games with an opponent and imperfect games without an opponent have the property of needing to play as if you are in multiple subgames, because the definition of the problem is that you don't know which subgame you are in. His claim was that the policy in one subgame could influence the EV of another subgame - and in this problem, it does. I believe you're thinking of the EV of the envelope when you think you are proving this game doesn't have that property via calculation.

To see his claim applies to this game consider the case where P(Switch)=1. Being able to calculate the EV of the envelope's contents is a bit different from solving the subgame. Here, we have two subgames E1 and E2. We can know a priori what the expected values of envelope's contents in E1 and E2 are. But if you change your policy in E1, it changes your expected value in E2. If you doubt this, remember the core of the paradox again - choose to always switch and your EV is no longer the EV of the envelopes. Ergo, the EV of the subgame E1 is dependent on the strategies and policies of another subgame, E2.

If we take the poker example and we modify it by "locking" our opponent's strategy, then this property is removed. Suddenly the optimal strategy for us no longer includes any GTO-like thinking such as "balancing our range", we should simply maximize our EV for each hand "in a vacuum" without any thought to other subgames. We no longer care how our range looks to our opponent, because they are no longer able to change their strategy.

> To see his claim applies to this game consider the case where P(Switch)=1. The policy you chose in one subgame just changed the EV of another subgame.

Sorry, but I don't understand this. This sounds to me like we fix the probability of switching to 1, which means that we end up in infinite loop and the outcome can not be computed. I don't understand this premise, nor its implications for the EV of the other subgame.

> This is a subtle distinction that I mentioned earlier - the EV of the envelope as in the wikipedia problem isn't the EV of the subgame. So you're not solving the subgame if you figure out the EV of the envelope.

The expression you use "EV of the envelope" is ambiguous in this context. I'm not sure if you mean EV relative to the value of the total amount of money in the game, or if you mean EV relative to the value of the firstly-chosen envelope.

When we're talking about "solving a game", we're talking about finding the optimal decisions within a game to maximize the expected value from the game as a whole. In the Two Envelope game we have just one decision: switch or not. So we need to find out if EV(switch) > EV(stay), where both EVs are relative to the total amount of money in the game (not relative to the value of firstly-chosen envelope). We have many ways to conclude that both of these actions have expected value zero. We don't have to be able to compute the "EV of the envelope". We only need to know the relative difference between the EV of these 2 actions. There's many ways of computing them, and all of those ways lead us to the conclusion that the EV of both actions is zero. I'm not aware of any "incorrect" way of computing those EVs such that we would get a nonzero result.

I guarantee you that your solution is going to have to incorporate a set somewhere that includes both subgames. You might forget it does, because you simplify to a scalar, but it is going to be there. In perfect information, it isn't there. In imperfect information it is.

Obviously the EV of envelope 1 is the contents of envelope 1. If you know the probability of reaching it you can calculate the expected value of that envelope by multiplying by the probability of reaching it. But why are you multiplying by 1/2? Probability is defined in terms of sets. What are the set that makes it 1/2? Does that set contain only the subgames that are part of the subgame you are in?

# Defining Counterfactuals

Consider a fair coin flip. You have {Heads, Tails}. Lets assume you are going to get heads, take it as a given - that is what actually happens. It actually happens. It is factual. However, for the purposes of analysis, sometimes it doesn't really matter that we know what happened. We need to consider all the cases that didn't happen. Tails in our analysis would be the counterfactual. These two situations, the factual heads and the counterfactual tails, they're associated with each other. There is a set {HT} that contains both of them. E.g P(head) = |{H}|/|{H, T}|.

When I'm saying counterfactual I'm referring to the events that we didn't assume to be factual, but which we want to keep track of. Probability kind of drops these terms when it says "assume" because it says |{H}|/|{H, T}| becomes |{H}|/|{H}| which is equal to one. This is perfectly fine from a math perspective. The thing is that just like saying 5/x = y lets us move to 5=xy is valid, it has some assumptions built into it. Namely that x can't be zero. Our counterfactuals are a bit like the x, because they offer an easily hidden constraint on what it is valid to do. If you reintroduce uncertainty about whether or not you are in H, you have to do so in a way that takes you back to having the set {H, T}.

Let me show you a practical example of that to make the point very clear:

Let the value of heads be one and the value of tails be zero. P(Head) = 0.5 But assume heads on the same coin flip. P(Head|assumptions) = 1.0 But assume heads again on the same coin flip. P(Head|assumptions) = 1.0. Now since P(Head) is actually true with 1/2 probability: Ev(Head) = 1/2*P(Head|assumption) + 1/2P(Head|assumption)?

Well, it is certainty true that 1/2P(Head|assumption) is a correct term. So you can't say this is wrong on the basis of the assumptions alone. Being very precise, the problem is the neglected counterfactual wasn't handled. Every term leading up to the equation was technically true, but obviously we just did something really weird right? And to be very precise, we neglected the counterfactual associated with heads.

# Defining subgames

Most games can be written out as a game tree. I showed one in my previous post. When you move down the tree, you are in a subgame of that tree.

In a perfect information game like chess if you are in a subgame, a portion lower on the tree, the other parts of the tree don't matter anymore. Your results are independent of the rest of the game tree.

In imperfect information though, just because you are in a subtree doesn't mean you know which subtree you are in. Your actual view into the game is through the information you have. Just like in the {HT} case you have to consider the potential that you have both H or T, in a subgame you have to consider the potential you are in every subgame that is reachable given the information you've seen.

Check out this to get a better sense of what I'm talking about: https://www.youtube.com/watch?v=EbKmZLp5HvA

Switching away from using A to avoid ambiguity.

> This is a fuzzy explanation that gives a feeling "something about this explains the issue", but it's not a complete explanation that precisely pinpoints what is wrong.

Yes it does, actually. Well, to me. I'll go more in depth so it less fuzzy for you.

The issue is that when you handle imperfect information correctly you have counterfactuals implied by your state-oriented reasoning, because you can't actually escape into perfect information world - you're not in it. When you combine the state-derived probabilities the - I don't know the word for this, so forgive me, but the - superposition of the two counterfactuals implied by those state-derived probabilities end up occupying the same space. They exist, because they are implied by the imperfect information game. They just aren't writing them out in the equations on wikipedia.

Edit: My 'spatial' probabilistic reasoning in my head is explained here, but I show you the identity rule that proves this in the next section.

> I never claimed that A = 2A

You aren't, but the counterfactual terms that get realized into the same position, but which weren't written out, claim that Z = 2Z and that Z = Z/2. The two cases were under two different games. So their implied counterfactual components don't agree with each other and we should never have been allowed to combine them.

We agree on this!

You're just more focused on the they come from different games part and not noticing the other part of what I'm telling you: you can equate the counterfactual components that they don't show between the two games, because there is an identity implied by being under imperfect information. Look at the set relationship closely across the two subgames and you'll realize that the set is defined to be equal to itself across all subgames where the set is used.

That is quite literally one of the logical contradictions. This is where they claim that 2=1. The sets aren't equal to each other after their operations. So by the identity implied by the set, they've claimed 2=1.

And yet when I try to claim this is a core aspect you throw out this...

> This is false. We can easily construct imperfect information games similar to this one, but tweak a few things in such a way that a "naively constructed EV calculation" yields the correct results.

This is a really dumb nitpick with very poor support. If you're going to be this fallacious, you might as well go all out. Why not say I'm wrong because first graders learning to add numbers aren't learning how to handle imperfect information subgames? After all, your argument for me being wrong is that the pedagogical value of problems is independent of the subproblems they contain.

> Nope! I was very clear about which very specific claims I was refuting.

You have a more subtle point than I thought you were making. I'll check out your other post.

> I didn't say "I spotted error X in Wikipedia which explains Two Envelope problem", I said "I spotted error X in this other poster's Hacker News comment". Please read the very specific comments I made about very specific claims made by the person.

Well, he does have another error; EV isn't defined over all policy choices. It is a problem on many of the wikipedia solutions too. He does see it - its why he mentioned other people talking about infinite series - but his correction attempt was more like "halt here because of type error" which is something that I as a programmer can respect.

But if only look at the formulat at bullet point 7 there "2A" and "0.5A" as amounts but not "A". It just doesn't describe the current state of reality

not trying to brag, just reformulating the simplest way for everyone to see

It's two versions of the reality in the same equation, which is wrong.

Use 100 usd / 200 usd instead of A and 2A and you'll see. If you never switch and if you always switch in both case the equation is

100×0.5 + 200x0.5

The problem is that they interchange A being the lowest and the highest in the same equation.

But the "possible values" they put in are A/2 and 2A, which makes no sense. A is a random variable.

Don't forget that random variables are really functions on a probability space with an implicit argument, so (1) when multiple random variables appear in a formula, they're implicitly evaluated at the same argument omega, and the formula must hold for all omega from the probability space, and more importantly, (2) there can't be free-standing omegas in a formula for expectation because expectation is an integral (or sum in this case where the probability space is discrete) over all possible omegas.

In my opinion, the Wikipedia article is making a disservice to readers by mentioning unnecessarily complex mathematical arguments involving bayesian reasoning and infinite distributions. I believe all of these are distractions from the more fundamental typing error that invalidates the switching argument.

> in particular, the puzzle is not solved by the very simple task of finding another way to calculate the probabilities that does not lead to a contradiction

The reason the calculations are wrong are fundamentally related to why correcting the calculations leads to the correct probabilities. If you understand why the problem gives you the wrong result, you proceed to correcting it, and you get the right result - that doesn't mean you didn't understand. It means you did. You can tell you did, because you have the correct answer.

But if I show the calculations produce the correct answers, well, that is a step too far. We can now dismiss the understanding on the basis that it got the correct answer, apparently?

It's no wonder the author of the wiki writes such a bullshit claim - that no one can agree on a definitive conclusion. Their terms of engagement are self-defeating. Correctness is error, because correctness means you didn't /really/ understand. Its a no true scottsman fallacy - get the right answer, and you aren't engaging with the 'real' problem.

But its a flawed no true scottsman, because it defines something measurable: it tells us the goal, that it is to avoid this type of mistake in our thinking. And generalized algorithms for solving decisions problems that include this as a case which is successfully solved are many - and they just so happen to be in the imperfect information setting. And that setting has studied the problem of infinite recursion and has solutions for them. Which I can apply. To get the right answer. And, in general, avoid the problems they claim we aim to avoid.

More importantly and to the point of this thread - this isn't an intractable debate, because its been solved and used in production settings for literally decades. So what if some people are going to pretend it isn't? This isn't an unsolved problem. The actual game theory math is /well/ beyond this level of complexity. Its contending with things like environments where you have so much complexity you have to reduce to a blueprint abstraction, not stumbling at a decision problem that is quite literally simpler than rock paper scissors.

You can arrive at the correct conclusion either by pinpointing exactly where the original argument is incorrect, or you can come up with a completely different argument that does not have an error.

The puzzle challenges you to pinpoint the error because coming up with the correct solution is trivial (and the puzzle is deliberately set up this way).

This is not a "nonsense goal." If this came up in real mathematical research - two papers coming to contradictory conclusions - and no one could find where either paper went wrong, we would have a real paradox on our hands.

I think the paradox is that the algorithm equates the expected value of the contents of an envelope with the expected value of a policy choice for a player. When I correct what I feel is the root of the paradox, my solution drastically differs in fundamental ways such that the way the problem restricts to pointing out the wrong step feels disingenuous.

The entire structure is wrong, because even if you do correct the error that leads to the wrong EV for the envelope, you still haven't resolved the paradox. The right probabilities don't resolve the paradox, because they still imply that always switching has the same EV as not switching. If they were really equal, I could always choose switch, but I can't - so the paradox is still there.

My resolution ends up being so critical of their argument that the entire way they go about solving gets thrown out. I end up seeing, not just a specific wrong EV calculation, but a decision problem that is just fundamentally using an inappropriate algorithm to determine the policy function.

We can agree that "the entire structure is wrong" because the "entire structure" is giving a wrong formula for the EV and saying "this is the formula for the EV."

Yes, switching and not switching have the same EV and you can always switch.

We aren't in agreement about this. I realize we have to fix this, but fixing it doesn't resolve the paradox. It is a red herring.

> Yes, switching and not switching have the same EV and you can always switch.

With all due respect, this isn't true and asserting this doesn't resolve the paradox. See my other reply for why it doesn't resolve the paradox.

To try and stress to you how big a problem this is, pretend you were playing the game and you wanted to find the right move that was going to make your EV the highest. Now, if you go with the logic of the problem, you are allowed to select not on the basis of your EV, but on the basis of some other EV. So instead of choosing the envelope, why not choose something else that has no relationship with our EV? Say, the weather in Alaska. If it is sunny, we like sunny. So switch. If it isn't sunny, we don't like that. So keep. It is crazy to do this, because there is no relationship between the EV you are using as a selection criteria and the EV your policy gets. This is the same situation as using the EV of the envelope. It sounds really crazy when you use the Alaska example, because it is so obviously unrelated. It sound so reasonable when you use the envelope example, because it isn't as obvious that they are unrelated. Yet for the policy of P(switch)=1, the ev of the envelope and the ev of the policy with respect to the game are not the same thing.

Now imagine the wikipedia article for the Alaska problem variant of the two envelope problem. Do you really think everyone would be so focused on the EV of the envelope as the step that was wrong? How could they? We have the same paradox still, but there is no EV calculation for the envelope included in the problem. If we can remove the EV calculation, yet still have the same paradox, it seems to me the paradox is not the expected value calculation.

So what is my solution? Well, to actually find your correct policy function you need to get the argmax of the policy with respect to the game. There are multiple ways to do this:

- Reinforcement learning does it by finding argmax pi with respect to Q_pi(s, a) = R(s') + P(keep)Q_pi(s',keep) + P(switch) Q_pi(s', switch).

- Game theory sets it up a bit differently. You define a similar graph using a different formalism, but simplified to operate over information sets. You can use a thing called regret matching; basically it turns out that if you play in proportion your normalized counterfactual regret, the average of those policies is the optimal best response.

In both cases you need to do something about the fact you're actually on an infinite graph. So the actual solution in the general case looks very very different from their way of solving the problem. It isn't just simple probability; I mean, it is, but taking the limit of an infinite sequence and taking advantage of the properties of markov chains aren't usually what I think of when someone tells me that something is simple probability. That is one formalism. In the other, we do have simple probability, but it isn't necessarily obvious that the central limit theorem gives us the optimal policy when we play in proportion to not just our regret, but our counterfactual regret. So yes, simple probability, but also, most people who know simple probability don't necessarily even know what a counterfactual is. So maybe not that simple after all.

But lets say we stick to the problem. We are here to learn how to avoid this problem, right? Nope. If you don't do things like this, you'll just be wrong in more complicated situations. Because the EV of the envelope is not the EV of the game with respect to your policy. This gets increasingly true as your imperfect information games get more complicated; it is very true of complex real world situations. The value of a wallet with a hundred dollars in the real world is different depending on whether you got that wallet with a policy function of robbing people versus earning it at your work. I feel sticking to their formalism means you end up conceited with regard to your ability to protect yourself from this paradox, because you consider yourself a master of the expected value of the envelope, but you're still vulnerable to the paradox, because the expected value of the envelope isn't the expected value of the game with your policy. So sticking with the problem is the opposite of protecting yourself.

I'm so far from what they want the problem to focus on, but they are wrong to focus on that. They aren't protecting themselves from making the same mistake. They're dooming themselves to use the wrong tools for solving this problem.. So they will make this mistake and they'll even be more confident in themselves as they do it, because they were clever and did the wrong thing in a better way, calculating the EV correctly, but staying within the land of paradox despite that.

The big problem is that you can't have a uniform distribution on the natural numbers.

(And by extension, you can't have a uniform distribution on the rounded-to-integer version of a distribution on the real numbers.)

Imagine we have a distribution that satisfies that assumption, and then someone tells you they've sampled from that distribution and found that the result is of the form (say) 7*2^k, for some k > 0. That conditional distribution for k would seem to have to be uniform, right?

Of course, the lack of a uniform distribution on the reals or rationals presents the same problem.

Well, you can either assume that the envelope's numbers are specified only up to pennies. Or you can just round and say you don't care about sub-pennies.

Or you can go with your suggestion, and look at the lack of a uniform distribution over the reals / rationals.

Or code that “obviously” has a bug only after it caused an issue in production.

Would be nice if someone warned me before I do a PR: “ok, fyi there is a subtle but devastating bug in the new_feature.cpp”

Where is the bug in this programm?

  END

Cognitively, the mind filters out quite a bit of information for performance reasons.

Are we biased in favor of reasoning that "sounds plausible"?

My "hot dice" say "yes".

The case where switching gives you 2A and the case where switching gives you A/2 describe 2 completely different universes, not two different actions in one.

Take the practical example of $100 and $200: A is either $100 or $200 depending on which envelope you receive first, so the equation is either 0.5*A + 0.5*2A, or it is 0.5*A + 0.5*(A/2). It can never be 0.5*2A + 0.5*(A/2)

The thing that helped me reconcile this was realizing that the A in the two equations are different values; then replacing them.

    (0.5⋅(0.5⋅A + 0.5⋅2.A)) + (0.5⋅(0.5⋅A + 0.5⋅0.5⋅A)) = 9/8 A

Replacing the As with their actual values

    0.5⋅(0.5⋅100+0.5⋅2⋅100)+0.5⋅(0.5⋅200+0.5⋅0.5⋅200) = 150

> If A is the smaller amount, then the other envelope contains 2A. > If A is the larger amount, then the other envelope contains A/2.

These are conditional probabilities so you can't simply add them up and compute an expected value of switching like they show in the example.

`B = (2A if A=50, A/2 if A=100)`. Simplifying this to `B = 2A or A/2` loses important information: namely that when B is smaller, you expect A to be larger. Or alternatively, treating A as fixed (say A=100) conflates two different situations: one where the amounts are `100, 200` and one where they are `100, 50`. So you end up thinking B must have (200+50)/2 in it, which is incoherent. If you compute the expected B correctly then `A` is different in each branch.

It is subtle though. If this appeared in a paper, arguing something not obviously wrong, it'd be hard to convince everyone that the reasoning is bad.

However, suppose x is placed in an envelope and handed to you. Then a fair coin is flipped. If it comes up heads, 2x is placed in another envelope and if it comes up tail, x/2 is placed in that envelope. Then you should switch.

It's a subtle difference in how the envelopes are prepared, but it makes all the difference.

I’m not sure I’d have naively realized that the fixed amount in your envelope makes so much difference.

For people confused like me, think about the outcomes:

When the two are prepared together, say $2 and $4, then when you exchange your options are +2 and -2 with 50:50 odds.

When the second envelope is prepared based on $2 in your envelope, then when you exchange your options are +2 and -1 with 50:50 odds.

(I had to diagram this all out; unintuitive to me!)

The introduction of a second "stage" based on your action changes things in a non-obvious way. Your first action is less impactful than your second one, regardless of what you did.

I see that the article also says "commonly one writer proposes a solution to the problem as stated, after which another writer shows that altering the problem slightly revives the paradox." But it doesn't seem to elaborate on where the simple resolution falls down, if it does.

https://www.youtube.com/watch?v=_NGPncypY68

TL;DR (Spoiler alert): the expected value of the amount of money you end up with is an infinite series whose sum changes depending on the order in which you add up the terms, and so you can choose an order that makes this value come out to be positive, negative, or zero.

I believe mike_hock provides the clearest and simplest explanation in this thread: https://news.ycombinator.com/item?id=31567251

I also made this argument separately: https://news.ycombinator.com/item?id=31569991

When E[X], E[A], and E[X - A] are all well-defined, it is indeed the case that if E[X | A = a] > a for every particular value a, then E[X] > E[A].

What goes awry in this case is that E[X - A] is not well-defined (where X is the value in the unselected envelope and A is the value in the selected envelope). It is given by a conditionally convergent series, as noted.

That initial setup being, the act of starting the game with someone is(?) confers value in and of itself.

So I’m glad the real solution is wonky.

When the amount you multiply your money by depends on the amount of money you currently have, you have to factor in your initial money to each case to compute expected return.

In particular, I am disputing the fact that "no proposed solution is widely accepted as definitive" (exact quote). Indeed, the switching argument (or at least the argument as it is presented in the Wikipedia article) makes a clear and precise mistake that I claim any trained mathematician will immediately agree on once pointed to it.

This mistake is explained in the following comments: https://news.ycombinator.com/item?id=31566226, https://news.ycombinator.com/item?id=31567251 and https://news.ycombinator.com/item?id=31569991.

Once you have identified it, this mistake is all but subtle. It is not about infinite series or Bayesian reasoning. It does not require a 30 minutes rebuttal talk. It is simply about misusing the very definition of an expected value in a way that could be qualified as a typing error (see linked comments). This error can only go undetected because of the ambiguity of the English language. Most of the fancy mathematical discussions I've been reading are distractions. This paradox is about language and not about any deep mathematical fact of probability theory.

The issue in this case is that E[X - A] is not well-defined. The expected profit from switching is given by an infinite series whose positive and negative components are each of infinite total magnitude, thus yielding different sums when bracketed differently ("conditional convergence"; just a coincidence that the word "conditional" comes up here again).

The reason for the apparent disagreement is that in order to point out a logical flaw in an argument, one must make the argument formal and explicit enough first. There are several plausible ways that the Wikipedia argument can be translated into a machine-checkable formal proof (and this ambiguity is at the core of the paradox). When I make such an attempt in my head, I am not interpreting the expectation as a conditional one and the problematic step is about conflating a random variable with a fixed constant. In your attempt to formalize the Wikipedia argument, you try and use the iterated expectation theorem and the problematic step becomes different. Seeing from the comments, several people agree with my interpretation but clearly there is an ambiguity here that is part of the paradox.

Thanks for prompting me to add nuance to my comment.

There is no such thing in mathematics such as an unresolved dispute over whether or not a five line proof with elementary concepts is flawed or not. The only possible situations are: 1) the proof can be checked to be correct at the level of axioms, 2) an incorrect reasoning step can be pointed to or 3) the proof is ambiguous and/or people cannot agree on what is being proved.

There isn't really a mathematical literature about the two envelopes paradox because the paradox is not really interesting from a mathematical standpoint. Or at least, making it interesting from a mathematical standpoint would require presenting a different argument than the one presented in the Wikipedia article. There may be a scholarly debate about different philosophical or linguistic aspects of this paradox. However, there is certainly no debate about where the flaw is in the presented switching argument once you make it precise enough.

(And the answer should not involve infinite series unless you are looking at a different, strong-arm version of the argument.)

A better article would first introduce a more precise version of the switching argument and then precisely identify the flaw in it. The more advanced mathematical and philosophical discussion that explores variations of the basic argument should be separated and contextualized clearly.

Normally we would assume there is someone who owns the envelopes of money. Now their incentive could be to offer to switch only if the envelope you chose contains more money (so they have a chance of keeping more). More like Monty Hall.

Even without that, after switching, should you switch back? The equation given argues you should switch back, so obviously the equation must be wrong.

It is easier to think: if I switch I have a 50% chance of making $X and a 50% chance of losing $X. Switching doesn’t change expected $.

I actually think the later problem in the Wikipedia article is more clever:

  Two people, equally rich, meet to compare the contents of their wallets. Each is ignorant of the contents of the two wallets. The game is as follows: whoever has the least money receives the contents of the wallet of the other (in the case where the amounts are equal, nothing happens). One of the two men can reason: "I have the amount A in my wallet. That's the maximum that I could lose. If I win (probability 0.5), the amount that I'll have in my possession at the end of the game will be more than 2A. Therefore the game is favourable to me." The other man can reason in exactly the same way. In fact, by symmetry, the game is fair. Where is the mistake in the reasoning of each man? — "Martin Gardner: Aha! Gotcha"

But assuming a more surprise situation in which the game is suggested* the reasoning is pretty good for both if they're happy with a 50% chance at doubling their money + X. But I think maybe its the hidden prize that makes the logic work (or not work)? For one of them the prize is less then double their money (a prize they'd never win but still) so the deal isnt a good deal. Not sure how the math works for that, but a contest where you might win 2a or less then 2a is presumably a different reasoning.

*Where similar to the first point we should assume the suggesters wallet is empty.

Ah, that observation is very clever! Even if you let yourself be bamboozled by the logic for switching, there is no reason then not to switch again by using the same logic. And again.. and again!

Now what is the probability of each winning? Did adding that step actually change the problem?

Or reword the problem just like I did in my grandparent comment: call the amount in the larger wallet $X. If you lose then you lose $X, and if you win then you win $X. 50% chance and expected outcome $X/2 by playing.

Suppose the amount in the envelope you choose is $100. If your amount is the smaller one, the other one has $200. If your amount is the larger one, the other one has $50. So the expectation supporting the switching argument is computed over two different scenarios, where the amounts in the envelopes are {50, 100} and {100, 200} respectively.

This calculation seems to violate a hidden logical constraint: the set of amounts in the two envelopes must be the same no matter what conditional branches we consider for the expectation.

Another related issue - if you switch, the argument for switching back assumes the amount in your original envelope is 4x what you originally said it was.

If you wanted to, you could explicitly model all possible values of the envelopes, and all possible observations of A – and you'd get the right answer again, including in the case above. You just can't define A in a path-dependent way, and then treat it as having the same value in all paths.

The relative percentage "rule of thumb" doesn't even feel like a primitive in math. It seems wrong to reason from that.

What is at question is the reason for getting to the expected value is the same.

this video explains the paradox properly, with a very reasonable explanation.

it doesn't really matter what the distribution of the amounts are, as long as there's an infinite number of possibilities in the distribution (ie., it's not a finite amount of possible envelopes).

For example if instead of halving the probability of each value as he does in the video we take 1/20 then we get the expected value as the sum of 9/20^2 - 9/20^2 + 90/20^3 - 9/20^3 + … Here the series is absolutely convergent since the positive terms sum to 9/10 and the negative terms sum to 9/10.

but then the probabilities don't all add up to 1.

how would one prove that claim? it's not obvious to me. it seems like the specific conditions under which the series of terms in the total expectation has a well defined sum is important, but I didn't fully grasp those conditions

In programming terms, the switching argument (see original link) is incorrect because it does not typecheck. And it does not typecheck because variable A is used out of its scope when writing down the (5/4)*A expected value.

Indeed, variable A is tied to a specific random outcome and so it simply does not make sense to refer to it in an expected value ranging over this same outcome.

Trying to formalize the argument in a proof assistant makes the mistake clear and obvious. However, the ambiguity of the English language makes it possible for such typing errors to sneak in undetected.

But that's simply not true.

> variable A is tied to a specific random outcome and so it simply does not make sense to refer to it in an expected value ranging over this same outcome

No, it isn't. It is the value of the chosen envelope -- which is known. You can open the envelope and look inside.

> Trying to formalize the argument in a proof assistant makes the mistake clear and obvious.

Have you actually tried this?

Consider the following alternative scenario: I give you $20 and offer you the following wager: we will flip a fair coin. If it lands heads you lose $10, tails you win (an additional) $20. Would you take that wager? If so, how is that different from the envelope problem? (Note that the $20 grant is a no-op, all it does is serve to fix the amount of the payouts after the coin flip.)

I'm pretty sure this could be reduced to the secretary problem where there's a pool of 2 candidates, which yields an optimal hire with probability 50%.

Maybe you play word games and say, "I guess the other number is not higher," or "I guess the other number is not lower." Since the number you observed was produced once, there is some non-zero probability that it was produced twice, in which case the other number is neither nigher nor lower.

Here's a hint that is not a full solution. If you knew that the numbers in both envelopes were independently sampled from the same Gaussian (but not necessarily which Gaussian), then there is a simple strategy that wins more than 50% of the time: pick an envelope to peek at uniformly at random and guess that it is the larger one if and only if it shows a positive number.

Why does this work? If both numbers are positive, your strategy is equivalent to "pick a random envelope" and you're left with a uniformly random choice of envelope. If both numbers are negative, you're also left with a uniformly random choice of envelope. But if one is positive and the other is negative, you win 100% of the time.

What are the odds of the third case? Well every Gaussian has at least some mass on positive numbers and some mass on negative numbers. So there is some nonzero chance, even if you don't know what it is. So while the strategy might not always do better than a coin toss, some positive percent of the time you win every time. And so you get a distinct advantage over random guessing.

The problem is now how would one transfer such an approach to the original problem without the Gaussian assumption. Somehow the two problems are less different than they initially seem.

Yep.

> Therefore, if the number is 9, both strategies tell you to do different things, yet in each case, your probability of winning is >½. There must be a hole in the logic somewhere…

For any nonnegative value C, the probability of Gaussian draw x being larger than (iid) Gaussian draw y is strictly bigger than 1/2 when conditioned solely on x > C.

The particular choice of C might change which specific draws of x and y the strategy succeeds with, but as you noticed for every C a thresholding strategy of the above form does give you some pointwise nonzero advantage over random guessing.

You pick an arbitrary threshold, if your envelope is below the threshold, you switch.

(You can add randomness as necessary.)

Choose a monotonically increasing function f with values between 0 and 1. Choose one of the envelopes at random. Then look at the number x in the envelope. Then, with probability f(x) say that you have the larger envelope.

Both are equally baffling in how / why they work.

A tangential question: real numbers are uncountably infinite. Are probability distributions over the real numbers likewise uncountably infinite, or do they form a higher infinity?

As for what uncountable cardinality they form, it's the same as the real numbers [0]. Roughly, a probability distribution is determined by the countable collection of real numbers P(X <= q) with q rational. That means the cardinality is no more than R^Q, which is isomorphic to R. (the cardinality is at least R due to, say, uniform distributions on [0, x] for x real).

[0] https://math.stackexchange.com/questions/3698864/why-does-th...

1. If the number you pick is positive, then there are technically (although arbitrarily small) more negative numbers that can be chosen for the other envelope. So you have a slightly larger than 50% chance of winning. 2. The inverse is true if you chose negative, however.

That said - I think this would generally imply you should always switch, which is why I'm not convinced I'm right. Consider a purely positive set, for example. If my number shows up as "12" - then I know there are infinitely more numbers larger than it, but only 11 numbers lower than it. But this starts to feel like the original two envelopes paradox.

--

tldr; I'm not sure of the answer, although I think if I saw the answer I would have an "Aha!" moment.

For whatever reason I can't get past my intuitive feeling that this problem is just a simple 50/50 and these proofs are just fancy window dressing.

"No proposed solution is widely accepted as definitive."

I mean for me this is totally a "cannot see the forest because of all the trees" situation and the intuitive solution is the right one.

But I thought the same of the monty hall problem (back in school) and only was convinved, after I wrote a small program to simulate it, which confirmed it.

But unlike in the monty hall problem, there is no new information here, when you are given the opportunity to switch. So the discussion seems weird to me.

Switching back and forth obviously doesn’t have any positive. What they mean by “is not definitive” is what explanation is the definitive one.

That is, the probability is 1/2. That's all that matters to the decision making. Calculating an "expected value" at all is completely useless, whether or not you do it "correctly".

Am I missing something?

No, because you're not actually wagering anything in the envelope game, so it makes no sense to calculate probabilities as though you are.

An analogous coin toss example would be something like: I'll flip a coin, you call heads or tails. If you call it right, I'll give you $10. If you're wrong, I'll give you $5. (So either way you make $5, so I don't know why anyone would even offer this game!) After I flip the coin, I'll conceal it in my hand and give you a chance to change your choice of heads or tails. Well, of course there's no reason to change your choice, it's completely arbitrary! You've got a 50-50 chance of winning $10 regardless. The paradox makes you think you're wagering your unknown potential winnings, but you're not actually wagering anything.

It has nothing to do with calculating whether or not a specific wager is worth it given some set of probabilities. That's a different problem for a different sort of game.

If we consider the decision point where you can either keep the first envelope or switch it, you are effectively wagering the value of the first envelope. You're just muddying the waters when you're trying to make some kind of point about receiving the first envelope for free. Yes yes, you are only gambling your "winnings" that you won earlier, it doesn't make a difference here.

> An analogous coin toss example would be something like: [...] I don't know why anyone would even offer this game!

Look, you made the claim that expected value doesn't matter for anything at all, the only thing that matters is the probability of winning. I offered you a game where you have a 50% probability of winning on each coin toss and I offered to pay you $1 for each coin toss to incentivize you to play it. Can you please explain why you are refusing to play this game? Yes, you don't like the analogy, I get that, but you also don't like free money? I find that hard to believe. A more plausible explanation is that you don't actually believe the claim you are making. That's why you aren't willing to wager any money on it.

It makes all the difference because you don't know what those "winnings" are, and what you're potentially wagering them for depends on what they are. So ultimately you're not really wagering anything. (Again, I think this is the crux of the "paradox".)

> Look, you made the claim that expected value doesn't matter for anything at all

I never meant to claim it doesn't matter for "anything at all", just not for this envelope game. (Apologies if the meaning of "at all" was ambiguous in my original post.)

When you say "this envelope game", I assume you are also including minor variations of this game?

If you mean specifically this exact envelope game, where the expected value for all actions is zero, then it is strictly true that it doesn't matter how we make decisions - using expected value or not - though it's not a particularly interesting point to make.

I will proceed assuming you mean also including minor variations of this game.

You wrote this earlier:

> That is, the probability is 1/2. That's all that matters to the decision making. Calculating an "expected value" at all is completely useless, whether or not you do it "correctly".

We can make a minor variation to the game such that the probability will still remain at 1/2, but the expected value for switching can be changed. We can make the minor variation such that it will be profitable to switch, or such that it will be unprofitable to switch. We can do this while the probability remains at 1/2. According to you the probability is all that matters, and it's useless to calculate the expected value for a game like this? This would lead to making unprofitable decisions in a game with a small variation as described above.

No; it seems obvious to me that the argument for switching presented in the original wikipedia article is meant to apply only to the evelope game as it's presented. Of course introducing variations could easily change the meaningfulness of the article's premise. That is, it wouldn't be considered a "problem" or a "paradox" if calculating an "expected value" were actually meaningful.

> then it is strictly true that it doesn't matter how we make decisions - using expected value or not - though it's not a particularly interesting point to make

True, but my point was more of a question: if it's obvious that calculating an "expected value" is irrelevant in this specific case (as the article says, "It may seem obvious that there is no point in switching envelopes as the situation is symmetric"), why is the argument presented in the article considered compelling? That is, either it's not actually compelling, or the "expected value" being meaningless in this case is not necessarily so obvious at first... but if so, why not? (Or, to put it another way, why is the argument in the article compelling enough to warrant such a long wikipedia page with such numerous proposed "resolutions"?)

Your question is akin to a driver plowing through red lights without an accident and concluding that the traffic light was useless in this specific instance. "I didn't cause a crash even though I ran a red light, so the traffic light was meaningless! In this specific instance I mean! It didn't matter if I stopped to the red light or ran across it, no accident would have happened either way in these very specific circumstances, so why are people even talking about traffic lights?"

I'd be happy to take you up on that offer. Let's play some dice or card games that are set up such that you'll always have 9/10 probability of winning. You'll play, regardless of the expected value, right?

You play the following game (say for many rounds). Someone puts different values in two envelopes (they can pick the values arbitrarily, even maliciously, each round). You want to pick the higher valued envelope. You pick an envelope, they show you the value of the other. You can hold your value or you can switch.

It also works if the game is they show you your own value and you can choose to hold or switch. Actually, now that I think about it, you can even make the game such that you pick an envelope and tell them which envelope to show you, then you can hold or switch. More interesting :)

The questions is: is there a strategy where you get the higher value strictly more than 50% of the time?

The surprising answer is, yes, there is such a strategy. It's really neat, and I've tried to find other places to apply the reasoning, but have not found another interesting place.

And yes, this problem and strategy are mathematically correct, not cheating, not "out of the box" stuff.

Good luck :)

For envelopes with two different numbers n, m, the above is guaranteed to give you the higher one strictly more than 50% of the time.

For example, exp^{-x^2} with normalization factor is a simple choice.

Asking for a friend, I obviously fully comprehend what you're talking about here.

Suppose you have a way to pick a random number yourself, that has nonzero chance to pick any number. Suppose the person putting things in envelopes picks X < Y as their numbers. You too pick a random number, say T. Open an envelope. If that envelope is less than T, then switch. You will get the larger number more than half the time.

Here is why it works. You pick X or Y envelope with 50/50 odds. 3 cases:

1) Suppose you picked a T < X. If you opened X, then T < X, you don't switch, so you lose. If you opened Y, T < Y, you don't switch, you win. So if T < X you win half the time.

2) Suppose you picked a T with Y < T. Then no matter what you pick, T is not < your envelope, you will not switch, and again you win half the time. Nothing gained so far.

But, if you happened to pick X < T < Y, which happens with some nonzero chance, then analyze: if you open X, X < T, switch, you win. If you open Y, T < Y, you don't switch, you win. This case gives you more than 50/50 odds.

The technical details is it's minorly tricky to pick a real number out of an infinite set at random, with any number being a possible outcome. But the probability distributions above do the trick - basically any function you can draw that is everywhere positive, with the tails squeezing to zero fast enough (but never reaching it) will work.

You cannot calculate the expected value (of the envelope you get, when you pick one randomly and then swap) like that, as A is not a constant and actually depends on if you took the less or more valuable envelope initially.

If you use A1=X in case you took the less valuable envelope initially and A2=2X in the other case, the expected value is (1/2)*(2*A1) + (1/2)*(A2/2) = 1.5X

and if you don't swap, you get: (1/2)*A1 + (1/2)*A2 = 1.5X

... which makes sense.

If you change the experiment so that the value of the second envelope does not depend on the first one (if you first chose and only then the value of the other envelope is randomly either double or half), A is constant and you actually should swap.

In point 2. the solution starts talking about probabilities without defining the sample space.

And this is why the solution is nonsensical. "One envelope contains twice as much as the other" does not define a sample space, so it is too early to start talking about probabilities.

If you say "the sample space is all pairs of natural numbers where one is twice as big as the other", then what are the probabilities assigned to each pair? They cannot be pairwise equal because the space is infinite.

So even if probabilities for (X, 2*X) and (X, X/2) happen to be equal for a particular X, they definitely cannot be equal for every X, so the "infinite swap" doesn't hold anymore.

https://en.wikipedia.org/wiki/Monty_Hall_problem

(except that problem has a more definite solution)

https://ycmusings.com/why-wont-we-switch/

http://wikibon.org/wiki/v/Prepare_three_envelopes

             -> Keep    -> 2A
          2A -> Switch  -> A
    0.5 ->
          A  -> Keep    -> A
             -> Switch  -> 2A

They created two trees one with 2A.

             -> Keep    -> 2A
          2A -> Switch  -> A
    0.5 ->
          A  -> Keep    -> A
             -> Switch  -> 2A

                -> Keep    -> A
          A     -> Switch  -> 1/2A
    0.5 ->
          1/2A  -> Keep    -> 1/2A
                -> Switch  -> A

Some people are pointing at the error I mentioned above, but I think the problem is actually much deeper than that. Identifying this error is basically identifying the superficial reason for why they went wrong. It doesn't dig deep enough to systematically eliminate the error.

I want to point out something. Notice their logic when they call out why it is a paradox. You can switch multiple times and it would never terminate.

Mathematical formalism like markov decision processes and the bellman equations actually have the ability to capture this type of reasoning. They can even deal with infinite loops as happens here by including multiplication by a horizon term which makes the limit of the recursion equal to zero.

So the root problem is that, actually, the entire problem wasn't even using the right theoretical grounding.

To get really explicit on how it was not using the right grounding I want to point out the key error again, but stated a bit differently.

The author neglects information sets. He creates two game trees, discriminating on the basis of knowledge of which subgame he is in. This is a huge red flag. You can do that in perfect information games, but you can't in imperfect information games! You aren't playing over states in imperfect information games. You're playing over information sets.

You end up getting more insights into how this is wrong when you think about the problem in this way. For example, there might not be an error in this particular problem, but the choice to not express the action space as a probability vector is going to bite you in more complicated imperfect information decision problems.

So for every strategy selection except the one the article chooses, the EV is what I mentioned before. But for the last it is zero.

Its the same problem: they aren't walking the graph of the game tree. But its a bit different to my simplified version of the game that shows where there EV calculations went super wrong, because the actual game tree is of infinite length and there is /never/ a node with SWITCH that terminates in a reward, because every SWITCH recurses to another decision point.

You can solve it using various formalism by adding a discount factor. That lets the limit go to zero for the recursive cases. I guess technically its undefined since the game never ends, but I don't consider being stuck in a loop to be rational [1]. You really have to let your action probabilities vary as you solve imperfect information problems. It happens in MDP and MCCFR for a reason - you don't get the correct action without for the way your policy choice affects the outcome distribution. Your expectation is dependent on your policy it doesn't exist in a void.

That last statement, well, it should be very obvious in more complex situations. That it isn't obvious in this situation speaks to the problems deceptive simplicity.

[1]: Unlike people who think humans are irrational for having cognitive biases.

Well no, one doesn't contain one fourth of the other.

Yes, B = A/2 or B = 2A with probability .5 each, but not for the same value of A.

E.g. if the maximum volume of currency that could fit in an envelope is $10k, it would be possible to have a uniform prior between 0-10k, at which point I would stick if my envelope had $5.01k.

A more extreme prior could be one capped at the largest ever academic research grant (I bet it's not more than $100m).

It could also be that you have a prior that has infinite mean, in which case it is not surprising that you will always want to switch if you draw a specific value.

If you have risk aversion, this further increases the range that you would like to stick, since switching could decrease your expected utility, even if it increases your expected return. There is a separate paradox in decision theory that we should be approximately risk-neural for 'small' amounts.

There are two flaws. One is the omission of counterfactual reasoning. This produces the logical contradiction 2=1 at step 7, but you get there a bit earlier because the steps before it are where you do case based reasoning. The scenario where this happens is when you are in imperfect information contexts. You can reason about subgames in perfect information games without the subgames influencing each other. You can't reason about them in imperfect information games without the subgames influencing each other.

The lessons is this - you have to consider counterfactuals. To give a concrete example of someone doing this, think Jeff Bezos when he talks about how he decided to found Amazon. He says he considered the situation in which he founded it and failed and the situation where he founded it and succeeded and the situation where he didn't found it. He didn't get his expectation conditioned on one state, but over an information set that contained many counterfactual outcomes.

The second flaw is much deeper and is what leads to the paradox. The failure is that the entire framing fails to recognize that EV is a function of policy. You can see this by setting the policy to always switch, as they do, and noting that the actual EV for switch is now undefined. Therefore in claiming knowledge of EV without having policy as a higher order function of EV you get a contradiction. 3/2A=0 and/or 3/2A=undefined.

The lesson in this is that policy function influences EV. This should hopefully be obvious to most people in more complicated situations. For example, slamming your head into your table has a lower EV than enjoying a drink of water. You have to account for this whenever your policy choice isn't defined.

Below I did two runs with a million cases. One envelope has 1 unit; the other has 2 units. I shuffle the envelopes, and the "player" chooses an envelope. "noChange" means this is the payoff if the player doesn't switch envelopes. "yaChange" means this is the payoff if the player switches envelopes.

$ python3 ./twoEnvelopes_00.py 1000000 noChange = 1500023 yaChange = 1499977

$ python3 ./twoEnvelopes_00.py 1000000 noChange = 1499984 yaChange = 1500016

When modeling Monte Hall, the payoff for changing is obvious.

The Two Envelopes Problem: the most boring paradox in the world - https://news.ycombinator.com/item?id=6388645 - Sept 2013 (12 comments)

Two envelopes problem - https://news.ycombinator.com/item?id=6387044 - Sept 2013 (88 comments)

Two Envelopes Problem - https://news.ycombinator.com/item?id=1582219 - Aug 2010 (88 comments)

[edit] Now submitted: https://news.ycombinator.com/item?id=31568880

https://www.youtube.com/watch?v=0yjVv_iB1h0 (Interestingly, a lot of those DoND comments have gone. Did they delete them?)

let M be the maximum amount of money that a envelope can contain (at worst it can be the total amount of money in the world). You don't know the value of this upper bound M.

Most of the time, you get 2*x or x/2 with 50% chance if you choose the other envelope (which on average is a win)

But when x=M you get M/2 instead of M and therefore you loose M/2 with 100% chance. And when it happens you have lost much more than in the other cases (because exponentiel...)

If you do the math, you can see that what you win for 1 2 4 8 16 ... M/2 is equal to what you loose for M.

And so on average what win from switching is 0.

(The usual term is sample space; it's just more fun to split and eliminate universes than states.)

Three friends go out for dinner and decide they will split the bill threeways. The bill comes to $25. Each friend gives a $10 note with $30 pooled together to pay the bill. The waitress returns with five $1 bills in change. They leave a $3 tip for the waitress with $2 in change remaining.

The question is: Of the original $30 paid if we deduct $3 in tips paid, we get $27. Adding the $2 in change remaining we get $29. Where is the other $1?

At the end I constructed a super weird example where regardless of what you see in your envelope, you should switch (this seems to go against the symmetry argument, but is sort of saved by a divergence in the expectation value).

"Having chosen... you are given the chance to switch"

Nowhere does it say, you'll be offered the switch no matter which envelope you choose.

Same idea applies, to the very similar Monty Hall problem.

Then whatever trick is being played you still have a 50-50 chance.

If the envelopes contain, say, $50 and $100, it looks like a doubling/halving. But nothing materially changes if we add $1000 to each one to make $1050 and $1100. The probabilities don't depend on what is in the envelopes, and the win/loss is just a spread of the difference between their values.

Why would anyone, while solving some problem, worry about some unspecified more complicated situation which supposedly resembles that problem?

Give me the specific of that more complicated problem and I will knock it out of the ballpark using whatever reasoning fits that problem.