While raking, I think I finally thought of a proof that the before-offer-probability can’t be known.
The question is basically ‘what fraction of all Turing machines making an offer (which is accepted) will then output a certain result?’
We could rewrite this as ’what is the probability that a random Turing machine will output a certain result?
We could then devise a rewriting of all those Turing machines into Turing machines that halt or not when their offer is accepted (eg. halting might = delivering, not halting = welshing on the deal. This is like Rice’s theorem).
Now we are asking ‘what fraction of all these Turing machines will halt?’
However, this is asking ‘what is Chaitin’s constant for this rewritten set of Turing machines?’ and that is uncomputable!
Since Turing machine-based agents are a subset of all agents that might try to employ Pascal’s Mugging (even if we won’t grant that agents must be Turing machines), the probability is at least partially uncomputable. A decision procedure which entails uncomputability is unacceptable, so we reject giving the probability in advance, and so our probability must be contingent on the offer’s details (like its payoff).
I think Nesov is right, you’ve basically (re)discovered that the universal prior is uncomputable and thought that this result is related to Pascal’s Mugging because you made the discovery while thinking about Pascal’s Mugging. Pascal’s Mugging seems to be more about the utility function having to be bounded in some way.
You might be interested in this thread, where I talked about how a computable decision process might be able to use an uncomputable prior:
It seems to be an argument against possibility of making any decision, and hence not a valid argument about this particular decision. Under the same assumptions, you could in principle formalize any situation in this way. (The problem boils down to uncomputability of universal prior itself.)
Besides, not making the decision is not an option, so you have to fall down to some default decision when you don’t know how to choose, but where does this default come from?
I take it as an argument against making perfect decisions. If perfection is uncomputable, then any computable agent is not perfect in some way.
The question is what imperfection do we want our agent to have? This might be the deep justification for choosing to scale probability by utility that I was looking for. Scaling linearly corresponds to being willing to lose a fixed amount to mugging, scaling superlinearly correspond to not willing to lose any genuine offer, scaling sublinearly corresponds to not being willing to ever be fooled. Or something like that. The details need some work.
In order to make a decision, we do not always need an exact probability: sometimes just knowing that a probability is less than, say, 0.5 is enough to determine the correct decision. So, even though an exact probability p may be incomputable, that doesn’t mean that the truth value of the statement “p<0.1” can not be computed (for some particular case). And that computation may be all we need.
That said, I’m not sure exactly how to interpret “A decision procedure which entails uncomputability is unacceptable.” Unacceptable to whom? Do decision procedures have to be deterministic? To be algorithms? To be recursive? To be guaranteed to terminate in a finite time. To be guaranteed to terminate in a bounded time? To be guaranteed to terminate by the deadline for making a decision?
In order to make a decision, we do not always need an exact probability: sometimes just knowing that a probability is less than, say, 0.5 is enough to determine the correct decision.
Alright, so you compute away and determine that the upper bound on Chaitin’s constant for your needed formalism is 0.01. The mugger than multiplies his offering by 100, and proceeds to mug you, no? (After all, you don’t know that the right probability isn’t 0.01 and actually some smaller number.)
That said, I’m not sure exactly how to interpret “A decision procedure which entails uncomputability is unacceptable.”
This is pretty intuitive to me—a decision procedure which cannot be computed cannot make decisions, and a decision procedure which cannot make decisions cannot do anything. I mean, do you have any reason to think that the optimal, correct, decision theory is uncomputable?
I have no idea whether we are even talking about the same problem. (Probably not, since my thinking did not arise from raking). But you do seem to be suggesting that the multiplication by 100 does not alter the upper bound on the probability. As I read the wiki article on “Pascal’s Mugging”, Robin Hanson suggests that it does. Assuming, of course, that by “his offering” you mean the amount of disutility he threatens. And the multiplication by 100 does also affect the number (in this example 0.01) which I need to know whether p is less than. Which strikes me as the real point.
This whole subject seems bizarre to me. Are we assuming that this mugger has Omega-like psy powers? Why? If not, how does my upper bound calculation and its timing have an effect on his “offer”? I seem to have walked into the middle of a conversation with no way from the context to guess what went before.
While raking, I think I finally thought of a proof that the before-offer-probability can’t be known.
The question is basically ‘what fraction of all Turing machines making an offer (which is accepted) will then output a certain result?’
We could rewrite this as ’what is the probability that a random Turing machine will output a certain result?
We could then devise a rewriting of all those Turing machines into Turing machines that halt or not when their offer is accepted (eg. halting might = delivering, not halting = welshing on the deal. This is like Rice’s theorem).
Now we are asking ‘what fraction of all these Turing machines will halt?’
However, this is asking ‘what is Chaitin’s constant for this rewritten set of Turing machines?’ and that is uncomputable!
Since Turing machine-based agents are a subset of all agents that might try to employ Pascal’s Mugging (even if we won’t grant that agents must be Turing machines), the probability is at least partially uncomputable. A decision procedure which entails uncomputability is unacceptable, so we reject giving the probability in advance, and so our probability must be contingent on the offer’s details (like its payoff).
Thoughts?
I think Nesov is right, you’ve basically (re)discovered that the universal prior is uncomputable and thought that this result is related to Pascal’s Mugging because you made the discovery while thinking about Pascal’s Mugging. Pascal’s Mugging seems to be more about the utility function having to be bounded in some way.
You might be interested in this thread, where I talked about how a computable decision process might be able to use an uncomputable prior:
http://groups.google.com/group/one-logic/browse_frm/thread/b499a90ef9e5fd84/2193ca2c204a55d8?#2193ca2c204a55d8
It seems to be an argument against possibility of making any decision, and hence not a valid argument about this particular decision. Under the same assumptions, you could in principle formalize any situation in this way. (The problem boils down to uncomputability of universal prior itself.)
Besides, not making the decision is not an option, so you have to fall down to some default decision when you don’t know how to choose, but where does this default come from?
I take it as an argument against making perfect decisions. If perfection is uncomputable, then any computable agent is not perfect in some way.
The question is what imperfection do we want our agent to have? This might be the deep justification for choosing to scale probability by utility that I was looking for. Scaling linearly corresponds to being willing to lose a fixed amount to mugging, scaling superlinearly correspond to not willing to lose any genuine offer, scaling sublinearly corresponds to not being willing to ever be fooled. Or something like that. The details need some work.
In order to make a decision, we do not always need an exact probability: sometimes just knowing that a probability is less than, say, 0.5 is enough to determine the correct decision. So, even though an exact probability p may be incomputable, that doesn’t mean that the truth value of the statement “p<0.1” can not be computed (for some particular case). And that computation may be all we need.
That said, I’m not sure exactly how to interpret “A decision procedure which entails uncomputability is unacceptable.” Unacceptable to whom? Do decision procedures have to be deterministic? To be algorithms? To be recursive? To be guaranteed to terminate in a finite time. To be guaranteed to terminate in a bounded time? To be guaranteed to terminate by the deadline for making a decision?
Alright, so you compute away and determine that the upper bound on Chaitin’s constant for your needed formalism is 0.01. The mugger than multiplies his offering by 100, and proceeds to mug you, no? (After all, you don’t know that the right probability isn’t 0.01 and actually some smaller number.)
This is pretty intuitive to me—a decision procedure which cannot be computed cannot make decisions, and a decision procedure which cannot make decisions cannot do anything. I mean, do you have any reason to think that the optimal, correct, decision theory is uncomputable?
I have no idea whether we are even talking about the same problem. (Probably not, since my thinking did not arise from raking). But you do seem to be suggesting that the multiplication by 100 does not alter the upper bound on the probability. As I read the wiki article on “Pascal’s Mugging”, Robin Hanson suggests that it does. Assuming, of course, that by “his offering” you mean the amount of disutility he threatens. And the multiplication by 100 does also affect the number (in this example 0.01) which I need to know whether p is less than. Which strikes me as the real point.
This whole subject seems bizarre to me. Are we assuming that this mugger has Omega-like psy powers? Why? If not, how does my upper bound calculation and its timing have an effect on his “offer”? I seem to have walked into the middle of a conversation with no way from the context to guess what went before.