Saturday, December 8, 2012

Game Theory Made Easy: The Criss-Cross Method

A couple weeks ago, we discussed the Criss-Cross Method for multiplication as a way to make it much easier when we get into larger numbers. The traditional method seemed easy, but in reality, it wasn't so easy.

Before I begin, let me mention a quick thing about game theory. Back when I did my four posts on finding game theory strategies, I gave examples of what are called non-zero sum games. These are games where the two players' payoffs do not add to a consistent sum. For instance, in the game between the police and the criminals, we ran across these payoffs.

CrimeLay Low
3, -5
0, 1
-2, 3
2, 0

If you look in each box containing numbers, you will see that the sums are all different.

3 + (-5) = -2
0 + 1 = 1
-2 + 3 = 1
2 + 0 = 2

However, any game you can quickly think of probably does have a consistent sum. Though the card game war is not a true mathematical game (it is not strategic), I will use it for an example.

Every time you put down a card, you either have a card that is higher, lower, or equal to your opponent's card. If it is higher, you keep your card and win their card (a payoff of 1) and your opponent loses their card (a payoff of -1). Same goes vice versa, you lose your card (a payoff of -1) and they win your card (a payoff of 1). If it is a draw, you do war, which makes you put down four more cards in addition to the original one; three face-down cards and one that you use for the actual war. If you win the war, you win five cards (a payoff of 5) and your opponent loses five cards (a payoff of -5), and vice versa.

If you'll notice, in every instance, your payoff is the additive inverse, or the negative of your opponent's payoff. This seems to be rare, but most games are actually like this. These are called zero-sum games, because in every scenario, you and your opponent's payoffs sum to zero.

Back to what I wanted to say today, game theory has something as well that is completely impractical in certain situations. Namely, the method to find mixed-strategy equilibria. It is already fascinating, but the game theory Criss-Cross Method is much more efficient.

Let's take the following fictional example. Say Bob and Joe are playing a game of tennis, and Bob is serving. Bob can choose to serve to the left side of the court or the right side of the court. Joe can choose to position his body weight so that he is ready for a serve coming to the left side, the right side, or just wait and see where it ends up.

Bob has a very strong serve going to the left, and Joe knows this. So, these made-up payoffs are what the odds (in percent form) are that Bob and Joe will win the match:

Prepare LeftPrepare RightWait Until Serve
Serve Left
60, 40
90, 10
       80, 20
Serve Right
80, 20
30, 70
       50, 50

These don't look like zero-sum payoffs. However, I mentioned earlier that a zero-sum game is a game whose sums are consistent, but they actually don't have to be zero. In this case, the payoffs sum to 100.

The next thing we would have to do now is narrow this down from a 2xn game to a 2x2 game. There is a graphing method that I don't have the time to explain right now that will narrow it down for us. The basic purpose of it is to see if there are any of Joe's strategies where no matter what strategy Bob uses, there will be another strategy better than it. In this case, Joe is always better off preparing one way than just waiting until the serve. So, "Wait Until Serve" is a dominated strategy, or it is a strategy that can always be beaten by another one.

Just to simplify the game a little bit, I will divide each number by ten and then subtract five from them. This will make it more like a common zero-sum game.

Prepare LeftPrepare Right
Serve Left
1, -1
4, -4
Serve Right
3, -3
-2, 2

A zero-sum game in this notation can be written with just player one's, or Bob's, payoff in the boxes, and then the analyst can conclude the other player's payoff. Let's write it that way for simplicity's sake.

Prepare LeftPrepare Right
Serve Left
Serve Right

Now, we would normally go about our regular algebra. Let me do it out here:

Bob's Strategy:

(-1)x + (-3)(1 - x) = (-4)x + (2)(1 - x)
-x - 3 + 3x = -4x + 2 - 2x
2x - 3 = 2 - 6x
8x - 3 = 2
8x = 5
x = 5/8

Serve to the left 5/8 of the time and to the right 3/8 of the time.

Joe's Strategy:

(1)x + (4)(1 - x) = (3)x + (-2)(1 - x)
x + 4 - 4x = 3x - 2 + 2x
4 - 3x = 5x - 2
4 = 8x - 2
6 = 8x
6/8 = x

Prepare left 6/8, or 3/4 of the time and right 2/8, or 1/4 of the time. Never make your decision after the ball is served.

Okay, that was complicated. Imagine if we never simplified the game. But the Criss-Cross Method would have made this a lot easier. For Bob's strategy, we would find the absolute value (distance from zero) of the difference of his possible payoffs for serving left. We would do the same thing for his payoffs for serving right.

Serving Left: | 1 - 4 | = | -3 | = 3
Serving Right: | 3 - (-2) | = | 5 | = 5

If we add those together, we get the common denominator used for their probabilities. 3 + 5 = 8, so the probability will be out of eight.

How do we find the numerators? Simply flop the three and the five, or criss-cross them. This will give you 5/8 for serving left and 3/8 for serving right, which is the same as the algebra.

Same thing for Joe, except we go vertically now.

Preparing Left: | 1 - 3 | = | -2 | = 2
Preparing Right: | 4 - (-2) | = | 6 | = 6

Add these together, and we get a common denominator of eight. Now, criss-cross the 2 and 6 to get 6/8 of the time preparing left and 2/8 preparing right. Same as before.

It might seem a little weird at first as to why on earth that would work, which I don't have a clue about. Please comment if you do know why it works.

I probably made it look more complicated than it is with the example I used. However, I wanted to keep the post practical, and you won't find people talking about payoffs of four in life. In fact, you probably won't hear the success statistics in real life. A game theorist would have to take data of both players and determine the statistics. However, the process after must be completed before you actually get down to the criss-cross method at the end. But it is a really cool way to finish off the problem.

No comments:

Post a Comment