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!
cited_by
cites
container_end_page 302
container_issue
container_start_page 293
container_title
container_volume
creator Azar, Y.
Birnbaum, B.
Celis, L.E.
Devanur, N.R.
Peres, Y.
description 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.
doi_str_mv 10.1109/FOCS.2009.33
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_5438622</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>5438622</ieee_id><sourcerecordid>5438622</sourcerecordid><originalsourceid>FETCH-LOGICAL-i175t-48e042d5ab82c7e795d4ac15cd91693ed7e969ea765678a353708a5ae3e7d4453</originalsourceid><addsrcrecordid>eNotj7lOw0AURUcCJEJIR0czP2Az-1KCSQKShQugjh4zL8HgeJDHLPl7LMFpbnGkKx1CLjgrOWf-atVUj6VgzJdSHpEzroRSmnNjj8mMCSsKrYQ7JYuc39jE5LRzM7KuUv-Fww77gDRtaZ0CdPT20MO-DZmOid5AB5OMtPkcQ9pjpm1Plz_hFfod0gccv9Pwns_JyRa6jIv_nZPn1fKpuivqZn1fXddFy60eC-WQKRE1vDgRLFqvo4LAdYieGy8xWvTGI1ijjXUgtbTMgQaUaOMUJOfk8u-3RcTNx9DuYThstJLOCCF_Abi4Sj0</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Azar, Y. ; Birnbaum, B. ; Celis, L.E. ; Devanur, N.R. ; Peres, Y.</creator><creatorcontrib>Azar, Y. ; Birnbaum, B. ; Celis, L.E. ; Devanur, N.R. ; Peres, Y.</creatorcontrib><description>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.</description><identifier>ISSN: 0272-5428</identifier><identifier>ISBN: 1424451167</identifier><identifier>ISBN: 9781424451166</identifier><identifier>DOI: 10.1109/FOCS.2009.33</identifier><language>eng</language><publisher>IEEE</publisher><subject>Computer science ; Convergence ; Game theory ; Network topology ; Polynomials ; Sociology ; Stability</subject><ispartof>2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, p.293-302</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/5438622$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54555,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/5438622$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Azar, Y.</creatorcontrib><creatorcontrib>Birnbaum, B.</creatorcontrib><creatorcontrib>Celis, L.E.</creatorcontrib><creatorcontrib>Devanur, N.R.</creatorcontrib><creatorcontrib>Peres, Y.</creatorcontrib><title>Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks</title><title>2009 50th Annual IEEE Symposium on Foundations of Computer Science</title><addtitle>FOCS</addtitle><description>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.</description><subject>Computer science</subject><subject>Convergence</subject><subject>Game theory</subject><subject>Network topology</subject><subject>Polynomials</subject><subject>Sociology</subject><subject>Stability</subject><issn>0272-5428</issn><isbn>1424451167</isbn><isbn>9781424451166</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2009</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotj7lOw0AURUcCJEJIR0czP2Az-1KCSQKShQugjh4zL8HgeJDHLPl7LMFpbnGkKx1CLjgrOWf-atVUj6VgzJdSHpEzroRSmnNjj8mMCSsKrYQ7JYuc39jE5LRzM7KuUv-Fww77gDRtaZ0CdPT20MO-DZmOid5AB5OMtPkcQ9pjpm1Plz_hFfod0gccv9Pwns_JyRa6jIv_nZPn1fKpuivqZn1fXddFy60eC-WQKRE1vDgRLFqvo4LAdYieGy8xWvTGI1ijjXUgtbTMgQaUaOMUJOfk8u-3RcTNx9DuYThstJLOCCF_Abi4Sj0</recordid><startdate>200910</startdate><enddate>200910</enddate><creator>Azar, Y.</creator><creator>Birnbaum, B.</creator><creator>Celis, L.E.</creator><creator>Devanur, N.R.</creator><creator>Peres, Y.</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>200910</creationdate><title>Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks</title><author>Azar, Y. ; Birnbaum, B. ; Celis, L.E. ; Devanur, N.R. ; Peres, Y.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i175t-48e042d5ab82c7e795d4ac15cd91693ed7e969ea765678a353708a5ae3e7d4453</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Computer science</topic><topic>Convergence</topic><topic>Game theory</topic><topic>Network topology</topic><topic>Polynomials</topic><topic>Sociology</topic><topic>Stability</topic><toplevel>online_resources</toplevel><creatorcontrib>Azar, Y.</creatorcontrib><creatorcontrib>Birnbaum, B.</creatorcontrib><creatorcontrib>Celis, L.E.</creatorcontrib><creatorcontrib>Devanur, N.R.</creatorcontrib><creatorcontrib>Peres, Y.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Xplore</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Azar, Y.</au><au>Birnbaum, B.</au><au>Celis, L.E.</au><au>Devanur, N.R.</au><au>Peres, Y.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks</atitle><btitle>2009 50th Annual IEEE Symposium on Foundations of Computer Science</btitle><stitle>FOCS</stitle><date>2009-10</date><risdate>2009</risdate><spage>293</spage><epage>302</epage><pages>293-302</pages><issn>0272-5428</issn><isbn>1424451167</isbn><isbn>9781424451166</isbn><abstract>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.</abstract><pub>IEEE</pub><doi>10.1109/FOCS.2009.33</doi><tpages>10</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 0272-5428
ispartof 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, p.293-302
issn 0272-5428
language eng
recordid cdi_ieee_primary_5438622
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Computer science
Convergence
Game theory
Network topology
Polynomials
Sociology
Stability
title Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-02T20%3A09%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Convergence%20of%20Local%20Dynamics%20to%20Balanced%20Outcomes%20in%20Exchange%20Networks&rft.btitle=2009%2050th%20Annual%20IEEE%20Symposium%20on%20Foundations%20of%20Computer%20Science&rft.au=Azar,%20Y.&rft.date=2009-10&rft.spage=293&rft.epage=302&rft.pages=293-302&rft.issn=0272-5428&rft.isbn=1424451167&rft.isbn_list=9781424451166&rft_id=info:doi/10.1109/FOCS.2009.33&rft_dat=%3Cieee_6IE%3E5438622%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i175t-48e042d5ab82c7e795d4ac15cd91693ed7e969ea765678a353708a5ae3e7d4453%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=5438622&rfr_iscdi=true