### Modeling Social and Economic Exchange in Networks

### Speaker: Jon Kleinberg

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.)