In his seminal 1950 paper, John NashIn his seminal 1950 paper, John Nash defined the bargaining game; the ensuing theory of bargaining lies at the... » More

In his seminal 1950 paper, John NashIn his seminal 1950 paper, John Nash defined the bargaining game; the ensuing theory of bargaining lies at the heart of game theory. In this work, we initiate an algorithmic study of Nash bargaining games.

For a certain class of Nash bargaining games, we show that they can be transformed into a market (in a new variant of a traditional market model from mathematical economics). We then extend techniques developed in theoretical computer science over the last seven years to give a combinatorial, polynomial time algorithm for computing an equilibrium for this market. The latter in turn yields the solution to the Nash bargaining game.

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 themes 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. Talk by Vijay Vazirani, Georgia Tech Professor.

defined the bargaining game; the ensuing

theory of bargaining lies at the heart of game theory. In this work, we initiate

an algorithmic study of Nash bargaining games.

For a certain class of Nash bargaining games, we show that they can be transformed

into a market (in a new variant of a traditional market model from mathematical

economics). We then extend techniques developed in theoretical computer science over

the last seven years to give a combinatorial, polynomial time algorithm for

computing an equilibrium for this market. The latter in turn yields the solution to

the Nash bargaining game.

Over the years, a fascinating theory has started forming around a convex program. Talk by Vijay Vazirani, Georgia Tech Professor.

given by Eisenberg and Gale in 1959. Besides market equilibria, this theory touches

on such disparate themes 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.

« Hide