Game Theory: Is there an ideal strategy for winning the war on terrorism?

Before the events of September 11th, my plan was to do October's essay on game theory. After September 11th, I decided to do something mathematical as it relates to the events. My first thought was to focus on rare scares and rare scare mongering that is going on in reaction to the terrorist attacks. I abandoned the idea, for now, for three reasons: 1.) It may seem a bit too insensitive to talk about reactionary policy so soon after the tragedy that caused the policies, 2.) There really is not enough data to prove my case at this point, 3.) Junkscience.com beat me to the punch with a well written warning against bad policies.

So back to the original plan: Game Theory. It seems somewhat appropriate since one of the reasons Game Theory was developed was to help strategize what to do during the "Cold War" and what our policies should be toward the Soviet Union. No doubt Game Theory principles will prove useful in the "War on Terrorism", which has many similarities to the "Cold War" in terms of strategies and objectives.

I mentioned in a previous essay that the Game Theory/Cold War relationship can be found in the movies Dr. Strangelove and War Games. Interestingly enough, the mathematician who is credited with the development of Game Theory, John Forbes Nash, is the subject of an upcoming movie A Beautiful Mind, starring Russell Crowe (Gladiator) and directed by Ron Howard (Apollo 13), which will be released nationally in January 2002. However, the movie is unlikely to focus on Nash's theories as much as it will focus on his disease. Like many famous Mathematicians (Gödel, Cantor, Turing, Von Neumann, etc.) he suffered from a psychological disorder, in Nash's case it was paranoid schizophrenia. You can read more about Nash here. Sorry to spoil the movie, but the 73 year old Nash has recovered and he is still alive today.

What is Game Theory?

Basically, Game Theory is the mathematics of strategy. The primary theory is the Minimax Theorem which basically says that if all the players of a game play the best, most rational strategy, the resulting outcome of the game is predictable. Everything from tic-tac-toe to the stock market can be described by Game Theory.

Obviously, there is a huge difference between predicting tic-tac-toe outcomes and stock market outcomes. Tic-tac-toe, when played smartly by both players, always results in a tie. All we can do in the case of the stock market is describe its "likely" behavior on the assumption that people play the market rationally. Attempts to use mathematical formulas to predict outcomes, and thus make money off the market, tend to work only temporarily until unpredictable irrational behavior, like say terrorist attacks on the financial capital of the world, throw the models into a tailspin.

Game theory deals with "rational behavior" with in different kinds of games. Stock market theories are too complicated for a beginners tutorial, so I will focus primarily on board games and parlor games that most everyone is familiar with. Here are a list of the more important categories of games:

1. Non-random vs. Random - Random games include some randomizing element: dice, a spinner, dealing of cards, ping pong balls in a Lotto machine. Non-random games are pure strategy: Chess, Checkers, tic-tac-toe, etc.
2. Perfect Knowledge vs. Non-perfect Knowledge - Perfect knowledge games are those where all the components of the game are visible to all players: Chess, Checkers, Monopoly™, etc. Non-perfect have hidden aspects, such as card games, Battleship™, Stratego™, etc.
3. One Player, Two Player, n - Player games - Solitary games (mazes, puzzles, etc.) can also include cooperative games where everyone is trying to solve the same thing without competition. The A.I. game I mentioned here had over 7000 players is actually a one player game, because all 7000 played on the same team. Two players are those that only involve two, no less no more, players (chess, Battleship™, etc.) or teams (sports for example). n - player games involve two or more, such as Monopoly™, poker, the lottery, or the stock market.
4. Zero Sum vs. Non-Zero Sum - In zero sum games, the total value of the game stays the same or goes down. In a normal Poker game, players buy into a game with the same amount of money to start with. If six players each start out with $50 worth of chips, then at any point in the progress of the game the total of player holdings and the pot will equal $300. (In many poker games, however, people add more money from their pocket, but we can safely say that that the total amount of money in the game does not exceed the total worth of the players in a game). Chess is another zero sum game, because the number of chess pieces available never goes up. Non-zero sum games are those where values can and do rise. In Monopoly™, every time someone passes GO another $200 in Monopoly money is added to the game. Othello™ (Reversi) and Go are non-zero sum board games where pieces are added to the board as the game progresses. 
   
   There is much debate among economists whether or not the economy as a whole is a zero sum game. If it is, then all the economy is a constant redistribution of the same pile of wealth. As the rich get richer, the poor get poorer according to them. Most, however, believe that the economy is not a zero sum game. As wealth gets created, the rich get richer and the poor get richer. This is a fundamental difference between socialist theories and capitalist theories.

The general game theorem goes as follows: In every two player, zero sum, non-random, perfect knowledge game, there exists a perfect strategy guaranteed to at least result in a tie game.

So what are these two player, zero sum, non-random, perfect knowledge games? Checkers, chess, tic-tac-toe, nim, dots, etc. We know what some of these ideal strategies are. One we do not know is chess. It is too complicated, but it is the subject of efforts such as "Deep Blue" which attempts to computerize chess strategies and create the perfect player.

One game we do know is tic-tac-toe. When O starts, that player has 9 possible moves, X then has 8 possible counter moves, for a total of 72 openings. We can calculate that there are 362,880 (9!) possible game outcomes. Of course, that is way too high. Most games will end before they get to 9 moves.

While we are eliminating games, lets start looking at only "smart" moves. If O starts, they can only really open with the center square or one of the corners. Thus there are only 5 predictable opening moves. If X is also playing smart they will counter with the middle if O picks a corner, or a corner if O picks the middle. So one player picks the middle and one picks a corner, which leaves a total of 8 possible smart outcomes in the opening round of moves. I created a chart of all possible rational outcomes (sorry for the poor quality, I did not feel like spending four hours making it look more professional):

Every possible game is either a reflection or a rotation of these six outcomes. There are six possible non redundant outcomes, all of which can be oriented or reflected 8 different ways, for a total of 48 possible rational outcomes of tic-tac-toe, all of them draws.

The Best Strategy

The way to analyze games mathematically is to create a table with outcomes listed for each strategy. A non random two player strategy table might look like this:

Players choosing a strategy can find the outcome of the game by looking it up on the table.

Two strategies within the table to look for:
Minimax - The least good of all good outcomes.
Maximin - The least bad of all bad outcomes.

The Minimax Theorem: If a Minimax of one player corresponds to a Maximin of the other player, then that outcome is the best both players can hope for. So if there is the possibility of a tie game, then that is the most likely outcome. This outcome is called a Saddle point.

Take for example two children arguing over who gets the last piece of cake. It is decided that one child will cut the piece, and the other will choose which piece to eat. The strategy table looks as follows:

The Minimax solution for the chooser is to get half plus a crumb more. This is also the Maximin solution for the cutter. Thus this is almost certain to be the outcome.

Many games do not have a saddle point outcome, in fact this is true of most games. A simple example is rock, paper, scissors:

Despite the lack of a predictable saddle point outcome, there is a mixed strategy that works best. The strategy is to pick as randomly as possible, picking each a third of the time, following no pattern. If you favor one choice, or if you follow a pattern, your opponent might pick up on your pattern and use it against you. (There is a whole strategy guide available on the internet) There are, of course, bad strategies as well:

Lisa: Look, there's only one way to settle this Rock-Paper-Scissors.
Lisa's Brain: Poor predictable Bart. Always picks rock.
Bart's Brain: Good ol' rock. Nothin' beats that!
(Bart shows rock, Lisa shows paper)
Bart: Doh! 
- The Simpsons (Episode "The Front")

A mixed strategy is to choose randomly between different strategies based on calculated "weighted" possibilities. In the case of rock, paper, scissors, the best strategies are "weighted" evenly.

Mixed Strategies and Random Games

Most games involve some random element, a dice throw, cards dealt, etc. While the Minimax theorem cannot guarantee a winning strategy in these games, it can tell you that there is a mixed strategy which will give you the best chance of success. Take for example the following chart between pitcher and batter, and the batting average that results based on what the pitcher throws and what the batter expects:

Based on these probabilities, the pitcher has to decide what to throw. Conversely, the batter must decide what to expect. A lot of second guessing goes on in these situations. The best mixed strategy for the pitcher is to throw screwballs 60% of the time and curveballs 40% of the time. In response, the batter should expect 80% fastballs and 20% screwballs. If both use these strategies, the batter will bat a .240 average.

I will not get into how these ideal mixed strategies are calculated. The point is for every two player, zero sum game there is an ideal mixed strategy.

Non-zero sum games

In zero sum games, there is a fixed total value. Every point won by one player means another player loses a point. Non-zero sum games means that both players could potentially gain or lose based on their strategy. Consider the game of Chicken, two teenagers race toward one another in cars. If one swerves, the other wins. If both swerve, no one wins, but both survive. If neither swerves, both lose their cars and possibly their lives. The ideal strategy? Swerve!

Another famous non-zero sum strategy game is The Prisoner's Dilemma: 

Two suspects in an armed robbery are arrested on unrelated drug charges. Both are interviewed separately and given the same plea bargain deal: If you squeal on your friend, you can go free and your friend will get five years in jail. If you both squeal, you will both get 3 years. If neither of you squeal, you will both serve a year on the drug charges. If you are one of the prisoners, what do you do?

This is an example of a non-zero sum game with no minimax saddle point. In terms of timed served by both prisoners, it would be best if they both kept their mouth shut. But, in terms of individual time in jail, it is better if you tell on your friend.

Here is a more positive one I like to give to school classes (it generates great debate):

An eccentric philanthropist is offering $3000 to any member of this class who wants it. All you have to do is write a note saying, "Yes, I want it." Now, this same eccentric philanthropist also believes in rewarding unselfishness and cooperation, so if everybody writes a note saying, "No, I do not want it", then every member of the class will get $10,000. If just one person writes "Yes, I want it" they will get $3000 and everyone who writes "No, I do not want it" will get nothing. What do you do? Do you go for the guaranteed $3000, or do you trust the rest of the class to get $10,000?

These are often called cooperate-defect games, and they are interesting in their relevance to ethical situations. Do you vote? Recycle? Contribute to charities? Doing these things cost you time and money and your own individual effort will not make that much difference, but if enough people "cooperate", it will make a difference.

Strategy for the War On Terrorism?

Can Game Theory be of any benefit to war? That, and economic strategy is why it was invented in the first place. The following is my opinion, and should not in any way be taken as fact.

What is the absolute worst thing that could happen? World War III could happen. While I have no doubt who would ultimately be victorious, if this escalates into a war between "The West" vs. "Islam" it would be disastrous for everybody. If we act too vengeful, we could lose sympathetic favor and most Islamic countries could suddenly decide to sympathize with the Taliban. This is what the Taliban is hoping for, and therefore it is something we have to avoid at all costs.

Almost as bad is the escalation to tactical Nuclear War. This is far more likely than World War III. Pakistan is caught in the middle of this mess. While the Pakistani leadership does not support the Taliban, there are enough Taliban supporters within Pakistan that they make a very vocal minority that the government has to at least give them recognition. Because Pakistan neighbors Afghanistan, and has many Taliban supporters as citizens, it is very likely Pakistan will find itself at war, either a civil war or they could be forced to take sides (either is possible) in Afghanistan. Pakistan is a nuclear power, they have had "the bomb" since 1998. It is unlikely that they have a stockpile of nuclear weapons, but all they need is one for things to get messy.

But, the only way we can avoid these worse case scenarios is to do nothing. The result of which will certainly be more terrorist attacks in one form or another. This is also an unacceptable scenario. So we conclude, there is such a thing as not doing enough, and there is also such a thing as doing too much.

War is random, it is n-player, non-zero, and non-perfect knowledge. It is going to require smart well thought out strategy, but it is also going to require risk. The "saddle point" probably falls on this result: We will win the war, but we will also likely lose many battles. Lets hope whatever strategy we decide on turns out to be ideal (the fewest losses possible).

More to Come on Game Theory

This will not be the last article on Game Theory, this is just the introductory chapter. In the future, I am planning a closer look at the math behind simulation games and comparing the math of Poker and Baseball, but unlike "What is Mathematics?", this will be an occasional series not a multipart series.

The interesting thing about Game Theory is that it is a serious topic of mathematics that covers something we experience regularly. We all play games, whether they be for fun, profit, or romance. Whether we know it or not, playing games is a way of "doing math".

Back to the Glossary
Back to Archives