The Primal-Dual Schema and its Applications to Game Theory

Vijay V. Vazirani


Georgia Tech

Abstract:

The primal-dual schema has emerged as an important unifying principle in Approximation Algorithms, an area that has been the focus of algorithmic research over the last decade. Over the last couple of years, in order to address new issues arising from the Internet, the area of Algorithmic Game Theory has been taking shape. Interestingly enough, the basic idea underlying the primal-dual schema has been useful in this new (non-optimization) setting as well.

I will describe both aspects in the context of the following problems:

(i)

The classical facility location problem, whose modern-day applications include finding good clusterings and cost-effective placements of servers on the Internet. We give an algorithm whose running time is dominated by the time to sort the edges of the underlying metric.

(ii)

Market equilibrium: we give the first polynomial time algorithm for finding a price vector under which market clears, assuming that buyers have linear utilities.

(iii)

Cost allocation: we give a way of distributing the cost of a shared resource among users in a way that guarantees truth-revealing as well as fairness criteria.