Mixed strategy Nash equilibrium

This stuff is like arithmetic: one right answer, nothing to argue about.

Under the assumption of universal rationality. Without that assumption (which would not be fulfilled in a real fantasy sword-fighting game), the best strategy/mixed strategy does not correspond to the Nash equilibrium, and there remains plenty to argue about.

What happens when some percentage of people are picking randomly, some people are "stylin", and some people are performing "misinformed" calculations and/or simulations? The fact that some people actually did the latter shows that the effect must be taken into account.

It's indeed a mystery to me why anyone bothered to post and discuss "solutions" different from Rayhawk's in the swords and armor thread. This stuff is like arithmetic: one right answer, nothing to argue about.

In some sense, I agree with you. The problem as posed had a clear answer that was calculable by a known method (if one had done the requisite reading in game theory). The thing I particularly liked about Rayhawk's post was the link to the a library of game theory software and tools for the construction and analysis of finite extensive and strategic games: gambit. That link was the kind of novel and useful pointer that is one of the many reasons I have for reading LW :-)

On the other hand, I find that the world frequently fails to present situations to me that are intelligible to the point that I can build a payoff matrix and run the numbers. So, as a simple exercise standing in for a more complex world there was potentially much more to say about the puzzle. In that vein I particularly liked Nominull's fast and frugal answer:

My general heuristic for these sorts of games is to play the option that beats the option that beats the option that looks best to me at first blush. In this case that means I play green sword, yellow armor. It's a reasonably fast heuristic that does reasonably well.

I expect that I would find it very difficult to mimic Rayhawk's application of gambit in the bulk of real life circumstances. Nominull's heuristic (which incidentally produced one of the options from the optimal mixed strategy) seems more generally applicable. I can imagine using Nominull's heuristic in much fuzzier contexts for much lower data gathering costs and getting pretty good results thereby. Not that I've tested it or anything... but it's the sort of thing I'll be looking for an opportunity to try out in the real world someday, and see if it helps :-)

As an extra added bonus, I'll mention the "revelation principle" which applies in games where there is some uncertainty regarding the other guy's payoffs or constraints. (No math or proofs here - I just want to sketch the problem and assert the solution. For proofs and details, see a good game theory textbook, such as Myerson.)

For example, say that Player1 has arthritis and can't form a fist for "rock" without some pain. As a result, this player suffers a penalty of -1/3 whenever he plays "rock" - meaning he only has a net payoff of 2/3 against "scissors" and actually loses 1/3 against "rock" or "paper". Player2 has heard rumors about Player1's arthritis, but doesn't know whether the pain occurs when Player 1 plays "rock" or whether it is "paper" that causes the problem. She assigns a Bayesian prior probability of 0.5 to each kind of arthritis. Player 1 knows about these priors - that is, these priors are common knowledge.

Clearly, Player1 wants to keep secret from Player2 exactly which form of arthritis he suffers from. Harsanyi (1967 or so) invented the concept of "Bayesian equilibrium" to characterize and calculate solutions to these kinds of games where the players are unsure of each other's payoffs and beliefs.

Cousin_it just told us about how the basic concept of Nash equilibrium can sometimes be improved to "correlated equilibrium" if the players can find a mutually trusted 3rd person to assist them. Actually, they don't need a person - a mutually trusted machine will do just fine. So the question naturally arises whether a Bayesian equilibrium can be improved to a correlated equilibrium just as the simpler Nash equilibrium could be improved. The answer is yes - but there is a catch. The catch is called the "revelation principle".

The principle is that both players have to trust the 3rd person or machine with their secrets. It turns out that there always is a correlated equilibrium in which both players have an incentive to reveal their secrets honestly to the arbitrator (though not to each other) and both players have an incentive to carry out the instructions of the arbitrator.

The algorithms used by the arbitrator in a correlated equilibrium are not rocket science. They can't be. They have to be understandable and understood by both players. How else can they be convinced that they will do better by trusting the arbitrator than by just playing the game without arbitration?

So if the game players are two powerful AIs, they will want to use a very simple and secure computer system as the jointly trusted arbiter. I can't help but wonder whether the best way to avoid uFAIs that secretly seek to take over the world is to somehow make use of the revelation principle.

I actually briefly considered mentioning correlated equilibria, but the post was getting long already.

Short answer: I already addressed this. Is your point that I didn't emphasize it enough?

One thing should be kept in mind. A Nash equilibrium strategy, much like a minimax strategy, is "safe". It makes sure your expected payoff won't be too low no matter how clever your opponent is. But what if you don't want to be safe - what if you want to win? If you have good reason to believe you are smarter than your opponent, that he will play a non-equilibrium strategy you'll be able to predict, then go ahead and counter that strategy. Nash equilibria are for smart people facing smarter people.

Long answer:

The distribution of sword/armor choices in an MMO will not be the Nash equilibrium with overwhelming probability. In fact, it probably won't be anywhere close if the choice is at all complicated.

Correct. Do you know what the distribution is? Can you gather statistics? Do you understand the mentality of your opponents so well that you can predict their actions? Can you put the game in some reference class and generalize from that? If any of the above, knock yourself out. Otherwise there's no justification to use anything but the equilibrium.

If you are playing an MMO with random pvp, populated by people the people who play MMOs, and you choose the Nash equilibrium, you will probably do worse than me.

If you assume I will continue to use the NE, even after collecting sufficient statistics to show that the players follow some specific distribution (as opposed to "not Nash equilibrium"), then this is a strawman. If you're just saying you're very good at understanding the mind of the MMOer then that's likely, but doesn't have much to do with the post.

But saying that someone who talks about what their opponents are likely to do is "wrong" is itself quite wrong.

I did not criticize the rare swords&armor posts that actually tried to profile their opponents and predict their actions. I criticized the posts that tried to do some fancy math to arrive at the "optimal" solution inherent to the game, and then failed to either acknowledge or reconcile the fact that their solution is unstable.

Reasoning about the distribution of strategies your opponents play is the correct approach to this problem, not reasoning about the Nash equilibrium.

One should first learn how to do Nash equilibrium, then learn how to not do Nash equilibrium. NE is the baseline default choice. If someone doesn't understand the problem well enough to realize that any suggested deterministic strategy will be unstable and that the NE is the answer to that, what hope does he have with the harder problem of reasoning about the distribution of opponents?

If 90% of American generals in the past have chosen to attack West, it is probably wrong to defend East with the "optimal" probability.

Even under the strong assumption that there is some clear reference class about which you can collect these statistics, this is true only if one of the following conditions holds:

• The attacker hasn't heard about those statistics.
• The attacker is stupid.
• The attacker is plagued with the same inside-view biases that made all his predecessors attack west.

The plausibility of each depends on the exact setting. If one holds, and we know it, and we really do expect to be attacked west with 90% probability, then this is no longer a two-player game. It's a one-player decision theory problem where we should take the action that maximizes our expected utility, based on the probability of each contingency.

But if all fail, we have the same problem all over again. The attacker will think, "paulfchristiano will look at the statistics and defend west! I'll go east". How many levels of recursion are "correct"?

The true limit would be 0 if everyone was rational, and aware of the rationality of everyone else, but rational people in the real world should be taking into account...

the fact that most people only seem to be able cope with two or three recursions before they get bored and pick an option

So what you should do, based on that, is try to figure out how many iterations "most people" will do, and then estimate the smaller percentage of the "rank one pragmatic rationalists" who will realize this and aim for 2/3 of "most people" and so on until you have accounted for 100% of the population. The trick is knowing that some people aren't logical means logical strategy (that will actually win) requires population modeling rather than game theory. Hearing your average of 30 makes me hypothesize that the distribution of people looks something like this:

0.1% 100 Blind number repeaters

4.9% 66 Blind multipliers

17% 44 Beating the blind!

28% 30 "most people"

20% 20 Read a study or use a "recurse three times" heuristic

15% 13 Contrarian rationalists

10% 9 Meta-contrarian rationalists

4.9% 6 Economists (I kid!)

0.1% 0 Obstinate game theorists

Suppose you run the experiment again (say, on a mixture of people from LW who have read this combined with others) where you expect that a lot of people might have actually seen this hypothesis, but a lot of people will naively play normally. I think the trick might be to figure out what the percentage of LWers you're dealing with is and then figure out what to do based on that.

I'm tempted (because it would be amusing) to try to estimate the percentage of LWers relative to naive, and then model the LWers as people who execute some variant of timeless decision theory in the presence of the baseline people. If I understand timeless decision theory correctly, the trick would be for everyone to independently derive the number all the LWers would have to pick in order for us all to tie at winning given the presence of baselines. It seems kind of far fetched, but it would be ticklesome if it ever happened :-D

OK, now I'm curious! I think I might try this at the next SoCal meetup.

ETA: ...or does utilitarian consequentialism mean we need to calculate the value we'd all have to vote to maximize the number of winners, whether or not they were expected to participate in the calculation? That sounds even harder.

I think you're making a distinction between one-shot and iterated games. This is a different distinction than that between mixed and non-mixed strategies. You can have a mixed strategy equilibrium in a one-shot game, as in both the swords-n-armour example and the attack/defend East/West example.

So: if the game is one-shot (and you can see the current distribution), the right decision depends only on the current distribution, as you said.

But if you can't look at the current distribution, you still need to use the equilibrium for this single choice. Otherwise, you're at risk that everyone will think the same as you, except for a few smarter players who will counter it.

I'll consider it, But I don't know if I'm the right person for that, or if I'll have the time.

I would take the basic premise to be that we are trying the "guilty party" with the idea of "reasonable doubt".

I'm ok with "Agatha Christy" to the limit of fictional argument, but one would have to give a stronger argument than the "Corax" to find a plausible definition to a physical phenomena. After all, the whole point is to understand.

Fixed.

Thanks. I'll move it as soon as I have the required karma.

Now that I've looked it up, I don't think it really has the same intuitions behind it as mixed strategy NE. But it does have an interesting connection with swings. If you try to push a heavy pendulum one way, you won't get very far. Trying the other way you'll also be out of luck. But if you push and pull alternately at the right frequency, you will obtain an impressive amplitude and height. Maybe it is because I've had firsthand experience with this that I don't find Parrondo's paradox all that puzzling.