What you need to avoid the mugging is that P(more than X years of fun iff I pay up | deal for X years offered) goes to zero faster than log(X) grows
No.
In order to avoid the mugging you need just that
P(more than X years of fun iff I pay up | deal for X years offered) (log(X) - MarginalU($5)) < P(Y years of fun iff I pay up | deal for X years offered) (log(Y) - MarginalU($5))
where Y is the number of years of fun you will get anyway if the mugger gives you nothing (assuming, for simplicity, that the mugger either gives you X or more years of fun or gives you nothing, but the argument can be generalized to scenarios where the mugger may give you Z < X years of fun)
the number of bits in the program "offer n^^^n years of fun, and grant this iff subject pays up" grows only linearly with n
That seems incorrect.
I think that the source of your confusion stems from the fact that the program length of the (shortest) program "write n^^^n on the tape" is K(n^^^n) <= log_2(n) .
But the length of programs consistent with "offer n^^^n years of fun, and grant this iff subject pays up" must grow faster than K(n^^^n).
Proof by reductio ad absurdum:
Suppose that length of the shortest program A(n^^^n) = "offer n^^^n years of fun, and grant this iff subject pays up" grows with K(n^^^n).
Then, up to some additive constant, Len(A(n^^^n)) is the length of the concatenation of two shortest programs:
W(n^^^n) = "write n^^^n on the tape" and
B = "read X from the tape, offer X years of fun, and grant this iff subject pays up"
where Len(W(n^^^n)) = K(n^^^n) and Len(B) is a constant independent of n^^^n.
Consider the posterior:
post = p(grant this iff subject pays up | offer n^^^n years of fun) = p("offer n^^^n years of fun, and grant this iff subject pays up") / p("offer n^^^n years of fun")
Define the shortest program O(n^^^n) = "offer n^^^n years of fun".
Again, if Len(O(n^^^n)) grows with K(n^^^n), then up to some additive constant Len(O(n^^^n)) is the length of the concatenation of W(n^^^n) and program C = "read X from the tape, offer X years of fun" which doesn't depend on n^^^n.
That is,
Len(A(n^^^n)) = K(n^^^n) + Len(B)
Len(O(n^^^n)) = K(n^^^n) + Len(C)
Therefore
post =~= 2^-(Len(A(n^^^n)) - Len(O(n^^^n))) =
= 2^-((K(n^^^n) + Len(B)) - (K(n^^^n) + Len(C))) =
= 2^-(Len(B) - Len(C))
As you can see this posterior doesn't depend on n^^^n or even on n, which is clearly inconsistent with the notion (formalized in a theorem by Solomonoff) that Solomonoff induction learns an accurate model of the environment.
Therefore, the assumption that there is a shortest program consistent with "offer n^^^n years of fun, and grant this iff subject pays up" whose length grows with K(n^^^n) must be incorrect.
What you need to avoid the mugging is that P(more than X years of fun iff I pay up | deal for X years offered) goes to zero faster than log(X) grows
No.
Okay, you're saying that as X goes up, the probability of getting X years of fun even if you don't pay up also goes up, because any program that offers a deal of X years has to include a specification of the number X? So the expected utility of not paying up doesn't stay constant as we vary X, but increases with X (at least asymptotically, for very large X)?
Well, you're right on that, and that's in fac...
Followup to: Pascal's Mugging: Tiny probabilities of vast utilities; The Lifespan Dilemma
This is Pascal's Mugging: Someone comes to you and says, "Give me five dollars, and I'll use my powers from outside the matrix to grant you 4^^^^4 years of fun." And they're lying, of course, but under a Solomonoff prior, the probability that they're not, though surely very small, isn't going to be less than one in 3^^^3; and so if you shut up and multiply, it's clear that the expected utility of paying up outweighs the expected utility of anything sensible you might be doing with those five dollars, and therefore—
Well, fortunately, if you're afraid that your utility-maximizing AI will end up paying all its money to the first clever mugger to come along and ask: never to worry! It will do so only if it can't think of anything better to do with five dollars, after all. So to avoid being mugged, all it has to do is to think of a harebrained scheme for spending $5 that has more than a one-in-4^^^4 chance of providing 5^^^^5 years of fun. Problem solved.
If, however, you would like to be there be a chance greater than one-in-hell that your AI ends up doing something actually useful, you'll need to do something else. And the simplest answer is to adopt a bounded utility function: any positive singularity gives at least 50 utils, a billion years gives 80 utils, a googol years gives 99 utils, a googolplex years gives 99.9 utils, and 4^^^^4 years of fun give 100 utils (minus epsilon).
This will, indeed, solve the problem. Probability of getting mugged: used to be one (minus epsilon, of course); has now been brought down to zero. That's right: zero.
(Plus epsilon.)
But let's suppose that the impossible happens, and the universe turns out to be able to support TREE(100) years of fun, and we've already lived out 4^^^^4 of them, and the AI has long since folded up operations and faded out of existence because humanity has become sufficiently sane that we no longer need it—
And lo, someone comes to you and says, "Alas, you're not really experiencing 4^^^^4 years of fun here; you're really a mere billion-year-old living in a very convincing simulation. Give me five dollars, and I'll use my powers from outside the matrix to extend your lifespan to a googol years."
And they're lying, of course — but it has been a long time indeed since you last faced a choice that could make a difference of nineteen whole utils...
*
If you truly have a bounded utility function, you must agree that in this situation, paying up is exactly what you'd want to do. Even though it means that you will not experience 4^^^^4 years of fun, even conditional on the universe being capable of supporting TREE(100) of them.
[ETA: To clarify, by "4^^^^4", I really mean any number so large that your utility function assigns (100 - epsilon) utils to it. It's possible to have a utility function where this is only true for infinite numbers which are so incredibly infinite that, given a particular formal language, their definition is so long and complicated that no mere human-sized mind could comprehend it. See this comment thread for discussion of bounded utility functions that assign significant weight to very large lifetimes.]