Abstract
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.
This work was initiated in the International Problem Solving Workshop, held in July 16-20, 2012. and organized as part of the MITACS International Focus Period “Advances in Network Analysis and its Applications”. We would like to thank MITACS for this great opportunity.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bateni, M., Hajiaghayi, M., Immorlica, N., Mahini, H.: The cooperative game theory foundations of network bargaining games. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 67–78. Springer, Heidelberg (2010)
Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational Aspects of Cooperative Game Theory. Morgan & Claypool Publishers (2011)
Conitzer, V., Sandholm, T.: Complexity of constructing solutions in the core based on synergies among coalitions. Artif. Intell. 170(6-7), 607–619 (2006)
Deng, X., Fang, Q.: Algorithmic cooperative game theory. In: Pareto Optimality, Game Theory and Equilibria. Springer Optimization and Its Applications, vol. 17, pp. 159–185. Springer (2008)
Deng, X., Ibaraki, T., Nagamochi, H.: Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24(3), 751–766 (1999)
Faigle, U., Kern, W., Fekete, S.P., Hochstättler, W.: On the complexity of testing membership in the core of min-cost spanning tree games. Int. J. Game Theory 26(3), 361–366 (1997)
Faigle, U., Kern, W., Kuipers, J.: An efficient algorithm for nucleolus and prekernel computation in some classes of tu-games. Technical Report 1464, U. of Twente (1998)
Granot, D., Granot, F.: On some network flow games. Math. Oper. Res. 17(4), 792–841 (1992)
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)
Kleinberg, J.M., Tardos, É.: Balanced outcomes in social exchange networks. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 295–304 (2008)
Meinhardt, H.: An lp approach to compute the pre-kernel for cooperative games. Computers & OR 33, 535–557 (2006)
Nash, J.: The bargaining problem. Econometrica 18, 155–162 (1950)
Schrijver, A.: Combinatorial optimization. Springer, New York (2003)
Shapley, L.S., Shubik, M.: The assignment game: the core. International Journal of Game Theory 1(1), 111–130 (1971)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Georgiou, K., Karakostas, G., Könemann, J., Stamirowska, Z. (2013). Social Exchange Networks with Distant Bargaining. In: Du, DZ., Zhang, G. (eds) Computing and Combinatorics. COCOON 2013. Lecture Notes in Computer Science, vol 7936. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38768-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-38768-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38767-8
Online ISBN: 978-3-642-38768-5
eBook Packages: Computer ScienceComputer Science (R0)