Bargaining Dynamics in Exchange Networks

We consider some known dynamical systems for Nash bargaining on graphs and focus on their rate of convergence. We first consider the edge-balanced dynamical system by Azer 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 time is quadratic in the number of matched edges. We then consider another linear system, the path bounding process of natural dynamics by Kanoria et al, and show a result that allows to improve their convergence time bound to O(n^4+ε), any ε > 0, for a graph of n nodes that has a unique maximum-weight matching and satisfies a positive gap condition.