Foundations of Network Optimization and Games by Terry L. Friesz and David Bernstein is a book intended for scholars from all disciplines working on deterministic nonlinear network models expressed as nonlinear programs and mathematical games, as well as for graduate students encountering nonlinear network models for the first time.
The book purposely emphasizes model formulation, algorithm selection, and illustrative numerical examples rather than theoretical results on convergence and algorithm complexity. As such Foundations of Network Optimization and Games will be especially useful to individuals who are builders of so-called computable models meant for direct decision support or comprehensive numerical discovery of the properties of complex, networked systems.
Chapter 1 provides a quick tour of timely nonlinear network applications, including traffic assignment, data network flows, electrical power grids, and water resource management. Chapters 2 and 3 provide a review of essential notions and tools from nonlinear programming and graph theory, respectively. These early chapters set the stage for Chapter 4's indepth discussion of the implications of network structure in mathematical programming. Chapter 5 explores algorithms for large-scale as well as near-network programs; among the algorithms considered are Lagrangian relaxation, Dantzig-Wolfe decomposition, Benders decomposition, and simplicial decomposition.
Chapter 6 considers a variety of normative network models, and illustrates how the material of the preceding chapters may be applied. Several solved numerical examples are included. The normative models studied include classical network problems such as the primal minimum cost flow problem with transshipment, the traveling salesman problem, the vehicle routing problem, and the capacitated plant location problem. Also considered are nonlinear network models of irrigation network operations and telecommunications flow routing.
Chapter 7 is devoted to Nash games and the mathematical apparatus needed to model them. The longest chapter of the book, Chapter 7 describes how to create fixed point, variational inequality and complementarity formulations of Nash games. Algorithms for solving Nash games are also presented, including gap-function methods and successive linearization of nonlinear complementarity formulations.
Chapter 8 provides a detailed discussion of vehicular network equilibrium, including alternative formulations and algorithms. Chapter 9 studies spatial network equilibrium using the tools presented in Chapter 7, including Samuelson-Takayama-Judge models of spatial competition. Spatial arbitrage in network oligopolies and freight network equilibrium are also analyzed.
Chapter 10, the final chapter, provides an introduction to Stackelberg games on networks, the price of anarchy, congestion pricing, and network design. The natural formulation of Stackelberg games as mathematical programs with equilibrium constraints (MPECs) is explored from several points of view, including the price of anarchy, the Braess paradox, and the algorithmic implications of variational inequality sensitivity analysis. Nontraditional methods, in particular simulated annealing and swarm optimization, for solving MPECs and Stackelberg games are presented. Numerical examples of Electric power pricing and vehicular network design are included.
