The Theory of Linear Economic Models/ David Gale

Contents
Chapter I. Linear Programming: ExampleSt Definitions, and State
ments of the Principal Theorems i
1. Examples 1
The diet problem 1
The transportatioQ problem . 4
Production to meet given demand at minimum cost 6
Production to maximize income from given resources 7
2. Duality and prices . . . . S
3. Further interpretation of duality 13
4. Price equilibrium . 19
Bibliographical notes 23
Ex^dses . . . 23
Chapter 2, Real Linear Algebra 28
1. Vectors 30
2. Scalar product, matrices, linear equations 35
3. Real linear equations and inequalities 42
4. Basic solutions of equations . . . . 49
5. Geometry of linear inequalities. Convex cones 51
6. Extreme vectors and extreme solutions . . . 60
7. Convex sets and polj^pes 66
Bibliographical notes 69
Exercises. 69
Chapter 3. The Theory of Linear Programming 74
1. Definitions 75
2. The duality theorems . 78
3. The equilibrium theorems . 82
4. Basic solutions . . . . 84
5. An application: allocation of resources in a competitive economy . . 85
Bibliographical notes 93
Exercises 93
Chapter 4. Computation. The Simplex Method 97
1. Solving simultaneous equations and inverting a matrix 98
2. The simplex method for linear programming. Discussion 105
3. Theory of the simplex method 108
4. Some numerical examples 113
5. Nonnegative solutions of linear equations 119
6. Solving linear inequalities 121
7. Degeneracy. The generalized simplex method. 123
Bibliographical notes 128
Exercises 129
Chapter 5. Integral Linear Programming 132
1. Examples 132
Transportation problem with indivisible commodity . 132
The optimal-assignment problem 133
The loading problem. . . . 134
2. Flows in networks 134
3. The simple-assignment problem . 143
4. The transshipment problem 148
5. The optimal-assignment problem 155
6. A problem related to optimal assignment. Price equilibrium . . . 160
7. The transportation problem 162
8. Other examples: shortest route; the caterer 170
9. Concluding remarks and open questions. . 172
Bibliographical notes 174
Exercises 1^^
Chapter 6. Two-person Games: Examples, Definitions, and Ele^
mentary Theory ISO
1. First examples and definitions. 182
Odds and evens (matching pennies) 182
Morra 1^
2. Further examples of matrix games . l84
Goofspiel . 1^
Bluffing 1^®
A,B,C . . . . 18J
3. Solutions of games. Mixed strategies 189
4. Value of a game and optimal strategies l93
5. Some infinite games 1^®
Continuous bluffing . 1^®
Duels
The oil prospector (a game against nature) 18J
The bomber and the submarine 201
High number . . . . 20
Low number . . . . 20
6. Saddle points and minimax 2U
7. SjTnmetric gamea 204
8. Proof of the fundamental theorem 207
Appendix to Chapter 6: A geometric "proof" of the fundamental
theorem of game theory. 208
Bibliographical notes . . 211
Exercises 212
Chapter 7. Solutions of Matrix Games 216
1. Relation between matrix games and linear programming 216
2. Solving games by the simplex method . 220
3. Optimal strategies 223
4. Solutions. 227
5. Examples 231
6. The structure of symmetric games . . . . 233
7. Constructing a game with prescribed solutions . 235
8. Basic optimal strategies . . . . 241
9. A method of "learning" a game . 246
10. Convergence of the learning method 250
Bibliographical notes 256
Exercises 256
Chapter 8. Linear Models of Exchange. 260
1. Examples 260
The simple exchange model. The price problem 260
The simple linear model of international trade . 263
2. Equilibrium for the exchange model . 264
3. Dynamic theory 271
4. Dynamics in the reducible case . . . . 278
5. Price equilibrium for linear exchange models 281
6. An example of price equilibrium .
7. Uniqueness of equilibrium prices .
Bibliographical notes
Exercises
287
289
290
290
Chapter 9. Linear Models of Production . 294
1. The simple linear production model . 294
2. A dynamic property of the simple model 299
3. The Leontief model 301
4. The general linear production model. Efficient pointe 306
5. Von Neumann's expanding model 310
6. Some examples 315
7. The expanding simple model . 317
Bibliographical notes . . . . 318
Exercises 319
Bibliography . 323
Index . . . 327