Selfish routing in the presence of side constraints

George Karakostas (karakosmcmaster.ca)
Stavros Kolliopoulos (stavrosmcmaster.ca)

Abstract: The natural approach for describing network flow problems is to introduce side constraints that capture restrictions of a logical or technological nature, e.g., capacity constraints. We study the traffic equilibria arising from selfish routing of individual users in networks with side constraints. We examine first the case of linear latency functions. Under very general assumptions for the side constraints we show that the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency. This matches the known lower bound. For general latency functions we formulate the traffic equilibrium as the solution to a nonlinear complementarity problem. We use a classic transformation to reduce the existence of a solution to the complementarity problem to the existence of a fixed point for an appropriate continuous function. Such a fixed point always exists if a set of Lagrangean multipliers from the complementarity problem is bounded from above. As an application we cast the recent optimal taxes result of Cole, Dodis and Roughgarden in this general framework.

Keywords: traffic equilibria, side constraints

Category 1: Network Optimization

Citation: Tech. report CAS-03-13-GK, Dept. of Computing & Software, McMaster University, Hamilton, Ontario Canada Submitted 11/2003

Download: [PDF]

Entry Submitted: 12/22/2003
Entry Accepted: 01/16/2004
Entry Last Modified: 04/01/2004

Modify/Update this entry