2012/02/06 by Moez Draief, Draief, Moez, Milan Vojnovic +1
Computer Science · Mathematics · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.GT #math.OC
paper · pdf · doi:10.48550/arxiv.1202.1089
Short version appeared in Allerton 2010
arxiv created 2012/02/06 · arxiv updated 2012/02/07
We consider a dynamical system for computing Nash bargaining solutions on graphs and focus on its rate of convergence. More precisely, we analyze the edge-balanced dynamical system by Azar et al and fully specify its convergence for an important class of elementary graph structures that arise in Kleinberg and Tardos' procedure for computing a Nash bargaining solution on general graphs. We show that all these dynamical systems are either linear or eventually become linear and that their convergence times are quadratic in the number of matched edges.