Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks

Details Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks

2009-07-24

arxiv.org/abs/0907.4356v1

Computer Science

Computer Science and Game Theory

Full version of FOCS 2009 paper

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-310853