Stability in shortest path problems

Bahel, Eric and Gómez-Rúa, María and Vidal-Puga, Juan (2020): Stability in shortest path problems.

Abstract

We study three remarkable cost sharing rules in the context of shortest path problems, where agents have demands that can only be supplied by a source in a network. The demander rule requires each demander to pay the cost of their cheapest connection to the source. The supplier rule charges to each demander the cost of the second-cheapest connection and splits the excess payment equally between her access suppliers. The alexia rule averages out the lexicographic allocations, each of which allows suppliers to extract rent in some pre-specified order. We show that all three rules are anonymous and demand-additive core selections. Moreover, with three or more agents, the demander rule is characterized by core selection and a specific version of cost additivity. Finally, convex combinations of the demander rule and the supplier rule are axiomatized using core selection, a second version of cost additivity and two additional axioms that ensure the fair compensation of intermediaries.

• Item Type: MPRA Paper
• Language: English
• Keywords: Shortest path, cost sharing, core selection, additivity.
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D85 - Network Formation and Analysis: Theory

References

Bahel, E. and Trudeau, C. (2014). Stable lexicographic rules for shortest path games. Economic Letters, 125(2):266-269.

Bahel, E. and Trudeau, C. (2017). Minimum incoming cost rules for arborescences. Social Choice and Welfare, 49(2):287-314.

Bergantiños, G. and Vidal-Puga, J. (2009). Additivity in minimum cost spanning tree problems. Journal of Mathematical Economics, 45(1-2):38-42.

Bryan, D. and O'Kelly, M. (1999). Hub-and-spoke networks in air transportation: An analytical review. Journal of Regional Science, 39(2):275-295.

Dutta, B. and Kar, A. (2004). Cost monotonicity, consistency and minimum cost spanning tree games. Games and Economic Behavior, 48(2):223-248.

Dutta, B. and Mishra, D. (2012). Minimum cost arborescences. Games and Economic Behavior, 74(1):120-143.

Roni, M. S., Eksioglu, S. D., Cafferty, K. G., and Jacobson, J. J. (2017). A multiobjective, hub-and-spoke model to design and manage biofuel supply chains. Annals of Operations Research, 249(1):351-380.

Rosenthal, E. C. (2013). Shortest path games. European Journal of Operational Research, 224(1):132-140.

Shapley, L. S. (1953). A value for n-person games. In Kuhn, H. and Tucker, A., editors, Contributions to the theory of games, volume II of Annals of Mathematics Studies, pages 307-317. Princeton University Press, Princeton NJ.

Sim, T., Lowe, T. J., and Thomas, B. W. (2009). The stochastic-hub center problem with service-level constraints. Computers & Operations Research, 36(12):3166-3177.

Tijs, S., Borm, P., Lohmann, E., and Quant, M. (2011). An average lexicographic value for cooperative games. European Journal of Operational Research, 213(1):210-220.

Yang, T.-H. (2009). Stochastic air freight hub location and flight routes planning. Applied Mathematical Modelling, 33(12):4424-4430.