> I drew in an ASCII art a diagram of the various game trees so it will be easier for you to see this:
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 game tree only makes sense if you change the definition of A.
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.
Basically when the wiki says 2A because less than and A/2 because greater than things are okay, but we're in dangerous territory. If we ever introduce uncertainty the imperfect information scenario we are in is going to force us to acknowledge that we don't know which game we are in. Which means if that happens we don't have just 2A, but a information set {2A, A}. And we don't just have A/2, but an information set {A/2, A}. In game theory if you have two subtrees and they share an information set than the information sets are equal to each other. You can't tell which subtree you are in, so the information set contains both subgames. You can think of one as factual and the other as counterfactual and vice versa, but the elements in that set need to be equal. 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.
> 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.
> 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.
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 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!"
> 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
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.
> If both are worth the same, well, why not always switch?
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 feel like this is a detour that we can avoid by adding a small cost to switching.
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/0e358db69fc04ad39781acdc8300059e7a93791a 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.
> 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.
# 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 https://www.youtube.com/watch?v=EbKmZLp5HvA