Nonlinear Networks

Catalog description

Foundation in congestion games, including elements of non-cooperative game theory, equilibrium network flows, Braess paradox, and the price of anarchy. I E 588 Nonlinear Networks (3) This course examines the theory of congestion games, developed originally to describe flows on congested transport networks but recently embraced to model data networks. Students will learn how to formulate descriptive models of traffic and data network flows in the presence of congestion as Nash games expressed as variational inequalities (VIs). These models will be used to derive theoretical bounds on the price of anarchy (the social costs of not achieving a truly cooperative or system optimal flow). Students will also learn how to formulate normative network design problems and Stackelberg games or so-called mathematical programs with equilibrium constraints (MPECs) to avoid the Braess paradox. Numerical techniques for solving Vis and MPECs will be discussed and illustrated. The course begins with an introduction to so-called system optimal network flow models that explicitly incorporate network congestion. The study of system optimal flows contains an introduction to nonlinear network optimization algorithms, including feasible direction, gradient projection, simplicial decomposition and affine scaling algorithms. Following the consideration of system optimal flows, both atomic and non-atomic network equilibrium models in the form of non-cooperative Nash games are discussed in-depth. The price of anarchy is presented as the ratio of the cost of Nash equilibrium flows to the cost of system optimal flows within the network of interest. Various theoretical bounds on the price of anarchy are derived. Numerical experiments to determine the price of anarchy are also described. The Braess paradox, wherein global congestion can increase when local capacity is added to a nonlinear network, is introduced and its relationship to the price of anarchy demonstrated. Discrete and continuous equilibrium network design models that eliminate any possibility for the Braess paradox to arise are articulated. Each such design model is shown to be equivalent to a Stackelberg game, which is a type of mathematical program with equilibrium constraints (MPEC).Mechanism design in the form of network congestion pricing to alleviate the effects of congestion is also considered and show to have an MPEC structure as well. Algorithms for solving MPECs to ascertain efficient network topology/efficient tolling will be discussed in detail, including simulated annealing and other types of computational intelligence on the one hand; and duality, penalty, decomposition and other types of nonlinear programming algorithms on the other. Students interested in taking this course should have completed a course in linear programming (I E 505); a course in nonlinear programming is also recommended.