Abstract
In classical cooperative connection situations, the agents are located at some nodes of a network and the cost of a coalition is based on the problem of finding a network of minimum cost connecting all the members of the coalition to a source.
In this paper we study a different connection situation with no source and where the agents are the edges, and yet the optimal network associated to each coalition (of edges) is not fixed and follows a cost-optimization procedure. The proposed model shares some similarities with classical minimum cost spanning tree games, but also substantial differences, specifically on the appropriate way to share the costs among the agents located at the edges. We show that the core of these particular cooperative games is always non-empty and some core allocations can be easily computed.
S. Moretti—This work benefited from the support of the French National Research Agency (ANR) projects NETLEARN (grant no. ANR-13-INFR-004) and CoCoRICo-CoDec (grant no. ANR-14-CE24-0007).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aziz, H., Lachish, O., Paterson, M., Savani, R.: Wiretapping a hidden network. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 438–446. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10841-9_40
Bergañtinos, G., Lorenzo, L., Lorenzo-Freire, S.: A generalization of obligation rules for minimum cost spanning tree problems. Eur. J. Oper. Res. 211, 122–129 (2011)
Bird, C.: On cost allocation for a spanning tree: a game theoretic approach. Networks 6, 335–350 (1976)
Branzei, R., Moretti, S., Norde, H., Tijs, S.: The P-value for cost sharing in minimum cost spanning tree situations. Theory Decis. 56, 47–61 (2004)
Claus, A., Kleitman, D.J.: Cost allocation for a spanning tree. Networks 3, 289–304 (1973)
Feltkamp, V.: Cooperation in controlled network structures, PhD Dissertation, Tilburg University, The Netherlands (1995)
Granot, D., Huberman, G.: On minimum cost spanning tree games. Math. Prog. 21, 1–18 (1981)
Hougaard, J.L., Moulin, H.: Sharing the cost of redundant items. Games Econ. Behav. 87, 339–352 (2014)
Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7, 48–50 (1956)
Moretti, S., Tijs, S., Branzei, R., Norde, H.: Cost allocation protocols for supply contract design in network situations. Math. Meth. Oper. Res. 69(1), 181–202 (2009)
Moulin, H., Laigret, F.: Equal-need sharing of a network under connectivity constraints. Games Econ. Behav. 72(1), 314–320 (2011)
Nagamochi, H., Zeng, D.Z., Kabutoya, N., Ibaraki, T.: Complexity of the minimum base game on matroids. Math. Oper. Res. 22(1), 146–164 (1997)
Norde, H., Moretti, S., Tijs, S.: Minimum cost spanning tree games and population monotonic allocation schemes. Eur. J. Oper. Res. 154(1), 84–97 (2004)
Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389–1401 (1957)
Shapley, L.S.: A Value for n-Person Games. In: Kuhn, H.W., Tucker, A.W. (ed.) Contributions to the Theory of Games II, Ann. Math. Studies 28, 307–317, Princeton University Press (1953)
Shapley, L.S.: Cores and convex games. Int. J. Game Theory 1, 1–26 (1971)
Sprumont, Y.: Population monotonic allocation schemes for cooperative games with transferable utility. Games Econ. Behav. 2, 378–394 (1990)
Tijs, S., Branzei, R., Moretti, S., Norde, H.: Obligation rules for minimum cost spanning tree situations and their monotonicity properties. Eur. J. Oper. Res. 175, 121–134 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Moretti, S. (2018). On Cooperative Connection Situations Where the Players Are Located at the Edges. In: Belardinelli, F., Argente, E. (eds) Multi-Agent Systems and Agreement Technologies. EUMAS AT 2017 2017. Lecture Notes in Computer Science(), vol 10767. Springer, Cham. https://doi.org/10.1007/978-3-030-01713-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-030-01713-2_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-01712-5
Online ISBN: 978-3-030-01713-2
eBook Packages: Computer ScienceComputer Science (R0)