A Game Theoretic View of Efficiency Loss in Network Resource Allocation
<-- Return to the list
Date: 10-17-2006
Start Time:
1:00pm
End Time: 2:00pm
Speaker: John Tsitsiklis, MIT
Location: Mudd 303
Abstract
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 network congestion games in which the users of congested links anticipate the effect of their actions on the link prices. We discuss various mechanisms, all based on market-clearing ideas, some more scalable than others, and characterize the inefficiency of the resulting Nash equilibria compared to the social optimum. We also develop VCG-like mechanisms that only require each player to communicate a single scalar quantity. Despite the limited communication, we establish the existence of an efficient Nash equilibrium. Under some further assumptions, we establish that all Nash equilibria are efficient.
Joint work with Ramesh Johari.
Bio
John N. Tsitsiklis (Ph.D. 1984, MIT) is a professor of electrical engineering and computer science at MIT. 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, an associate editor of Mathematics of Operations Research, and a member of the national Council on Research and Technology Council in Greece.