2010 | OriginalPaper | Chapter
Local Dynamics in Bargaining Networks via Random-Turn Games
Authors : L. Elisa Celis, Nikhil R. Devanur, Yuval Peres
Published in: Internet and Network Economics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a new technique for analyzing the rate of convergence of local dynamics in bargaining networks. The technique reduces balancing in a bargaining network to optimal play in a random-turn game. We analyze this game using techniques from martingale and Markov chain theory. We obtain a tight polynomial bound on the rate of convergence for a nontrivial class of unweighted graphs (the previous known bound was exponential). Additionally, we show this technique extends naturally to many other graphs and dynamics.