Abstract
We study balanced solutions for network bargaining games with general capacities, where agents can participate in a fixed but arbitrary number of contracts. We provide the first polynomial time algorithm for computing balanced solutions for these games. In addition, we prove that an instance has a balanced solution if and only if it has a stable one. Our methods use a new idea of reducing an instance with general capacities to a network bargaining game with unit capacities defined on an auxiliary graph. This represents a departure from previous approaches, which rely on computing an allocation in the intersection of the core and prekernel of a corresponding cooperative game, and then proving that the solution corresponding to this allocation is balanced. In fact, we show that such cooperative game methods do not extend to general capacity games, since contrary to the case of unit capacities, there exist allocations in the intersection of the core and prekernel with no corresponding balanced solution. Finally, we identify two sufficient conditions under which the set of balanced solutions corresponds to the intersection of the core and prekernel, thereby extending the class of games for which this result was previously known.
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
Kleinberg, J., Tardos, É.: Balanced outcomes in social exchange networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 295–304. ACM (2008)
Azar, Y., Devanur, N., Jain, K., Rabani, Y.: Monotonicity in bargaining networks. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 817–826 (2010)
Bateni, M., Hajiaghayi, M., Immorlica, N., Mahini, H.: The cooperative game theory foundations of network bargaining games. Automata, Languages and Programming, 67–78 (2010)
Cook, K., Emerson, R., Gillmore, M., Yamagishi, T.: The distribution of power in exchange networks: Theory and experimental results. American Journal of Sociology, 275–305 (1983)
Cook, K., Yamagishi, T.: Power in exchange networks: A power-dependence formulation. Social Networks 14(3), 245–265 (1992)
Faigle, U., Kern, W., Kuipers, J.: An efficient algorithm for nucleolus and prekernel computation in some classes of tu-games (1998)
Kanoria, Y., Bayati, M., Borgs, C., Chayes, J., Montanari, A.: A natural dynamics for bargaining on exchange networks. arXiv preprint arXiv:0911.1767 (2009)
Nash Jr., J.: The bargaining problem. Econometrica: Journal of the Econometric Society, 155–162 (1950)
Rochford, S.: Symmetrically pairwise-bargained allocations in an assignment market. Journal of Economic Theory 34(2), 262–281 (1984)
Shapley, L., Shubik, M.: The assignment game i: The core. International Journal of Game Theory 1(1), 111–130 (1971)
Willer, D.: Network exchange theory. Praeger Publishers (1999)
Farczadi, L., Georgiou, K., Könemann, J.: Network bargaining with general capacities. arXiv preprint arXiv:1306.4302 (2013)
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
Farczadi, L., Georgiou, K., Könemann, J. (2013). Network Bargaining with General Capacities. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_37
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)