 |
Google Tech Talks
September 12, 2008
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.
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.
Speaker: Vijay V. Vazirani
Vijay Vazirani got his Bachelor's degree in
Computer Science from MIT in 1979 and his
Ph.D. from the University of California at
Berkeley in 1983. His research has spanned a
broad range of themes within the design of
efficient algorithms - combinatorial
optimization, approximation algorithms,
randomized algorithms, parallel algorithms,
and most recently algorithmic issues in game
theory and mathematical economics. He has
also worked in complexity theory,
cryptography and information theory.
In 2001 he published what is widely regarded
as the definitive book on Approximation
Algorithms. This book has been translated
into Japanese, Polish and French. Last year,
he co-edited a comprehensive volume on
Algorithmic Game Theory. He is a Fellow of
the ACM.
Tags : google techtalks techtalk engedu talk talks googletechtalks education |
