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. Motivated by the division of power within social groups more generally, the field of network exchange theory 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 based on the work of Cook and Yamagishi 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 results exploit connections to the structure of matchings in graphs, including decomposition theorems for graphs with perfect matchings.
(This talk represents joint work with Eva Tardos.)