(If you haven't read it yet, Introduction to Game Theory might be a useful prerequisite.)
You're playing a game against a complete stranger (let's call him Tim.) Tim writes down a number from 1 to 1,000,000. Then you try to guess his number. If you get it right, he gives you $1,000,000. If you get it wrong, you give him $1.
Tim has written down his number already, and you're about to write down your guess, when he tells you, "My number is 302." You have no additional information about whether he's telling the truth. Take a minute to think about what you would do.
It's pretty clear that it isn't rational for Tim to tell you his real number. The prior probability of Tim losing is quite low, but this gives you additional evidence, and you're a lot more likely to guess it. So you assume Tim's probably not telling the truth.
But Tim is not perfectly rational. It's possible he's trying to use some failed form of reverse psychology. Or maybe he's taken a promise to always be radically honest. Or maybe he meant to write down 302 and tell you it was 547, but he got confused and thought he had written down 547 and was telling you 302. You still think he's probably lying, but you estimate a probability of 1/500, summing over all possibilities, that he's telling the truth. (This number is probably not accurate, the important thing is that it's much more than 1/1,000,000.)
So you do an expected utility calculation. If you guess a number other than 302, your chances of being right are slightly under 1/1,000,000. If you guess 302, you have a 1/500 chance of being right. Clearly, you should guess 302...
Except that this isn't a Nash Equilibrium- it's incredibly easy to exploit. If Tim guesses beforehand that you'll guess any number he tells you, he can get a guaranteed win every time just by writing down 506,849 and telling you it's 302.
In this case, it still seems like it's worth it. What does it matter if Tim can often win? You're still going to be ahead in average money gained. But it gets more complicated if Tim knows a bit more about you.
Suppose that now Tim has complete knowledge of your source code, and can predict what you'll do. You would have just used an online random number generator, if he had said nothing, but he tells you, "My number is 302." What do you do now?
While the chance that he'll tell the truth has dropped, there are still enough idiots in the world that it's more than 1/1,000,000. The expected utility calculation, at least according to classical decision theory, still says to guess 302. But on the other hand, Tim knows this. If you change your mind based on something he says, he can always find a way to trick you into losing. So should you just stick with your original plan, and generate a random number?
What is the best possible procedure you can use to make your decision, given that Tim is fully aware of this procedure?
At the moment, I'm still leaning towards guessing 302, but it seems intuitively like there's probably something better. Does anyone else have any other ideas that might outperform this?