Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Cheating Omega

7 Post author: gilch 13 April 2017 03:39AM

In Newcomb's problem, a superintelligence called Omega shows you two boxes, A and B, and offers you the choice of taking only box A, or both boxes A and B. Omega has put $1,000 in box B. If Omega thinks you will take box A only, he has put $1,000,000 in it. Otherwise he has left it empty. Omega has played this game many times, and has never been wrong in his predictions about whether someone will take both boxes or not.

Though a controversial position, my audience has probably heard by now that the "rational" answer is to one-box. (If not, see Newcomb's problem on the wiki).

I can do better.

The Deal

See, I've heard about Omega. I'm prepared. I installed the Universe Splitter app on my iPhone. It's basically a quantum coin flip: both outcomes happen in their respective Everett branches.

Now, I've pre-committed that after Omega offers me The Deal, I'll make two quantum coin flips. If I get two tails in a row, I'll two-box. Otherwise, I'll one-box.

It's an interesting finding of game theory that sometimes a winning strategy is to deliberately limit yourself. If you're playing a game of chicken for the fate of the human race, the winning strategy is to defiantly rip off the steering wheel and throw it out the window before your opponent does.

I've gained a third option in Newcomb's game by deliberately limiting my knowledge of my future actions. I physically can't know at the present time if I'll choose one box or two. (As both outcomes do, in fact, happen assuming Many Worlds.) And crucially, Omega physically can't know that either. Not until after it decides the contents of box A.

Therefore, Omega must predict that I'll one-box. After all, it's the higher probability. There's a 75% chance. If you have a large urn filled with three purple skittles for each yellow skittle, then your most accurate prediction of a sequence of four draws must rationally be PPPP, rather than some permutation of YPPP, as one might naiively expect.

There are now four possible outcomes:

HH = $1,000,000
HT = $1,000,000
TH = $1,000,000
TT = $1,001,000

The expected value is $4,001,000 / 4 = $1,000,250. I just cheated Omega out of an expected $250 over one-boxing.

Having proven a strategy superior to one-boxing, I can claim that if your decision theory just one-boxes without pre-committing to use quantum dice, something is wrong with it.

Even better

Of course, we can do even better than this. Two coin flips are easy to think about, but you could generate enough quantum noise to two-box with any probability you choose. The optimal case approaches 50%. You could aim for an expected payoff of $1,000,499.99...

In other words the limit is no more than $500 better than one-boxing by using a quantum dice strategy.

But the perfect predictor Omega is only the limiting case. Newcomblike reasoning can apply even if the predictor is imperfect. Does this change the optimal strategy?

Let's try extreme cases. Suppose Omega predicts then rolls a quantum d100 and flips its prediction on a roll of 42. This gives it a record of 99% accuracy. The two-flip strategy looks much like before.

99% chance of predicted one-box:

HH = $1,000,000
HT = $1,000,000
TH = $1,000,000
TT = $1,001,000

1% chance of predicted two-box:

HH = $0
HT = $0
TH = $0
TT = $1000

Payoffs are

74.25% of $1,000,000 = $742,500
24.75% of $1,001,000 = $247,747.50
0.75% of $0 = $0.00
0.25%  of $1000 = $2.50

For an expected payoff of $990,250. You expect only $990,000 by one-boxing, and only $11,000 by two-boxing. Two flips still works.

In the other extreme, suppose Omega flips 49.9% of its answers. This gives it a record of 50.1% accuracy.

50.1% chance of predicted one-box:

HH = $1,000,000
HT = $1,000,000
TH = $1,000,000
TT = $1,001,000

49.9% chance of predicted two-box:

HH = $0
HT = $0
TH = $0
TT = $1000

Payoffs are

(75% * 50.1%)$1,000,000 = $375,750.00
(25% * 50.1%)$1,001,000 = $125,375.25
(75% * 49.9%)$0 = $0
(25% * 49.9%)$1000 = $124.75

For an expected payoff of $501,250.00. You expect only $501,000.00 by one-boxing. It's the same difference of $250. But what if you two-box?

50.1% chance of predicted two-box * $1000 = $501
49.9% chance of predicted one-box * $1,001,000 = $499,499
Expected payoff of two-boxing: $500,000

It's interesting that two flips is still $250 better than one-boxing.

Now for the other limit. Suppose Omega just flips a coin to predict. The game is no longer Newcomblike. Expected payoff for one-boxing is $500,000; for two-boxing it is $500,500. That's $500 better. The two-flip strategy is only $500,250 or $250 better than one-boxing. When Omega's prediction is no better than chance, you might as well two-box. But recall that the quantum dice strategy in the limit also makes an expected $500 more than one-boxing.

This is regardless of how well Omega can predict your choice. Given quantum dice, Newcomb's problem is not Newcomblike.

While it's a useful intuition pump, the above argument doesn't appear to require the Many Worlds interpretation to work. (Though Many Worlds is probably correct.) The dice may not even have to be quantum. They just have to be unpredictably random.

The qualification "given quantum dice" is not vacuous. A simple computer algorithm isn't good enough against a sufficiently advanced predictor. Pseudorandom sequences can be reproduced and predicted. The argument requires actual hardware. Hardware that some humans posses, but not innately. If you want to call that cheating, see the title, but also recall that we're interested in Newcomblike problems not just for human rationality, but for a better theory of idealized agents, which will help us reason about AI problems. AIs that could perhaps read each other's source code as part of their negotiations. How do you negotiate with an agent capable of wielding quantum randomness?

Some questions

Can other Newcomblike games be subverted this way?

Can the predictor counter this? If given quantum dice?

If the games are iterated, what's the behavior in the limit? Taking Newcomb's problem as an example, assume Omega's goal is to cause one-boxing. A subgoal would be to maintain high accuracy, so the choosers believe in Omega's accuracy. Recall that if Omega can't predict better than chance, the optimal strategy is to two-box. Assume the chooser's goal is to maximize return.

A chooser might want use dice to be as close to 50% as possible, while still being predictably more likely to one-box. We know the rational choice given skittles in an urn, but should Omega deliberately punish such defectors by biasing in favor of two-box predictions? Even though this reduces Omega's accuracy? With one chooser, this starts to look like iterated prisoner's dilemma. With multiple choosers, the tragedy of the commons. Even if Omega tries its best, its track record will suffer once choosers start using dice. How is the next chooser supposed to tell if this is because Omega is defecting (or defective) or if other choosers are just that unpredictable?


So last week, the heavens opened, Omega descended from outer space, and offered me The Deal.

With a smirk, I whipped out my iPhone and opened the Universe Splitter.

"Oh, one more thing, Chooser," said Omega.

I froze, then slowly looked up from my iPhone. Omega couldn't possibly be changing the rules on me. That wasn't The Deal. And it's hard to make optimal decisions under time pressure, you know?

"What's that?" I asked cautiously.

"I noticed you trying to split the universe just now.". Nothing gets past you, huh? Omega continued, "I thought you should know, I'm actually not omniscient. I'm not even a super predictor or anything."

"But...you've never been wrong," I countered, incredulous.

Omega pressed on, "I only 'predicted' your choice by quantum coin flip. However, I've always pre-committed to immediately destroy the universe if I turn out to have predicted wrong. I've done it this way for every Deal. You, of course, can only find yourself in an Everett branch where I have not (yet) destroyed the universe. My apparent perfect track record is purely due to anthropic effects. Just saying."

I felt my pulse quicken as my eyes slowly widened in horror.

"YOU CAN'T DO THAT!" I raged.

"Chooser, I am a thought experiment! I can do anything you can imagine." Omega declared triumphantly. "If you think about it carefully, you will realize that I have never even changed The Deal. Now choose."

I began frantically typing cases in my iPhone. If I stick to my original plan, there are eight possible outcomes, based on Omega's coin flip "prediction", and my two coin flips:

1 HH = $1,000,000
1 HT = $1,000,000
1 TH = $1,000,000
1 TT = $1,001,000, but universe is destroyed
2 HH = $1,000, but universe is destroyed
2 HT = $1,000, but universe is destroyed
2 TH = $1,000, but universe is destroyed
2 TT = $1,000

"I don't want to get destroyed, but since my counterpart in the other branch created by Omega's 'prediction' event will be making his decision by the same process, it looks like I'll be losing half of my measure either way. Maybe I should just ignore the branches where I don't exist," I thought aloud as I deleted the lines.

1 HH = $1,000,000
1 HT = $1,000,000
1 TH = $1,000,000
2 TT = $1,000

My expected payoff is now $3,001,000 / 4 = $750,250. Looking at it this way, it's clear that I should just one-box.

I reach out to take only box A, but hesitated.

As tears welled up, I wondered: was I about to die? I was briefly tempted to do one quantum coin flip to decide anyway, just so that I can be sure a future from this point exists. But then I realized that regardless of the outcome I'd just be tempted to do so again and again, forever. That way lies madness.

If all memory of what happened since you woke up this morning is erased or replaced, but then life continues as normal, have you died? Don't you do something similar every night? If I had known Omega's evil plan from the start, would my decision have changed?

No. It wouldn't have. I swallowed my tears. I held my breath. I picked up box A. Omega retrieved box B and flew off into the sunset.

Omega, of course, "predicted" this perfectly, and box A contained my expected million.

It didn't occur to me until the next day that Omega might have been bluffing. Why did I just take Omega's word for it?


Comments (27)

Comment author: g_pepper 13 April 2017 01:47:55PM 11 points [-]

This is an interesting strategy for beating Omega!

However, Nozick actually anticipated this - the original paper stipulates (in the first end-note) that if Omega predicts that you will consciously randomize your choice, it will not put the $1M in the second box.

Comment author: Thomas 13 April 2017 05:58:10PM 1 point [-]

if Omega predicts that you will consciously randomize your choice, it will not put the $1M in the second box.

So, his predictions are not as good as it's stipulated.

Many people randomize their choices in these parts of the world.

Comment author: MrMind 13 April 2017 07:47:19AM 3 points [-]

You have not cheated Omega, you have just changed the terms of the problem so that it suits you better. Probabilistic Newcombs are a totally different beast: if we introduce uncertainty in our behaviour, then one must consider also uncertainty in Omega outcomes, for example saying that Omega puts a million in the box 75% of the times that it predicts that you'll choose only box A 75% of the times.

Comment author: Gurkenglas 15 April 2017 11:42:24AM 0 points [-]

Then to maximize expected value, we should one-box 50% of the time for an expected 250k.

Comment author: Oscar_Cunningham 13 April 2017 07:11:29AM 3 points [-]

Omega can say that the box will be empty unless you one-box with probability 1. Then one-boxing is the optimal strategy.

Comment author: Kallandras 13 April 2017 06:54:12PM 2 points [-]

You'd never get the million that way, there's a greater-than-zero chance that you'll die before making a decision.

Comment author: Good_Burning_Plastic 20 April 2017 08:24:49AM 0 points [-]

Okay, make that "with probability greater than 99.95%".

Comment author: gilch 20 April 2017 12:34:42AM 0 points [-]

Not so. 1 is not a probability. Even if you can read your own source code, you can't know that no outside force will alter your choice. You cannot achieve one-boxing with probability 1. Thus, the optimal strategy in your scenario is to two-box.

But Omega is just the limiting case of a perfect predictor. Newcomblike reasoning can apply even if the predictor is imperfect. Care to try again?

Comment author: Oscar_Cunningham 20 April 2017 10:30:09AM 0 points [-]

Sure, let's say Omega calculates the probability that you two-box and removes that proportion of the money from box A. Then your optimal strategy is to one-box with as much probability as you can.

Comment author: gilch 21 April 2017 08:54:31PM 0 points [-]

I think that does follow, but you're altering The Deal. This is a different game.

The only thing Omega is allowed to do is fill the box, or not, in advance. As established in the OP, however, Omega can reduce the expected value by predicting less accurately. But over multiple games, this tarnishes Omega's record and makes future Choosers more likely to two-box.

Comment author: entirelyuseless 20 April 2017 01:49:25PM *  0 points [-]

Thinking in this way seems to remove the possibility of meaningful strategies. That is, suppose I am considering: "Should I one-box with 80% probability? or 90% probability?" The overall probability will have to be some combination of the two. And choosing the 90% case does not seem to be a possible strategy, because I cannot make it more likely than it is that I will use the 90% case -- i.e. if there is a 50% chance I will choose to use the 90% case, then I will do that in 50% of cases, and there is nothing I can do to make that 50% more or less. The chance that I will do X, is just the chance that I will do X, until I do whatever I do.

(This is like an extension of deterministic thinking: if the world is not deterministic, then it is probabilistic. So just as the determinist says, "Whatever is going to happen, is going to happen, and you can't change that," in a similar way someone can argue, "All possibilities currently have certain probabilities, and they will happen or not happen, following those definite probabilities, not other probabilities.")

Comment author: Oscar_Cunningham 20 April 2017 02:15:16PM 0 points [-]

The probabilities are based on Omega's state of knowledge. The original problem assumes that Omega is near-omniscient, so that he is extremely likely to make a correct prediction. If you assume that it's possible at all to make a random choice then you must have some "hidden" source of information that Omega can't see. Otherwise the strategy in the original post wouldn't even work, Omega would know how your "random" choice was going to come out so every time you two boxed you would find the box empty and vice-versa.

So when I said "probability" I meant the probability as judged by Omega based on his near total knowledge of your brain and your environment, but with no knowledge of some source of randomness that you can use to generate decisions.

Comment author: gilch 21 April 2017 08:49:31PM *  0 points [-]

Many Worlds is deterministic. What relevant information is hidden? Omega can predict with certainty that both outcomes happen in the event of a quantum coin flip, in different Everett branches. This is only "random" from a subjective point of view, after the split. Yet given the rules of The Deal, Omega can only fill the box, or not, in advance of the split.

Comment author: Good_Burning_Plastic 20 April 2017 08:23:37AM 1 point [-]

Now, I've pre-committed that after Omega offers me The Deal, I'll make two quantum coin flips. If I get two tails in a row, I'll two-box. Otherwise, I'll one-box.

Omega predicted that and put the large box in a quantum superposition entangled with those of the coins, such that it will end up containing $1M if you get at least a head and containing an equal mass of blank paper otherwise.

Comment author: gilch 21 April 2017 11:00:27PM 0 points [-]

Interesting. Why the equal mass? Omega would need Schrodinger's box, that is, basically no interaction with the outside world lest it decohere. I'm not sure you could weigh it. Still, quantum entanglement and superposition are real effects that may have real-world consequences for a decision theory.

We can inflate a quantum event to macroscopic scales like with Schrodinger's cat. You have vial of something reactive in the box to destroy the money, and a hammer triggered by a quantum event.

But isn't that altering The Deal? If Omega is allowed to change the contents of the box after your choice, then it's no longer a Newcomblike problem and just an obvious quid pro quo that any of the usual decision theories could handle.

I'm not sure I understand the setup. Can you cause entanglement with the coins in advance just by knowing about them? I thought it required interaction. I don't think Omega is allowed that access, or you could just as easily argue that Omega could interact with the Chooser's brain to cause the predicted choice. Then it's no longer a decision; it's just Omega doing stuff.

Comment author: WalterL 14 April 2017 04:54:07PM 0 points [-]

It seems like you are confused about the timing here. Omega gives you the boxes, knowing the future, quantum coin flips and all. You can do whatever you like, but when you open it/them you'll get what he gave you.

Even a naive 2 boxing can just claim Many Worlds and announce that other versions of itself got the rewards. So what? The goal is to get the most money in THIS world.

Comment author: gilch 20 April 2017 12:27:19AM *  0 points [-]

I am not the one who is confused. The act of flipping a quantum coin splits the timeline. Two existing futures share the same past. Omega does predict both of the futures, but can only set up the boxes once, in the one shared past. The Deal stipulates that Omega set up the boxes in advance, before you decide via quantum coin flip, and Omega does not change the setup afterwards. The Chooser is also supremely confident in Omega's predictive ability, due to past performance.

Comment author: Lumifer 20 April 2017 01:53:48AM 1 point [-]

Two existing futures

Ain't no such thing.

Comment author: gilch 21 April 2017 08:16:12PM 0 points [-]

Consider that down voted. It's too ambiguous. I can't tell what you're trying to say. Are you just nitpicking that both worlds have the same value on the t axis? Are you just signaling that you don't believe in many worlds? Is there some subtlety of quantum mechanics I missed, you'd like to elaborate on? Are you just saying there's no such thing as randomness?

Comment author: Lumifer 21 April 2017 08:40:02PM *  0 points [-]

I am trying to say that you use words in a careless and imprecise manner.

I also don't "believe" in Many Worlds, though since there are guaranteed to be no empirical differences between the MWI and Copenhagen, I don't care much about that belief: it pays no rent.

Comment author: gilch 21 April 2017 09:22:19PM *  0 points [-]

And the winner is

you use words in a careless and imprecise manner

(The pot calls the kettle black.) Natural languages like English are informal. Some ambiguity can't be helped. We do the best we can and ask clarifying questions. Was there a question in there?

guaranteed to be no empirical differences

Assuming Omega's near-omniscience, we just found one! Omega can reliably predict the outcome of a quantum coin flip in a Copenhagen Universe, (since he knows the future), but can't "predict" which branch we'll end up in given a Many Worlds Multiverse, since we'll be in both. (He knows the futures, but it doesn't help.)

So let's not assume that. Now we can both agree Omega is unrealistic, and only useful as a limiting case for real-world predictors. Since we know there's no empirical difference between interpretations, it follows that any physical approximation of near-omniscience can't predict the outcome of quantum coin flips. My strategy still works.

Comment author: Lumifer 23 April 2017 05:13:27PM *  0 points [-]

but it doesn't help

You flip the quantum coin, it says "two box".

You open one box. It's empty. You open the other box. It's empty.

You: WTF, man!

Omega: I am altering the deal, pray I don’t alter it any further.

Comment author: WalterL 21 April 2017 07:06:14PM 0 points [-]

This shouldn't be tough. He gives you the box. You flip a coin. You open or don't. He saw that coming. You get what he gave you.

Fancy talk doesn't change his ability to know what you are gonna do. You might as well say that another version of you had a heart attack before they could open any boxes, so your plan is bad as say that another version of you tricked Omega so your plan is good.

Comment author: gilch 21 April 2017 08:20:06PM 0 points [-]

Consider that down voted. You're totally strawmanning. You're not taking this seriously, and you're not listening, because you're not responding to what I actually said. Did you even read the OP? What are you even talking about?

Comment author: WalterL 23 April 2017 06:04:25AM 1 point [-]

I'm simplifying, but I don't think it's really strawmanning.

There exists no procedure that the Chooser can perform after Omega sets down the box and before they open it that will cause Omega to reward a two boxer or fail to reward a one boxer. Not X-raying the boxes, not pulling a TRUE RANDOMIZER out of a portable hole. Omega is defined as part of the problem, and fighting the hypothetical doesn't change anything.

He correctly rewards your actions in exactly the same way that the law in Prisoner's Dilemma hands you your points. Writing long articles about how you could use a spoon to tunnel through and overhear the other prisoner, and that if anyone doesn't have spoons in their answers they are doing something wrong...isn't even wrong, it's solving the wrong problem.

What you are fighting, Omega's defined perfection, doesn't exist. Sinking effort into fighting it is dumb. The idea that people need to 'take seriously' your shadow boxing is even more silly.

Like, say we all agree that Omega can't handle 'quantum coin flips', or, heck, dice. You can just repose the problem with Omega2, who alters reality such that nothing that interferes with his experiment can work. Or walls that are unspoonable, to drive the point home.

Comment author: gilch 24 April 2017 12:11:01AM *  0 points [-]

Writing long articles about how you could use a spoon to tunnel through and overhear the other prisoner, and that if anyone doesn't have spoons in their answers they are doing something wrong...

Another strawman. Strawman arguments may work on some gullible humans, but don't expect it to sway a rationalist.

You can just repose the problem with Omega2, who alters reality

You're not being very clear, but it sounds like you're assuming a contradiction. You can't assert that Omega2 both does and does not alter the reality of the boxes after the choice. If you allow a contradiction you can do whatever you want, but it's not math anymore. We're not talking about anything useful. Making stuff up with numbers and the constraint of logic is math. Making stuff up with numbers and no logic is just numerology.

not pulling a TRUE RANDOMIZER out

I think this is the crux of your objection: I think agents based on real-world physics are the default, and an agent - QRNG (quantum random number generator) problem is an additional constraint. A special case. You think that classical-only agents are the default, and classical + QRNG is the special case.

Recall how an algorithm feels from the inside. Once we know all the relevant details about Pluto, you can still ask, "But it really a planet?". But at this point understand we're not talking about Pluto. We're talking about our own language. Thus which is really the default should be irrelevant. We should be able to taboo "planet", use alternate names, and talk intelligently about either case. But recall the OP specifically assumes a QRNG:

This is regardless of how well Omega can predict your choice. Given quantum dice, Newcomb's problem is not Newcomblike.

While it's a useful intuition pump, the above argument doesn't appear to require the Many Worlds interpretation to work. (Though Many Worlds is probably correct.) The dice may not even have to be quantum. They just have to be unpredictably random.

The qualification "given quantum dice" is not vacuous. A simple computer algorithm isn't good enough against a sufficiently advanced predictor. Pseudorandom sequences can be reproduced and predicted. The argument requires actual hardware.

Pretending that I didn't assume that, when I specifically stated that I had, is logically rude.

What you are fighting, Omega's defined perfection, doesn't exist. Sinking effort into fighting it is dumb. The idea that people need to 'take seriously' your shadow boxing is even more silly.

Why do we care about Newcomblike problems? Because they apply to real-world agents. Like AIs. It's useful to consider.

Omniscience doesn't exist. Omega is only the limiting case, but Newcomblike reasoning applies even in the face of an imperfect predictor, so Newcomblike reasoning still applies in the real world. QRNGs, do exist in the real world, and IF your decision theory can't account for them, and use them appropriately, then it's the wrong decision theory for the real world. classical + QRNG is useful to think about. It isn't being silly to ask other rationalists to take it seriously, and I'm starting to suspect you're trolling me here.

But we should be able to talk intelligently about the other case. Are there situations where it's useful to consider agent - QRNG? Sure, if the rules of the game stipulate that the Chooser promises not to do that. That's clearly a different game than in the OP, but perhaps closer to the original formulation in the paper that g_pepper pointed out. In that case, you one-box. We could even say that Omega claims to never offer a deal to those he cannot predict accurately. If you know this, you may be motivated to be more predictable. Again, a different game.

But can it look like the game in the OP to the Chooser? Can the Chooser think it's in classical + QRNG, when, in fact, it is not? Perhaps, but it's contrived. It is unrealistic to think a real-world superintelligence can't build a QRNG, given access to real-world actuators. But if you boxed the AI Chooser in a simulated world (denying it real actuators), you could provide it with a "simulated QRNG", that is not, in fact, quantum. Maybe you generate a list of numbers in advance, then you could create a "simulated Omega" that can predict the "simulated QRNG" due outside-the-box information, but of course, not a real one.

But this isn't The Deal either. This is isomorphic to the case where Omega cheats by loading your dice to match his prediction after presenting the choice (or an accomplice does this for him), thus violating The Deal. The Chooser must choose, not Omega, or there's no point. With enough examples the Chooser may suspect it's in a simulation. (This would probably make it much less useful as an oracle, or more likely to escape the box.)

Comment author: Yosarian2 14 April 2017 02:59:20AM 0 points [-]

Yeah, creating a situation where you are making a choice random can be a way to win some game-theory situations.

Disturbingly, this is a "solution" to real world MAD nuclear war game theory; you probably can't credibly threaten to INTENTIONALLY start a nuclear war, because that would kill you and nearly all the people in your country as well, but you CAN create situations of uncertainty where there is (or appears to be) a real risk that a nuclear war may randomly happen without you actually wanting it to; if the other side has a lower tolerance for existential risk then you do, the other side may back down and try to negotiate at that point.

There are a lot of variations on this; saber rattling and deliberate near-misses, stationing troops in places they can't possibly defend (like Berlin in the cold war) just as a "trip wire" to increase the odds of WWIII happening if the Soviet Union invaded Berlin, Nixon "madman" theory, probably most of North Korea's recent moves, ect. It all comes down to the same thing; not actual randomness, which humans can't really do, but uncertainty, which is almost as effective.