There’s a certain type of problem where it appears that having more computing power hurts you. That problem is the “agent simulates predictor” Newcomb’s Dilemma.
As Gary Drescher put it:
There’s a version of Newcomb’s Problem that poses the same sort of challenge to UDT that comes up in some multiagent/gametheoretic scenarios.
Suppose:
 The predictor does not run a detailed simulation of the agent, but relies instead on a highlevel understanding of the agent’s decision theory and computational power.
 The agent runs UDT, and has the ability to fully simulate the predictor.
Since the agent can deduce (by lowlevel simulation) what the predictor will do, the agent does not regard the prediction outcome as contingent on the agent’s computation. Instead, either predictonebox or predicttwobox has a probability of 1 (since one or the other of those is deducible), and a probability of 1 remains the same regardless of what we condition on. The agent will then calculate greater utility for twoboxing than for oneboxing.
Meanwhile, the predictor, knowing that the the agent runs UDT and will fully simulate the predictor, can reason as in the preceding paragraph, and thus deduce that the agent will twobox. So the large box is left empty and the agent twoboxes (and the agent’s detailed simulation of the predictor correctly shows the predictor correctly predicting twoboxing).
The agent would be better off, though, running a different decision theory that does not twobox here, and that the predictor can deduce does not twobox.
EDITED 5/19/15: There’s a formal model of this due to Vladimir Slepnev where the agent and the predictor both have different types of predictive powers, such that in some sense they each know how the other will act in this universe. We’ll write this out along with another case where things work out properly.
(One algorithm has more computing power, but the other has stronger axioms: in particular, strong enough to prove that the other formal system is sound, as ZFC proves that PA is sound.)
In one of the following cases, proofbased UDT oneboxes for correct reasons; in the other case, it twoboxes analogously to the reasoning above.
In both cases, we’ll use the following lemma:
Lemma: Let \(A()\) be an algorithm that returns either 1 or 2, such that ZFC has a proof of length \(\approx \log(N)\) of “\(A()\) returns in \(\leq N\) steps”. Then ZFC has a proof of length \(\approx \log(N)\) that “\(A()=1\) if and only if PA proves that \(A()=1\).”
Proof: ZFC knows that PA is sound, so ZFC has a short proof that “if PA proves that \(A()=1\), then \(A()=1\)”. The other direction follows from the fact that the algorithm is bounded, and PA can simply show the execution trace of \(A\) in \(\leq CN\) steps.
Case 1: Success (Agent Trusts Predictor)
Omega looks through all proofs in PA; when it finds a proof that the agent oneboxes or a proof that the agent twoboxes, it stops looking and fills or empties the box accordingly. (If it fails to prove either, it empties the box.)
The agent looks several times through all proofs in ZFC of length \(\leq N\); it first looks for a proof that one of its actions leads to the payoff $1001000, then $1000000, then $1000, then $0. The first time it finds a proof that an action implies the outcome it’s looking for, it immediately takes that action. (If it fails to find any such proof, it twoboxes.)
I claim that for sufficiently large \(N\), the agent oneboxes, and Omega fills the box.
Proof: We use the Lemma. ZFC proves in \(\leq N\) steps that \(A()=1 \leftrightarrow \Box_{PA}[A()=1]\). Since we (from outside the problem) assume ZFC is consistent, it will not be able to prove that twoboxing gets it $1001000, nor that oneboxing gets it $1001000, nor that twoboxing gets it $1000000, but it will be able to prove that oneboxing gets it $1000000. Thus it oneboxes. Since it runs in finite time, of course PA proves it oneboxes, and so Omega fills the box.
Case 2: Failure (Agent Simulates Predictor)
We’ll swap the deductive processes this time. Omega looks through all proofs in ZFC of length \(\leq N\); when it finds a proof that the agent oneboxes or a proof that the agent twoboxes, it stops looking and fills or empties the box accordingly. (If it fails to prove either, it empties the box.)
The agent looks several times through all proofs in PA; it first looks for a proof that one of its actions leads to the payoff $1001000, then $1000000, then $1000, then $0. The first time it finds a proof that an action implies the outcome it’s looking for, it immediately takes that action. (If it fails to find any such proof, it twoboxes.)
I claim that the agent twoboxes, and Omega leaves the box empty.
Proof: Again, by the lemma, ZFC proves that \(\Omega()=1 \leftrightarrow \Box_{PA}[\Omega()=1]\) (where \(\Omega()=1\) means “Omega predicts oneboxing and thus fills the box”). Now note that \(\Omega()=1\) implies that PA proves \(A()=2 \to U=\$1001000\) and does not prove that \(A()=1 \to U=\$1001000\), and thus in this case \(A()=2\); and similarly, \(\Omega()=2\) implies that PA proves \(A()=2 \to U=\$1000\) and does not prove any of the prior counterfactuals, so again \(A()=2\). All of these proofs are quick within ZFC, so \(\Omega\) does prove that \(A()=2\), and thus \(\Omega()=2\).
