Network Resource Allocation: Price Heterogeneity and Strategic Games

April 9, 2007
Time: 11:00am-12:00pm
Speaker: Ao Kevin Tang, California Institute of Technology


Price based resource allocation has been widely used in networking because of its distributed nature and provable optimality. There are two implicit yet fundamental assumptions underlying it: the homogeneity of price and users being price takers. However, there are important networks where these assumptions are violated that need new frameworks.

During the first part of the talk, we study the equilibrium of networks that are shared by heterogeneous congestion control protocols. The standard utility maximization framework breaks down in such a heterogeneous network. We develop a new theory that characterizes all major equilibrium properties such as existence, uniqueness, optimality, and stability. Surprisingly we show that, unlike a homogeneous network, a heterogeneous network can have multiple equilibrium points, and we propose a slow timescale control that steers the network to the unique optimal equilibrium. In the second part, we focus on wireless medium access control (MAC). We show that the contention resolution algorithm in MAC protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse-engineered from the protocol description. We further characterize its Nash equilibrium. In particular, we establish the minimum amount of backoff aggressiveness needed, as a function of density of active users, for uniqueness of and convergence to a Nash equilibrium. In contrast to TCP, the MAC results highlight the non-cooperative nature of random access. In terms of tools, game theory plays the main role instead of optimization and control theories. At the end of the talk, we discuss connections between these problems and related ones in economics and mathematics.

Speaker Biography

A. Kevin Tang received his Ph.D. in electrical engineering with a minor in applied and computational mathematics from the California Institute of Technology in 2006. He is currently a Junior Fellow in the Social and Information Sciences Laboratory at Caltech, where his main research interests include communication networks (wireless and wireline), control and dynamical systems, optimization and game theory. Dr. Tang was the recipient of the 2006 George B. Dantzig Best Dissertation Award from INFORMS.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University