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