Game Theory

A Nontechnical Introduction to the Analysis of Strategy

Roger A McCain

• Publisher: WSPC
• Year: 2010
• ISBN:
  9789814365222
• Topic: Mathematics
• Subtopic: Applied Mathematics
• Index: Mathematics

This book serves as an introduction to game theory for students with no prior game theory knowledge, or with limited background in economics and mathematics. It is specifically designed to provide an intuitive and accessible interdisciplinary approach to game theory, while simultaneously exploring cooperative games, repeated play, correlated equilibrium, and a range of applications.

The Instructor Manual is available upon request for all instructors who adopt this book as a course text. Please send your request to [email protected].

Contents:

• Fundamentals
• Two-Person Games
• Larger Numbers and Uncertainty
• Games in Extensive Form and Repeated Play
• Cooperation
• Behavioral and Evolutionary Game Theory
• Selected Applications

Readership: Undergraduates and graduates studying game theory or those interested in knowing more about game theory.

PART 1

Fundamentals

CHAPTER 1

Conflict, Strategy, and Games

What is game theory? And what does it have to do with strategy and conflict? Of course, strategy and conflict arise in many aspects of human life, including games. Conflicts may have winners and losers, and games often have winners or losers. This textbook is an introduction to a way of thinking about strategy, a way of thinking derived from the mathematical study of games. Of course, the first step, in this chapter, is to answer those questions — what is game theory and what does it have to do with strategy? But rather than answer the questions immediately, let us begin with some examples. The first one will be an example of the human activity we most often associate with strategy and conflict: war.

1. THE SPANISH REBELLION: PUTTIN’ THE HURT ON HIRTULEIUS

Here is the story (as novelized by Colleen McCullough from the history of the Roman Republic):

In about 75 BCE, Spain (Hispania in Latin) was in rebellion against Rome, but the leaders of the Spanish rebellion were Roman soldiers and Spanish Roman wannabees. It was widely believed that the Spanish leader, Quintus Sertorius, meant to use Spain as a basis to make himself master of Rome. Rome sent two armies to put down the rebellion: one commanded by the senior, aristocratic, and respected Metellus Pius, and the other commanded by Pompey, who was (as yet) young and untried but very rich and willing to pay for his own army. Pompey was in command over Metellus Pius. Pius resented his subordinate position since Pompey was not only younger but also a social inferior. Pompey set out to relieve the siege of a small Roman garrison at New Carthage, but got no further west than Lauro, where Sertorius caught and besieged him. (See the map in Figure 1.1.) Thus, Pompey and Sertorius had stalemated one another in Eastern Spain. Metellus Pius and his army were in Western Spain, where Pius was governor. This suited Sertorius, who did not want the two Roman armies to unite, and Sertorius sent his second-in-command, Hirtuleius, to garrison Laminium, northeast of Pius's camp, and prevent Pius from coming east to make contact with Pompey.

Figure 1.1. Spain, with Strategies for Hirtuleius and Pius.

HEADS UP!

Here are some concepts we will develop as this chapter goes along:

Game theory is the study of the choice of strategies by interacting rational agents, or in other words, interactive decision theory.

A key step in a game theoretic analysis is to discover which strategy is a person's best response to the strategies chosen by the others. Following the example of neoclassical economics, we define the best response for a player as the strategy that gives that player the maximum payoff, given the strategy the other player(s) has chosen or can be expected to choose.

Game theory is based on a scientific metaphor, the idea that many interactions we do not usually think of as games, such as economic competition, war and elections, can be treated and analyzed as we would analyze games.

Pius had two strategies to choose from. They are shown by the light gray arrows in the map. He could attack Hirtuleius and take Laminium, which, if successful, would open the way to Eastern Spain and deprive the rebels of one of their armies. If successful, he could then march on to Lauro and unite with Pompey against Sertorius. But his chances of success were poor. Fighting a defensive battle in the rough terrain around Laminium, the Spanish legions would be very dangerous and would probably destroy Pius’ legions. Alternatively, Pius could make his way to Gades and take ships to New Carthage, raise the siege Pompey had been unable to raise, and march on to Lauro, raising the siege of Pompey's much larger forces. To Pius, this was the better outcome, since it would not only unite the Roman armies and set the stage for the defeat of the rebels, but would also show up the upstart Pompey, demonstrating that the young whippersnapper couldn't do the job without getting his army saved by a seasoned Roman aristocrat.

Hirtuleius, a fine soldier, faced a difficult problem of strategy choice to fulfill his mission to contain or destroy Pius. Hirtuleius could march directly to New Carthage, and fight Pius at New Carthage along with the small force already there. His chances of defeating Pius would be very good, but Pius would learn that Hirtuleius was marching for New Carthage, and then Hirtuleius could divert his own march to the north, take Laminium without a fight, and break out to the northeast. Thus, Hirtuleius would fail in his mission. Alternatively, Hirtuleius could remain at Laminium until Pius marched out of his camp, and then intercept Pius at the ford of the River Baetis. He would arrive with a tired army and would fight on terrain more favorable to the Romans, and so his chances were less favorable; but there would be no possibility of losing Laminium and the Romans would have to fight to break out of their isolation.

Thus, each of the two commanders has to make a decision. We can visualize the decisions as a tree diagram like the one in Figure 1.2. Hirtuleius must first decide whether to commit his troops to the march to New Carthage or remain at Laminium where he can intercept Pius at the Baetis. Begin at the left, with Hirtuleius’ decision, and then we see the decision Pius has to make depending on which decision Hirtuleius has made. What about the results? For Hirtuleius, the downside is the simple part. If he fails to stop Pius, he fails in his mission. If he intercepts Pius at New Carthage, he has a good chance of winning. If he intercepts Pius at the ford on the Baetis, he has at least a 50–50 chance of losing the battle. On the whole, Pius wins when Hirtuleius loses. If he breaks out by taking Laminium he is successful. However, if he raises the siege of New Carthage, he gets the pleasure of showing up his boss as well. But he cannot be sure of winning if he goes to New Carthage.

Figure 1.2. The Game Tree for the Spanish Rebellion.

Figure 1.2 shows a tree diagram with the essence of Hirtuleius’ problem.

If Hirtuleius goes to New Carthage, Pius will go to Laminium and win. If Hirtuleius stays at Laminium, Pius will strike for New Carthage. Thus, the best Hirtuleius can do is to stay at Laminium and try to intercept Pius at the river.

In fact, Pius moved more quickly that Hirtuleius expected, so that Hirtuleius’ tired troops had to fight a rested Roman army. The rebels were badly beaten and ran, opening the way for Pius to continue to Gades and transport his legions by sea to New Carthage, where they raised the siege and moved on to raise the siege of Pompey in Lauro, and so Pius returned to Rome a hero. Pompey had plenty of years left to build his own reputation, and would eventually be First Man in Rome, only to find himself in Julius Caesar's headlights. But that is another story.¹

In analyzing the strategies of Pius and Hirtuleius with the tree diagram, we are using concepts from game theory.

2. WHAT DOES THIS HAVE TO DO WITH GAMES?

The story about The Spanish Rebellion is a good example of the way we ordinarily think about strategy in conflict. Hirtuleius has to go first, and he has to try to guess how Metellus Pius will respond to his decision. Somehow, each one wants to try to outsmart the other one. According to common sense, that's what strategy is all about.

There are some games that work very much like the conflict between Metellus Pius and Hirtuleius. A very simple game of that kind is called Nim. Actually, Nim is a whole family of games, from smaller and simpler versions up to larger and more complex versions. For this example, though, we will only look at the very simplest version. Three coins are laid out in two rows, as shown in Figure 1.3. One coin is in the first row, and two are in the second. The two players take turns, and on each turn a player must take at least one coin. At each turn, the player can take as many coins as he/she wishes from a single row, but can never take coins from more than one row on any round of play. The winner is the player who picks up the last coin. Thus, the objective is to put the opponent in the position that she is required to leave just one coin behind.

Figure 1.3. Nim.

There are some questions about this game that we would like to answer. What is the best sequence of plays for each of the two players? Is there such a best strategy at all? Can we be certain that the first player can win? Or the second? These are questions you might like to know the answer to, for example, if someone offered to make you a bet on a game of Nim.

Let us say that our two Nim players are Anna and Barbara. Anna will play first. Once again, we will visualize the strategies of our two players with a tree diagram. The diagram is shown in Figure 1.4. Anna will begin with the oval at the left, and each oval shows the coins that the player will see in case she arrives at that oval. Thus, Anna, playing first, will see all three coins. Anna can then choose among three plays at this first stage. The three plays are:

Figure 1.4. A Tree Diagram for Nim.

1. Take one coin from the top row.
2. Take one coin from the second row.
3. Take both coins from the second row.

The arrows shown leading away from the first oval correspond from top to bottom to these three moves. Thus, if Anna chooses the first move, Barbara will see the two coins shown side by side in the top oval of the second column. In that case Barbara has the choice of taking either one or two coins from the second row, leaving either none or one for Anna to choose in the next round as shown in the top two ovals of the third column. Of course, by taking two coins, leaving none for Anna, Barbara will have won the game.

A Closer Look: John von
Neumann, 1904–1957

Born in Budapest, Hungary, John von Neumann earned doctorates in both mathematics and chemistry, but is most known as a mathematician and one of the founders of modern computation. In addition, he made important contributions to mathematical economics. As a co-author with Oskar Morgenstern, he wrote the founding book of game theory, The Theory of Games and Economic Behavior.

In a similar way, we can see in the diagram how Anna's other two choices leave Barbara with other alternative moves. Looking to strategy 3, we see that it leaves Barbara with only one possibility; but that one possibility means that Barbara wins. From Anna's point of view move 2, in the middle, is the most interesting. As we see in the middle oval, second column, this leaves Barbara with one coin in each row. Barbara has to take one or the other — those are her only choices. But each one leaves Anna with just one coin to take, leaving Barbara with nothing on her next turn, and thus winning the game. We can now see that Anna's best move is to take one coin from the second row, and once she has done that, there is nothing Barbara can do to keep Anna from winning.

Now we know the answers to the questions above. There is a best strategy for the game of Nim. For Anna, the best strategy is “Take one coin from the second row on the first turn, and then take whichever coin Barbara leaves.” For Barbara, the best strategy is “If Anna leaves coins on only one row, take them all. Otherwise, take any coin.” We can also be sure that Anna will win if he plays her best strategy.

3. GAME THEORY EMERGES

Early in the 20th century, mathematicians began to study some relatively simple games and, later, much more complex games like Chess. These studies were the beginning of game theory. The great mathematician John von Neumann extended the study to games like poker. Poker is different from Nim and Chess in a fundamental way. In Nim, each player always knows what moves the other player has made. That's also true in Chess, even though Chess is very much more complex than Nim. In poker, by contrast, you may not know whether or not your opponent is “bluffing.” Games like Nim and Chess are called games of perfect information, since there is no bluffing, and every player always ...