Decisions, decisions

« Cartesian closed categories and the Lawvere fixed point theorem

Decisions, decisions

October 9, 2013 by Qiaochu Yuan

Newcomb’s paradox is the name usually given to the following problem. You are playing a game against another player, often called Omega, who claims to be omniscient; in particular, Omega claims to be able to predict how you will play in the game. Assume that Omega has convinced you in some way that it is, if not omniscient, at least remarkably accurate: for example, perhaps it has accurately predicted your behavior many times in the past.

Omega places before you two opaque boxes. Box A, it informs you, contains $1,000. Box B, it informs you, contains either $1,000,000 or nothing. You must decide whether to take only Box B or to take both Box A and Box B, with the following caveat: Omega filled Box B with $1,000,000 if and only if it predicted that you would take only Box B.

What do you do?

(If you haven’t heard this problem before, please take a minute to decide on an option before continuing.)

The paradox

The paradox is that there appear to be two reasonable arguments about which option to take, but unfortunately the two arguments
support opposite conclusions.

The two-box argument is that you should clearly take both boxes. You take Box B either way, so the only decision you’re making is whether to also take Box A. No matter what Omega did before offering the boxes to you, Box A is guaranteed to contain $1,000, so taking it is guaranteed to make you $1,000 richer.

The one-box argument is that you should clearly take only Box B. By hypothesis, if you take only Box B, Omega will predict that and will fill Box B, so you get $1,000,000; if you take both boxes, Omega will predict that and won’t fill Box B, so you only get $1,000.

The two-boxer might respond to the one-boxer as follows: “it sounds like you think a decision you make in the present, at the moment Omega offers you the boxes, will affect what Omega did in the past, at the moment Omega filled the boxes. That’s absurd.”

The one-boxer might respond to the two-boxer as follows: “it sounds like you think you can just make decisions without Omega predicting them. But by hypothesis he can predict them. That’s absurd.”

Now what do you do?

(Again, please take a minute to reassess your original choice before continuing.)

The von Neumann-Morgenstern theorem

Let’s avoid the above question entirely by asking some other questions instead. For example, a question one might want to ask after having thought about Newcomb’s paradox for a bit is “in general, how should I think about the process of making decisions?” This is the subject of decision theory, which is roughly about decisions in the same sense that game theory is about games. The things that make decisions in decision theory are abstractions that we will refer to as agents. Agents have some preferences about the world and are making decisions in an attempt to satisfy their preferences.

One model of preferences is as follows: there is a set $\mathcal{O}$ of (mutually exclusive) outcomes, and we will model preferences by a binary relation $o_1 \le o_2$ on outcomes describing pairs of outcomes such that the agent weakly prefers $o_2$ to $o_1$ . This means either that in a decision between the two the agent would pick $o_2$ over $o_1$ (the agent strictly prefers $o_2$ to $o_1$ ; we write this as $o_1 < o_2$ ) or that the agent is indifferent between them. The weak preference relation should be a total preorder; that is, it should satisfy the following axioms:

Reflexivity: $o \le o$ . (The agent is indifferent between an outcome and itself.)
Transitivity: If $o_1 \le o_2$ and $o_2 \le o_3$ , then $o_1 \le o_3$ . (The agent’s preferences are transitive.)
Totality: Either $o_1 \le o_2$ or $o_2 \le o_1$ . (The agent has a preference about every pair of outcomes.)

If $o_1 \le o_2$ and $o_2 \le o_1$ then this means that the agent is indifferent between the two outcomes; we write this as $o_1 \simeq o_2$ . The axioms above imply that indifference is an equivalence relation.

The strong assumptions here are transitivity and totality. One reason totality is a reasonable axiom is that an agent whose preferences aren’t total may be incapable of making a decision if presented with a choice between two outcomes the agent doesn’t have a defined preference between, and this seems undesirable. For example, if we were trying to write a program to make medical decisions, we wouldn’t want the program to crash if faced with the wrong kind of medical crisis.

One reason transitivity is a reasonable axiom is that an agent whose preferences aren’t transitive can be money pumped. For example, if an agent strictly prefers apples to oranges, oranges to bananas, and bananas to apples, then I can offer the agent an apple, then offer to trade it a banana for the apple and a penny (say), then offer to trade it an orange for the banana and a penny (say), and so forth. Again, if we were trying to write a program to make important decisions of some kind, this kind of vulnerability would be very dangerous.

In this model, an agent makes decisions as follows. Each time it makes a decision, it must choose from some number of actions. It needs to determine what outcomes $o \in \mathcal{O}$ result from each of these actions. Then it needs to determine which of these outcomes is greatest in its preference ordering, and it selects the corresponding action.

This is very unsatisfying as a model of decision making because it fails to take into account uncertainty. In practice, agents making decisions cannot completely determine what outcomes result from their actions: instead, they have some uncertainty about possible outcomes, and that uncertainty should be factored into the decision-making process. We will take uncertainty into account as follows. Define a lottery over outcomes to be a formal linear combination

$\displaystyle \ell = \sum_i p_i o_i$

of outcomes, where the $p_i \in [0, 1]$ are real numbers summing to $1$ and should be interpreted as the probabilities that the outcomes $o_i$ occurs. (Equivalently, a lottery is a particularly simple kind of probability measure on the space of outcomes, which is given the discrete $\sigma$ -algebra as a measurable space, but we will not need to use this language.) We now want our agent to have preferences over lotteries rather than preferences over outcomes. That is, the agent’s preferences are now modeled by a total order $\ell_1 \le \ell_2$ on lotteries.

Aside from the axioms defining a total order, what other axioms seem reasonable? First, suppose that $\ell_1, \ell_2$ are two lotteries such that $\ell_1 \le \ell_2$ . Now consider the modified lotteries $p \ell_1 + (1 - p) \ell_3$ and $p \ell_2 + (1 - p) \ell_3$ where with probability $p$ the original lotteries occur but with probability $1 - p$ some other fixed lottery occurs. Whether we are in the first case or not, we either prefer or are indifferent to what happens in the second lottery, so the following seems reasonable.

Independence: If $\ell_1 \le \ell_2$ , then for all $\ell_3$ and all $p \in [0, 1]$ we have $p \ell_1 + (1 - p) \ell_3 \le p \ell_2 + (1-p) \ell_3$ . Moreover, if $\ell_1 < \ell_2$ and $p \in (0, 1]$ then $p \ell_1 + (1 - p) \ell_3 < p \ell_2 + (1 - p) \ell_3$ .

Note that by taking the contrapositive of the second part of independence we get a partial converse of the first part: if $p \in (0, 1]$ such that $p \ell_1 + (1 - p) \ell_3 \le p \ell_2 + (1 - p) \ell_3$ , then $\ell_1 \le \ell_2$ . In particular, if $p \ell_1 + (1 - p) \ell_3 \simeq p \ell_2 + (1 - p) \ell_3$ , then $\ell_1 \simeq \ell_2$ . This will be useful later.

Another reasonable axiom is the following. Suppose $\ell_1, \ell_2, \ell_3$ are three lotteries such that $\ell_1 \le \ell_2 \le \ell_3$ . Now consider the family of lotteries $p \ell_1 + (1 - p) \ell_3$ . When $p = 0$ the agent weakly prefers this lottery to $\ell_2$ , but when $p = 1$ the agent weakly prefers $\ell_2$ to this lottery. What happens for intermediate values of $p$ ? It seems reasonable for an “intermediate value theorem” to hold here: the agent’s preferences should not jump as $p$ varies. So the following seems reasonable.

Continuity: If $\ell_1 \le \ell_2 \le \ell_3$ , then there exists some $p \in [0, 1]$ such that $\ell_2 \simeq p \ell_1 + (1 - p) \ell_3$ .

With these axioms we can now state the following foundational theorem.

Theorem (von Neumann-Morgenstern): Suppose an agent’s preferences satisfy the above axioms. Then there exists a function $U : \mathcal{O} \to \mathbb{R}$ on outcomes, the utility function of the agent, such that $\ell_1 \le \ell_2$ if and only if

$\displaystyle \sum_i p_i U(o_i) \le \sum_j q_j U(o_j)$

where $\ell_1 = \sum_i p_i o_i$ and $\ell_2 = \sum_j q_j o_j$ . The utility function $U$ is unique up to affine transformations $U \mapsto aU + b$ where $a > 0$ .

If $\ell$ is a lottery, the corresponding sum $U(\ell) = \sum_i p_i U(o_i)$ is the expected utility with respect to the lottery, so the von Neumann-Morgenstern theorem allows us to describe the goal of an agent (a VNM-rational agent) satisfying the above axioms as maximizing expected utility.

Proof. First observe that we can reduce to the case that $\mathcal{O}$ is finite. If the theorem were false in the infinite case, then for any proposed utility function $U$ we would be able to find a pair of lotteries $\ell_1, \ell_2$ such that $\ell_1 \le \ell_2$ but $U(\ell_1) > U(\ell_2)$ . But since $\ell_1, \ell_2$ in total only involve finitely many outcomes, $U$ restricts to a utility function with the same property on the finitely many outcomes involved in $\ell_1, \ell_2$ , so the theorem is false in the finite case.

Now for the proof. It is possible to take a fairly concrete but tedious approach by first constructing $U$ using continuity and then proving that $U$ satisfies the conclusions of the theorem by induction. We will instead take a more abstract approach by appealing to the hyperplane separation theorem. To start with, think of the set of lotteries as sitting inside Euclidean space $\mathbb{R}^{\mathcal{O}}$ as the probability simplex $\Delta = \{ p_i : p_i \in [0, 1], \sum p_i = 1 \}$ . Let $o_0, o_1$ be outcomes which are minimal resp. maximal in the agent’s preference ordering. For $p \in (0, 1)$ , let $o_p = p o_1 + (1 - p) o_0$ .

We would like to show that the subset

$\displaystyle U_p = \{ \ell : o_p < \ell < o_1 \}$

(of lotteries the agent strictly prefers to $o_p$ , but strictly prefers $o_1$ to) and the subset

$\displaystyle D_p = \{ \ell : o_0 < \ell < o_p \}$

(of lotteries the agent strictly prefers $o_p$ to but strictly prefers to $o_0$ ) are disjoint convex open subsets of $\mathbb{R}^{\mathcal{O}}$ . That they are disjoint follows from the definition of strict preference. That they are convex can be seen as follows: if $\ell_1 \le \ell_2$ are two lotteries such that $o_p < \ell_1, \ell_2$ , then by independence we have

$\ell_1 \cong q \ell_1 + (1 - q) \ell_1 \le q \ell_1 + (1 - q) \ell_2$

for all $q \in [0, 1]$ , hence $o_p < q \ell_1 + (1 - q) \ell_2$ for all $q \in [0, 1]$ . Applying this argument with $p = 0$ and then applying the argument with reversed inequality signs, first with general $p$ and then with $p = 1$ , gives the desired result.

Finally, that they are open can be seen as follows: let $\ell_1$ be a lottery such that $o_p < \ell_1$ . By inspection every point in an open ball around $\ell_1$ has the form $q \ell_1 + (1 - q) \ell_2$ where $\ell_2$ is some other lottery, which can be taken to be either a lottery equivalent to $o_p$ (in that the agent is indifferent between them) or a lottery such that $\ell_1 \le \ell_2$ . So it suffices by convexity to show that for any such $\ell_2$ there exists some $q \in [0, 1]$ such that $o_p < q \ell_1 + (1 - q) \ell_2$ .

In the case that $\ell_2$ can be taken to be equivalent to $o_p$ this is straightforward; by independence

$\displaystyle o_p \cong \frac{1}{2} o_p + \frac{1}{2} \ell_2 < \frac{1}{2} \ell_1 + \frac{1}{2} \ell_2$ .

In the case that $\ell_2$ can be taken to satisfy $\ell_1 \le \ell_2$ , a similar application of independence gives

$\displaystyle o_p < \ell_1 \le \frac{1}{2} \ell_1 + \frac{1}{2} \ell_2$ .

Again, applying the argument with $p = 0$ and then applying the argument with reversed inequality signs, first with general $p$ and then with $p = 1$ , gives the desired result.

Now by the hyperplane separation theorem there exists a hyperplane $H_p : \sum u_{i,p} p_i = c$ separating $U_p$ and $D_p$ , where $u_{i,p}$ are constants. These constants are in fact independent of $p$ and are (up to affine transformation, and in particular we may need to flip their signs) the utility function we seek. To see this, let $\ell_1 \le \ell_2$ be two lotteries. Then by independence $\ell_1 \le \frac{1}{2} \ell_1 + \frac{1}{2} \ell_2 \le \ell_2$ , and by continuity there is a constant $p$ such that

$\displaystyle \frac{1}{2} \ell_1 + \frac{1}{2} \ell_2 \cong (1 - p) o_0 + p o_1 = o_p$ .

If $\ell_1 \cong \ell_2$ , then $\ell_1 \cong \ell_2 \cong \frac{1}{2} \ell_1 + \frac{1}{2} \ell_2 \cong o_p$ , and the separating hyperplane $H_p$ must pass through both $\ell_1$ and $\ell_2$ (since $\ell_1, \ell_2$ are in neither $U_p$ nor $D_p$ , and the complement of their union consists of lotteries equivalent to $o_p$ ), so they have the same utility. Conversely, if a separating hyperplane passes through two lotteries then they must be equivalent to the same $o_p$ and hence must be equivalent.

Otherwise, $\ell_1 < \frac{1}{2} \ell_1 + \frac{1}{2} \ell_2 \cong o_p < \ell_2$ , and the separating hyperplane $H_p$ separates $\ell_1$ and $\ell_2$ . With the correct choice of signs, it follows that $U(\ell_1) < U(\ell_2)$ as desired. Conversely, if a separating hyperplane separates two lotteries then they cannot have the same expected utility and hence cannot be equivalent; with the correct choice of signs, if $U(\ell_1) < U(\ell_2)$ then $\ell_1 < \ell_2$ .

It remains to address the uniqueness claim. The above discussion shows that the utility function is uniquely determined by its value on $o_0$ and $o_1$ , subject to the constraint that $U(o_0) < U(o_1)$ . To fix the correct choice of signs above we may set $U(o_0) = 0, U(o_1) = 1$ ; any other choice is related to this choice by a unique positive affine linear transformation. $\Box$

But what about the paradox?

The relevance of the von Neumann-Morgenstern theorem to Newcomb’s paradox is that a particular interpretation of Newcomb’s paradox in the context of expected utility maximization supports the one-box argument. A VNM-rational agent participating in Newcomb’s paradox should be acting in order to maximize expected utility. For the purposes of recasting Newcomb’s paradox in this framework, it’s reasonable to equate utility with money; agents certainly don’t need to have the property that their utility functions are linear in money, but Newcomb’s paradox can just be restated in units of utility (utilons) rather than money.

So, it remains to determine the expected utility of the lottery that occurs if the agent takes one box and the lottery that occurs if the agent takes two boxes. Newcomb’s paradox can be interpreted as saying that in the first lottery, the box contains $1,000,000 with high probability (whatever probability the agent assigns to Omega being an accurate predictor), while in the second lottery, the two boxes together contain $1,000 with high probability. Provided that this probability is sufficiently high, which again can be absorbed into a suitable restatement of Newcomb’s paradox, it seems clear that a VNM-rational agent should take one box. (Note that stating the one-box argument in this way shows that it does not depend on Omega being a perfect predictor; Omega need only be a sufficiently good predictor, where the meaning of “sufficiently” depends on the ratio of the amounts of money in each box.)

This version of the one-box argument is therefore based on the principle of expected utility (to be distinguished from the von Neumann-Morgenstern theorem); roughly speaking, that rational agents should act so as to maximize expected utility. Relative to the definition of expected utility given above this says exactly that rational agents should be VNM-rational.

The two-box argument can also be based on a decision-making principle, namely the principle of dominance, which says the following. Suppose an agent is choosing between two options $A$ and $B$ . Say that $A$ dominates $B$ if there is a way to partition possible states of the world such that in each partition, the agent would prefer $A$ to choice $B$ . (The notion of domination does not depend on having a notion of probability distribution over world states; it requires something much weaker, namely a set of possible world states.) The principle of dominance asserts that rational agents should choose dominant options.

This seems plausible. But it also seems to be the case that taking two boxes dominates taking one box in Newcomb’s paradox:

If Omega has filled Box B with $1,000,000, then taking both boxes gives you $1,001,000 rather than $1,000,000, so it’s $1,000 better.
If Omega hasn’t filled Box B with $1,000,000, then taking both boxes gives you $1,000 rather than $0, so it’s still $1,000 better.

One situation in which the principle of dominance doesn’t make sense is if the choice between options itself affects which partition of world-states you’re in. For example, if you chose which boxes to open and then Omega chose whether to fill Box B based on your choice, then the above reasoning doesn’t seem to apply since Omega gets to choose which partition of world-states you’re in after seeing your choice between the two options. But in the setting of Newcomb’s paradox itself this doesn’t seem to be the case: Omega has already made its decision in the past, and it seems absurd to think of the agent’s decision in the present as having an effect on Omega’s past decision.

So Newcomb’s paradox appears to show that the principle of expected utility maximization and the principle of dominance are inconsistent.

Now what do you do?

Further reading

Newcomb’s paradox remains, as far as I can tell, a hotly debated topic in the philosophical literature, and in particular is considered unresolved. Campbell and Sowden’s Paradoxes of Rationality and Cooperation is a thorough, if somewhat outdated, overview of some aspects of Newcomb’s paradox and its relationship to the prisoner’s dilemma.

Posted in Uncategorized | 41 Comments

41 Responses

on May 12, 2015 at 11:06 pm | Reply MMP2

I’m a little confused.
on September 25, 2014 at 9:00 am | Reply arch1

I admit to being so seduced by the two-box choice that I am having a hard time appreciating one-box arguments. The seduction runs along these lines:
1) Everyone agrees Box A must contain $1000, so we can ditch Box A and slap the $1000 bill it contained on the table in front of me without changing the logical structure of the game, right?
2) And I must take Box B regardless, so let’s dispense with that preliminary immediately. In particular let’s assume that people I trust have taken B’s contents (if any) and deposited them into my bank account. For good measure, let’s broadcast that process on the internet, visible to everyone except me, locked in a Faraday cage staring at that $1000 bill.
..it’s still the same game, right?

Since it *is* the same game, my decision is logically the same as it always was, but freed from the distractions removed by 1) and 2) above: What it has boiled down to is simply *whether to reach out and pick up that $1000 bill*. Consistent two-boxers will presumably say Yes, consistent one-boxers No. But the correct answer is obvious: Yes! Why? Because if I pick it up, I will immediately become $1000 richer, while my bank balance is of course unchanged (as I can later verify at my leisure).

I know, a two-boxer’s true burden is to understand and refute the best one-box arguments. But while I struggle to get mentally unstuck in that regard it would be very interesting to see any attempts at directly refuting the above.
- on September 25, 2014 at 9:07 am | Reply Qiaochu Yuan
  
  Sure, but this argument completely ignores the part of the premise where Omega is predicting whether or not you reach out and pick up the $1000 and changing the contents of that Faraday cage accordingly.
  - on September 25, 2014 at 9:39 am | Reply arch1
    
    It’s true that I didn’t explicitly mention Omega. Maybe I should have added an explicit claim that the statements in the argument are all true despite the information we are given concerning Omega. (Please consider it so added:-)
- on September 25, 2014 at 1:32 pm | Reply alQpr
  
  Actually, if the game ever really gets played, the two-boxer’s true burden will be to quickly come up with a one-box argument that is sufficiently convincing to appear to Omega to have converted the player (which, according to the description of Omega’s capacities, means you actually have to believe it).
  - on September 25, 2014 at 4:18 pm | Reply arch1
    
    Well you’ve had nearly a year to self-convert and it looks as though it may still be a work in progress:-). If so, perhaps poking holes in the two-box argument above would re-energize your effort. (In any case I wouldn’t dawdle indefinitely; word is that Omega doesn’t give folks a lot of lead time).
    - on September 26, 2014 at 4:25 am | Reply alQpr
      
      I gave my reason for converting back when this first came out, and it still works for me. I don’t know if the emotion that makes it work could be programmed into a machine in a way that could be shown to provide a net positive expectation over a wide range of problems, but when Omega does come along I’ll be happy to take my million and give up a thousand for the satisfaction of properly testing her bona fides.
      
      PS What I think is wrong with your argument above is that Omega’s perfect predictive capacity means that the situation cannot be modeled by loading BoxB before you choose. I would say that a more correct model would be to first give you a limited time with BoxA and leave BoxB empty until after you have elected to forego BoxA. (After all, it is hard to predict the future but the past is often easier – except, apparently, for the case of predicting who will have been first to make this observation.)
on November 6, 2013 at 5:16 am | Reply J.P. McCarthy

Some of my own thoughts would be along these lines

From your past behaviour, Omega should be able to predict whether or not you are rational and whether you want to maximise utility or expected value. Perhaps Omega can place you on a spectrum and know at which point you will switch between the two decision rules.

If Omega has convinced you of its predictive power, then it has profiled you and has found you to be rational in the sense that you have a predictable set of decision rules. Otherwise Omega would not have been able to predict your past behaviour.

Therefore you must be rational and and there must be a point where you value utility above expected value. The values involved here are such that you are either going to maximise the utility or the expected value.

Therefore to answer this best you must know thyself. However if you ask yourself are you a one-boxer or a two-boxer you will come to a conclusion: if I am a one-boxer then I am for utility if I am a two-boxer then I am for expected value.

Case 1: If you decide to pick one box then Omega knows that you will pick one box and you will get E1,000,000.

Case 2: If you decide to pick two boxes then Omega knows you will do that too and leave Box B empty.

Therefore you might think that you should pick one box if you are for expected value. However if you have shown a willingness to switch your decision rules then Omega would not have been able to convince you of its prediction power and the problem doesn’t arise.

In conclusion, variety is the spice of life although if you go for something different you might paradoxically have less options available to you.
- on November 6, 2013 at 10:23 am | Reply Qiaochu Yuan
  
  I’m confused by this. What are you maximizing the expected value of if it’s not utility? (Remember that by the von Neumann-Morgenstern theorem, utility is by definition the thing that a VNM-rational agent maximizes the expected value of.)
  - on November 7, 2013 at 1:25 am | Reply J.P. McCarthy
    
    I have misunderstood and took the dominance principle (DP-) agent as being one who wants to maximise the expected value and sees the the possible states of the boxes being 50-50 (i.e. taking one box as an EV of 500,000 while taking two boxes as an EV of 500,500).
    
    I rewrite.
    
    From your past behaviour, Omega should be able to predict whether or not you are a rational VNM-agent or a DP-agent. If Omega has convinced you of its predictive power, then it has profiled you and has found you to be rational in the sense that you have a predictable set of decision rules. Otherwise Omega would not have been able to predict your past behaviour. Perhaps Omega can place you on a spectrum and know at which point you will switch between the two decision rules.
    
    Therefore you must be rational and and there may be a cut-off where you switch from acting as a VNM-agent to a DP-agent. In this extreme example, we are far from this cut-off and act as either VNM or DP.
    
    Therefore to answer this best you must know thyself. However if you ask yourself are you a one-boxer or a two-boxer you will come to a conclusion: if I am a one-boxer then I am VNM if I am a two-boxer then I am DP.
    
    Case 1: If you decide to pick one box then Omega knows that you will pick one box and you will get E1,000,000.
    
    Case 2: If you decide to pick two boxes then Omega knows you will do that too and leave Box B empty and you will get E1,000.
    
    Therefore you might think that you should pick one box if you are DP. However if you have shown a willingness to switch your decision rules then Omega would not have been able to convince you of its prediction power and the problem doesn’t arise.
    - on November 7, 2013 at 8:38 am | Reply Qiaochu Yuan
      
      Part of the problem is about what sort of agent you should want to be, not just what sort of agent you are.
      - on November 8, 2013 at 2:42 am | Reply J.P. McCarthy
        
        My conclusion for this example it is better to be a VNM agent so.
on October 26, 2013 at 10:49 pm | Reply dude

I did the analysis wrong in my previous post. Here’s the corrected version:

This is what I would do. I flip a biased coin that comes up with heads 0.499999999999 portion of the time. If it’s heads, I take both boxes, and otherwise I just take B.

Here’s the reasoning. I’m going to assume that Omega really is good at predicting my actions. Specifically, she knows exactly what my decision making process will be. However, I assume that I can flip coins, and I’ll assume that Omega doesn’t have any special skill at predicting the outcome of the coin flips. So my strategy can be described by some boolean function F, which when given an input representing the outcome of a bunch of coin flips, tells me if I should choose both boxes or just B. Now I assume Omega will know the function F that I am using, and I will assume that her goal will be to try to maximize the chance that she correctly predicts my choice of box(es). Since I’m using the outcomes of coin tosses, she won’t be able to predict my choice all the time, but she wants to do the best she can. Any possible F that I might select will give me a strategy of the form: “pick both boxes with probability p, and otherwise just pick B”.

Now if p>0.5, then Omega’s best prediction is that I will pick both boxes, so she won’t put the money in B. So then my expected earnings are p(1000).

On, the other hand if p<0.5, Omega will put the money in B, and my expected earnings will be (1-p)(1,000,000) + p(1,000,000 + 1,000).

If p=0.5, Omega will be right exactly 0.5 portion of the time no matter what she does. I think I'll assume that her secondary goal is to give me as little money as possible, in which case she won't put money in B. So when p=0.5, I earn (0.5)(1000)=500. So the best thing to do is choose p just slightly less than 0.5. In this way, I can get my expected earnings arbitrarily close to 1,000,500.
- on October 27, 2013 at 6:28 pm | Reply Qiaochu Yuan
  
  You’re dodging the paradox. Assume that your algorithm must be deterministic. Having access to random bits that Omega doesn’t have access to is a moral violation of the assumption that Omega is good at predicting you.
on October 26, 2013 at 10:22 pm | Reply dude

This is what I would do:
I’m going to assume that Omega really is good at predicting my actions. Specifically, she knows exactly what my decision making process will be. However, I assume that I can flip coins, and I’ll assume that Omega doesn’t have any special skill at predicting the outcome of the coin flips. So my strategy can be described by some boolean function F, which when given an input representing the outcome of a bunch of coin flips, tells me if I should choose both boxes or just B. Now I assume Omega will know the function F that I am using, and I will assume that her goal will be to try to maximize the chance that she correctly predicts my choice of box(es). Since I’m using the outcomes of coin tosses, she won’t be able to predict my choice all the time, but she wants to do the best she can. Any possible F that I might select will give me a strategy of the form: “pick both boxes with probability p, and otherwise just pick B”. Now if p>0.5, then Omega’s best strategy is to not put the money in B, since she will be correct a portion p of the time, and she can do no better than this. So then I will always get $1,000. On, the other hand if p<0.5, Omega will put the money in B, and my expected earnings will be $1,000 + p($1,000,000). If p=0.5, Omega will be right exactly 0.5 portion of the time no matter what she does. I think I'll assume that her secondary goal is to give me as little money as possible, in which she won't put money in B. So when p=0.5, I earn $1,000. So the best thing to do is choose p just slightly less than 0.5. In this way, I can get my expected earnings to be arbitrarily close to $501,000.
on October 18, 2013 at 1:21 pm | Reply Sam

I don’t see the paradox here. The two-boxer is using assumption that we haven’t made (that the future can’t affect the past). Since this assumption is clearly inconsistent with the assumption that Omega is omniscient, we can’t assume both.

Anyway that’s philosophy which I guess I’ll have to leave to the experts but I also don’t see the mathematical problem, as you yourself pointed out the dominance argument that you made here simply doesn’t apply because by hypothesis, the outcome where you take both boxes and they both have money in them doesn’t actually exist.
- on October 18, 2013 at 2:53 pm | Reply Qiaochu Yuan
  
  Omega being omniscient doesn’t require backward causality, and Omega also doesn’t need to be omniscient for the one-boxer argument to go through; the probabilistic version only requires that Omega’s accuracy is sufficiently high.
  
  The problem isn’t really mathematical. I haven’t stated Newcomb as a mathematical problem because for any given mathematical formalization of the paradox a philosopher can plausibly argue that it doesn’t capture all the features of the original problem. I mean, that’s precisely what the two-boxer is arguing when presented with the one-boxer argument I presented.
  
  Again, it seems like I haven’t made the two-boxer case persuasive enough. I’ll try to fix this in a later post!
on October 12, 2013 at 3:07 am | Reply Owen Biesel

I’m usually a one-boxer, because one-boxers get $1,000,000 more than two-boxers, but the following variant on the paradox makes the dominance argument very tempting: Omega makes its prediction, fills one or both boxes, and you are presented with the choice as usual. The twist is that the backs of the boxes are transparent, and your friends and family can all see inside. (Of course, you can’t see the boxes’ contents or your family.) Whatever the contents of the boxes, your family wants you to take both. To them, there’s no wishy-washy “what you choose now decides what Omega has predicted you will choose, and therefore what the boxes have been filled with” reasoning; to them, the money is there for the taking.

It would be kind of fun to watch: a one-boxer comes up to the boxes, which have been filled with $1,000 and nothing, rests his hand on box B as if to take only it—all those watching are willing him to take box A too or he’ll regret it—he too follows that line of reasoning and takes both. Just as Omega predicted.

—

It’s also interesting to consider a probabilistic version of Newcomb’s paradox, and see at what threshold of Omega’s inaccuracy a one-boxer would want to change her mind. Let’s say that if someone ends up taking just box B, Omega has probability p of having predicted that she would take both boxes, if someone takes both boxes, then Omega has probability q of having predicted that he would just take box B. (In particular, the better Omega is at predicting, the smaller p and q are.) Now it’s your turn: given that you take just box B, your expected reward is (1-p) * $1000000, while given that you take both boxes, your expected reward is (1-q) * $1000 + q * $1001000 = $1000 + q * $1000000. It’s still preferable (assuming “$” is your unit of utility) to one-box rather than two-box, as long as p + q is no bigger than 0.999 (or, more generally, 1 – 1/A, where A is the ratio in prize values). That means Omega could be wildly inaccurate, even guessing wrongly 49.94% of the time, and evidentiary reasoning says it still makes sense to one-box.
on October 10, 2013 at 6:27 pm | Reply alQpr » Blog Archive » Newcomb’s Paradox

[…] via Decisions, decisions | Annoying Precision. […]
on October 10, 2013 at 6:01 pm | Reply Alan Cooper

I thought I put this in yesterday but it seems not to have “taken”:

If I were told that whatever money would ever be in the boxes was already there, then I would indeed take them both (and be pretty certain of getting only $1000).

But if there is any way of convincing Omega that I will choose just B then surely I should give it a try. So here goes!

Whether I choose one box or two depends on whether and to what extent I value the experience of proving Omega wrong. It costs me only $1000 to abandon Box A. If I do that I gain either $1000000 or the experience of proving Omega wrong. If I choose both I get $1000 plus $1000000 and the experience of proving Omega wrong, or just $1000 and the uncomfortable knowledge that Omega was right. Clearly I choose just B, and if Omega has any idea at all of how I think I’ll be $1000000 richer than I am now.

Of course I must also convince Omega that I won’t change my mind, and the only way I know how to do that is to just commit firmly to not changing it and somehow forcing myself to be the kind of person who wouldn’t be tempted to risk the big prize for a relatively paltry increment.
on October 10, 2013 at 4:04 am | Reply john doe

I will do what I need to do.

Regardless of my ‘choice’ Omega knows the outcome. Therefore, I have no free will (since the outcome is predetermined). Therefore, the entire question of what I will do is meaningless. I have no choice so while I think I can choose, I really can’t.
IOW the discussion of choice is meaningless if no-free will exists. So asking me about my strategy makes no sense. It has been determined.

Another way of looking at this is a recursion of interactions between my decisions and Omega’s decisions.
I should take only Box B iff Omega put money in B. But if Omega has previously put money in B (i.e., committed) I should take both boxes. But in this case Omega will not put money in B. Thus I should take only B to cause Omega to put money in B. But if Omega puts money in B I should take both.
Obviously, this is a circular argument which does not converge. By allowing a perfect prediction and a feedback loop with the illusion to change my mind even though it has been by assumption predetermined you raise the paradox.
This paradox is simply a version of the age-old theological question about whether if god is omniscient how can free will exist. (http://en.wikipedia.org/wiki/Argument_from_free_will)
I don’t see why it has anything to do with utility.
- on October 10, 2013 at 9:56 am | Reply Qiaochu Yuan
  
  I wasn’t planning on doing this until later, but there’s a way to restate Newcomb’s paradox so it has nothing to do with free will and also so that the circularity you describe doesn’t come into play. Imagine that you and Omega are both programs. Omega has been given your source code as input, and it makes predictions by analyzing that input. As a program, you can only execute your source code, but the question is what kind of source code you should want and why (equivalently, if you were a program that could modify your own source code, what would you want to modify it to and why?).
  - on October 10, 2013 at 10:39 am | Reply john doe
    
    That is precisely the point. If you are a program that can modify your source code you have free will.
    Of course, if you have to commit to a source code before Omega sees your code it is trivially obvious to commit to just opening B. This is because you commit *before* Omega. Hence if you were to commit to taking two boxes the value is only 1000. Hence there is no dominance.
    IOW if you are a program the problem changes. In this case the problem can be stated by reversing temporality. You open the boxes and then Omega puts the money (due to the determinism of the programs). This means that if you open both boxes there will be only 1000 while if you open only B there will be 100000. There is no paradox.
  - on October 11, 2013 at 9:09 am | Reply Alan Cooper
    
    Surely I should want source code which makes me choose just Box B! (Or at least which I can be confident will look to Omega like such code)
    - on October 11, 2013 at 9:18 am | Reply Qiaochu Yuan
      
      Of course. But there are two related questions here, namely 1) how do you design a “changing-your-source-code” module so that it notices this if you didn’t notice it was a good idea to take Box B already, and 2) can you avoid changing your source code to just “take Box B” and instead write a general-purpose decision-making algorithm which generally makes good decisions and, as a special case, will take Box B?
      
      Elaborating on 1): it’s not clear a priori that a program which makes decisions one way will choose, if given the opportunity, to rewrite how it makes decisions to make decisions another way; this should feel roughly analogous to a human rewriting its own morality. It’s also not clear that, if a program decides to rewrite how it makes decisions, the process will stabilize: maybe the program writes itself into program’, which rewrites itself into program”, etc., without ever settling on a decision-making algorithm that endorses itself.
on October 10, 2013 at 2:40 am | Reply gowers

A one-boxer would object to the dominance argument by protesting that “If Omega has filled Box B with $1,000,000, then taking both boxes gives you $1,001,000 rather than $1,000,000, so it’s $1,000 better.” doesn’t make sense. If Omega is a perfect predictor, then you just won’t take two boxes in this situation.

The transitivity of preferences issue reminds me of a paradox due to Derek Parfit. He asks you to imagine various distributions of happiness that there might be in the universe. To measure this, let’s suppose that there is a zero level, at which a life is worth living, but only just, and that we can attach a numerical measure to the amount of happiness in a given life. He then asks you to consider the following options.

Option 1. Do you prefer N people at level L of happiness (where L is positive) and nobody else, or N people at level L and another N people at a level slightly below L (let’s say 9L/10)?

A plausible argument is that you should prefer the second option, especially if the two populations are isolated from each other: why deny N people a level 9L/10 of happiness? Is it really better if they don’t exist? And their existence doesn’t bother the original L people.

Option 2. Do you prefer N people at level L and N people at level 9L/10, or do you prefer 2N people at level 9999L/10000?

The argument here is that you should prefer the second option: it’s a tiny loss for the first N people and a much bigger gain for the second N people.

If you concede these two points, then by iterating the argument you can deduce that rather than having N people at level L it is better to have a vast population of people whose lives are just above the point where they are worth living. But that seems far from obvious. So we appear to have a non-transitivity.
- on October 10, 2013 at 10:12 am | Reply Qiaochu Yuan
  
  Yes, there’s an interesting issue involving how the two-boxer is taking counterfactuals that I hope to address later.
  
  Parfit’s repugnant conclusion comes about more generally from total utilitarianism, which I’m happy to reject on the grounds of complexity of value. There are other terrible problems with naive forms of total utilitarianism, e.g. they suggest creating large numbers of people and wireheading them.
- on October 10, 2013 at 11:10 am | Reply john doe
  
  > A plausible argument is that you should prefer the second option, \
  > especially if the two populations are isolated from each other: why deny N
  > people a level 9L/10 of happiness? Is it really better if they don’t exist? And
  > their existence doesn’t bother the original L people.
  
  If people do not exist, I see no reason why one should have any preference for creating them in order for them to have happiness. Life is for the living 🙂
  Your statement of a minimal level of happiness in which a life is worth living only makes sense for those living. I personally, do not recall having a preference for live before being conceived. In fact, it is perfectly possible that “But the person who hasn’t been born yet is better off than both of them. He hasn’t seen the evil that is done under the sun.”
  - on October 10, 2013 at 11:14 am | Reply john doe
    
    Or for a book length study of the problem: “Better Never to Have Been: The Harm of Coming into Existence” (David Benatar)
    
    http://www.amazon.com/Better-Never-Have-Been-Existence/dp/0199549265?ie=UTF8&s=books&qid=1220468652&sr=1-1
on October 9, 2013 at 11:58 pm | Reply rittwik

If the probability that omega predicts me what I will do in the future is “sufficiently” high then I will choose only box B and I will choose Box A otherwise. This is expected utility maximization argument.

What an agent will do depends on what her objective. So, if the objective of the agent is to maximize her expected utility then she will choose a box according to the argument given above.

So, I don’t understand what is the paradox. Perhaps before asking “What do you do?” one should state what is my objective when I am doing something.
on October 9, 2013 at 5:04 pm | Reply sflammia

This is a really interesting post. I find the two-box argument to be lacking for additional reasons to the ones you mention. While Omega might be incapable of influencing the past through present decisions, this does not preclude the possibility of affecting the outcome. Omega and Player 1 are essentially engaging in a commitment scheme, where Omega commits to putting the money in the box and Player commits to a box choice. If Omega is indeed as powerful as possible (but still bound by the laws of physics, which I will grant as seems to be consistent with the reasoning of the two-boxers), then I would worry about Omega playing a quantum mechanical strategy. In particular, Lo & Chau and Mayers have shown that quantum bit commitment is impossible because Omega can use an entangled quantum state and delay commitment. Thus, the claims of the two-boxers are suspect on physical grounds, which seemed a priori to be the main selling point of their argument.

Also, any complete discussion would have to weigh the rather small marginal gain of of taking box A against the risk of getting a much smaller payout. That is, maximizing expected utility is find, but it should be weighted by some kind of variance. Presumably this more obvious point is discussed in detail in the literature, though.
- on October 9, 2013 at 5:08 pm | Reply Qiaochu Yuan
  
  I don’t think it’s necessary to bring in quantum mechanics. Newcomb’s paradox is already problematic to me in a completely classical universe.
  
  The whole point of the von Neumann-Morgenstern theorem is that a VNM-rational agent doesn’t need to take into account the variance of utility; by definition utility is the thing that you only need to worry about the expected value of. The reason decision-makers care about variance in practice is because the things they care about the variance of contribute nonlinearly to their utility. For example, if your utility function is quadratic in money then you need to worry about the expected utility and the variance of money. Humans probably have more complicated utility functions than this but it’s plausible to speculate that for humans the marginal utility of money is very high if you don’t have much of it but gets lower once you have more.
  
  (On the other hand, a more realistic model of decision-making should take into account uncertainty in the agent’s assessment of the utility of various outcomes, and depending on how you swing you might not want to subsume this entirely into your uncertainty about the world. At the most basic level all I’m saying is that you should distinguish the claim “someone told me this outcome has utility U” from the claim “this outcome has utility U.”)
  - on October 9, 2013 at 5:24 pm | Reply sflammia
    
    I don’t really understand what you mean by “problematic” in your response.
    
    I hadn’t appreciated that utility is the thing that linearizes all of your considerations. That actually clarifies a lot of statements that I’ve seen over the years which always looked over simplified to me.
    - on October 9, 2013 at 10:00 pm | Reply Qiaochu Yuan
      
      I mean before you start worrying about quantum Newcomb it seems to me like there’s already plenty to worry about in classical Newcomb.
      - on October 10, 2013 at 1:05 am | Reply sflammia
        
        I see. What I took away from your post, by contrast, was that there were two principles that one might use for decision making, dominance and expected utility, and that these two principles lead to different strategies. Then you seemed to point out that the dominance principle leads to some not necessarily justifiable assumptions about “partition of world-states”. While this doesn’t necessarily imply that the dominance principle is wrong, it certainly takes some of the initial tension out of the paradox, because it isn’t clear how to fix the reasoning. So I came away from your post being less worried about the paradox!
        
        on October 10, 2013 at 9:52 am | Reply Qiaochu Yuan
        
        Hmm. In that case, I didn’t do a good enough job making dominance sound convincing. I’ll try to fix that in a future post.
        
        on December 3, 2013 at 10:13 pm | Reply Jonathan D
        
        I understood sflammia to be saying that quantum mechanics makes the dominance argument less convincing, and hence there’s less to worry about in the paradox. That would mean that to make dominance more convincing you would need to address or reject the quantum argument, rather than say there are enough problems without it.
        
        With or without quantum mechanics, I’d like to see the more convincing explanation, because at the moment I’m having trouble seeing the two box approach as anything other than simply rejecting the claim of omniscience. I mean this in the sense that whether or not it is absurd to say my choice affects Omega’s past decision, the claim which we are by assumption convinced of is certainly that they are not independent. (I’m also not sure that a positive record of predicting my actions should sway me at all regarding this claim unless the successful predictions were also in situations where those actions involved relying on a claim on omniscience.)
        
        on December 4, 2013 at 1:00 pm | Reply Qiaochu Yuan
        
        The reason I think quantum mechanics is a distraction is that the underlying issues here should be relatively independent of the details of the laws of physics (provided only that backwards causation is ruled out) – we can imagine all this taking place in an arbitrary virtual environment where programs interact with each other in arbitrary ways.
        
        Some philosophers agree that two-boxing does not cause you to win the game that Omega is playing, so in that sense they aren’t rejecting omniscience, but they insist that 1) two-boxing is still the rational decision and 2) it’s not their fault that Omega is rewarding irrational behavior. More generally, whatever you think it means for an agent to have a rational decision-making algorithm, you might imagine that Omega decides to go around the universe giving millions of utilons only to agents who don’t have rational decision-making algorithms, and the fact that Omega is doing this shouldn’t change your notion of rationality.
on October 9, 2013 at 3:35 pm | Reply Alan Cooper

I originally made the two box argument, based on the idea that whatever Omega had done was done and couldn’t be retroactively adjusted, but I haven’t actually been told that its method doesn’t involve monitoring my thought processes right to the end and only placing the money when it is sure that it knows what I will do (which apparently according to recent studies may well be somewhat before I know myself). If I were told that whatever money would ever be in the boxes was already there, then I would indeed take them both (and be pretty certain of getting only $1000).

But if there is any way of convincing Omega that I will choose just B then surely I should give it a try. So here goes!

Whether I choose one box or two depends on whether and to what extent I value the experience of proving Omega wrong. It costs me only $1000 to abandon Box A. If I do that I gain either $1000000 or the experience of proving Omega wrong. If I choose both I get $1000 plus $1000000 and the experience of proving Omega wrong, or just $1000 and the uncomfortable knowledge that Omega was right. Clearly I choose just B, and if Omega has any idea at all of how I think I’ll be $1000000 richer than I am now.

Of course I must also convince Omega that I won’t change my mind and the only way I know how to do that is to just commit firmly to not changing it and somehow forcing myself to be the kind of person who wouldn’t be tempted to risk the big prize for a relatively paltry increment. (It would be interesting to see how my response there might depend on the relative sizes of the amounts in the two boxes)
on October 9, 2013 at 2:12 pm | Reply Keshav Kini (@ffee_machine)

Typo in the definition of continuity – should be $\ell_3$ rather than $\ell_2$ at the end.
- on October 9, 2013 at 3:07 pm | Reply Qiaochu Yuan
  
  So it should. Thanks for the correction!

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos