Theory Colloquium


"Taxes for heterogeneous, selfish users of a multicommodity network"

Lisa K. Fleischer, IBM T.J.Watson

Wednesday, April 28, 2004 at 4:00 P.M.

Lubrano Conference Room

We prove the existence of taxes to induce multicommodity, heterogeneous network users that independently choose routes minimizing their own linear function of taxes versus latency to collectively form the traffic pattern of a minimum average latency flow. Unlike previous proofs for single commodity users in general graphs, our proof is constructive - it does not rely on a fixed point theorem - and results in a simple polynomial-sized linear program to compute taxes when the number of different types of users is bounded by a polynomial.

We give a complete characterization of flows that are enforceable by taxes. Thus, taxes exist to minimize average weighted latency flows, maximum latency flows, and other natural objectives.

For single commodity traffic, we prove that taxes that are linear in the size of the network are sufficient to induce enforceable congestions.

Finally, we show that our result extends to handle general nonatomic congestion games. In particular, taxes exist even when 1) latencies depend on user type; 2) latency functions are nonseparable functions of traffic on edges; 3) the latency of a set S is an arbitrary function of the latencies of the resources contained in S.

This is joint work with Kamal Jain of Microsoft Research and Mohammad Mahdian of MIT.

Host: Philip Klein