Abstract
We study a network extension to the Nash bargaining game, as introduced by Kleinberg and Tardos [9], where the set of players corresponds to vertices in a graph G=(V,E) and each edge i j∈E represents a possible deal between players i and j. We reformulate the problem as a cooperative game and study the following question: Given a game with an empty core (i.e. an unstable game) is it possible, through minimal changes in the underlying network, to stabilize the game? We show that by removing edges in the network that belong to a blocking set we can find a stable solution in polynomial time. This motivates the problem of finding small blocking sets. While it has been previously shown that finding the smallest blocking set is NP-hard [3], we show that it is possible to efficiently find approximate blocking sets in sparse graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
We abuse notation slightly in this definition of s i j , and let s i j (x)=−x i if i has no neighbour other than j.
References
Bachrach, Y., Elkind, E., Meir, R., Pasechnik, D., Zuckerman, M., Rothe, J., Rosenschein, J.: The cost of stability in coalitional games. In: Symposium on Algorithmic Game Theory, pp 122–134 (2009)
Bateni, M., Hajiaghayi, M., Immorlica, N., Mahini, H.: The cooperative game theory foundations of network bargaining games. In: Proceedings of International Colloquium on Automata, Languages and Processing, pp 67–78 (2010)
Biró, P., Kern, W., Paulusma, D.: On solution concepts for matching games. In: TAMC, pp 117–127 (2010)
Bock, A., Chandrasekaran, K., Könemann, J., Peis, B., Sanità, L.: Finding small stabilizers for unstable graphs. In: Proceedings of MPS Conference on Integer Programming and Combinatorial Optimization (2013)
Chakraborty, T., Kearns, M.: Bargaining solutions in social network. In: Fourth International Workshop on Internet and Network Economics (WINE), pp 548–555 (2008)
Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational Aspects of Cooperative Game Theory. Morgan & Claypool Publishers, San Rafael, CA (2011)
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., Kuipers, J.: An efficient algorithm for nucleolus and prekernel computation in some classes of tu-games. Tech. Rep. 1464, U. of Twente (1998)
Kleinberg, J.M., Tardos, É.: Balanced outcomes in social exchange networks. In: Proceedings of ACM Symposium on Theory of Computing, pp 295–304 (2008)
Lau, L.C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization. Cambridge University Press, Cambridge, UK (2011)
Mader, W.: Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Math. Ann. 174(4), 265–268 (1967)
Nash, J.: The bargaining problem. Econometrica 18, 155–162 (1950)
Peleg, B., Sudhölter, P.: Introduction to the Theory of Cooperative Games. Springer, Berlin (2003)
Schmeidler, D.: The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17(6), 1163–1170 (1969)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)
Shapley, L.S., Shubik, M.: The assignment game : the core. Int. J. Game Theory 1(1), 111–130 (1971). doi:10.1007/BF01753437
Stearns, R.: Convergent transfer schemes for n-person games. Trans. Amer. Math. Soc. 134, 449–459 (1968)
Acknowledgments
We thank the anonymous referees for their careful reading, and for the many detailed comments provided in their reports.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Könemann, J., Larson, K. & Steiner, D. Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances. Theory Comput Syst 57, 655–672 (2015). https://doi.org/10.1007/s00224-015-9650-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-015-9650-4