## Saturday, August 11, 2012

### How to Win Games Part 2: Strategizing for Any Game

Today is part two of my game theory posts. Last week, we looked a game that had a saddle point, where there is a dominant strategy for each player. That made it fairly easy to solve, as each player should play a certain strategy every single time regardless of the other player's move.

Yet, not every game is so simple. Sometimes, there isn't a saddle point, and playing a single strategy will just make yourself predictable to the opponent. You need to mix it up, but not 50-50. That's predictable too. You need to determine how you should mix it up mathematically that will give you the best possible outcome.

For instance, let's look at the following game between the cops and the criminals. It is nighttime: the time the criminals commit crime. The police are trying to decide if they should go on patrol and try to catch criminals or socialize at the donut shop. The criminals are trying to decide if they should commit crime or lay low. The matrix would look something like this (assuming that the police are player one and the criminals are player two):

Crime Lay Low
Patrol
3, -5
0, 1
Donuts
-2, 3
2, 0

First, we said we would look for dominant strategies (formally called the pure strategy equilibrium), but there don't seem to be any. This sticks us with this 2x2 matrix that we have to solve for.

We will solve it with a mixed strategy equilibrium, where we figure out what probability we should play each strategy.

To do this, we first set our variables. Let's say that x of the time, we play patrol, meaning that 1-x of the time, we play donuts. Now, we must solve for the criminals' expected payoff for each of their strategies.

If the criminal commits crime:
-5(x) + 3(1 - x) = 3 - 8x

If the criminal lays low:
1(x) + 0(1 - x) = x

We want their expected payoffs to be equal (if they aren't equal, the criminals will just go for the higher of the two outcomes and receive more than they could have otherwise), so we will set the 3 - 8x equal to the x.

3 - 8x = x
3 = 9x
1/3 = x

Therefore, the police should patrol one third of the time, which may be surprising to you considering that donuts is risking a -2 while patrolling is only risking a zero.

The criminals can solve for their optimal strategy using the same logic:

Patrol:
3x - 0(1 - x) = 3x

Donuts:
-2x + 2(1 - x) = 2 - 4x

2 - 4x = 3x
2 = 7x
2/7 = x

The criminals should commit crime two sevenths of the time, which isn't as shocking, considering the risk of the -5.

This strategy works well, as you are making your opponent's outcome as low as possible. The problem is when you know your opponent is playing like this, you have no control over your own outcome. Regardless of how you play, you are going to get the same outcome. Your goal then becomes making your opponent's as low as possible so you can actually pull a win.

In game theory, this is called playing spitefully, where you are purposely trying to make your opponent's payoff low in order to win more easily. Next week, we will learn how to deal with spiteful players, and how to deal with players who think you are spiteful as well.

Answer: A little less than a month ago, I gave you the monk problem, which is another great puzzle. Here is the solution:

First off, remember how the head monk phrased it. There are "sinners" among us. This suggests that there are more than one. So, if you only saw one sinner, you would leave since you would be the second sinner.

The next day goes by, and there are still sinners. Now, if you saw two sinners, you would leave. This is because you know the other two would have seen each other and left unless they saw another sinner. You realize that you must have been that other sinner, and you leave.

The third day goes by and there are still sinners. Now, if you saw three sinners, you would leave. Same logic as before, you know that the three you saw would have left if there were truly three sinners. You then realize that you must be the fourth, and you leave.

Since there were no sinners on the fourth day, that means that there were four sinners, and they left on the third day because of the logic in the paragraph above.