Speaker: Vijay Vazirani, Georgia Tech
Title: Nash Bargaining via Flexible Budget Markets
Abstract:
In his seminal 1950 paper, John Nash defined the bargaining problem; the ensuing theory of bargaining lies
today at the heart of game theory. In this work, we initiate an algorithmic study of Nash bargaining
problems.
We consider a class of Nash bargaining problems whose solution can be stated as a convex program. For these
problems, we show that there corresponds a market whose equilibrium allocations yield the solution
to the convex program and hence the bargaining problem. For several of these markets, we give combinatorial,
polynomial time algorithms, using the primal-dual paradigm.
Unlike the traditional Fisher market model, in which buyers spend a fixed amount of money, in these markets,
each buyer declares a lower bound on the amount of utility she wishes to derive. The amount of money she
actually spends is a specific function of this bound and the announced prices of goods.
Over the years, a fascinating theory has started forming around a convex program given by Eisenberg and Gale
in 1959. Besides market equilibria, this theory touches on such disparate topics as TCP congestion control and
efficient solvability of nonlinear programs by combinatorial means. Our work shows that the Nash bargaining
problem fits harmoniously in this collage of ideas.