Saturday, January 26, 2008

But I know that he knows that I know

When two people in America need to make a boolean decision and a coin isn't available, the go-to method of problem resolution is probably Rock, Paper, Scissors.

Generally people feel this game is fair, meaning there's an equal likelihood of each participant winning, losing, or tying. And of course if you're an academic who believes Big-Oh embodies everything you need to know about algorithms, you might leave it at that.

But we real geeks can never leave things at that. And I don't (just) mean playing Bear, Ninja, Cowboy:

Cowboy beats bear, bear beats ninja, ninja beats cowboy. The theory behind this is that cowboys can shoot bears but are not fast enough to prevent a ninja from assassinating them, but a bear's acute sense of smell prevents the ninja from gaining the element of surprise, thus allowing the bear to maul him. --Wikipedia

The UK-based Telegraph tells us there's a strategy that wins more often than 1/3 of the time:

Research [from the New Scientist] shows that stone, also called rock, is the most popular of the three possible moves in the game.

That means that your opponent is likely to choose paper, because they will expect to you to start the game with stone.

By going with scissors, you achieve an early victory.

But hold on. If rock is the most popular move, going with scissors means you would be defeated. But here it says you'll win. Which is it?

It depends on what your opponent knows. Let's first assume that neither player knows anything about the statistics or analysis of RPS. (Yeah, RPS is not only an accepted acronym, there are even RPS tournaments. Wowzies.) A and B are innocent players, but we want to give A an advantage.

The new study says that, unbeknownst to the players, rock is the most popular move. That means ignorant B will throw more rock than average, so A can win by throwing more paper against it. So we should whisper into A's ear that he should throw more paper.

But what if B has read about this new study? His "beknownst" state has flipped to true. Then we expect B to favor paper, so in this case we should instruct A to favor scissors.

Ah but it gets worse, as it often does with these things. What if B knows that A knows that B read the study? Then B will figure out that A will favor scissors, and will start favoring rock again. Double-fake!

But you see what's coming next. If A knows all of this, A can double-fake too. And so on.

So where does all this leave us? That, at least in regard to this study, he with the most information wins. There's probably a life lesson in there somewhere.

Another life lesson is to always keep digging. Like, this isn't even over yet. One strategy is to call out what you're going to throw, and then actually throw it. The theory is that the other person generally won't believe you. Why is this an advantage? Let's take a concrete example.

A says, "I'm going to throw rock." Let's go with the theory that B doesn't believe it. So B thinks A will throw paper or scissors. If B throws rock, he figures 50% chance to win, 50% chance to lose. If B throws paper, it's 50% to tie, 50% to lose, so that's no good. If B throws scissors, it's 50% to win, 50% to tie. Add it up: B's best move (under his assumption) is scissors, and second-best is rock.

Since A will actually throw rock according to this strategy, and we figure B will throw rock or scissors, A will either tie or win. Awesome!

Until B knows that strategy, of course...

Which leads to the final point, which is that Wikipedia and the ideals of the open source movement of freedom of information has crept far and wide.

Take another look at the image at the top of this post. Nice, right? I didn't make it, I stole it from Wikipedia. It's legal because Wikipedia is good like that. But wait, who made that image? It turns out each of the pieces were stolen from other Wikipedia images and composited together by a guy known to us only by "TheCoffee." Thanks, dude.

Oh, and take another look at that Telegraph article. They stole the image too. Except they didn't credit Wikipedia. They didn't even link to the larger version of the image. Nice, guys.

Freedom at the cost of anonymity.