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...
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.
Like to rate videos and let people know what you think?
Automatically share your ratings, favorites, and more on Facebook, Twitter, and Google Reader with YouTube Autoshare.
Autoshare makes certain YouTube activities public on the services you choose. Select only the services you are comfortable with - like Facebook, Twitter, or Google Reader - to let your friends know what you like on YouTube. You can turn Autoshare off at any time.
Like to share videos with friends?
Automatically share your ratings, favorites, and more on Facebook, Twitter, and Google Reader with YouTube Autoshare.
Autoshare makes certain YouTube activities public on the services you choose. Select only the services you are comfortable with - like Facebook, Twitter, or Google Reader - to let your friends know what you like on YouTube. You can turn Autoshare off at any time.
The bargaining situation is modeled as two people with their "happiness functions" (with a bunch of assumptions on continuity and convexity). When it comes to results, this kind of analysis may lead to interesting curiosities, but not economic truths.
There is no "right" solution in bargaining. Any solution where the two players are happy with the exchange is a good solution. Whether one player gets a better deal than the other is a question of bargaining skills, not maths or algorithms.
Autoshare makes certain YouTube activities public on the services you choose. Select only the services you are comfortable with - like Facebook, Twitter, or Google Reader - to let your friends know what you like on YouTube. You can turn Autoshare off at any time.
When it comes to results, this kind of analysis may lead to interesting curiosities, but not economic truths.
There is no "right" solution in bargaining. Any solution where the two players are happy with the exchange is a good solution.
Whether one player gets a better deal than the other is a question of bargaining skills, not maths or algorithms.
Tour of torture