A very quick intro to classic game theory

Games

Historically, game theory developed to study the strategic interactions among rational decision makers (players) who try to maximize their payoffs. Consider the following game of Matching Pennies between two players A and B. Both A and B contemporaneously place a penny on the table. Let H be A’s strategy of playing heads (placing heads up) and T that of playing tails. Similarly, let h be B’s strategy of playing heads and t that of playing tails. If the pennies match, then A wins B’s penny (and keeps his own); if not, B wins A’s penny (and keeps his own). The game can be conveniently represented by a strategy matrix:

Player B
Player A		h	t
	H	+1;-1	-1;+1
	T	-1;+1	+1;-1

Here is how to read the matrix. The top-left column with +1;-1 tells us that when both A plays H and B h, A wins one penny and B loses one; the box immediately below shows that when A plays T and B h, A loses his penny and B wins one. The rest of the matrix is read analogously.

Matching pennies is a zero-sum game in that whatever one player wins must be lost by another player. Since there are only 2 players, one’s wins are the other’s losses: the game is one of pure competition.

Note that in Matching Pennies each player knows:

1. The payoffs of each player and the strategies available to each player
2. The fact that each player knows that all the players know this.

A game in which such knowledge is available is a game of complete knowledge. Henceforth, unless otherwise stated, we consider only games of complete knowledge.

Equilibrium

The central notion for studying games is that of equilibrium, namely, a combination of strategies such that each player uses a best strategy, namely one most conducive to maximizing his payoff, given that the other players are trying to do the same. (What counts as a best strategy depends on the type of equilibrium, as we shall see). Solving a game consists in exhibiting its equilibrium or equilibriums if it has more than one.

Dominance

The simplest type of equilibrium is dominance equilibrium. Consider the following strategy matrix, where S1 and S2 are A’s strategies and s1 and s2 B’s.

Player B
Player A		s1	s2
	S1	1,1	-2,2
	S2	2,2	0,3

A brief analysis of the payoffs shows that A should adopt strategy S2 no matter what strategy B adopts, as in each box S2 has a greater payoff than S1. If by E(Si,sj) we understand the payoff of playing Si against sj, then

Sh strongly dominates Si if and only if E(Sh,sj)>E(Si,sj) for all sj’s.

We indicate this by Sh>Si. So, a strategy Sh has always better payoffs than strategy Si if and only if Sh>Si. In our case, S2 strongly dominates S1, that is, S2>S1. Note that dominance is a relation among the strategies of one player; hence it does makes sense to say (falsely) that S1 dominates S2, or to say that s1 dominates s2 (does it?), but not that, say, S1 dominates s2. When in a game both players have a dominant strategy, then the game has a dominance equilibrium. In the game we are considering, S2 and s2 provide such equilibrium. We shall then say that (S2; s2) is the dominant equilibrium of the game. Notice that an equilibrium need not be fair, as in the game 1,1 or 2,2 are fair outcomes while dominant strategy equilibrium outcome 0,3 is not.

Although in the previous game, we started by looking at A’s strategies and noted that S2>S1, we could have started with B’s strategies and noted that s2>s1. By contrast, in the game in table 4, neither of B’s strategies dominates the other; in other words, s1 does not dominate s2 and s2 does not dominate s1. However, if we look at A’s strategies, we see that S1>S2.

Player B
Player A		s1	s2
	S1	4;4	2;-2
	S2	3;-3	-4;4

Now both players know that S1>S2, and therefore both will reason as follows. As S1>S2, player A will always choose S1 no matter what. Hence, the S2 row can be deleted. But now, s1>s2, and therefore the column for s2 can be eliminated. This leaves only one strategy per player, namely (S1; s1), which is the solution to the game. The solution is reached by dominance iteration, namely by the sequential elimination of dominated strategies. Games that are solvable by the elimination of dominated strategies are dominance solvable. It is a nice feature of dominance solutions that they are unique.

Stag Hunt and Prisoners Dilemma

Matching Pennies is a zero sum game: the interests of the players are diametrically opposite.

The opposite kind of game is a coordination game, in which an outcome that is considered best by one player is considered best by all the others, as in Stag Hunt. Player A must decide whether to hunt a stag (S) or a hare (H); player B must do the same. Both A and B must pre-commit before they know what the other has decided. The problem is that if one choose S, one will be able to kill a stag only if the other has also chosen S, while if one chooses H, one is assured one will kill a hare. Of course, there’s more meat in a shared stag (4) than in an unshared hare (2), but choosing H is playing it safe. In effect, this is a game of cooperation vs. defection in which cooperation provides higher payoffs but at a higher risk.

Player B
Player A		S	H
	S	4;4	0;2
	H	2;0	2;2

The game is not dominance solvable (check it out!), but as 4,4 is clearly the best outcome for everyone, the real problem is the difficulty in coordinating strategies to get there.

Strategically, the more interesting games are mixed motives games, namely ones that are neither zero-sum nor coordination. The most famous mixed motive game is Prisoners Dilemma. Consider the following story. Two criminals are arrested and the prosecutor has not enough evidence to convict either of a serious crime unless one or both confesses; however, the two criminals do not know this. Hence he tells one of prisoners: “If you confess and the other guy does not, I’ll grant you immunity and you walk free. If the other confesses and you don’t, I shall make sure that you get a heavy sentence. If neither of you confesses I shall settle for misdemeanor charges, with the result that you will pay a small fine and walk free. If both of you confess, I shall charge both with a felony but also argue for shorter sentences than you would get if the other guy squeals and you do not.” Keeping in mind that the game is one of complete knowledge, what should a prisoner do?

Here is the strategy matrix, with S representing “keeping silent” and T “talk”, +10 the utility of walking free, -10 that of a heavy sentence, -6 that for felony charges but with shorter sentence, and +6 that for misdemeanor charges:

Player B
Player A		S	T
	S	+6;+6	-10;+10
	T	+10;-10	-6;-6

The game is neither a coordination nor a zero-sum game, but it is dominance solvable: T dominates S; consequently, (T,T) provide a dominance equilibrium. No matter what the other does, it’s better to talk: if you squeal and the other does not, you walk free (+10); if you squeal and the other does as well, you get a -6 payoff. At all cost you want to avoid keeping silent when the other confesses. Self-interest prevents both from following (S, S) (both keep silent), which would provide a better outcome for the two together. This is why this game is called “Prisoners Dilemma”: purely self-interested private rationality leads to common failure. One can think of Prisoners Dilemma in terms of cooperation (cooperating with the other by keeping silent) and defection (going at it alone by confessing). Notice two things:

1. If the players are self-regarding (only trying to maximize their own payoffs) communication does not solve the problem: even if I know that you will not squeal, it is still in my self-interest to confess.

2. Even finite iteration of the game need not change its outcome. For example, suppose both players know that the game will be played 10 times. Then A knows that in the tenth round she should confess, independently of what happened in the ninth round. Hence, in the eighth round she should confess because what happens in the ninth does not affect what happens in the tenth, and so on. The same applies to B.

Fortunately, most people do not behave as classical game theory suggests; in fact, there’s ample experimental evidence that very often we tend to cooperate unless we perceive that we are being taken advantage of. Hence, since most people are conditional cooperators, it often makes sense to cooperate, at least initially, unless the stakes are so high that cooperating against a defector leads to immediate big losses. Note that in Prisoners Dilemma it may be reasonable for the self-interested players to set up an enforcer that compels them to choose cooperation: in some cases limiting one’s options is perfectly rational as it maximizes one’s payoffs.

When Prisoners Dilemma is played an indefinite amount of times between two players, the structure of the reiterated game is different from that of each Prisoners Dilemma round. We shall come back to that later.

The Prisoners Dilemma can provide a rough strategic description of many real life situations. For example,

· a one shot arms “race” between two counties has the same strategic structure: arming dominates over not arming, but if both countries arm they’ll incur severe expenditures they could avoid by not arming.

· a one shot tariff confrontation between two countries has the same logic: if A raises its tariffs and B doesn’t, A will improve its trading balance, and if A doesn’t raise tariffs and B does, A will do worse than if both raise tariffs. So, raising tariffs dominates over not raising them. Hence, both countries will raise tariffs, with a decrease in business for both.

Nash equilibrium

Dominance equilibrium in interesting games is rare. However, there are other types of equilibrium. A strategy Si available to A is a best reply to strategy sj if Si’s payoffs are greater than, or at least equal to, those of any other strategy available to A. (B’s strategies are treated in the same way).

A pair of strategies Si and sj form a Nash equilibrium if and only if they are best replies to each other.

For example, if my strategy is to drive on the right, then your best reply is to drive on the right as well; and if you drive on the right, then my best strategy is to drive on the right

In the following game

Player B
Player A		s1	s2	s2
	S1	1,4	0,3	0,0
	S2	-1,0	5,2	1,1
	S3	2,-1	-1,0	1,1

there are no dominant strategies (check it out!). However, you may check out that S2 is a best reply to s2 and vice versa. That is, if A plays S2, then B’s best reply is s2, and A’s best reply to s2 is S2. Consequently, (S2,s2) constitute a Nash equilibrium. The idea is that player A has no incentive to change strategy S2 as long as B follows s2, and vice versa. This entails that if the conditions of the game do not change, a Nash equilibrium is stable. Abstractly understood, human conventions are Nash equilibriums; for example, if you drive on the right side of the road, it’s best for me to do the same, and vice versa; similarly, if we want to communicate, we must use a shared language, and as long as you don’t change it I won’t change it either; if in our culture we greet each other by shaking hands, it won’t do for me to try to rub your nose with mine; however, if the greeting involved rubbing noses, then it would be a mistake on my side to try to shake your hand if I want to greet you.

Note that

· A dominance equilibrium is a Nash equilibrium, but not vice versa (why?)

· A Nash equilibrium need not be fair and need not result in the best payoff for either player. For example, player B would be better off if he followed s1 and A followed S1.

Nash equilibriums are important for two reasons.

· The first has to do with dynamical systems, of which more later. Suppose we leave players out and consider only strategies competing against one another. Typically, they will outcompete each other until they reach a Nash equilibrium, at which point all of them will be optimal in the sense of being best responses to each other, at least as long as the environmental conditions do not change.

· The second reason involves the assumption of the rationality of the players, a more traditional ground for the theory. If the game is of complete knowledge, the players intend to maximize their payoffs, they are rational and try to predict the moves of their opponents, and all this is common knowledge among them, they can avoid much strife by settling for a Nash equilibrium. Here is why. Imagine a demonic book that told every player which strategy to follow to maximize his payoff given that all the others also maximize theirs. If the book is to be fully authoritative, then it must settle for some Nash equilibrium because otherwise at least one of the players would improve his payoff by changing strategy. Of course, if the game has more than one Nash equilibrium there may be coordination problems; moreover, if different players maximize their payoffs at different Nash equilibriums, they’ll find it difficult to settle on one.

Multiple Nash equilibriums

The existence of Nash equilibriums presents a new problem: many games have two or more Nash equilibriums, and they do not produce the same payoffs. For example, one can see that Stag Hunt has two Nash equilibriums (which are they?) with different payoffs. Another famous example comes from Battle of the Sexes, which goes as follows. Joe and Jill want to go on vacation. Joe can choose to go to the sea (S) or to the mountains (M), as similarly for Jill, who can choose s (sea) or m (mountains). Joe prefers the sea and Jill the mountains. However, they prefer going together rather than going alone.

Jill
Joe		s	m
	S	4;1	0;0
	M	0;0	1;4

This game has two Nash equilibriums, (S,s) and (M,m), that do not produce the same payoffs, and therefore are not interchangeable, as obviously Joe prefers the former and Jill the latter (check it out!).

Many situations can be modeled by Battle of the Sexes. For example, two companies A and B want to standardize their products but need to decide what standard to follow, A’s or B’s, or two parties that want to reach an agreement but need to decide on what language to use, and so on. Note that pre-commitment is advantageous in this game: if Joe has already a non-refundable train ticket for the sea, he has an advantage over Jill, another case in which limiting one’s options may be rational. However, Jill might decide to retaliate if she thinks Joe’s pre-commitment amounts to cheating.

How can the players choose among non-interchangeable Nash equilibriums?

In some cases, this can be achieved by appealing to Pareto dominance. An outcome X Pareto dominates an outcome Y just in case for all players X has at least a good a payoff as Y and at least for one player a better one. For example in the following Stag Hunt,

B
A		S	H
	S	4;4	0;2
	H	2;0	2;2

(S,S) Pareto dominates (H,H), although both are Nash equilibriums. A and B have an identical interest in choosing (S,S) because Stag Hunt is a coordination game, and if both players are perfectly rational, never make mistakes, and both know that, then they’ll end up with (S;S). Note, however, that:

· Pareto dominance does not work in Battle of the Sexes, a mixed motives rather than a coordination game.

· In a real Stag Hunt game (one in which, among other things, players make mistakes) would the Pareto dominant equilibrium be reached if in table 9 the payoffs for (S,H) were (-1000;2), or would A get cold feet, fearing a mistake by B?

In other cases, a common conjecture on how to play the game can be the outcome of cultural practices, human psychological idiosyncrasy, or of having played the game many times before. For example, suppose that two people want to meet in St. Louis at a given time known to both but they cannot communicate to decide where. If they really need to meet, an obvious place is at the Arch, this being the most prominent place in the city.