University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Tuesday, March 9, 2004

DTC Science and Technology Innovators Lecture Series

A Game Theoretic View of Efficiency Loss in Network Resource Allocation


John Tsitsiklis
Massachusetts Institute of Technology
Laboratory for Information and Decision Systems
Department of Electrical Engineering and Computer Science

Tuesday, March 9, 2004
4:30 p.m. Reception
5:00 p.m. Seminar

402 Walter Library

Download slides (pdf 111 KB) The Internet has evolved into a heterogeneous system, comprised of many users who value their own performance, rather than the efficiency of the system as a whole; as a result, proposals for network resource allocation must be robust against self-interested behavior of the network users. With this motivation, we analyze a network congestion game in which the users of congested finite-capacity links anticipate the effect of their actions on the link prices. We show existence of a Nash equilibrium, discuss uniqueness, and establish that the efficiency of the system drops by no more than 25% relative to the social optimum.

John Tsitsiklis

We consider several generalizations, such as: (a) competition for an unconstrained resource which is priced according to its marginal cost; (b) a more general resource allocation mechanism in which a set of producers compete for a limited amount of available resources; (c) a symmetrical situation involving a set of competing suppliers. This is joint work with Ramesh Johari and Shie Mannor.


John N. Tsitsiklis (Ph.D., 1984, MIT) is a Professor of Electrical Engineering and Computer Science at MIT, and a co-director of the Operations Research Center. His research interests are in the fields of systems, optimization, control, and operations research. He is a coauthor of four books, Parallel and Distributed Computation: Numerical Methods (1989, with D. Bertsekas), Neuro-Dynamic Programming (1996, with D. Bertsekas), Introduction to Linear Optimization (1997, with D. Bertsimas), and Introduction to Probability (2002, with D. Bertsekas). His awards include the INFORMS/CSTS prize (1997), and he is a Fellow of the IEEE. He is currently a member of the editorial board for the Springer-Verlag Lecture Notes in Control and Information Sciences series, and an associate editor of Mathematics of Operations Research.