Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks

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 comm...

Full description

Saved in:
Bibliographic Details
Main Authors: Azar, Y., Birnbaum, B., Celis, L.E., Devanur, N.R., Peres, Y.
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Convergence
Game theory
Network topology
Polynomials
Sociology
Stability
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0272-5428
DOI:10.1109/FOCS.2009.33