I wasn’t trying to criticize it—I think it’s a great heuristic and I think it touches on a very fundamental, non-obvious aspect of reality. I just want to better understand what kind of exception AMD and your game are.
For example, in cases where you don’t want to “improve” something for someone, randomness is, in a sense, good. For example, when hiding messages from an adversary, adding randomness is good—though only because it’s bad for someone else. This is consistent with the anti-randomness heuristic.
I phrased it one time as, “Randomness is like poison: yes, it can help you, but only if someone else takes it.”
It seems like there’s some word-trickery going on here. A randomized algorithm is just a deterministic algorithm plus a source of randomness, but the randomness source isn’t counted as an “input” but instead “part of the algorithm”. AMD is a situation where you want two copies of the same algorithm with the same inputs to have a different output, which is impossible. Using a “randomized” algorithm allows you to sneak around this limitation by giving each copy a possibly different input without calling it an input.
I wasn’t trying to criticize it—I think it’s a great heuristic and I think it touches on a very fundamental, non-obvious aspect of reality. I just want to better understand what kind of exception AMD and your game are.
The short version is this: Adding randomness is only useful when you are trying to obfuscate. Otherwise, adding randomness per se is always bad or neutral. However, many cases that are described as “adding randomness” are really about adding some information that turns out to be just what the agent needs, plus some randomness that turns out not to do any harm.
For example, in the AMD problem, the optimal strategy is often described as “exit with probability 1/3rd”. Now, what this really means is the following: The agent is given an input channel C, together with the knowledge that the input from C will belong to a set S such that some known set T contains 1/3rd of the elements of S (but no additional information). The agent then implements the deterministic algorithm of exiting iff the input from C belongs to the set T.
People often explain why this agent is able to do better than an agent without a “mixed” strategy by saying, “This agent has a source of randomness.” But I think that it’s better to say that the agent has an input channel about which it knows something, but not everything. In contrast, the agent employing a “non-mixed” strategy doesn’t have this information about the channel. So, naturally, the agent with the “mixed” strategy does better, because it knows more.
Thanks. I had forgotten that a clearer resolution of those heuristics had eventually been offered as that thread developed, and I appreciate you summarizing it here.
See my comments there too: I think that’s the only time I’ll ever outwit Aaronson on computer science (if only because he kept cheating by chaning the question).
Edit: Okay, that may be overstating; let’s just say that’s the best I’ll probably ever do against him on comp-sci.
I wasn’t trying to criticize it—I think it’s a great heuristic and I think it touches on a very fundamental, non-obvious aspect of reality. I just want to better understand what kind of exception AMD and your game are.
For example, in cases where you don’t want to “improve” something for someone, randomness is, in a sense, good. For example, when hiding messages from an adversary, adding randomness is good—though only because it’s bad for someone else. This is consistent with the anti-randomness heuristic.
I phrased it one time as, “Randomness is like poison: yes, it can help you, but only if someone else takes it.”
It seems like there’s some word-trickery going on here. A randomized algorithm is just a deterministic algorithm plus a source of randomness, but the randomness source isn’t counted as an “input” but instead “part of the algorithm”. AMD is a situation where you want two copies of the same algorithm with the same inputs to have a different output, which is impossible. Using a “randomized” algorithm allows you to sneak around this limitation by giving each copy a possibly different input without calling it an input.
Good point, but how is that a case of word-trickery, and what would you call this category of exception to the anti-randomness heuristic?
Here’s an old comment thread where I tried to explain how I think about this.
The short version is this: Adding randomness is only useful when you are trying to obfuscate. Otherwise, adding randomness per se is always bad or neutral. However, many cases that are described as “adding randomness” are really about adding some information that turns out to be just what the agent needs, plus some randomness that turns out not to do any harm.
For example, in the AMD problem, the optimal strategy is often described as “exit with probability 1/3rd”. Now, what this really means is the following: The agent is given an input channel C, together with the knowledge that the input from C will belong to a set S such that some known set T contains 1/3rd of the elements of S (but no additional information). The agent then implements the deterministic algorithm of exiting iff the input from C belongs to the set T.
People often explain why this agent is able to do better than an agent without a “mixed” strategy by saying, “This agent has a source of randomness.” But I think that it’s better to say that the agent has an input channel about which it knows something, but not everything. In contrast, the agent employing a “non-mixed” strategy doesn’t have this information about the channel. So, naturally, the agent with the “mixed” strategy does better, because it knows more.
Thanks. I had forgotten that a clearer resolution of those heuristics had eventually been offered as that thread developed, and I appreciate you summarizing it here.
For onlookers: also see this old thread, especially Scott Aaronson’s comments.
See my comments there too: I think that’s the only time I’ll ever outwit Aaronson on computer science (if only because he kept cheating by chaning the question).
Edit: Okay, that may be overstating; let’s just say that’s the best I’ll probably ever do against him on comp-sci.