Timeless Decision Theory: Problems I Can't Solve

There does not appear to be any such thing as a dominant majority vote.

Eliezer, are you aware that there's an academic field studying issues like this? It's called Social Choice Theory, and happens to be covered in chapter 4 of Hervé Moulin's Fair Division and Collective Welfare, which I recommended in my post about Cooperative Game Theory.

I know you're probably approaching this problem from a different angle, but it should still be helpful to read what other researchers have written about it.

A separate comment I want to make is that if you want others to help you solve problems in "timeless decision theory", you really need to publish the results you've got already. What you're doing now is like if Einstein had asked people to help him predict the temperature of black holes before having published the general theory of relativity.

As far as needing a long sequence, are you assuming that the reader has no background in decision theory? What if you just write to an audience of professional decision theorists, or someone who has at least read "The Foundations of Causal Decision Theory" or the equivalent?

Unfortunately this "timeless decision theory" would require a long sequence to write up, and it's not my current highest writing priority unless someone offers to let me do a PhD thesis on it.

• But it is the writeup most-frequently requested of you, and also, I think, the thing you have done that you refer to the most often.

• Nobody's going to offer. You have to ask them.

In case you're wondering, I'm writing this up because one of the SIAI Summer Project people asked if there was any Friendly AI problem that could be modularized and handed off and potentially written up afterward, and the answer to this is almost always "No"

Does it mean that the problem isn't reduced enough to reasonably modularize? It would be nice if you written up the outline of state of research at SIAI (even a brief one with unexplained labels) or an explanation of why you won't.

Hanson's example of ten people dividing the pie seems to hinge on arbitrarily passive actors who get to accept and make propositions instead of being able to solicit other deals or make counter proposals, and it is also contingent on infinite and costless bargaining time. The bargaining time bit may be a fair (if unrealistic) assumption, but the passivity does not make sense. It really depends on the kind of commitments and bargains players are able to make and enforce, and the degree/order of proposals from outgroup and ingroup members.

When the first two defectors say, "Hey, you each get an eighth if you join us," the four could pick another two of the in-crowd and say, "Hey, they offered us Y apiece, but we'll join you instead if you each give us X, Y<X (which is actually profitable to the other four so long as X < 1/4 - they get cut out entirely if they can't bargain)." No matter how it is divided, there will always be a subgroup in the in-crowd that could profitably bargain with the out-crowd, and there will always be a different subgroup in the in-crowd that will be able to make a better offer. So long as there is an out-crowd, there are people who can bargain profitably, and so longer as the in-crowd is > 6, people can be profitably removed.

If bargaining time is finite (or especially if it has non-zero cost), I suspect, but can't prove (for lack of effort/technical proficiency, not saying it's unprovable) that each actor will opt for the even 10-person split (especially if risk-averse) because it is (statistically) equivalent (or superior) to the sum*probability of other potential arrangements.

Here's a comment that took me way too long to formulate:

On the Prisoner's Dilemma in particular, this infinite regress can be cut short by expecting that the other agent is doing symmetrical reasoning on a symmetrical problem and will come to a symmetrical conclusion...

Eliezer, if such reasoning from symmetry is allowed, then we sure don't need your "TDT" to solve the PD!

Is Parfit's Hitchhiker essentially the same as Kavka's toxin, or is there some substantial difference between the two I'm missing?

For example, there's a problem introduced to me by Gary Drescher's marvelous Good and Real (OOPS: The below formulation was independently invented by Vladimir Nesov

For a moment I was wondering how the Optimally Ordered Problem Solver was relevant.

Is your majority vote problem related to Condorcet's paradox? It smells so, but I can't put a handle on why.

I cheated the PD infinite regress problem with a quine trick in Re-formalizing PD. The asymmetric case seems to be hard because fair division of utility is hard, not because quining is hard. Given a division procedure that everyone accepts as fair, the quine trick seems to solve the asymmetric case just as well.

Post your "timeless decision theory" already. If it's correct, it shouldn't be that complex. With your intelligence you can always write a PhD on some other AI topic should the opportunity arise. But after conversations with Vladimir Nesov I was kinda under the impression that you could solve the asymmetric PD-like cases too; if not, I'm a little disappointed in advance. :-(

"I believe X to be like me" => "whatever I decide, X will decide also" seems tenuous without some proof of likeness that is beyond any guarantee possible in humans.

I can accept your analysis in the context of actors who have irrevocably committed to some mechanically predictable decision rule, which, along with perfect information on all the causal inputs to the rule, gives me perfect predictions of their behavior, but I'm not sure such an actor could ever trust its understanding of an actual human.

Maybe you could aspire to such determinism in a proven-correct software system running on proven-robust hardware.

As a first off-the-cuff thought, the infinite regress of conditionality sounds suspiciously close to general recursion. Do you have any guarantee that a fully general theory that gives a decision wouldn't be equivalent to a Halting Oracle?

ETA: If you don't have such a guarantee, I would submit that the first priority should be either securing one, or proving isomorphism to the Entscheidungsproblem and, thus, the impossibility of the fully general solution.

If I were forced to pay $100 upon losing, I'd have a net gain of $4950 each time I play the game, on average. Transitioning from this into the game as it currently stands, I've merely been given an additional option. As a rationalist, I should not regret being one [? · GW]. Even knowing I won't get the $10,000, as the coin came up heads, I'm basically paying $100 for the other quantum me to receive $10,000. As the other quantum me, who saw the coin come up tails, my desire to have had the first quantum me pay $100 outweighs the other quantum me's desire to not lose $100. I'm not going to defect against myself for want of $100, and if you (general you, not eliezer specifically) would you should probably carry a weapon and a means of defending yourself against it because you can't trust yourself.

Unfortunately this "timeless decision theory" would require a long sequence to write up, and it's not my current highest writing priority unless someone offers to let me do a PhD thesis on it.

Can someone tell me the matrix of pay-offs for taking on Eleizer as a PhD student?

I swear I'll give you a PhD if you write the thesis. On fancy paper and everything.

Would timeless decision theory handle negotiation with your future self? For example if a timeless decision agent likes paperclips today but you knows it is going to be modified to like apples tomorrow, (and not care a bit about paperclips,) will it abstain from destroying the apple orchard, and its future self abstain from destroying the paperclips in exchange?

And is negotiation the right way to think about reconciling the difference between what I now want and what a predicted smarter, grown up, more knowledgeable version of me would want? or am I going the wrong way?

But I don't have a general theory which replies "Yes" [to a counterfactual mugging].

You don't? I was sure you'd handled this case with Timeless Decision Theory.

I will try to write up a sketch of my idea, which involves using a Markov State Machine to represent world states that transition into one another. Then you distinguish evidence about the structure of the MSM, from evidence of your historical path through the MSM. And the best decision to make in a world state is defined as the decision which is part of a policy that maximizes expected utility for the whole MSM.

OK, I just tried for four hours but couldn't successfully describe a useful formalism that provides a good analysis of counterfactual mugging. Will keep trying later.

Here's a crack at the coin problem.

Firstly TDT seems to answer correctly under one condition, if P(some agent will use my choice as evidence about how I am going to act in these situations and make this offer.) = 0. Then certainly, our AI shouldn't give omega any money. On the other hand, if P(some agent will use my choice as evidence about how I am going to act in these situations and make this offer.) = 0.5, then the expected utility =-100 + 0.5 ( 0.5 (1,000,000) + 0.5(-100)) So my general solution is this, add a node that represents the probability of repeating one of these trials, keep track of its value like any other node, carefully and gradually. Giving money would only be winning if you had the opportunity to make more money later because omega or someone else knows you give money, otherwise you shouldn't give money.

I THINK I SOLVED ONE - EDIT - Sorry, not quite.

"Suppose Omega (the same superagent from Newcomb's Problem, who is known to be honest about how it poses these sorts of dilemmas) comes to you and says: "I just flipped a fair coin. I decided, before I flipped the coin, that if it came up heads, I would ask you for $1000. And if it came up tails, I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads. The coin came up heads - can I have $1000?" Obviously, the only reflectively consistent answer in this case is "Yes - here's the $1000", because if you're an agent who expects to encounter many problems like this in the future, you will self-modify to be the sort of agent who answers "Yes" to this sort of question - just like with Newcomb's Problem or Parfit's Hitchhiker."

To me, this seems like losing. I disagree that a reflectively consistent agent would give Omega money in these instances.

Since Omega always tells the truth, we should program ourselves to give him $1000 if and only if we don't know that the coin came up heads. If we know that the coin came up heads, it no longer makes sense to give him $1000 dollars.

This in no way prevents us from maximizing utility. An opponent of this strategy would contend that this prevents us from receiving the larger cash prize. That assertion would be false, because this strategy only occurs in situations where we have literally zero possibility of receiving any money from Omega. "Not giving Omega $1000" in instance H does not mean that we wouldn't give Omega $1000 in instances where we don't know whether or not H.

The fact that Omega has already told us it came up heads completely precludes any possibility of a reward. The fact that we choose to not give Omega money in situations where we know the coin comes up heads in no way precludes us from giving him $1000 in scenarios where we have a chance that we'll receive the larger cash prize. By not giving $1000 when H, there is still no precedent set which precludes the larger reward. Therefore we should give Omega $1000 if and only if we do not know that the coin landed on heads.

Yay. That seems too easy, I'm kind of worried I made a super obvious logical mistake. But I think it's right.

Sorry for not using the quote feature, but I'm awful at editing. I even tried using the sandbox and couldn't get it right.

EDIT: So, unfortunately, I don't think this solves the issue. It technically does, but it really amounts to more of a reason that Omega is stupid and should rephrase his statements. Instead of Omega saying "I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads" he should say "I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads and I told you that the coin came up heads".

So it's a minor improvement but it's nothing really important.

Suppose Omega (the same superagent from Newcomb's Problem, who is known to be honest about how it poses these sorts of dilemmas) comes to you and says:

"I just flipped a fair coin. I decided, before I flipped the coin, that if it came up heads, I would ask you for $1000. And if it came up tails, I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads. The coin came up heads - can I have $1000?"

Obviously, the only reflectively consistent answer in this case is "Yes - here's the $1000", because if you're an agent who expects to encounter many problems like this in the future, you will self-modify to be the sort of agent who answers "Yes" to this sort of question - just like with Newcomb's Problem or Parfit's Hitchhiker.

Compute the probabilities P(0)..P(n) that this deal will be offered to you again n times in the future. Sum over 499500 P(n) (n) for all n and agree to pay if the sum is greater than 1,000.

Another stumper was presented to me by Robin Hanson at an OBLW meetup. Suppose you have ten ideal game-theoretic selfish agents and a pie to be divided by majority vote. Let's say that six of them form a coalition and decide to vote to divide the pie among themselves, one-sixth each. But then two of them think, "Hey, this leaves four agents out in the cold. We'll get together with those four agents and offer them to divide half the pie among the four of them, leaving one quarter apiece for the two of us. We get a larger share than one-sixth that way, and they get a larger share than zero, so it's an improvement from the perspectives of all six of us - they should take the deal." And those six then form a new coalition and redivide the pie. Then another two of the agents think: "The two of us are getting one-eighth apiece, while four other agents are getting zero - we should form a coalition with them, and by majority vote, give each of us one-sixth."

How I would approach this problem:

Suppose that it is easier to adjust the proportions within your existing coalitions than to switch coalitions. An agent will not consider switching coalitions until it cannot improve its share in its present coalition. Therefore, any coalition will reach a stable configuration before you need consider agents switching to another coalition. If you can show that the only stable configuration is an equal division, then there will be no coalition-switching.

You can probably show that any agent receiving less than its share can receive a larger share by switching to a different coalition. Assume the other agents know this proof. You may then be able to show that they can hold onto a larger share by giving that agent its fair share than by letting it quit the coalition. You may need to use derivatives to do this. Or not.

"I just flipped a fair coin. I decided, before I flipped the coin, that if it came up heads, I would ask you for $1000. And if it came up tails, I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads. The coin came up heads - can I have $1000?"

Err... pardon my noobishness but I am failing to see the game here. This is mostly me working it out audibly.

A less Omega version of this game involves flipping a coin, getting $100 on tails, losing $1 on heads. Using humans, it makes sense to have an arbiter holding $100 from the Flipper and $1 from the Guesser. With this setup, the Guesser should always play.

If the Flipper is Omega and offered the same game with the same fair arbiter there is no reason to not play. If Omega was a perfect predictor and knew what the coin would do before flipping it, should we play? If Omega commits to playing the game regardless of the prediction, yes, we should play.

If the arbiter is removed and Omega stands in as the arbiter, we should still play because it is assumed that Omega is honest and will pay out if tails appears. Even if we prepay before the coin flip, we should still play.

If the Flipper flips the coin before we prepay the arbiter, it should not matter. This is equivalent to the scenario of Omega being a perfect predictor.

The only two changes remaining are:

• Us knowing the coin flip before we agree to play
• Us not paying before we see the coin flip

The latter assumes we could renege on payment after seeing the coin but I highly doubt Omega would play the game with someone like this since this would be known to a perfect predictor. This means we can completely eliminate the arbiter.

This leaves us at the following scenario:

I just flipped a fair coin. I decided, before I flipped the coin, that if it came up heads, I would ask you for $1000. And if it came up tails, I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads. I know the result of the coin but will wait for you to agree to the game before I tell you what it is. Do you want to play?

The answer is "Yes." Why does it matter if Omega blurts out the answer beforehand? Because we know we will "lose"?

In my opinion this is a trivial problem. If we assume that Omega is (a) fair and (b) accurate we would always play the game. Omega is predefined to not take advantage of us. We just got unlucky, which is perfectly acceptable as long as we do not know the answer beforehand.

So... what am I missing? It seems like there is mental warning when imagining myself before Omega and handing him $1000 when I "never had a shot". But I did have a shot. I would never pay anyone other than Omega, but I am assuming Omega is being completely honest.

Why would anyone answer "No"? The basic answer, "Because you do not want to lose $1000" seems completely irrational to me. I can see why it would appear rational, but Omega's definition makes it irrational.

If the ten pie-sharers is to be more than a theoretical puzzle, but something with applicability to real decision problems, then certain expansions of the problem suggest themselves. For example, some of the players might conspire to forcibly exclude the others entirely. And then a subset of the conspirators do the same.

This is the plot of "For a Few Dollars More".

How do criminals arrange these matters in real life?

Is this equivalent to the modified Newcomb's problem?

Omega looks at my code and produces a perfect copy of me which it puts in a separate room. One of us (decided by the toss of a coin if you like) is told, "if you put $1000 in the box, I will give $1000000 to your clone."

Once Omega tells us this, we know that putting $1000 in the box won't get us anything, but if we are the sort of person who puts $1000 in the box then we would have gotten $1000000 if we were the other clone.

What happens now if Omega is able to change my utility function? Maybe I am a paperclipper, but my copy has been modified so that every instance of "paperclip" in its decision calculus has been replaced by "paperweight" (or more precisely, the copy is what would have happened if my entire history had been modified by replacing paperclips by paperweights). Omega then offers one of the copies of me, chosen randomly, the choice between producing 1000 paperclips (resp. paperweights) and 1000000 paperweights (resp. paperclips). This seems like just as reasonable a question, if changing an agent's utility function makes sense. But now suppose I remove the randomness, and just always give the paperweighter the choice between making 1000 paperweights and 1000000 paperclips. Now I can't find a reasonable argument for making the paperclips.

"Now of course you wish you could answer "Yes", but as an ideal game theorist yourself, you realize that, once you actually reach town, you'll have no further motive to pay off the driver."

Can't you contract your way out of this one?

Obviously, the only reflectively consistent answer in this case is "Yes - here's the $1000", because if you're an agent who expects to encounter many problems like this in the future, you will self- modify to be the sort of agent who answers "Yes" to this sort of question - just like with Newcomb's Problem or Parfit's Hitchhiker.

But I don't have a general theory which replies "Yes".

If you think being a rational agent includes an infinite ability to modify oneself, then the game has no solution because such an agent would be unable to guarantee the new trait's continued, unmodified existence without sacrificing the rationality that is a premise of the game.

So, for the game to be solvable, the self-modification ability must have limits, and the limits appear as parameters in the formalism.

"I can predict that if (the other agent predicts) I choose strategy X, then the other agent will implement strategy Y, and my expected payoff is Z"

...are we allowed to use self-reference?

"I just flipped a fair coin. I decided, before I flipped the coin, that if it came up heads, I would ask you for $1000. And if it came up tails, I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads. The coin came up heads - can I have $1000?"

X = "if the other agent is trustworthy (implicitly: I can trust that the other agent analyzed past-me sufficiently to know that I always use strategy X) then I agree to the bet.

Z = whatever the expected payoff of the bet was before the flip.

In effect, I only agree to a counterfactual bet if :

I know that you are aware that I've pre-committed to taking bets with those who are aware that I've pre-committed to taking bets with those who are aware I've pre-committed to taking bets with those who are aware ...

Youmight find some recent work on the iterated prisoner's dilemma interesting.

In an undergraduate seminar on game theory I attended, it was mentioned in an answer to a question posed to the presenter that, when computing a payoff matrix, the headings in the rows and columns aren't individual actions, but are rather entire strategies; in other words it's as if you pretty much decide what you do in all circumstances at the beginning of the game. This is because when evaluating strategies nobody cares when you decide, so might as well act as if you had them all planned out in advance. So in that spirit, I'm going to use the following principle:

An Agent should chose the strategy that it predicts gives the greatest outcome, weighted by probability of that outcome etcetc...

to approach every one of these problems.

On Omega's coin flip: Omega has given you the function you have to apply to your strategy, you just apply it, and the result's bigger if you answer "yes". Although, realistically, there's no way that Omega has provided nearly enough information for you to trust him, but whatever, that's the premise.

On Parfit's hitchhiker: Again, Ekman has access to your strategy. Just pick one that does benefit him, since those are the only ones that have you not dying at the outcome. If you don't have 100$, find something else you could give him.

On the Democratic Pie: Well, your problem has no strong Nash equilibrium. No solution is going to be stable. I don't really know how this works when you have more than two players, (undergraduate, remember) but I suggest looking into not using a pure strategy. If each voter votes randomly, but choses the probability of his votes appropriately, things work out a little better. You can then compute which semi-random strategy gets you the highest expected size of your slice, etcetc.... Find a book, I don't know how this works. (If I wanted to solve this problem on my own, I would trying to do it with 8 coconuts first, rather than a Continuum of cake.) (This also spells Doom for the AIs respecting whatever Constitution is given then. Not just Doom, Somewhat Unpredictable Doom.)

On the Prisoner's Dilema's Infinite Regress: I don't know.

For the coin came up tails give me 1000 please case does it reduce to this?

"I can predict that if (the other agent predicts) I choose strategy X: for any gamble I'd want to enter if the consequences were not already determined, I will pay when i lose, then the other agent will implement strategy Y: letting me play, and my expected payoff is Z:999,000",

"I just flipped a fair coin. I decided, before I flipped the coin, that if it came up heads, I would ask you for $1000. And if it came up tails, I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads. The coin came up heads - can I have $1000?" Obviously, the only reflectively consistent answer in this case is "Yes - here's the $1000", because if you're an agent who expects to encounter many problems like this in the future, you will self-modify to be the sort of agent who answers "Yes" to this sort of question - just like with Newcomb's Problem or Parfit's Hitchhiker."

I think more generally if there's any possibility that you'll encounter anything like this in the future you should precommit to paying up. Precommiting to paying up acts as an entry cost for positive utility gambles.

And it would definetely have to be utility rather than, say, money because rich enemies could bankrupt you if you were willing to take 51;49 bets of all your stakes vs some of theirs. This might be trivial but for a second I wasn't sure if this would make you more open to exploitation than if you would take that potential bankruptcy risk anyway.

Though I'm not sure provisioning for this kind of thing would be a good idea. Who's going to do this kind of thing anyway instead of just setting forth the terms of the bet. When are you going to know, as is stipulated here that there was a decent chance of you getting anything and they haven't just somehow tricked you. A simple solution might just be to refuse this kind of thing altogether, and then people who want to bet with you will have to ask in advance. I can't think of any scenario where someone would have a legitimate reason to bet like this rather than normally.

Suppose you have ten ideal game-theoretic selfish agents and a pie to be divided by majority vote....

...Every majority coalition and division of the pie, is dominated by another majority coalition in which each agent of the new majority gets more pie. There does not appear to be any such thing as a dominant majority vote.

I suggest offering the following deal at the outset:

"I offer each of you the opportunity to lobby for an open spot in a coalition with me, to split the pie equally six ways, formed with a mutual promise that we will not defect, and if any coalition members do defect, we agree to exclude them from future dealings and remain together as a voting bloc, offering the defectors' spots to the remaining agents not originally aligned with us, for a 1/6 + epsilon share, the cost of the excess portion divided among those of us remaining. I will award spots in this coalition to the five of you who are most successful at convincing me you will adhere to these terms."

Here's yet another problem whose proper formulation I'm still not sure of, and it runs as follows. First, consider the Prisoner's Dilemma. Informally, two timeless decision agents with common knowledge of the other's timeless decision agency, but no way to communicate or make binding commitments, will both Cooperate because they know that the other agent is in a similar epistemic state, running a similar decision algorithm, and will end up doing the same thing that they themselves do. In general, on the True Prisoner's Dilemma, facing an opponent who can accurately predict your own decisions, you want to cooperate only if the other agent will cooperate if and only if they predict that you will cooperate. And the other agent is reasoning similarly: They want to cooperate only if you will cooperate if and only if you accurately predict that they will cooperate.

But there's actually an infinite regress here which is being glossed over - you won't cooperate just because you predict that they will cooperate, you will only cooperate if you predict they will cooperate if and only if you cooperate. So the other agent needs to cooperate if they predict that you will cooperate if you predict that they will cooperate... (...only if they predict that you will cooperate, etcetera).

On the Prisoner's Dilemma in particular, this infinite regress can be cut short by expecting that the other agent is doing symmetrical reasoning on a symmetrical problem and will come to a symmetrical conclusion, so that you can expect their action to be the symmetrical analogue of your own - in which case (C, C) is preferable to (D, D). But what if you're facing a more general decision problem, with many agents having asymmetrical choices, and everyone wants to have their decisions depend on how they predict that other agents' decisions depend on their own predicted decisions? Is there a general way of resolving the regress?

Yes. You can condition on two prior probabilities: that an agent will successfully predict your actual action, and that an agent will respond in a particular way based on the action they predict you to take. For the solution in the case of the Truly Iterated Prisoner's Dilemma, see here.

(EDIT, 6/18/2011:

On further consideration, my assertion -- that the indicated solution to the Prisoner's Dilemma constitutes a general method for resolving infinite regress in the full class of problems specified -- is a naive oversimplification. The indicated solution to a specific dilemma is suggestive of an area of solution space to search for the general solution or solutions to specific similar problems, but considerable work remains to be done before a general solution to the problem class can be justifiably claimed. I'll analyze the full problem further and see what I come up with.)

I'm curious as to what extend is Timeless Decision Theory compared to this proposal: by Arntzenius http://uspfiloanalitica.googlegroups.com/web/No+regrets+%28Arntzenius%29.pdf?gda=0NZxMVIAAABcaixQLRmTdJ3- x5P8Pt_4Hkp7WOGi_UK-R218IYNjsD-841aBU4P0EA-DnPgAJsNWGgOFCWv8fj8kNZ7_xJRIVeLt2muIgCMmECKmxvZ2j4IeqPHHCwbz-gobneSjMyE

Agents A & B are two TDT agents playing some prisoner's dilemma scenario. A can reason:

u(c(A)) = P(c(B))u(C,C) + P(d(B))u(C,D)

u(d(A)) = P(c(B))u(D,C) + P(d(B))u(D,D)

( u(X) is utility of X, P() is probability, c() & d() are cooperate & defect predicates )

A will always pick the option with higher utility, so it reasons B will do the same:

p(c(B) u'(c(B)) > u'(d(B)) --> c(B)

(u'() is A's estimate of B's utility function)

But A can't perfectly predict B (even though it may be quite good at it), so A can represent this uncertainty as a random variable e:

u'(c(B)) + e > u'(d(B)) - e --> c(B)

In fact, we can give e a parameter, N, which is given by the depth of recursion, like a game of telephone:

u'(c(B)) + e(N) > u'(d(B)) - e(N) --> c(B)

Intuitively, it seems e(N) will tend to overwhelm u() for high enough N (since utilities don't increase as you recurse.) At that recursion depth:

p(c(B)) = p(d(B))

so:

u(c(A)) = u(C,C) +u(C,D)

u(d(A)) = u(D,C) + u(D,D)

u(D,C) > u(C,C) > u(D,D) > u(C,D)

so u(d(A)) > u(c(A)), meaning defection at the recursive depth where uncertainty overwhelms other considerations.

Does this mean a TDT agent must revert to CDT if it is not smart enough (or does not believe its opponent is smart enough) to transform the recursion to a closed-form solution?

I think I have a general theory that gives the "correct" answer to Omega problem here and Newcomb's problem.

The theory depends on the assumption that Omega makes his prediction by evaluating the decision of an accurate simulation of you (or does something computationally equivalent, which should be the same). In this case there are two of you, real-you and simulation-you. Since you are identical to your simulation the two of you can reasonably be assumed to share an identity and thus have common goals (presumably that real-you gets the money because simulation-you will likely not exist once the simulation ends). Additionally since it is an accurate simulation you have no way to tell whether you are real-you or simulation-you. So in the problem here:

• There's a 50% chance that you are really the simulation, in which case handing over the $1000 has a 50% chance of earning real-you $1000000, and a 50% chance of doing nothing.

• There's a 50% chance that you are actually real-you, in which case giving Omega $1000 has a 100% chance of loosing $1000.

So giving Omega the money nets real-you an expected $249000.

On the other hand, this might just say that you should put off deciding for as long as possible so that if you are the simulation you don't cease to exist when the simulation ends.

Anyway, this also handles Newcomb's problem similarly. Unfortunately it seems to me to be a little too silly to be a real decision theory.

My first thought on the coalition scenario is that the solution might hinge on something as simple as the agents deciding to avoid a stable equilibrium that does not terminate in anyone ending up with pie.

Edit: this seems to already have been discussed at length. That'll teach me to reply to year old threads without an adequate perusal of the preexisting comments.

"I just flipped a fair coin. I decided, before I flipped the coin, that if it came up heads, I would ask you for $1000. And if it came up tails, I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads. The coin came up heads - can I have $1000?"

Obviously, the only reflectively consistent answer in this case is "Yes - here's the $1000", because if you're an agent who expects to encounter many problems like this in the future, you will self-modify to be the sort of agent who answers "Yes" to this sort of question - just like with Newcomb's Problem or Parfit's Hitchhiker.

Why would I expect that, the next time I encounter an Omega, it will say, "I would give you $1,000,000 if and only if I predicted that you would give me $1000 if the coin had come up heads", instead of, "I would give you $1,000,000 if and only if I predicted that you would not give me $1000 if the coin had come up heads" ?

I don't really wanna rock the boat here, but in the words of one of my professors, it "needs more math".

I predict it will go somewhat like this: you specify the problem in terms of A implies B, etc; you find out there's infinite recursion; you prove that the solution doesn't exist. Reductio ad absurdum anyone?

Instead of assuming that other will behave as a function of our choice, we look at the rest of the universe (including other sentient being, including Omega) as a system where our own code is part of the data.

Given a prior on physics, there is a well defined code that maximizes our expected utility.

That code wins. It one boxes, it pays Omega when the coin falls on heads etc.

I think this solves the infinite regress problem, albeit in a very unpractical way,

If you're an AI, you do not have to (and shouldn't) pay the first $1000, you can just self-modify to pay $1000 in all the following coin flips (if we assume that the AI can easily rewrite/modify it's own behaviour in this way). Human brains probably don't have this capability, so I guess paying $1000 even in the first game makes sense.

I had a look at the existing literature. It seems as though the idea of a "rational agent" who takes one box goes quite a way back:

"Rationality, Dispositions, and the Newcomb Paradox" (Philosophical Studies, volume 88, number 1, October 1997)

Abstract: "In this article I point out two important ambiguities in the paradox. [...] I draw an analogy to Parfit's hitchhiker example which explains why some people are tempted to claim that taking only one box is rational. I go on to claim that although the ideal strategy is to adopt a necessitating disposition to take only one box, it is never rational to choose only one box. [...] I conclude that the rational action for a player in the Newcomb Paradox is taking both boxes, but that rational agents will usually take only one box because they have rationally adopted the disposition to do so."

• http://www.mtholyoke.edu/~ebarnes/publish.htm

Why can't Omega's coin toss game not be expressed formally simply by using expected values?

n = expected further encounters of Omega's coin toss game

EV(Yes) = -1000 + (.5 n -1000) + (.5 n 1000000)

EV(No) = 0

On dividing the pie, I ran across this in an introduction to game theory class. I think the instructor wanted us to figure out that there's a regress and see how we dealt with it. Different groups did different things, but two members of my group wanted to be nice and not cut anyone out, so our collective behavior was not particularly rational. "It's not about being nice! It's about getting the points!" I kept saying, but at the time the group was about 16 (and so was I), and had varying math backgrounds, and some were less interested in that aspect of the game.

I think at least one group realized there would always be a way to undermine the coalitions that assembled, and cut everyone in equally.

Actually here's my argument why (ignoring the simulation arguments) you should actually refuse to give Omega money.

Here's what actually happened:

Omega flipped a fair coin. If it comes up heads the stated conversation happened. If it comes up tails and Omega predicts that you would have given him $1000, he steals $1000000 from you.

If you have a policy of paying you earn 10^6/4 - 10^3/4 -10^6/2 = -$250250. If you have a policy of not paying you get 0.

More realistically having a policy of paying Omega in such a situation could earn or lose you money if people interact with you based on a prediction of your policy, but there is no reason to suspect one over the other.

There's a similar problem with the Prisoner's Dilemma solution. If you formalize it as two of you are in a Prisoner's Dilemma and can see each other's code, then modifying your code to cooperate against the mirror matchup helps you in the mirror matchup, but hurts you if you are playing against a program that cooperates unless you would cooperate in a mirror matchup. Unless you have a reason to suspect that running into one is more likely than running into the other, you can't tell which would work better.

At the point where Omega asks me this question, I already know that the coin came up heads, so I already know I'm not going to get the million. It seems like I want to decide "as if" I don't know whether the coin came up heads or tails, and then implement that decision even if I know the coin came up heads. But I don't have a good formal way of talking about how my decision in one state of knowledge has to be determined by the decision I would make if I occupied a different epistemic state, conditioning using the probability previously possessed by events I have since learned the outcome of...

Well, it seems to me that you always want to do this. According to timeless-reflectively-consistent-yada-yada decision theory, the best decision to make is to follow the strategy that you would have chosen at the very beginning.

The precise constraint this problem places on you is that the context you make your decision in is that there is a 50% chance that your decision results in you getting $1,000,000 instead of nothing.

Treat your observations as putting you in the context in which you make your decision.

I stopped reading at "Yes, you say". The correct solution is obviously obvious: you give him your credit card and promise to tell the PIN number once you're at the ATM.

You could also try to knock him off his bike.

"Suppose you have ten ideal game-theoretic selfish agents and a pie to be divided by majority vote. "

Well then, the statistical expected (average) share any agent is going to get long-term is 1/10th of the pie. The simplest solution that ensures this is the equal division; anticipating this from the start cuts down on negotiation costs, and if a majority agrees to follow this strategy (i.e agrees to not realize more than their "share"), it is also stable - anyone who ponders upsetting it risks to be the "odd man out" who eats the loss of an unsymmetric strategy.

In practice (i.e. in real life) there are other situations that are relatively stable, i.e. after a few rounds of "outsiders" bidding low to get in, there might be two powerful "insiders" who get large shares in liaison with four smaller insiders who agree to a very small share because it is better than nothing; the best the insiders can do then is to offer the four outsiders small shares also, so that each small-share individual wil be faced with the choice of cooperating and receiving a small share, or not cooperating and receiving nothing. Whether the two insiders can pull this off will depend on how they frame the problem, and how they present themselves ("we are the stabilizers that ensure that "social justice" is done and nobody has to starve").

How you can get an AI to understand setups like this (and if it wants to move past the singularity, it probably will have to) seems to be quite a problem; to recognize that statistically, it can realize no more than 1/10th, and to push for the simplest solution that ensures this seems far easier (and yet some commentators seem to think that this solution of "cutting everyone in" is somehow "inferior" as a strategy - puny humans ;-).