We consider a scenario in which leaders are required to recruit teams of followers. Each leader cannot recruit all followers, but interaction is constrained according to a bipartite network. The objective for each leader is to reach a state of local stability in which it controls a team whose size is equal to a given constraint. We focus on distributed strategies, in which agents have only local information of the network topology and propose a distributed algorithm in which leaders and followers act according to simple local rules. The performance of the algorithm is analyzed with respect to the convergence to a stable solution. Our results are as follows. For any network, the proposed algorithm is shown to converge to an approximate stable solution in polynomial time, namely the leaders quickly form teams in which the total number of additional followers required to satisfy all team size constraints is an arbitrarily small fraction of the entire population. In contrast, for general graphs there can be an exponential time gap between convergence to an approximate solution and to a stable solution.
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. This paper presents a theoretical analysis of the structural determinants of power in exchange networks, along with research findings from laboratory experiments and a computer simulation of bargaining in network structures. Two theoretical traditions are dealth with: (1) point centrality in graph-theoretic representations of structure, as an approach to power distributions; and (2) power dependence principles applied to exchange networks. Measures of centrality available in the literature have the advantage of being easily applied to large and complex networks. In contrast, power dependence concepts were conceived for use in microsociology and are found to be cumbersome in the analysis of complex networks. But despite the relative difficulty of applying power-dependence theory to network structures, that approach generates hypotheses about power distributions which are confirmed at nearly every point in a laboratory experiment with five-person networks and at every point in a computer simulation of netwo... 