eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
Product Details
| ISBN-13: | 9780486150062 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 10/17/2012 |
| Series: | Dover Books on Mathematics |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 208 |
| File size: | 18 MB |
| Note: | This product may take a few minutes to download. |
Read an Excerpt
The Mathematics of Games of Strategy Theory and Applications
By Melvin Dresher
Dover Publications, Inc.
Copyright © 1981 The Rand CorporationAll rights reserved.
ISBN: 978-0-486-15006-2
CHAPTER 1
GAME, STRATEGY, AND SADDLE-POINT
1. INTRODUCTION
The theory of games of strategy may be described as a mathematical theory of decision-making by participants in a competitive environment. In a typical problem to which the theory is applicable, each participant can bring some influence to bear upon the outcome of a certain event; no single participant by himself nor chance alone can determine the outcome completely. The theory is then concerned with the problem of choosing an optimal course of action which takes into account the possible actions of the participants and the chance events.
Examples of games of strategy are parlor games such as poker, chess, and bridge, military games such as the defense of targets against attack, and economic games such as the price competition between two sellers. Each of these games of strategy allows the players to make use of their ingenuity in order to influence the outcome. Although some of these games involve elements of chance (e.g., the cards dealt in poker and the hit of a target), we shall exclude from our discussion games of chance such as blackjack and craps since their outcomes depend entirely upon chance and cannot be influenced by the decisions of the players.
Games of chance have been studied mathematically for many years; the mathematical theory of probability was developed from their study. Although strategic situations have long been observed and recorded, the first attempt to abstract them into a mathematical theory of strategy was made in 1921 by Emile Borel. The theory was firmly established by John von Neumann in 1928 when he proved the minimax theorem, the fundamental theorem of games of strategy. However, it was not until the publication in 1944 of the impressive work, Theory of Games and Economic Behavior, by John von Neumann and Oskar Morgenstern, that the mathematical theory of games received much attention. This book emphasized a new approach to the general problem of competitive behavior through a study of games of strategy. Since then the theory has been applied to game-like problems—not only in economics, but also in the military and politics.
2. DESCRIPTION OF A GAME OF STRATEGY
A game of strategy is described by its set of rules. These rules specify clearly what each person called a player is allowed or required to do under all possible circumstances. The rules define the amount of information, if any, each player receives. If the game requires the use of chance devices, the rules describe how the chance events shall be interpreted. They also define the time the game ends, the amount each player pays or receives, and the objective of each player.
From the rules we can obtain such general properties of the game as the number of moves, the number of players, and the payoff. The game is finite if each player has a finite number of moves and a finite number of choices available at each move. It is convenient to classify games according to the number of players, i.e., as 2-person, 3-person, etc. It is also convenient to distinguish between games whose payoffs are zero-sum and those whose are not. If the players make payments only to each other, the game is said to be zero-sum.
We shall first analyze the 2-person, zero-sum, finite game—most parlor games and many military games are of this type. It is clear that in such a game the winnings of one player are the losses of the other player.
To simplify the mathematical description of a game, we introduce the concept of a "strategy." In the actual play of a game, instead of making his decision at each move each player may formulate in advance of the play a plan for playing the game from beginning to end. Such a plan must be complete and cover all possible contingencies that may arise in the play. Among other things, this plan would incorporate any information which may become available to the player in accordance with the rules of the game. Such a complete prescription for a play of a game by the player is called a strategy of that player. A player using a strategy loses no freedom of action since the strategy specifies the player's actions in terms of the information that might become available.
We may think of a strategy of a player as a set of instructions for playing the given game from the first move to the last. Conversely, each different way that a player may play a game is a strategy of that player. If we enumerate all the different ways for a player to play the game, we obtain all the strategies of that player. Of course, many of these strategies may be obviously poor ones, but they are included in the initial enumeration.
Every pair of strategies, consisting of one strategy for each player, determines a play of the game, which in turn determines a payoff to each player. Thus we may consider a play of a game to consist of each player's making one decision, namely the selection of a strategy.
In terms of this notion of strategy, we can now describe, corresponding to any given game, an equivalent game of much simpler character. Let us call the two players Blue and Red. Suppose Blue has m strategies, which may be designated by the numbers
i = 1, 2, ..., m.
Suppose Red has n strategies, which we may designate by
j = 1, 2, ..., n.
Then on the first move Blue chooses some strategy i. On the next move, Red, without being informed what choice Blue has made, chooses strategy j. These two choices determine a play of the game and a payoff to the two players. Let aij be the payoff to Blue. Since the game is zero-sum, the payoff to Red is - aij.
The game is thus determined by Blue's payoff matrix,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
In this matrix each Blue strategy is represented by a row; each Red strategy is represented by a column. If Blue chooses the ith strategy or ith row and Red chooses the j th strategy or jth. column, then Red is to pay Blue the amount aij. Blue wants aij to be as large as possible, but he controls only the choice of his strategy i. Red wants aij to be as small as possible but he controls only the choice of his strategy j. What are the guiding principles which should determine the choices and what is the expected outcome of the game?
3. ILLUSTRATIVE EXAMPLES
Example 1. Function of a Field Commander.
Military action by a commander against an enemy requires him to evaluate a situation and make a decision. The evaluation is made by considering the given mission, the capabilities of the enemy, and the possible courses of action available to both sides, and by comparing the likely consequences of one's own courses of action. These are the rules of the game. From his possible courses of action, the commander selects an optimal one—a course which promises to be most successful in accomplishing the mission.
The military doctrine covering the above evaluation is discussed in detail in the Naval Manual of Operational Planning of the Naval War College. The Manual states, "Each of our own courses of action ... is separately weighed in turn against each capability of the enemy which may interfere with the accomplishment of the mission. The results to be expected in each case are visualized. The advantages and disadvantages noted as a result of the analysis for each of our own courses of action are summarized and the various courses of action are compared and weighed." A commander thus enumerates the possible opposing courses of action and their outcomes. Each course of action is a strategy for the commander and each outcome yields a payoff.
Suppose that the mission of the Blue forces is to capture an objective defended by the Red forces. The Blue commander analyzes the possible courses of action within the capabilities of the Red forces which can affect the capture of the objective. Then Blue lists the various ways of capturing the objective. Let us assume that this yields three possible courses of action, r1, r2, r3, to the Red commander and three possible courses of action, b1, b2, b3, to the Blue commander. There are then nine possible outcomes which may be summarized by a 3 × 3 matrix. For example, the matrix may have the following descriptive entries:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
In this illustrative situation, the Blue commander estimates that if he uses strategy b1, for example, and the Red commander uses r1, Blue will fail to capture the objective. However, Blue will succeed if he uses strategy bi and the Red commander uses strategy r2 or r3. Similarly, the remaining six outcomes are the Blue commander's evaluation of the outcomes with respect to various courses of actions.
The problem of the Blue commander is to select the best course of action, or the strategy which will secure for him the most likely chance of capturing the objective. The Red commander will likewise try to select his best course of action, or that strategy which will minimize Blue's chance of capturing the objective. We thus have the following problem in competitive behavior: Blue wishes to maximize the outcome by a proper choice of his strategy, and Red wishes to minimize this same outcome, also by a proper choice of Red's strategy, where the outcome depends upon both Blue's and Red's choices.
The established doctrine of the "Estimate of the Situation" dictates the selection of the course of action which promises to be most successful in the accomplishment of the mission regardless of the course selected by the Red commander. Accordingly, Blue would choose, in this illustrative example, strategy b2 which yields either a successful outcome or a draw. For if the Blue commander uses a strategy b2 or b3 he may fail to accomplish the mission. Strategy b2 represents the most conservative decision of the Blue commander. It is equivalent to assuming that the Red commander can find out the decision of the Blue commander. In a later section we shall see how the Blue commander can, by taking chances, or bluffing, obtain on the average a more advantageous outcome. He accomplishes this by mixing his strategies, or by choosing his strategy with a chance device.
Example 2. The Game "Morra."
This is a game which has only personal moves. Each player shows one, two, or three fingers and simultaneously calls his guess of the number of fingers his opponent will show. If just one player guesses correctly, he wins an amount equal to the sum of the fingers shown by himself and his opponent; otherwise the game is a draw.
This game consists of one move for each player—the choice of a number to show and a number to guess. We may represent a strategy for each player by a pair of numbers (s, g), where s = 1, 2, 3 is the number of fingers he shows and g = 1, 2, 3 is his guess of the number of fingers his opponent will show. It is evident that each player has nine strategies, and thus there are 81 different possible plays of the game. With each of these 81 ways of playing the game, there is associated a payment to the players, as described by the rules of the game. These payments are summarized by a payoff matrix. In the following payoff matrix, the entries represent payments to Blue. Red will receive the negative of these payments.
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Example 3. The Game "Le Her."
This game involves both chance and personal moves. Although the game can be played by several people, we shall describe it for two players. From an ordinary deck of cards, a dealer gives a card at random to a receiver and takes one himself; neither player sees the other's card. The main object is for each to obtain a higher card than his opponent. The order of value is ace, two, three, ..., ten, jack, queen, king. Now if the receiver is not content with his card, he may compel the dealer to change with him; but if the dealer has a king, he is allowed to retain it. If the dealer is not content with the card which he at first obtained, or which he has been compelled to take from the receiver, he is allowed to change it for another taken out of the deck at random; but if the card he then draws is a king, he is not allowed to have it, but must keep the card which he held after the receiver exercised his option. The two players then compare cards, and the player with the higher card wins. If the dealer and receiver have cards of the same value, the dealer wins.
This game consists of three moves: The first move is a chance move, one card each being dealt at random to the receiver and dealer. The second move is a personal move by the receiver, who exchanges his card with the the dealer or stays with the original card. The third move is a personal move by the dealer, who exchanges his card with a card from the deck or stays with the card he holds.
The game can be summarized by defining a strategy for the receiver to be a determination of change or stay for each of the thirteen cards he may receive. One such strategy might be
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
where "C" means change and "S" means stay. Thus, the above strategy tells the receiver to change if he receives an ace, stay if he receives a two, change if he receives a three, ..., change if he receives a queen, stay if he receives a king. Note that the strategy is a complete set of instructions. It is apparent that the receiver has 213 strategies. Of course, most of them are poor strategies and should not be played, as will be described in a subsequent section.
Since the dealer's personal move, the third move of the game, is made after the receiver has exercised his option, the dealer may then have information about the receiver's card. Therefore a strategy for the dealer must include this information. However, to simplify the enumeration of the dealer's strategy, let us make the following two observations about rational behavior of the dealer:
(i) If the receiver exchanges cards with the dealer and the dealer thereby obtains a lower card than the receiver, then the dealer should exchange with the deck.
(ii) If the receiver exchanges cards with the dealer and the dealer thereby obtains a card at least as high as the receiver's, then the dealer should stay with that card.
Let us refer to these two instructions of rational behavior as R. They have the effect of eliminating obviously poor strategies. Now the strategies of the dealer may be enumerated in a manner similar to those of the receiver and at the same time incorporate the information about the receiver. A strategy for the dealer may be written as follows:
(R; S C C S ... S C).
This strategy tells the dealer to do the following: if the receiver exchanges cards, the dealer follows the two instructions R of rational behavior; if the receiver stays with his card and the dealer holds an ace, then the dealer stays; if the receiver stays and the dealer holds a two, then the dealer changes with the deck; etc. The dealer now has 213 strategies. Again, most of these strategies will turn out to be poor strategies as will be described in a later section.
Example 4. Colonel Blotto Game.
Colonel Blotto and his enemy each try to occupy two posts by properly distributing their forces. Let us assume that Colonel Blotto has 4 regiments and the enemy has 3 regiments which are to be divided between the two posts. Define the payoff to Colonel Blotto at each post as follows: If Colonel Blotto has more regiments than the enemy at the post, Colonel Blotto receives the enemy's regiments plus one (the occupation of the post is equivalent to capturing one regiment); if the enemy has more regiments than Colonel Blotto at the post, then Colonel Blotto loses one plus his regiments at the post; if each side places the same number of regiments, it is a draw and each side gets zero. The total payoff is the sum of the payoffs at the two posts.
Colonel Blotto has 5 strategies, or five different ways of dividing 4 regiments between the two posts. The enemy has 4 strategies, or four different ways of dividing his 3 regiments. There are therefore twenty ways for the two sides to distribute their forces.
It is evident that if Colonel Blotto places 3 regiments at the first post and 1 at the second, and if the enemy places 2 regiments at the first post and 1 at the second, then Blotto wins what amounts to 3 regiments. However, if Colonel Blotto places 2 regiments at each post and the enemy places all of his 3 regiments at either post, then Colonel Blotto loses 2 regiments. The following payoff matrix summarizes the payment to Colonel Blotto for each of the twenty possible distributions:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Example 5. A Coin Guessing Game.
Two players secretly choose to conceal 0, 1, or 2 coins. Each, in agreed turn, tries to guess exactly the total number concealed by the two players. However, the second guesser must guess a different number from that called by the first. If a player guesses correctly, he receives 1 from the other; otherwise 0.
(Continues...)
Excerpted from The Mathematics of Games of Strategy Theory and Applications by Melvin Dresher. Copyright © 1981 The Rand Corporation. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
Contents
1 GAME, STRATEGY, AND SADDLE-POINT,2 THE FUNDAMENTAL THEOREM,
3 PROPERTIES OF OPTIMAL STRATEGIES,
4 GAMES IN EXTENSIVE FORM,
5 METHODS OF SOLVING GAMES,
6 GAMES WITH INFINITE NUMBER OF STRATEGIES,
7 SOLUTION OF INFINITE GAMES,
8 GAMES WITH CONVEX PAYOFF FUNCTIONS,
9 GAMES OF TIMING—DUELS,
10 TACTICAL AIR-WAR GAME,
11 INFINITE GAMES WITH SEPARABLE PAYOFF FUNCTIONS,
BIBLIOGRAPHY,
INDEX,