(I'm filling in here to get the ball rolling; this is probably different from the original author's ideas. Hopefully he will provide them later when he finds the time )

Game theory is a branch of Mathematics that studies strategic situations where an individual's success depends not only on his choices but on those of others as well. It deals with "games", but in a broader setting it applies to economics and social sciences. The seminal work is "Theory of Games and Economic Behavior" (1944) by J. v. Neumann and O. Morgenstern.

As with any branch of Mathematics we need to start with a few definitions so we can agree what we talk about. I'll try to keep them as informal as possible.

A game consists of:

1. a set of players;
2. a game state;
3. a set of options or possible moves for each player depending on the state;
4. a payout function for each player depending on the final state of the game.

Example 1: Roshambo. This is a game for two players. Each player picks a symbol, either Rock, Paper, or Scissors. They simultaneously reveal their choices (by appropriate hand signs). Rock beats Scissors, Scissors beat Paper, Paper beats Rock. If both players pick the same symbol it is a draw.

We can visualize the various payouts in a matrix like this:

On the left we have the first player's symbol, on top the second player's symbol, and the entry gives the payout for the first player.


Since the gain of Player A is always equal to the loss of Player B the sum of both players' results is always 0. So we speak of a "two-player, zero-sum game" which is an important class of games.

Example 2: Chess.

Example 3: Three card poker. (This example is due to Mike Caro.) We use a deck of three cards, an ace, a king, and a queen. Rankings are as usual: A>K>Q. Two players, A and B, are dealt one card each. Both players put up an ante of $1. A acts first and can either check, or bet $1. If A checks, B has to check behind. If A bets, B can fold or call. If B folds, A wins the antes, otherwise the best hand wins the pot.

Again this is a two-person zero-sum game. What is new here is that the complete game state is not known to both players since they do not know their opponent's hole card. We speak of a game with "incomplete information". Chess has complete information; Roshambo has no state to speak of, so in a way each player knows everything, i.e., nothing.

Strategies

A strategy for a player in a game is his game plan. It tells him how to act in each situation. Mathematically speaking it is a mapping or function from the space of game states to the set of legal moves. One possible strategy for Player A in 3-card poker would be: Raise A, raise K, fold Q. One possible strategy for Player B would be: Call A, fold K, call Q.

Given the strategies for both players we can determine the outcome for each combination of hole cards:

• (A,K): A bets, B folds, A wins $1
• (A,Q): A bets, B calls, A wins $2
• (K,A): A bets, B calls, B wins $2
• (K,Q): A bets, B calls, A wins $2
• (Q,A): A checks, B wins $1
• (Q,K): A checks, B wins $1

So over the six possible outcomes, A wins 1+2-2+2-1-1=1. So on average A wins $.17 per game.

A fancier word for "average" is "expected value" or "EV", but it means exactly the same. So we say that given the two strategies for A and B the expected value is +$0.17 for A, and -$0.17 for B.

In Roshambo there are only three strategies available to each player: He can pick one of the three symbols. If B knew A's strategy he could adjust in order to beat A every time. So if A picked Rock, B would pick Paper, and win every game.

Similarly in three-card poker, if B knew that A played the strategy outlined above (raise K+, fold Q), he could devise a counterstrategy which would maximize his expected winnings. If A checks there's nothing to do. If A raises he holds a K or an A, so we can fold Q and K, and call with an A. Looking at the payout from A's perspective again we get

• (A,K): +1
• (A,Q): +1
• (K,A): -2
• (K,Q): +1
• (Q,A): -1
• (Q,K): -1

So here Player B wins $1 total, or $.17 on average.

By knowing A's strategy, B was able to adjust. We can say that B exploited A's strategy

Given an opponent's strategy, an exploitative strategy is one that maximises our expected value against that opponent.

However now A can adjust in turn; he will stop betting K's and start betting Q's instead; this will lower B's EV.

Usually we do not know our opponents strategy, so we try to optimize our results no matter what he does. In other words we assume that our opponent plays well.

In order to simplify things we can determine a few characteristics that a good strategy has to satisfy:

• B should always fold a queen since it can't beat anything
• B should always call with an ace since it will surely win
• A should bet aces always. If B folds nothing is lost, and if B calls we gain an additional $1 compared to checking
• A should never bet a king since it is called only by an ace.

So the only interesting situation occurs when Player A holds a queen, and Player B holds a king.

• If B calls with a king, A shouldn't bet a queen since it will always be called.
• If A doesn't bet a queen it means that he only bets an ace, and so B should fold his king.
• If B folds kings then A should bluff with his queen since he either wins $1 (against a king) or loses $2 (against an ace), so on average he loses $.50, whereas by checking he certainly loses $1.
• Finally if A bets queens then B should call with a king (risking $1 to win $3, winning half of the time).

So if they exploit each other we get into a circular situation: B calls -> A checks -> B folds -> A bets -> B calls. The same sort of circularity occurs in Roshambo.

Next up: Mixed strategies and equilibria

Looks promising, I like.
Found this in my History:
http://academicearth.org/lectures/in...to-game-theory

Online lectures from Yale:

2st?

3nd

I am half way through Yale's Game Theory Course. You can download it free from ITunes. Good stuff.

5th

Mixing it up

So when playing Roshambo or three-card poker we can't always play the same strategy against a thinking player since he will exploit us. Hence we must switch between different strategies.

If we do this in a predictable pattern we're off no better since our opponent knows what we do. Thus our only chance is to randomize our choices. In Roshambo we can assign different probabilities to the three strategic options Rock, Paper, and Scissors.

Assume we play Rock half of the time, and Paper the other half. If our opponent knows that he can always play Paper, winning 50% of the time and drawing the rest. This shows us that we have to use all our options. In fact, if we do not balance our choices exactly our opponent will have one fixed strategy that wins against us in the long run (another synonym of "average" by the way). So our only option is to choose each option with probability 1/3.

However this leads to the paradoxical situation that we can't lose, but we can't win neither. No matter what our opponent does we will break even; he has no opportunity to make a mistake against us. We are, as KurtSF would put it, "0EV against everyone, seriously".

This concept of mixing it up leads to the following definition:

A mixed strategy is a probability distribution of pure strategies.

So before starting the game we pick one strategy with a certain probability and stick to it. (Some may argue that we make probabilistic decisions throughout the game but it can be shown that this is equivalent to picking one fixed strategy before the game starts.)

In three-card poker we saw that most of our actions are straightforward (betting aces, checking kings, calling aces, folding queens). The only open questions were, what should Player A do with a queen, and what should Player B do with a king. Doing the same all the time opened us up to exploitation, so both players have to adopt mixed strategies if they want to optimise their results.

So let us say that A bets a queen with probability x, and B folds a king with probability y.

• (A,K) A wins $1 with prob. y, and wins $2 with prob. (1-y). EV: 2-y
• (A,Q) A wins $1 EV: 1
• (K,A) B wins $1 EV: -1
• (K,Q) A wins $1 EV: 1
• (Q,A) B wins $2 with probability x, and 1 with probability (1-x). EV: -1-x
• (Q,K) A checks, and B wins $1, with probability (1-x). A bets and B folds with probability xy, A wins $1. A bets and B calls with probability x(1-y), B wins $2. EV: (x-1)+xy+2x(y-1) = x-1 + xy + 2xy - 2x = 3xy - x - 1

Altogether the expected result is
2-y + 1 - 1 + 1 - 1-x + 3xy - x - 1
= 1 - y - x + 3xy = f(x,y)

We can now find the optimal frequencies with some higher Mathematics:
0=d/dx f(x,y) = -1+3y -> y = 1/3
0=d/dy f(x,y) = -1+3x -> x = 1/3

Hence, in order not to be exploitable Player A should bet a queen one third of the time, and Player B should fold a king one third of the time. Note that 1/3 is the fraction of the pot that B needs to call; this is not a coincidence.

If either player deviates from this strategy he immediately loses expected value. Moreover, he opens himself up for exploitation leading to further losses. So it is in his best interest to stick to this strategy. This situation is known as an equilibrium:

A set of strategies for all players in a game is a Nash equilibrium if no player can improve his EV by changing his strategy unilaterally.

A strategy that is part of a Nash equilibrium is call game-theoretically optimal (GTO).

Theorem (John Nash, 1949): If mixed strategies are allowed, a Nash equilibrium always exists.

Looks interesting read

Game theory applicable at micros though?

Yes. Villians are always making decisions and based on the type of decisions they make, i.e. bet A, check K, fold Q, we have to react properly. For example, in the micros we know that the typical villians statagy is to play too many hands preflop, call to much on the all streets and raise when they have a really strong hand. Since this is the typical villians stratagy, and they are not thinking villians and do not adjust to us, we can develop one stratagy for most everyone. That stratagy might be "bet all tptk hands for 3 streets. If they raise fold anything under top 2pair". This is just a generalization and not the stratagy I recommend.

When we face a different type of villian, say Agrodonk who's stratagty is to bet just about everything and enjoys getting into raise wars our stratagy above will simply not work since the option of being called down with worst wont happen. Or stratagy then becomes something like "call down with set+ on drawy boards, and bet AA-sets on drawy boards to get it in good and make him draw out".

So, yes we use Game Theory, just on level 2. if we get to level 3 against most micro players we are going to level ourselves.

Great post Cangurino.

great post/discussion!

I do not believe that game theory is only valueable to level 2 and under. Game theory deals with the framework in which you think about a game. The applies to all games including micros. Of course, while thinking beyond level 2 (and most situations level 1) is just asking for trouble in the micros.

Knowing how to think about the game (and any game for that fact) is essential in beating the said game. It will enble you to apply the appropriately instead of inappropriately math. Applying mathematical inappropriately will lead to faulty premises, therefore lead to poor decisions.

Since we all play the micros, we all make poor decisions. The way we get better is study mathematics (game theory, probability, combinitorics, algrebra, and other areas being a subset of mathematics), psychology, sociology and other field of study.

I wasn't saying that game theory only works at level 2 and under, but that at the micros we only play level 2 and under unless we have a reason (villian is someone we know).

hang over, so I will read tomorrow but it looks pretty good.