Lecture by Christian Borgs of Microsoft Research in the Stochastics Seminar of Prof. Ferrari

November 10, 17:00 (5 PM), Lipschitz-Hall

Title: Everyone Wants their Fair Share: Nash Bargaining on Exchange Networks



If two people are asked to split a dollar, with one of them suggesting a split, and the other either accepting the offer, or rejecting it (in which case the dollar is taken away), most subjects reject the offer unless the split is fair, i.e., roughly 50/50. In exchange networks, where agents have to decide which neighbor they want to trade with, as well as how to split the profit realized in a trade, the notion of fair splits is more complicated, and is captured in the concept of a so-called Nash bargaining solution. But this concept is an equilibrium concept, and does not address the question whether there exist local algorithms which mimic the behavior of real players and at the same time converge fast to the Nash bargaining solution. In this talk I review work by M. Bayati, J.T.Chayes, Y. Kanoria, A. Montanari and myself in which we give such an algorithm, and prove that it converges. One of the tools used in the paper is a beautiful fixed point theorem Brouwer wanted to prove but couldn't.