Minimum cost stability in exchange networks

Yuqing Zhu (), Ruidong Yan () and Deying Li ()
Additional contact information
Yuqing Zhu: California State University Los Angeles
Ruidong Yan: Renmin University of China
Deying Li: Renmin University of China

Journal of Combinatorial Optimization, 2019, vol. 38, issue 4, No 1, 987-1004

Abstract: Abstract Social exchange networks model the behavior of a set of players who need to reach pairwise agreements for making profits. The fundamental problem in exchange networks is how to find the equilibrium such that every participant has no better choices. To resolve this problem, a stable “outcome” which consists of a set of transactions and gains of players in these transactions must be found. In this paper, we first propose the general model of stable outcome applying to arbitrary social graphs, and then present the minimum stability problem (MinSTBL), which is to find the stable outcome the total weight of whose transactions is the minimum. MinSTBL can be employed by governments and companies to stimulate economic participation with the lowest cost. For graphs with unit edge weights, we give an almost optimal solution. For graphs with general edge weights, we prove that the maximum-weight matching is optimal if the graph is bipartite, and propose a relaxed solution that uses at most twice of the optimal cost for regular graphs that are not necessarily bipartite. Our algorithms have been tested on real world social networks and artificial networks, and their effectiveness is evaluated.

Keywords: Social networking; Game theory; Bargaining; Network exchange theory (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00431-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:4:d:10.1007_s10878-019-00431-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00431-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().