×

zbMATH — the first resource for mathematics

Routing-proofness in congestion-prone networks. (English) Zbl 1443.91025
Summary: We consider the problem of sharing the cost of connecting a large number of atomless agents in a network. The centralized agency elicits the target nodes that agents want to connect, and charges agents based on their demands. We look for a cost-sharing mechanism that satisfies three desirable properties: efficiency which charges agents based on the minimum total cost of connecting them in a network, stand-alone core stability which requires charging agents not more than the cost of connecting by themselves directly, and limit routing-proofness which prevents agents from profitable reporting as several agents connecting from A to C to B instead of A to B. We show that these three properties are not always compatible for any set of cost functions and demands. However, when these properties are compatible, a new egalitarian mechanism is shown to satisfy them. When the properties are not compatible, we find a rule that meets stand-alone core stability, limit routing-proofness and minimizes the budget deficit.
MSC:
91A12 Cooperative games
91A43 Games involving graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Han, L.; Juarez, R.; Free intermediation in resource transmission; Games Econ. Behav.: 2018; Volume 111 ,75-84. · Zbl 1416.91234
[2] Juarez, R.; Kumar, R.; Implementing efficient graphs in connection networks; Econ. Theory: 2013; Volume 54 ,359-403. · Zbl 1278.91092
[3] Frederick, H.; Gerald, L.; ; Introduction to Operations Research: Columbus, OH, USA 2009; .
[4] Moulin, H.; Cost sharing in networks: Some open questions; Int. Game Theory Rev.: 2013; Volume 15 ,1340001. · Zbl 1274.91051
[5] Dominique, H.; Moulin, H.; Traffic-based cost allocation in a network; RAND J. Econ.: 1996; Volume 27 ,332-345.
[6] Juarez, R.; Group strategyproof cost sharing: The role of indifferences; Games Econ. Behav.: 2013; Volume 82 ,218-239. · Zbl 1282.91129
[7] Melo, E.; Congestion pricing and learning in traffic network games; J. Public Econ. Theory: 2011; Volume 13 ,351-367.
[8] Roughgarden, T.; The Price of anarchy is independent of the network topology; J. Comput. Syst. Sci.: 2003; Volume 67 ,341-364. · Zbl 1072.68025
[9] Fotakis, D.; Spirakis, P.; Cost-balancing tolls for atomic network congestion games; Proceedings of the 3rd International Conference on Internet and Network Economics (WINE’07): ; ,179-190. · Zbl 1194.91057
[10] Moulin, H.; Pricing traffic in a spanning network; Proceedings of the 10th ACM Conference on Electronic Commerce (EC09): ; . · Zbl 1294.91037
[11] Juarez, R.; Ko, C.Y.; Xue, J.; Sharing sequential values in a network; J. Econ. Theory: 2018; Volume 77 ,734-779. · Zbl 1417.91045
[12] Chakrabarty, D.; Mehta, A.; Nagarajan, V.; Fairness and optimality in congestion games; Proceedings of the 6th ACM Conference on Electronic Commerce (EC ’05): ; ,52-57.
[13] Joel, S.; ; Linear Programming Note X Integer Programming: San Diego, CA, USA 2007; .
[14] Sprumont, Y.; The division problem with single-peaked preferences: A characterization of the uniform allocation rule; Econ. J. Econ. Soc.: 1991; Volume 59 ,509-519. · Zbl 0721.90012
[15] Benassy, J.P.; ; The Economics of Market Disequilibrium (No. 330.1/B45e): Cambridge, MA, USA 1982; .
[16] Bogomolnaia, A.; Holzman, R.; Moulin, H.; Sharing the cost of a capacity network; Math. Oper. Res.: 2010; Volume 35 ,173-192. · Zbl 1232.91063
[17] Dutta, B.; Mishra, D.; Minimum cost arborescences; Games Econ. Behav.: 2011; Volume 74 ,120-143. · Zbl 1278.91090
[18] Dong, B.; Guo, G.; Wang, Y.; Highway toll pricing; Eur. J. Oper. Res.: 2012; Volume 220 ,744-751. · Zbl 1253.91015
[19] Hougaard, J.L.; Tvede, M.; Truth-telling and nash equilibria in minimum cost spanning tree models; Eur. J. Oper. Res.: 2012; Volume 222 ,566-570. · Zbl 1253.91033
[20] Hougaard, J.L.; Tvede, M.; Minimum cost connection networks: Truth-telling and implementation; J. Econ. Theory: 2015; Volume 157 ,76-99. · Zbl 1330.91110
[21] Kumar, R.; Secure implementation in production economies; Math. Soc. Sci.: 2013; Volume 66 ,372-378. · Zbl 1296.91102
[22] Hougaard, J.L.; Moreno-Ternero, J.D.; Tvede, M.; sterdal, L.P.; Sharing the proceeds from a hierarchical venture; Games Econ. Behav.: 2017; Volume 102 ,98-110. · Zbl 1409.91148
[23] Moulin, H.; Laigret, F.; Equal-need sharing of a network under connectivity constraints; Games Econ. Behav.: 2011; Volume 72 ,314-320. · Zbl 1236.91094
[24] Juarez, R.; You, J.S.; Optimality of the uniform rule under single-peaked preferences; Econ. Theory Bull.: 2018; ,1-10.
[25] Hougaard, J.L.; ; An Introduction to Allocation Rules: Heidelberg/Berlin, Germany 2009; . · Zbl 1178.91001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.