CATS-Apr-19-2013
Title[edit]
The Combinatorics of Hidden Diversity
Speaker[edit]
David Johnson is Head of the Algorithms and Optimization Department at AT&T Labs-Research in Florham Park, NJ, and has been a researcher at the Labs (in its many incarnations) since 1973, when he received his PhD from MIT. He is perhaps best known as the co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which he and his co-author M. R. Garey won the INFORMS Lanchester Prize. His research interests include approximation algorithms for combinatorial problems, a subject on which he had several of the first key papers, starting with his PhD thesis on the infamous "bin packing" problem. In recent years he has become a leader in the experimental analysis of algorithms, and has been the creator and lead organizer for the series of DIMACS Implementation Challenges, covering topics from Network Flows to the Traveling Salesman Problem. He also founded the ACM-SIAM Symposium on Discrete Algorithms (SODA), and served as its Steering Committee Chair for its first 23 years. He is an ACM Fellow, a SIAM Fellow, an AT&T Fellow, and the winner of the 2010 Knuth Prize for outstanding contributions to the foundations of computer science.
Abstract[edit]
Network routing games are instrumental in understanding traffic patterns and improving congestion in networks. They have a direct application in transportation and telecommunication networks and extend to many other applications such as task planning, etc. Theoretically, network games were one of the central examples in the development of algorithmic game theory.
In these games, multiple users need to route between di fferent source-destination pairs and links are congestible, namely, each link delay is a non-decreasing function of the flow on the link. Many of the fundamental game theoretic questions are now well understood for these games, for example, does equilibrium exist, is it unique, can it be computed e fficiently, does it have a compact representation; the same questions can be asked of the socially optimal solution that minimizes the total user delay.
So far, most research has focused on the classical models in which the link delays are deterministic. In contrast, real world applications contain a lot of uncertainty, which may stem from exogenous factors such as weather, time of day, weekday versus weekend, etc. or endogenous factors such as the network tra ffic. Furthermore, many users are risk-averse in the presence of uncertainty, so that they do not simply want to minimize expected delays and instead may need to add a bu ffer to ensure a guaranteed arrival time to a destination.
I present my recent work on a new stochastic network game model with risk-averse users. Risk-aversion poses a computational challenge and it often fundamentally alters the mathematical structure of the game compared to its deterministic counterpart, requiring new tools for analysis. The talk will discuss best response and equilibrium analysis, as well as equilibrium efficiency (price of anarchy) and a new concept, the price of risk.
One relevant paper is here: http://faculty.cse.tamu.edu/nikolova/papers/Stochastic-selfish-routing-full.pdf
A short summary of the paper is here: http://www.sigecom.org/exchanges/volume_11/1/NIKOLOVA.pdf
