Foundations of Network Optimization and Games

This is a book about infrastructure networks that are intrinsically nonlinear. The networks considered range from vehicular networks to electric power networks to data networks. The main point of view taken is that of mathematical programming in concert with finite-dimensional variational inequality theory. The principle modeling perspectives are network optimization, the theory of Nash games, and mathematical programming with equilibrium constraints. Computational methods and novel mathematical formulations are emphasized. Among the numerical methods explored are network simplex, gradient projection, fixed-point, gap function, Lagrangian relaxation, Dantzig-Wolfe decomposition, simplicial decomposition, and computational intelligence algorithms. Many solved example problems are included that range from simple to quite challenging. Theoretical analyses of several models and algorithms, to uncover existence, uniqueness and convergence properties, are undertaken. The bookis meant for use in advanced undergraduate as well as doctoral courses taught in civil engineering, industrial engineering, systems engineering, and operations research degree programs. At the same time, the book should be a useful resource for industrial and university researchers engaged in the mathematical modeling and numerical analyses of infrastructure networks. 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.