eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
Product Details
| ISBN-13: | 9780486154428 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 10/17/2012 |
| Series: | Dover Books on Mathematics |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 384 |
| File size: | 14 MB |
| Note: | This product may take a few minutes to download. |
Read an Excerpt
Introduction to the Theory of Games
By J.C.C. McKinsey
Dover Publications, Inc.
Copyright © 2003 Dover Publications, Inc.All rights reserved.
ISBN: 978-0-486-15442-8
CHAPTER 1
RECTANGULAR GAMES
1. Introduction. In this book we shall be concerned with the mathematical theory of games of strategy. Examples of parlor games of strategy are such games as chess, bridge, and poker, where the various players can make use of their ingenuity in order to outwit each other. Aside from this application within the sphere of social amusement, the theory of games is gaining importance because of its general applicability to situations which involve conflicting interests, and in which the outcome is controlled partly by one side and partly by the opposing side of the conflict. Many conflict situations which form the subject of economic, social, political, or military discourse are of this kind.
Although many real-life conflicts as well as parlor games involve elements of chance (as in the cards dealt in bridge or the weather encountered in a military operation), we shall ordinarily exclude from our discussion games in which the outcome depends entirely on chance and cannot be affected by the cleverness of the players.
The essential difference between games of strategy and games of (pure) chance lies in the circumstance that intelligence and skill are useful in playing the former but not the latter. Thus an amateur would be extremely unwise to play chess for even money and high stakes against a master: he would face almost certain ruin. But, contrary to the stories occasionally heard (stories which are most likely fabricated by the proprietors of gaming houses), there is no "system" for playing roulette on an unbiased wheel: an idiot has as good a chance of winning at this game as has a man of sense. (This is not to say that there do not remain difficult unsolved mathematical problems in connection with games of chance; but there exist, at least, standard methods for attacking such problems, and we shall not treat of them here.)
Although our attention will be devoted almost entirely to the purely mathematical aspects of the theory of games of strategy, it is perhaps well to begin with some brief remarks about the history of economics. These remarks may serve to convince the student that our theory is not altogether frivolous; for buying and selling are customarily regarded as more serious and respectable occupations than is playing poker—or even chess, for that matter.
For many decades economists tended to take as a standard model for their science the situation of Robinson Crusoe, marooned on an uninhabited island and concerned with behaving in such a way as to maximize the goods he could obtain from nature. It was generally felt that it would be possible to get an insight into the behavior of groups of individuals by starting with a detailed analysis of the behavior proper in this simplest possible case: the case of a single individual all alone and struggling against nature.
This line of attack on economic problems, however, suffers from the defect that in going from a one-man society to even a two-man society, qualitatively different situations arise which could hardly have been foreseen from the one-man case. In a society which contains two members, it may happen that each desires a certain commodity (the supply of which is not sufficient for both) and that each member has control of some, but not all, of the factors which determine how the commodity is to be distributed. The behavior of each, then, if it is to be rational, must take into account the expected behavior of the other. No such situation as this can arise in the one-man case, where the one member of society is concerned simply with maximizing the amount of the commodity he is to receive from nature. For, though we often personify nature (by capitalizing the word and even by treating it as being of feminine gender) and though we sometimes poetically speak of the "perverseness" of nature, no one seriously believes that nature is really a conscious being, who takes thought about what we are to do and adjusts her own behavior accordingly.
In a society with two or more members, entirely new problems appear which are radically different from anything found in a one-man society. For this reason it is not possible to determine the properties of ordinary society by simply extrapolating from the case of a Robinson Crusoe society.
It was through considerations of this sort that the mathematician John von Neumann was led, some twenty years ago, to believe that economics could more profitably be viewed under the analogy to parlor games (of strategy) than under the simpler analogy to the analytic problem of finding maxima and minima. This approach to economics has by now been explored rather thoroughly by mathematicians as well as by economists. References to the relevant books and papers can be found in the Bibliography at the end of this book.
(In connection with the question of guessing at the economic laws of an n-man society by using the laws of a one-man society, it should be remarked that, rather paradoxically, a better approximation is obtained in this way to the case that n is large, than to the case that n is small but greater than one. For if Smith has only one competitor, he must take account of the very real possibility that his antagonist will behave in a rational way—that he will even, indeed, attempt to guess what Smith is going to do, and to adjust his own behavior accordingly. And if Smith has but a few competitors, he should not neglect the possibility that they may all behave rationally, or that they may combine together in a coalition against him and thus, in essence, behave as if they were but one. But as n becomes very large, the probability that a large proportion of Smith's opponents will behave rationally becomes small, and the advantage they could gain by combining against him becomes negligible. Therefore, it becomes increasingly plausible for Smith to assume that the average behavior of the rest of the population is determined by prevalent superstitions and fallacies, for instance, or by the average level of intelligence; and it becomes reasonable for Smith to feel confidence in his predictions of the behavior of his competitors—e.g., predictions based on their past behavior—and to treat the rest of mankind like a part of nature. But the advocate of Robinson Crusoe economics, before he becomes too complacent from considering this little paradox, should reflect that in modern society men tend to combine into a few large coalitions—corporations, cooperatives, labor unions, and the like—which, for many practical purposes, behave like individual human beings.)
It should be mentioned, finally, that the theory of games of strategy can be expected to find practical application in domains which would not ordinarily be regarded as economic: to the problems arising in connection with courtship and marriage, for instance, where the end in view is not necessarily monetary; or to the problems which confront a politician trying to get elected to office in a country which allows more than one candidate to have his name on the ballot. It is possible that this theory will throw light on all kinds of situations in which various people have opposing goals and in which each of them, although he may exert some influence on the outcome, cannot completely dominate the course of events.
2. Terminology, and Classification of Games. The word "game," as used in everyday English, is ambiguous. Sometimes, as when we say "Chess is a more difficult game than checkers," we use the word "game" to refer to a set of rules and conventions for playing; at other times, as when we say "I played three games of chess last night," we use the word to refer to a particular possible realization of the rules. For our purposes, it is convenient to distinguish these two notions: accordingly, we shall use the word "game" only for the first meaning and shall employ the word "play" for the second meaning. Thus we shall still say "Chess is a more difficult game than checkers," but now we shall say "I played three plays of chess last night."
In a similar way, we shall use the word "move" to mean a point in a game at which one of the players (or chance, in some cases) picks out an alternative from some set of alternatives, and we shall use the word "choice" to mean the alternative picked out. (In ordinary speech, the word "move" is used, ambiguously, for both notions.) Thus we shall say "Black won by a clever choice in his tenth move."
The number, and variety, of games of strategy is enormous. We shall now indicate some modes of classification.
We first distinguish a game according to the number of players: one-person games, two-person games, and so on. Solitaire, for example, is a one-person game and chess is a two-person game. When we call a game n person, however, we do not necessarily mean that in every play of it exactly n people participate, but, rather, merely that the rules of the game are such that the players fall into n mutually exclusive sets in such a way that the people within each set have identical interests. These n sets of people with identical interests are referred to as "persons" (just as, in law, a corporation is referred to as a person). For example, although chess is ordinarily played by just two people, it could also be played by two "teams," each consisting, say, of three people; and even if this were done, the game would still be chess and would still be a two-person game, not a six-person game. In the same way, bridge is to be regarded as a two-person game, not a four-person game, since North and South have identical interests and are therefore considered as one person, and East and West are similarly considered as one person.
When people play social games, they sometimes decide that at the end of the play they will make monetary payments among themselves in a manner determined by the rules of the game. This is almost always done, for example, in games of pure chance such as craps (since otherwise these games would hardly be interesting to play), and it is usually done in poker and often in bridge. In other cases, the players keep track of the "score," so that at the end of the play numbers are calculated which measure the relative skill with which the participants have played, but no money is exchanged; this is often done in bridge, for example. Finally, in some cases, no attempt is made even to calculate any kind of scores, but it is simply announced who has "won" and who has "lost"; this is usually done, for example, in ticktacktoe, checkers, and chess. For our purposes, however, it turns out to be convenient to neglect the second and third of the above alternatives and to speak as though all games were played for money; thus we shall usually speak of the "payments" made among the players at the end of a play and shall think of these payments as sums of money. (The assumption that there are money payments may appear to constitute simply a limitation of our field of inquiry; but it is also possible to argue that, even when no money changes hands, the players derive pleasure or pain from their relative scores and to maintain that they would be able, if questioned, to set a monetary value to their experiencing the emotions in question—so that the game could just as well be conceived as being played for these equivalent sums of money. But we do not want to enter into these knotty problems about value, which lie in the province of economics or philosophy rather than in that of mathematics.)
Suppose, now, that we consider a play of an n-person game with players P1, P2, ..., Pn and let pi (for i = 1, ···, n) be the payment made to Pi at the end of the play (if Pi has to pay, pi is negative). Then if
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
we call the play zero-sum. If every possible play of a game is zero-sum, we call the game itself zero-sum. It is clear that all the ordinary parlor games which are played for money are zero-sum, since wealth is neither created nor destroyed in the course of playing them. But non-zero-sum games are nevertheless very important; for if we wish to find models for economic processes in the theory of games, then we shall be forced to consider non-zero-sum games, since economic processes usually create (or destroy) wealth. It can happen that an economic process increases (or decreases) the wealth of each of the participants.
We can also classify games according to how many moves they have. Thus ticktacktoe, when played to the bitter end, has nine moves, five of which are made by one player and four by the other. Some games do not have all of their plays of the same length—a play of chess may be short or long, depending on the relative skill of the two players.
A finite game has a finite number of moves, each of which involves only a finite number of alternatives; other games are called infinite.
Finally, games can be classified according to the amount of information available to the players regarding the past choices. In checkers and chess, for example, players are kept informed at all times as to what the previous choices have been; but in bridge a player does not know what cards have been dealt to the other people and is therefore in partial ignorance. It is clear that, starting out with a given game, it is possible to get an entirely different game by altering the rules regarding the information to be given to the players. Thus bridge would become a quite different game if everyone had to expose his cards at the beginning of the play. And one obtains from chess a completely new game (called Kriegsspiel) by denying to the players information about the choices of their opponents.
3. Definition of Rectangular Games. A zero-sum one-person game presents no intellectual difficulties; for regardless of what the one player does, he gets zero, and he may as well do one thing as another. In playing a non-zero-sum one-person game, the player has merely to solve an ordinary maximization problem: he must simply pick out from among the various courses of action open to him the one which will maximize his gain, or, in case the game involves also some chance moves, the one which will maximize his mathematical expectation of gain. Thus, in order to study the characteristic properties of games of strategy, it is necessary to go to games which involve more than one player.
We shall begin our studies with the case of two-person zero-sum games where each player has but one move. The first player chooses a number from the first m positive integers, and the second player, without being informed what choice the first player has made, chooses a number from the first n positive integers. The two numbers are then compared, and one of the players pays the other an amount, depending on the choices made, which is specified by the rules of the game. In order to have a name for such games, we shall call them, rather arbitrarily, rectangular games. (We are going to see later that rectangular games do not constitute such an extremely special kind of games as might appear at first glance; a very wide variety of other games can be put into the form of rectangular games.)
An example of a rectangular game is the following. Player P1 chooses a number from the set {1, 2, 3} and player P2, without having been informed what choice P1 has made, chooses a number from the set {1, 2, 3, 4}. After the two choices have been made, P2 pays P1 an amount given by the following table:
[TABLE OMITTED]
That is to say, if, for example, P1 chooses 1 and P2 chooses 3, then P2 pays P1 ten dollars (or ten cents, or ten of whatever has been taken as the unit of money). If P1chooses 3 and P2 chooses 2, then P2 pays P1 minus five dollars; i.e., P1 pays P2 five dollars. For the sake of brevity, we shall henceforth describe such a game as this by giving merely the payoff matrix:
[TABLE OMITTED]
(Continues...)
Excerpted from Introduction to the Theory of Games by J.C.C. McKinsey. Copyright © 2003 Dover Publications, Inc.. 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
1. Rectangular Games2. The Fundamental Theorem for Rectangular Games
3. The Solutions of a Rectangular Game
4. A Method of Approximating the Value of a Game
5. Games in Extensive Form
6. Games in Extensive Form--General Theory
7. Games with Infinitely Many Strategies
8. Distribution Functions
9. Stieltjes Integrals
10. The Fundamental Theorem for Continuous Games
11. Separable Games
12. Games with Convex Payoff Functions
13. Applications to Statistical Inference
14. Linear Programming
15. Zero-sum n-Person Games
16. Solutions of n-Person Games
17. Games Without Zero-sum Restriction: The von Neumann-Morgenstern Theory
18. Some Open Problems
Bibliography. Index.