%0 Journal Article
%T Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks
%A Yossi Azar
%A Benjamin Birnbaum
%A L. Elisa Celis
%A Nikhil R. Devanur
%A Yuval Peres
%J Computer Science
%D 2009
%I arXiv
%X Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and fairness. In a recent paper, Kleinberg and Tardos introduced balanced outcomes to the computer science community and provided a polynomial-time algorithm to compute the set of such outcomes. Their work left open a pertinent question: are there natural, local dynamics that converge quickly to a balanced outcome? In this paper, we provide a partial answer to this question by showing that simple edge-balancing dynamics converge to a balanced outcome whenever one exists.
%U http://arxiv.org/abs/0907.4356v1