Mathematical in Games, Programming, Volume I MATRIX GAMES, PROGRAMMING, AND MATHEMATICAL ECONOMICS Methods and Theory and Economics by SAMUEL KARLIN Stanford University ΎΎ PERGAMON PRESS LONDON-PARIS 1959 ADDISON-WESLEY PUBLISHING COMPANY, INC. READING, MASSACHUSETTS, U.S.A. LONDON, ENGLAND Copyright © 1959 ADDISON-WESLEY PUBLISHING COMPANY, INC. Printed in the United States of America ALL RIGHTS RESERVED. THIS BOOK, OR PARTS THERE­ OF, MAY NOT BE REPRODUCED IN ANY FORM WITH­ OUT WRITTEN PERMISSION OF THE PUBLISHER. Library of Congress Catalog Card No. 60-5402 Sole distributors in the United Kingdom: PERGAMON PRESS LTD. 4 and 5 Fitzroy Square, London W. 1 PERGAMON PRESS S.A.R.L. 24 Rue des Écoles, Paris Ve PREFACE The mathematics involved in decision making is playing an increasingly important role in the analysis of management problems, in economic studies, in military tactics, and in operations research. These areas of application have led to challenging new types of mathematical structures. The development of game theory, linear and nonlinear programming, and mathematical economics marks one significant aspect of this kind of mathematics. Essentially, these volumes are an attempt at a preliminary synthesis of the concepts of game theory and programming theory, together with the concepts and techniques of mathematical economics, into a single sys­ tematic theory. Secondarily, I hope they will prove useful as textbooks and reference books in these subjects, and as a basis for further study and research. The coverage of these volumes is in no sense exhaustive; I have stressed most what appeals to me most. At the same time, I have tried to supply the necessary routine and basic information on which a proper under­ standing of game theory and programming depends. The presentation of each subject is designed to be self-contained and completely rigorous, but every effort has been made to bring out the conceptual depth and formal elegance of the over-all theory. In both volumes, the principles of game theory and programming are applied to a variety of simplified problems based on economic models, business decision, and military tactics in an attempt to clarify the key mathematical concepts involved and suggest their applicability to other similar problems. Each chapter includes a certain amount of advanced exposition, which is generally incorporated in starred (*) sections. Elementary background material is presented in the appendixes, and more advanced background material is incorporated directly in the text. Each chapter contains problems of various degrees of difficulty, many of them leading to extensions of the theory. Solutions to most of the problems and hints for solving others are given at the end of each Part. The three Parts (Parts I and II in Volume I, and Volume II, which comprises Part III) are independent of each other except for the material in starred sections, and may be studied independently in conjunction with the relevant appendixes. For the readers convenience, a diagram showing the interrelationships of the various nonadvanced portions of Parts I and II of Volume I is presented on the following page. Each chapter ends with a section of historical remarks, general comments on technical details, and citations of books and articles that may profitably be consulted for further information. All references cited are listed in the v VI PREFACE bibliography at the close of each book. In some instances the historical remarks consist in assigning priorities to notable discoveries; any inac­ curacies or omissions along these lines are wholly unintentional and deeply regretted. My indebtedness extends to many, and not least to Stanford University, California Institute of Technology, the RAND Corporation, and the Office of Naval Research, all of which provided facilities, intellectual stimulation, and encouragement without which these books might never have been written. Among my academic colleagues, I am grateful to Professors Bowker, Lieberman, Madow, Parzen, and Scarf of Stanford for their constant en­ couragement; to Professor H. F. Bohnenblust of California Institute of Technology, who introduced me to this field of study and who taught me more than I know how to acknowledge; to my students Rodriguez Restrepo and R. V. Miller, who wrote up my initial lectures on which the material of these books is based; to my students William Pruitt and Charles Stone, each of whom made valuable suggestions for organizing and improving the final manuscript; to Professors Hirofumi Uzawa and K. J. Arrow, who taught me most of what I know about mathematical economics; to my friends Melvin Dresher, Ray Fulkerson, and Harvey Wagner for their helpful comments on the first six chapters; and to Irving Glicksberg for assistance in developing the appendixes. Finally, I am indebted to J. G. Bell, Jr., for helping to straighten out my syntax; to Frieda Gennerich, Sally Morgan, and Babette Doyle for their superb technical typing; and above all to my wife, who has offered warm encouragement, unbounded patience and kind consideration during these trying years of writing. SAMUEL KARLIN Stanford, California August 1959 LOGICAL INTERDEPENDENCE OF THE VARIOUS CHAPTERS {applies only to unstarred sections of each chapter) PART I PAR! 1 II Chap. 1 Chap. 5 / \ Chap. 2 Chap. 6 Chap. 7 / \ 1 Chap. 3 Chap. 4 Chap. 8 1 1 Chap. 9 INTRODUCTION THE NATURE OF THE MATHEMATICAL THEORY OF DECISION PROCESSES Section 1. The background. The art of making optimal judgments according to various criteria is as old as mankind ; it is the essence of every field of endeavor from volleyball to logistics. The science of making such judgments, as opposed to the mere art, is a newer development, and the mathematical theory of decision-making is newer still—only a little over twenty years old. It has grown fast. Particularly in this last decade, we have seen a rapid spread of the use of scientific disciplines in economic planning, military strategy, business management, and systems engineer­ ing. There has been a steady interplay between the more careful formula­ tion of business and logistics problems and the development of the mathe­ matical tools needed for their solution. Along with and partly as a result of advances in game theory, linear programming, and queueing theory, there have grown up new practical disciplines whose very names were un­ known forty years ago : operations research, management science, systems analysis, and a score of others. All these disciplines are concerned with the same fundamental task, that of scientifically analyzing various possible courses of action with a view to determining which course is "best" under the circumstances. What a decision problem is must be clearly defined. Specifically, the possible courses of action, their consequences, the objectives of the various participants, and the nature of the random effects must be ascertained. From here on, the theory tries to evaluate and make comparisons of the various alternatives of action in terms of the objectives. A decision problem typically has four parts: (1) a model, expressing a set of assumed empirical relations among the set of variables; (2) a specified subset of decision variables, whose values are to be chosen by the firm or other decision-making entity; (3) an objective function of the variables, formu­ lated in such a way that the higher its value, the better the situation is from the viewpoint of the firm ; and (4) procedures for analyzing the effect on the objective function of alternative values of the decision variables. The main component of a decision problem is the model. The following definition may help explain the significance and scope embodied in this concept. A model is a suitable abstraction of reality preserving the essen­ tial structure of the problem in such a way that its analysis affords insight into both the original concrete situation and other situations which have the same formal structure. 1 2 INTRODUCTION Model building has become increasingly widespread in these past years, particularly in the social sciences. Modern psychologists approach the study of learning processes in terms of a model involving stochastic variables. Econometricians, drawing on game theory and programming theory, have developed global equilibrium models in an attempt to under­ stand the relationship of consumption, production, and price units in a competitive economy. Some political scientists are using the concepts of n-person game theory in an effort to analyze the power relationships that govern the decisions of legislative bodies. More and more business firms are applying rigorous mathematical thinking to management problems, inventory problems, production problems. Engineers are engaged in in­ tensive studies in the new field of systems analysis, whose main technique consists of simulating idealized models of a given operation. The basic mathematics used in these studies is a mixture of the mathematical con­ cepts and thinking processes of statistics, probability, and general de­ cision theory. The past fifty years have been years of fruitful fermentation in the disciplines of probability, stochastic processes, and statistics on the one hand, and have witnessed the development of game theory and linear programming on the other. These mathematical disciplines are the natural tools for the analytical investigation of problems arising in the social and managerial sciences. In this respect it is interesting to compare briefly the usefulness of probability, statistics, and decision theory with that of the other types of pure and applied mathematics. The development of classical mathematics was principally inspired by problems based on phenomena in the fields of physics and engineering. In the usual classical physics problem, the variables of the system are seen to satisfy a system of well-defined deterministic relations. All parameters of the problem can be assumed known or accurately measurable, and one seeks to determine the relations between them in order to predict exactly what will happen in similar or analogous circumstances in the future. Until recently scientists were primarily concerned with just such determin­ istic problems, problems that could be solved, by and large, by the methods of partial differential equations and related mathematical techniques. Clearly, however, these deterministic concepts and techniques are not altogether suitable for the social sciences, which typically present problems involving uncertainties and variability. Whenever human beings play a crucial role in the formulation of a model, we must allow for the unknown and sometimes random character of human actions, and for the randomness inherent in the environment in general, if we are to arrive at meaningful results. It is therefore inevitable that students of human behavior should be concerned prominently with the theories of probability, statistics, and decision analysis of the kind embodied in game theory and linear pro­ gramming. INTRODUCTION 3 The reverse is also true: mathematicians and statisticians are increas­ ingly concerned with the analytical problems originating from the analysis of human behavior. It is now no longer exclusively the physical sciences and engineering, but also the social and management sciences, that signal promising new directions for mathematical research. There are two aspects to this research : the construction of the model, in which probability and stochastic processes play a fundamental role, and the normative essence of the model (optimization), the province of statis­ tics, game theory, decision theory, and operations research. In practice these two aspects are inseparable. Obviously, to understand how to optimize the objective function, it is necessary to understand the structure and mechanism of the model; and to construct a model properly, it is necessary to understand what use is to be made of it. In order to properly delimit the scope of these researches, we also men­ tion the descriptive significance in the study of mathematical model building. This is in contrast to the normative essence of the model which we have emphasized. From the standpoint of mathematical models in psychology and sociology, the bulk of current literature is concerned with the orientation of the model toward empirical adequacy. On the other hand, the model based on situations in management, economics, and statistics is more concerned with the kind of normative questions of rational behavior theory (game and decision theory) to which we devote our main attention. Inevitably the techniques of probability, statistics, and decision theory interact, and developments in each lead to developments in the others. As a result, the determination of optimum procedures for decision problems must be considered not in terms of half a dozen, or three, or two more or less separate sets of techniques, but in terms of a single over-all analytical methodology. It is this methodology, in the context of game theory, programming, and mathematical economics, that we seek to delineate in this book. We may summarize our aims as an attempt to unify the mathematical tech­ niques of the field and to help crystallize the concepts underlying these kinds of decision problems. It is not our purpose to propose a formal structure which will encompass all problems in the areas covered. We do not concentrate on definitions and abstractions per se. Rather, we attempt to develop in detail the principal mathematical methods that are applicable, putting emphasis wherever possible on mathematical proto­ types and their analyses. Section 2. The classification of the mathematics of decision problems. Our purpose in this section is to describe various useful mathematical classifications of decision problems that are also applicable to the theory of games, programming, and mathematical economics. 4 INTRODUCTION I. Decision problems can be divided into two contrasting types—static problems and dynamic problems. A static decision problem is one in which the variables do not involve time explicitly. A dynamic model is one in which time plays a very decisive role. The distinction between static and dynamic problems is not always clear. Often a static situation is a stationary state of a dynamic situation, i.e., an equilibrium phase achieved by a dynamic process that has been in operation over a long period of time. Or an ostensibly dynamic process can be regarded as static, as when the same variables are introduced at the successive time points as new variables. Nevertheless there is an intrinsic difference in concept and technique between the two kinds of problems which will be manifest throughout the detailed analysis. The principal technical difference between dynamic (multistage) models and static models is the degree of complexity involved in describing a given strategy or procedure. In a static situation a strategy is selected once and for all to be carried out directly, whereas the strategies available in the dynamic situation are usually complicated functions of information re­ ceived and actions undertaken in the preceding stages. Theoretically, by defining a strategy suitably, we can reduce any dynamic model to a static model. In practice, however, this operation so complicates the nature of the strategy that it is often impossible to analyze the problem in the result­ ing terms. The essence of the analysis of a dynamic problem seems to be the exploitation of the recursive, time-dependent nature of the problem and the symmetries made available by the infinite horizon of time. The significance of dynamic decision problems is obvious, since almost all human activity takes place in time. Events and learning processes are sequential. Most business decisions involve a time element. Economists try to take account of dynamic fluctuations in time. Nonetheless, the recognition and mathematical analysis of dynamic decision problems are of recent origin. A notable innovator in this regard was Wald, whose Sequential Analysis of Statistical Data [244]* contained the essence of the notion of sequential decision-making for the accumulation of information. Other more special contributors to the sequential decision problem include Bellman [19], who saw the generality of the sequential idea and used it in the formulation of several multistage management decision models, and Arrow, Harris, and Marschak [8], who cast a type of inventory decision problem in dynamic form. The theory of multistage games is an extension of the usual theory of games to a dynamic situation. A recent volume [72] shows the importance of this development. The study of static models serves two purposes. First, a static model may be the best way of describing a static problem whose solution is inter- * References are to the Bibliography. INTRODUCTION 5 esting in itself and affords insight into the workings and structure of a given operation. One common static problem of this sort is that of optimiz­ ing a given criterion among different procedures where the variables range over a prescribed set in which the time variable is not a special variable. Second, from a technical point of view, many dynamic models must be approached through the study of modified static problems. For example, it is often convenient to reduce the infinite version of the dynamic problem to the case of a finite number of periods N. The solution of the resulting problem is obtained by a simple extension of the static model, after which a passage to the limit on N produces the solution of the full dynamic problem. II. Decision problems can also be classified in terms of the number of antagonistic participants involved. We note three examples. (1) If there are at least two irreconcilable participants, we are dealing with problems in the theory of games. Where there are just two such opponents, their objectives are clear: each strives to achieve as great a return as possible, knowing that his opponent will strive for the same ob­ jective with all his ability and intelligence. Where there are more than two, their objectives ate not so clear. The conceptual framework of this model has not yet been well established, and therefore it is difficult to develop appropriate mathematical methodology for it. (2) Where there is only one participant involved and his objectives are clearly defined, the basic decision problem reduces technically to a strict maximization of the objective functions subject to the natural constraints of the model. Generally, this situation leads to variational problems, with the solution usually occurring on the boundaries of the domain of the variables. To solve such extreme constrained problems entails developing new techniques. The fields of linear and dynamic programming abound with models of this kind. (3) Where there is one participant and uncertainties are present, a solution can usually be obtained by combining the methods of statistics with variational techniques. III. A third breakdown of the general decision model is into determin­ istic and stochastic cases. Naturally the deterministic models are con­ ceptually and technically much simpler and more frequently amenable to thorough analytical treatment. However, the majority of practical prob­ lems involve uncertainties, variability, and all kinds of randomness. To solve problems of this sort requires a thorough acquaintance with the theory of stochastic processes and the corresponding theory of inference in stochastic processes. IV. Another classification can be made in terms of the complexity of the available strategies (the strategy space). Strategy spaces can be divided into two categories: finite-dimensional and infinite-dimensional. In many