Allowing Exploitability in Game Theory

by Liam Goddard1 min read17th May 20204 comments

2

Game TheoryRationalityWorld OptimizationAIWorld Modeling
Frontpage

(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?

2

4 comments, sorted by Highlighting new comments since Today at 7:17 AM
New Comment

If Tim tells the truth with probability $p$, you simply get that you should guess what he said if $p<\frac{1}{1000000}$, and $p>\frac{1}{1000000}$. For Tim the optimal choice is to have $p=\frac{1}{1000000}$ in order not to give you any information: Anything else is playing on psychology and human biases, which exist in reality but trying to play a "perfect" game by assuming your opponent is not also leaves you vulnerable to exploitability, as you mentioned.

It seems you are trying to get a deeper understanding of human fallibility rather than playing optimal games. Have I misunderstood it?

Your equations didn't render.

Optimality goes out the window when you throw psychology into the mix. If you know your opponent is better than you at this game, you absolutely should just randomize and take your $0 average payout (or choose not to play, if money is less than linear utility to you). If you know your opponent is foolish or really innumerate (like doesn't understand probabilities, and thinks 302 is a "big enough" number to fool you, pick 302 or 301 (depending on your best read of your opponent). Remember, the only reason to randomize, rather than picking the single number you assign highest chance to, is to prevent your opponent from adjusting, which doesn't matter in a one-shot. If this repeated or your opponent knows you before this, you could assign higher weight to 302, near 302, and very far from 302.

I used to hang with (and still am Facebook-acquaintances with many) a gambling group (mostly +ev focused - poker, some sports and horse betting, +EV video poker, rarely some blackjack (opportunities had mostly dried up by then, though we did have some ex-MIT-team members), and a bunch of fun-but-negative games). For a few years in the late 90s, I participated in $100 buy-in single-elimination roshambo tournaments, as well as settling a LOT of bar bills and other small contests by rock-scissors-paper. It became the STANDARD opening statement for the defender to accept a challenge of "shall we roshambo for it?" with "OK, I'm going Rock". The Simpsons reference "good old rock, nothing beats rock" was optional. As was ACTUALLY throwing rock, though it was much more frequent than 1/3, because winning with a declared throw came with extra bragging rights. And because we all knew this, scissors was second-most-common after declaring rock - recurse as deep as you like. The common exclamation on losing was "Damn! I was thinking TWO LEVELS (or 5 or 29 or 101 or any 3N+2) above you".

In any case, even for a stranger, you have a lot of information just from the circumstances of the game, his or her mannerisms, etc. If you think you have enough information to pick a distribution other than "equally likely for all numbers equally likely", you've got an edge. Also, for a million-to-one payout, I'd have to consider that the chance of being cheated is not insignificant either, and my edge would have to be higher than that, which is unlikely.

This is related to https://www.lesswrong.com/posts/RzvEs2fj8kFwezXNi/how-to-avoid-schelling-points . The main difference being your example is adversarial - the stranger wants to trick you (probably - the chance that it's an altruist or just a bad player is in scope). But it doesn't matter - once you have an anchor, the distribution is no longer flat.

A paradox is a sign of an inconsistency.

It's pretty clear that it isn't rational for Tim to tell you his real number.

Assuming Tim is trying to win.