Social Exchange Networks with Distant Bargaining

Network bargaining

is a natural extension of the classical, 2-player

Nash bargaining

solution to the network setting. Here one is given an exchange network

G

connecting a set of players

V

in which edges correspond to potential contracts between their endpoints. In the standard model, a player may engage in at most one contract, and feasible outcomes therefore correspond to matchings in the underlying graph. Kleinberg and Tardos [STOC’08] recently proposed this model, and introduced the concepts of

stability

and

balance

for feasible outcomes. The authors characterized the class of instances that admit such solutions, and presented a polynomial-time algorithm to compute them.

In this paper, we generalize the work of Kleinberg and Tardos by allowing agents to engage into more complex contracts that span more than two agents. We provide suitable generalizations of the above stability and balance notions, and show that many of the previously known results for the matching case extend to our new setting. In particular, we can show that a given instance admits a stable outcome only if it also admits a balanced one. Like Bateni et al. [ICALP’10] we exploit connections to cooperative games. We fully characterize the core of these games, and show that checking its non-emptiness is NP-complete. On the other hand, we provide efficient algorithms to compute core elements for several special cases of the problem, making use of compact linear programming formulations.