Local Dynamics in Bargaining Networks via Random Turn Games

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. For unweighted bipartite
graphs with unique balanced outcomes we obtain a tight polynomial bound on 
the rate of convergence (the
previous known bound was exponential). Additionally, we show this 
technique extends naturally to many
other graphs and dynamics.

Joint work with Elisa Celis and Yuval Peres.