Weeks 1 and 2

WEEK 1

Our term began on March 4th with an introduction to our class, Advanced Analytical Techniques. On the first day, Professor Kris Wheaton gave a brief overview of what to expect throughout the term and what was expected of us as students. He passed out a list of dozens of methods/modifiers that we could choose from to study for the term. As I was perusing the list, most of the methods/modifiers had brief descriptions of each and nothing seemed to catch my attention. That is, until I reached game theory (which, by the way, did not have a description underneath).

All that I knew about game theory was what a zero-sum game is (to be detailed in a later post) or at least I heard of it before. Actually, that's not entirely true; I also knew that it was mathematically complex, but I was confident in my ability to grasp the concepts by the end of the term. But, since we did not have to decide what we wanted to study until the end of week 2 (we only had one class the first week), I decided I would do a little background research to make sure I actually wanted to study it, so I read the Wikipedia article.

As soon as I read it, I knew I had chosen the right subject. However, it was not because I was overly excited about game theory itself. On the contrary, I was excited about the possible range of topics that I could apply it to, which was the other requirement of the course. Specifically, I learned that game theory is used extensively in international relations, which just happens to be what my undergraduate background is in. Essentially, that's what happened during the first week; nothing out of the ordinary, thus, so far so good.

WEEK 2

This week turned out to be a wash, at least when it came to my research of game theory. You see, I'm also a member of the Competitive Intelligence club here in the department and we were quite fortunate to receive an invitation from SCIP (Society of Competitive Intelligence Professionals) to come volunteer at their annual conference in Washington, DC. The conference lasted the entire second week of Spring Term (March 8-12). I had high hopes of getting some work done after the business day concluded, but, frankly, that was wishful thinking on my part. Let me just say that even though the conference was great, it was one of the most tiring weeks I have ever had to go through. And trust me, if you're enrolled in Mercyhurst College Institute of Intelligence Studies, you experience many weeks of extreme fatigue! But, at least I was able to lock down game theory as my subject for the term. Beginning in week three, that's when the real fun started...

Related articles by Zemanta

• Prisoner's Dilemma. John van Neumann, game theory, and the puzzle of the bomb. William Poundstone (regnordman.com)

Zero-Sum and Non-Zero Sum Games

Image via Wikipedia

A zero-sum game is a game where the total payoffs are fixed, where one player’s gain is another player’s loss. An excellent example of this is a poker game where the players contribute money into a pot and someone “wins” it after all the bets are tallied and the winning hand is revealed. However, nobody actually “won” the pot of money, rather all the other players lost money that another player gained. The total amount of money available will never change in this game. The simplest form of a zero-sum game consists of two players and two strategies because a one-player game is not a game and only having one choice of strategies is not really a choice. The only way for a player to win is for the other player to lose, no cooperation is possible. That is, in order to be a true zero-sum game, the expected payoff for one player must equal the expected cost for the other player (if I gain $1, you must lose $1) for a sum of zero.

NON-ZERO SUM GAMES

A non-zero sum game where one player's gain does not necessarily mean the other player's loss; these games are actually more complex because there is usually more than one rational strategy. They are referred to as "non-zero sum" because the sum of the two player's payoffs does not always equal zero. Furthermore, non-zero sum games are not forced to be non-cooperative. That is, sometimes cooperation between the players leads to the optimal solution. The greatest example of a non-zero sum game is the prisoner's dilemma (I'll explain it in a later post). Essentially, each player is acting in his own self-interest, but that doesn't necessarily mean that the one player's gain is the other player's loss. Depending on how much the prisoner's cooperate with each other, that will determine each player's individual strategy. Furthermore, examples of non-zero sum games are more prevalent in real world situations, which makes them more useful to game theorists.

John von Neumann and The Minimax Principle

Image via Wikipedia

JOHN VON NEUMANN

John von Neumann was a Hungarian-American mathematician who is widely regarded as the father of game theory (although, a Frenchman named Emile Borel published seven years before von Neumann). He was born in Budapest, Hungary in 1903 and possessed an eidetic memory which allowed him to excel in his studies. Von Neumann's inspiration for developing game theory came from poker, which he played rather unsuccessfully. He quickly realized that poker was not guided by probabilities alone and that one needed to play against the players, not against the cards. Furthermore, he wanted to formalize the notion of deception against the other players in the game. It was in his 1928 paper "Theory of Parlor Games" where he first broached the subject of game theory and proved the minimax theorem. In fact, von Neumann is quoted as saying, "As far as I can see, there could be no theory of games on these bases without that theorem...throughout the period in question I though there was nothing worth publishing until the 'minimax theorem' was proved." Once he proved the theorem, he collaborated with Oskar Morgenstern, an Austrian mathematician, to work on game theory. In 1944, they published their seminal work "Theory of Games and Economic Behavior" which is widely considered one of the most important texts of modern economic theory. To illustrate the point, the intended audience for the book was originally only economists, but it was applied to other subjects such as politics, sociology, psychology, and many others. From that point on, John von Neumann focused much of his work on war and politics. In fact, he would go on to hold several positions within the United States government such as the RAND Corporation and the Atomic Energy Commission under the Eisenhower administration.

John von Neumann would have been considered an extreme hawk by today's standards. He openly advocated preventive war against the Soviet Union. Another famous quote attributed to him, "If you say why not bomb them tomorrow, I say why not today? If you say today at 5 o'clock, I say why not one o'clock?" Of course, by the mid-1950s, the USSR had amassed enough of a nuclear arsenal to sustain a more than credible deterrent against a first strike by the United States.

Unfortunately, von Neumann was diagnosed with bone cancer in 1955. Amazingly, he continued his work as a consultant even while receiving debilitating chemotherapy. In fact, he moved his office to Walter Reed Army Medical Center and received frequent visits from the Secretary of Defense and his colleagues in the U.S. Air Force. John von Neumann succumbed to his cancer on February 8, 1957 and would be remembered as one of the greatest minds of the twentieth century.

His other significant accomplishments include his development of the digital computer, basing computer calculations on binary numbers, and having computers store programs in a coded form instead of punch cards.

THE MINIMAX PRINCIPLE

To quote from William Poundstone, "the minimax theorem proves that every finite, two-person, zero-sum game has a rational solution in the form of a pure or mixed strategy." In other words, when there is a precisely defined conflict between two people whose interests are completely opposite from one another, there is always a rational solution. Essentially, a player is trying to minimize his potential loss while maximizing his potential gain. The solution is rational because each player cannot expect to do any better given the nature of the conflict. The principle is explained using an example of two kids and a cake.

The first kid cuts the cake into two slices and the second kid decides which slice he wants. The cutter expects to get the smaller piece because the chooser will select the larger piece. By cutting the cake as evenly as possible, the cutter guarantees himself almost half the cake. But, if he cuts the cake unevenly, he knows he will get the much smaller piece. Therefore, in order for the cutter to minimize his opponent’s maximum payoff, he will cut the cake as evenly as possible. This is a very basic example of the minimax principle, however, its proof demonstrated that two rational players, whose interests are completely opposed, can agree on a rational course of action confident that the opponent will follow suit (by cutting the cake as evenly as possible, the cutter can be sure that the opponent will leave about half the cake).

Von Neumann thought that the minimax principle could be applied to n-person (two or more) games as well. Take a three-person game for example. The preferences of Player 1 and Player 2 are completely opposed to each other, but Player 1 and Player 3 share similar (or the same) preferences. In that case, they could form a coalition and defeat Player 2. By allying with each other, Players 1 and 3 essentially constitute one player and Player 2 is the other. Now you've got two players with completely opposing preferences (sound familiar?) It doesn't have to stop there; using the minimax principle you could develop n-person games ad infinitum, discover all the possible winning coalitions, and reduce them to zero-sum games. However, the one problem with this line of reasoning is that you're assuming that rational actors would determine the results of every possible coalition and join the one with the maximum payoff. What about games where cooperation is outlawed? As I'll discuss in a later post, John Nash discovered a way to arrive at an equilibrium even when players cannot cooperate with each other.

I researched what the actual minimax proof looks like and found this one from Brigham Young University to be the least challenging (I still have trouble understanding it though). If you're mathematically gifted, I suggest you read it, because it is essentially the foundational principle of game theory.

The Predictioneer's Game and Prisoner's Dilemma (the book)

This post is dedicated to reviewing my two main sources of information for my study of game theory: Prisoner's Dilemma by William Poundstone and The Predictioneer's Game by Bruce Bueno de Mesquita (BDM).

PRISONER'S DILEMMA

Let me begin by saying that if you're even slightly interested in learning about game theory, you need to begin by reading this book. Game theory is not a subject that one can just delve into without any prior knowledge because it is quite mathematically complex. I learned this lesson the difficult way; when I first started studying game theory, I used the Internet just like almost of us would do. Unfortunately, most of the information online falls under two extremes: either it was too basic for someone to reach a novice level of understanding or it was so complex that it already assumed you know a significant amount of game theory beforehand.

Prisoner's Dilemma is great for beginners because it isn't just another mathematical book about game theory. Sure, some math is involved, it has to be to illustrate the concepts. But at least the examples are all user-friendly. Also, it serves as an excellent biography of John von Neumann and as a brief history of nuclear weapons and the Cold War. In fact, most of the applications that Poundstone uses come from the Cold War. For a book that is discussing one of the most complex theories in mathematics, Prisoner's Dilemma is surprisingly easy to read and, dare I say, a page-turner!

In addition to what you'd expect a work of this caliber to be, Prisoner's Dilemma also boosted my confidence that I could understand what game theory was, even if it was at just an introductory level. When I first started this process, I really underestimated the complexity of game theory and I experienced serious doubts about whether I could handle the subject. But when Professor Wheaton recommended it to me in class, and I started reading it, I was able to refocus my goal. I'm pretty ambitious and I thought I could teach myself the mathematical intricacies of game theory. When I (quickly) realized that that wasn't realistic, Prisoner's Dilemma allowed me to recognize that most people probably didn't know much about game theory besides that it existed and maybe what a zero-sum game or the prisoner's dilemma was. I can say with absolute certainty, that without this book, none of what you're reading on this blog would've been possible for me write about. Prisoner's Dilemma discusses most of the main concepts of game theory in a way that makes the reader want to increase his or her knowledge to the point where he or she can understand complex proofs, at least in my opinion. Bottom line: if you want to learn about game theory, you MUST to read this book.

THE PREDICTIONEER'S GAME

Bruce Bueno de Mesquita is one of the world's leading game theorist, if not THE leading game theorist today. Although he's written several texts, this one is aimed at the average person who probably has not had extensive exposure to game theory. I like to compare it Freakonomics, but it's not quite as good. Unlike Prisoner's Dilemma, BDM's book is more about the application of game theory to real-world situations rather than an introduction to the theory itself and the use of historical examples to illustrate the theory. In addition, he acts like a salesman on behalf of game theory. That is, he argues that game theory can be used not only to forecast the future, but if used properly, to actually shape future events. In fact, I developed the model for my personal application using BDM's recommendations. Unfortunately, his constant reference to his model never leads to him revealing what that model is, therefore, without his algorithms it would be nearly impossible for a game theory novice like myself to recreate it.

Although the book is quite an interesting read, and accessible to average reader, BDM's ego shines brightly. He never misses a chance to congratulate himself on his successful predictions as is clearly evident with is discussion of the Israeli-Palestinian conflict (he predicted the 1993 accord in 1991). Moreover, even though he devotes an entire chapter to his failure to predict the outcome of the 1994 health care debate, he blames the fact that he did not have the most accurate information. He even claims he would have been right if Illinois Rep. Dan Rostenkowski was never indicted on federal corruption charges! I'm not sure how he can say that since that's not what happened. That's one of the biggest criticisms of game theory, by the way; the notion that if the expected outcome never comes to fruition, the flaw occurred in how the model was used, not that the model itself is flawed (although I'll give BDM credit for admitting he needed to change his model to account for unpredictable events).

Up until now, I've been pretty harsh of my critique of The Predictioneer's Game, but in reality, for all the issues I had with it, the book did come in pretty handy. Like I said earlier, without BDM's recommendations, I would not have known where to begin building my model (see Week 5's post for the recommendations). In addition, even though I was not able to replicate his model, because I did not have access to his algorithm, by using his recommendations I did not need a complex equation to build it. And that is the main lesson I learned from reading this book: that in order to apply game theory, you do not necessarily need a complex algorithm to arrive at the rational solution. Of course, having those complex algorithms would allow an analyst to express more confidence in a forecast, but it's better than nothing. Although The Predictioneer's Game is not quite the necessity Prisoner's Dilemma is, I would recommend it to anyone who has an interest in game theory. It is an easy and interesting read and helps lessen the intimidation factor of game theory.