Vidal's library
Title: Balanced Outcomes in Social Exchange Networks
Author: Jon Kleinberg and Eva Tardos
Book Tittle: Proceedings of the 40th ACM Symposium on Theory of Computing
Year: 2008
Abstract: The study of bargaining has a long history, but many basic settings are still rich with unresolved questions. In particular, consider a set of agents who engage in bargaining with one another, but instead of pairs of agents interacting in isolation, agents have the opportunity to choose whom they want to negotiate with, along the edges of a graph representing social-network relations. The area of network exchange theory in sociology has developed a large body of experimental evidence for the way in which people behave in such network-constrained bargaining situations, and it is a challenging problem to develop models that are both mathematically tractable and in general agreement with the results of these experiments. We analyze a natural theoretical model arising in network exchange theory, which can be viewed as a direct extension of the well-known Nash bargaining solution to the case of multiple agents interacting on a graph. While this generalized Nash bargaining solution is surprisingly effective at picking up even subtle differences in bargaining power that have been observed experimentally on small examples, it has remained an open question to characterize the values taken by this solution on general graphs, or to find an efficient means to compute it. Here we resolve these questions, characterizing the possible values of this bargaining solution, and giving an efficient algorithm to compute the set of possible values. Our result exploits connections to the structure of matchings in graphs, including decomposition theorems for graphs with perfect matchings, and also involves the development of new techniques. In particular, the values we are seeking turn out to correspond to a novel combinatorially defined point in the interior of a fractional relaxation of the matching problem.

Cited by 1  -  Google Scholar

@InProceedings{kleinberg08a,
  author =	 {Jon Kleinberg and Eva Tardos},
  title =	 {Balanced Outcomes in Social Exchange Networks},
  booktitle =	 {Proceedings of the 40th {ACM} Symposium on Theory of
                  Computing},
  cluster = 	 {4259751300215444882},
  year =	 2008,
  abstract =	 {The study of bargaining has a long history, but many
                  basic settings are still rich with unresolved
                  questions. In particular, consider a set of agents
                  who engage in bargaining with one another, but
                  instead of pairs of agents interacting in isolation,
                  agents have the opportunity to choose whom they want
                  to negotiate with, along the edges of a graph
                  representing social-network relations. The area of
                  network exchange theory in sociology has developed a
                  large body of experimental evidence for the way in
                  which people behave in such network-constrained
                  bargaining situations, and it is a challenging
                  problem to develop models that are both
                  mathematically tractable and in general agreement
                  with the results of these experiments. We analyze a
                  natural theoretical model arising in network
                  exchange theory, which can be viewed as a direct
                  extension of the well-known Nash bargaining solution
                  to the case of multiple agents interacting on a
                  graph. While this generalized Nash bargaining
                  solution is surprisingly effective at picking up
                  even subtle differences in bargaining power that
                  have been observed experimentally on small examples,
                  it has remained an open question to characterize the
                  values taken by this solution on general graphs, or
                  to find an efficient means to compute it. Here we
                  resolve these questions, characterizing the possible
                  values of this bargaining solution, and giving an
                  efficient algorithm to compute the set of possible
                  values. Our result exploits connections to the
                  structure of matchings in graphs, including
                  decomposition theorems for graphs with perfect
                  matchings, and also involves the development of new
                  techniques. In particular, the values we are seeking
                  turn out to correspond to a novel combinatorially
                  defined point in the interior of a fractional
                  relaxation of the matching problem. },
  url = 	 {http://jmvidal.cse.sc.edu/library/kleinberg08a.pdf}
}
Last modified: Wed Mar 9 10:16:55 EST 2011