Saturday, August 27, 2011

Game Theory: Part I: Notation and Basic Concepts

Yes, evolution of cooperation, blah blah blah. I realized partway through that I needed some background material for that that I hadn't covered, and it's from a separate discipline. So let's start talking about game theory.

The following material is flagged Green Level. It is intended to reflect material that the author believes to be a matter of consensus among experts in the field. This belief may be incorrect, however; and as the author is not an expert and does not have an expert fact-checking the article, errors may creep in.
 So. What is this "game theory" thing? You may have heard some people talk about the "prisoners' dilemma" or the game of "chicken". Both of those are from game theory, which is essentially a branch of mathematics. And I will do my best to describe here how that works.
Let us suppose that you and I play a game. I will write down a letter (A or B) and you will try to guess it. If you guess correctly, I give you $1; if you guess incorrectly, you give me $1. This game can be represented as follows, where what you do is on the left, what I do is on the top, and what you get is in the intersection.


A $1 -$1
(Incidentally,this is what is called a zero-sum game: if you get anything, it hurts me exactly as much as it helps you. Most real applications of game theory do not deal with zero-sum games, but they are the easiest to understand.)
So what, you ask. What does this have to do with the Real World? Well, suppose instead that the two of us are generals. Your force is strong, but mine is stealthy. If we send our armies to the same location, yours will stomp mine, but if we send them to different locations, mine will take the objective of the skirmish.
In essence, game theory is a subject with a broad variety of applications. Game theory can be applied to any situation (called a game) where 1) there are multiple players involved, 2) the actions of each player have an impact on the outcome for that player, and 3) the actions of each player have an impact on the outcomes for other players. This covers "games" ranging from "Guess the Letter" above to the games of "Crash the Economy" played on Wall Street.
To make this game a bit more interesting, let's add the following change: if you guess "B", the payment is doubled. The game now looks like this:


Now, let's try to figure out what the best move for me to make is. Looking at the numbers, it looks like "A", right? If you guess wrongly, I win $2, but if you guess correctly, you win $1.
Wrong. Remember, you have a choice as well. Because you think I am likely to play "B", you choose to play "B". My payoff is -$1.
But let's say that I guess that you will reason that way, and choose to play "A". My payoff is now $1.
But then you anticipate my anticipation of your reasoning, and play "B". My payoff is now -$2. And so on to infinity. This is what makes game theory more than just an expected-value calculation: the non-random actions of another player.

So, how can we resolve this? Let's say that you manage to get a good look at what I write. This allows you to pick whatever I wrote. However, due to my psychic powers, I was able to know ahead of time that you would see it, and act accordingly. Thus, I choose to write the letter that will lose me the least (called my maximin solution), "A". You see that I have written "A", and guess "A", winning $1.

Alternately, let's say that you don't get a good look, but that I still have psychic powers. I know ahead of time what you are going to guess, and will write the letter that will gain me the most (called my minimax solution). But you know about my psychic powers, and choose to guess the letter that will lose you the least. Thus, you choose "B", forcing me to write "A". You lose $1.

<<First in Topic! | Game Theory | Dominating Strategies>>


  1. Aargh. I just realized that I had all my notation backwards from the standard form. Going through and fixing everything now.

  2. Oh dear. Now I'm going to have to stay up all night reading the rest of this series.