CS 789 THEORY SEMINAR [home]

Speaker:    Lisa Fleischer
Affiliation:  IBM TJ Watson Research Center
Date:          January 24, 2004
Title:          Tolls for heterogeneous, selfish users of a multicommodity network and generalized congestion games
 

Abstract:  In traffic networks, transit delay is a function of congestion. To provide a sufficient quality of service to customers, one goal of a network owner may be to have traffic that minimizes total, or average, system delay. On the other hand, if customers can choose their own routes, they would naturally seek routes that minimize their individual delay. The traffic pattern that results from customers acting ``selfishly'' may result in overall higher system-wide delay. A natural question
is: how can a network owner influence selfish network users to independently choose a traffic pattern that minimizes system-delay?

One natural approach is to charge network users for use of each link in the network via tolls. In this setting, each user selects a path that minimizes some function of delay plus tolls. Each user may have a different preference for delay versus toll. In such a setting, we give a complete characterization of traffic patterns that can be induced via tolls. These include patterns that minimize mean delay, mean weighted delay, and maximum delay. Our proof is constructive --- yielding a polynomial time algorithm --- and extends to general congestion games.

This is joint work with Kamal Jain and Mohammad Mahdian.