{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:24:13Z","timestamp":1740108253674,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T00:00:00Z","timestamp":1633046400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T00:00:00Z","timestamp":1635206400000},"content-version":"vor","delay-in-days":25,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014440","name":"Ministerio de Ciencia, Innovaci\u00f3n y Universidades","doi-asserted-by":"publisher","award":["PGC2018-095786-B-I00"],"award-info":[{"award-number":["PGC2018-095786-B-I00"]}],"id":[{"id":"10.13039\/100014440","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper considers networks in which nodes have communication needs between them. The cost of building or maintaining an edge with a given capacity is the same across any pair of agents. It is known that feasibility is reached by any maximal-capacity spanning tree. A multi-stage non-cooperative game is considered in which, at each stage, every agent simultaneously decides either to propose building a connection to another agent or to wait for a better opportunity. The required capacity between any pair of agents can be seen as being to their benefit if and only if, in the resulting tree, there exists a path between them such that every edge provides at least this required capacity. On the other hand, the agents who decide to connect have to pay for the link by equally splitting the cost. The problem is analyzed in a context in which the preferences of the agents regarding benefits and costs are lexicographic. The concepts of <jats:italic>capacity synthesis equilibrium<\/jats:italic> (CSE) and <jats:italic>strong capacity synthesis equilibrium<\/jats:italic> (strong CSE) are introduced and a mechanism to reach some of these equilibria is presented. We also analyze CSEs and strong CSEs in relation to the Nash equilibria of the benefit capacity synthesis game.<\/jats:p>","DOI":"10.1007\/s00186-021-00754-w","type":"journal-article","created":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T14:02:37Z","timestamp":1635256957000},"page":"219-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A non-cooperative game theory approach to cost sharing in networks"],"prefix":"10.1007","volume":"94","author":[{"given":"M. A.","family":"Hinojosa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Caro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,26]]},"reference":[{"key":"754_CR1","volume-title":"Network flows: theory. Algorithms and applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory. Algorithms and applications. Prentice Hall, New York"},{"key":"754_CR2","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s001860400352","volume":"59","author":"G Berganti\u00f1os","year":"2004","unstructured":"Berganti\u00f1os G, Lorenzo L (2004) A non-cooperative approach to the cost spanning tree problem. Math Methods Oper Res 59:393\u2013403","journal-title":"Math Methods Oper Res"},{"issue":"4","key":"754_CR3","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1007\/s00182-014-0456-4","volume":"44","author":"G Berganti\u00f1os","year":"2015","unstructured":"Berganti\u00f1os G, Vidal-Puga J (2015) Characterization of monotonic rules in minimum cost spanning tree problems. Internat J Game Theory 44(4):835\u2013868","journal-title":"Internat J Game Theory"},{"key":"754_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1002\/net.3230060404","volume":"6","author":"CG Bird","year":"1976","unstructured":"Bird CG (1976) On cost allocation for a spanning tree: a game theoretic approach. Networks 6:335\u2013350","journal-title":"Networks"},{"key":"754_CR5","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.geb.2009.11.001","volume":"69","author":"A Bogomolnaia","year":"2010","unstructured":"Bogomolnaia A, Moulin H (2010) Sharing the cost of a minimal-cost spanning tree: beyond the folk solution. Games Econom Behav 69:238\u2013248","journal-title":"Games Econom Behav"},{"issue":"1","key":"754_CR6","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1287\/moor.1090.0435","volume":"35","author":"A Bogomolnaia","year":"2010","unstructured":"Bogomolnaia A, Holzman R, Moulin T (2010) Sharing the cost of a capacity network. Math Oper Res 35(1):173\u2013192","journal-title":"Math Oper Res"},{"issue":"1","key":"754_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.11.1.1","volume":"11","author":"P Dubey","year":"1986","unstructured":"Dubey P (1986) Inefficiency of Nash equilibria. Math Oper Res 11(1):1\u20138","journal-title":"Math Oper Res"},{"issue":"3","key":"754_CR8","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s00186-008-0279-9","volume":"70","author":"FR Fern\u00e1ndez","year":"2009","unstructured":"Fern\u00e1ndez FR, Hinojosa MA, M\u00e1rmol A, Puerto J (2009) Opportune moment strategies for a (non-cooperative) cost spanning tree game. Math Methods Oper Res 70(3):451\u2013463","journal-title":"Math Methods Oper Res"},{"key":"754_CR9","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF02592000","volume":"29","author":"D Granot","year":"1984","unstructured":"Granot D, Huberman G (1984) On the core and nucleolus of minimum-cost spanning tree games. Math Program 29:323\u2013347","journal-title":"Math Program"},{"key":"754_CR10","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J Kruskal","year":"1956","unstructured":"Kruskal J (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7:48\u201350","journal-title":"Proc Am Math Soc"},{"key":"754_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S021919891340001X","volume":"15","author":"H Moulin","year":"2013","unstructured":"Moulin H (2013) Cost sharing in networks: some open questions. Int Game Theory Rev 15:1\u201310","journal-title":"Int Game Theory Rev"},{"key":"754_CR12","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1016\/j.geb.2018.08.002","volume":"113","author":"H Norde","year":"2019","unstructured":"Norde H (2019) The degree and cost adjusted folk solution for minimum cost spanning tree games. Games Econom Behav 113:734\u2013742","journal-title":"Games Econom Behav"},{"key":"754_CR13","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389\u20131401","journal-title":"Bell Syst Tech J"},{"key":"754_CR14","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF01594930","volume":"50","author":"A Tamir","year":"1991","unstructured":"Tamir A (1991) On the core of network synthesis games. Math Program 50:123\u2013135","journal-title":"Math Program"},{"key":"754_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/j.jet.2017.03.001","volume":"169","author":"C Trudeau","year":"2017","unstructured":"Trudeau C, Vidal-Puga J (2017) On the set of extreme core allocations for minimal cost spanning tree problems. J Econ Theory 169:425\u2013462","journal-title":"J Econ Theory"},{"key":"754_CR16","doi-asserted-by":"publisher","DOI":"10.1201\/9780203497289","volume-title":"Spanning trees and optimization problems","author":"BW Wu","year":"2004","unstructured":"Wu BW, Chao K (2004) Spanning trees and optimization problems. CRC Press, Boca Raton"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-021-00754-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-021-00754-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-021-00754-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T14:05:01Z","timestamp":1636639501000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-021-00754-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["754"],"URL":"https:\/\/doi.org\/10.1007\/s00186-021-00754-w","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"type":"print","value":"1432-2994"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[2021,10]]},"assertion":[{"value":"27 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}