@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}
}