One-way and two-way cost allocation in hub network problems

Bergantiños, Gustavo and Vidal-Puga, Juan (2018): One-way and two-way cost allocation in hub network problems.

Abstract

We consider a cost allocation problem arising from a hub network problem design. Finding an optimal hub network is NP-hard, so we start with a hub network that could be optimal or not. Our main objective is to divide the cost of such network among the nodes. We consider two cases. In the one-way flow case, we assume that the cost paid by a set of nodes depends only on the flow they send to other nodes (including nodes outside the set), but not on the flow they receive from nodes outside. In the two-way flow case, we assume that the cost paid by a set of nodes depends on the flow they send to other nodes(including nodes outside the set) and also on the flow they receive from nodes outside. In both cases, we study the core and the Shapley value of the corresponding cost game.

• Item Type: MPRA Paper
• Language: English
• Keywords: game theory; hub network; cost allocation; core; Shapley value
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

Alcalde-Unzu, J., G ́omez-R ́ua, M., and Molis, E. (2015). Sharing the costs of cleaning a river: the upstream responsibility rule.Games and Economic Behavior, 90:134–150.

Alumur, S. and Kara, B. Y. (2008). Network hub allocation problems: The state of the art. European Journal of Operational Research, 190:1–21.

Alumur, S. A., Nickel, S., Saldanha-da Gama, F., and Se ̧cerdin, Y. (2018). Multi-period hub network design problems with modular capacities. Annals of Operations Research, 246(1):289–312.

Azizi, N. (2018). Managing facility disruption in hub-and-spoke networks:formulations and efficient solution methods.Annals of Operations Re-search, Forthcoming.

Azizi, N., Vidyarthi, N., and Chauhan, S. S. (2018). Modelling and analysis of hub-and-spoke networks under stochastic demand and congestion.Annals of Operations Research, 264(1):1–40.

Bailey, J. (1997). The economics of Internet interconnection agreements. In McKnight, L. and Bailey, J., editors, Internet Economics, pages 115–168. MIT Press, Cambridge, MA.

Bergantiños, G. and Kar, A. (2010). On obligation rules for minimum cost spanning tree problems. Games and Economic Behavior, 69:224–237.

Bergantiños, G., Gómez-Rúa, M., Llorca, N., Pulido, M., and Sánchez-Soriano, J. (2014). A new rule for source connection problems. European Journal of Operational Research, 234(3):780–788.

Bogomolnaia, A. and Moulin, H. (2010). Sharing the cost of a minimal cost spanning tree: beyond the folk solution. Games and Economic Behavior,69(2):238–248.

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.

Contreras, I., Tanash, M., and Vidyarthi, N. (2017). Exact and heuristic approaches for the cycle hub location problem. Annals of Operations Research, 258(2):655–677.

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

Farahani, R. Z., Hekmatfar, M., Arabani, A. B., and Nikbakhsh, E.(2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4):1096–1109.

Gillies, D. (1959). Solutions to general non-zero sum games. In Tucker, A.and Luce, R., editors, Contributions to the theory of games, volume IV of Annals of Mathematics Studies, chapter 3, pages 47–85. Princeton UP, Princeton.

Greenfield, D. (2000). Europe’s virtual conundrum. Network Magazine, 15:116–123.

Guardiola, L. A., Meca, A., and Puerto, J. (2009). Production-inventory games: A new class of totally balanced combinatorial optimization games. Games and Economic Behavior, 65(1):205–219. Special Issue in Honor of Martin Shubik.

Guden, H. (2018). New complexity results for the p-hub median problem. Annals of Operations Research, Forthcoming.

Helme, M. and Magnanti, T. (1989). Designing satellite communication networks by zero-one quadratic programming. Networks, 19:427–450.

Jankovic, O., Miskovic, S., Stanimirovic, Z., and Todosijevic, R. (2017). Novel formulations and VNS-based heuristics for single and multiple allocation p-hub maximal covering problems. Annals of Operations Research, 259(1):191–216.

Matsubayashi, N., Umezawa, M., Masuda, Y., and Nishino, H. (2005). A cost allocation problem arising in hub-spoke network systems. European Journal of Operational Research, 160:821–838.

Moulin, H. (2014). Pricing traffic in a spanning network. Games and Economic Behavior, 86:475–490.

Perea, F., Puerto, J., and Fernandez, F. (2009). Modeling cooperation on a class of distribution problems. European Journal of Operational Research,198:726–733.

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

Shapley, L. S. (1953). A value for n-person games. In Kuhn, H.K.;Tucker,A., editor, 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.

Skorin-Kapov, D. (1998). Hub network games. Networks, 31:293–302.

Skorin-Kapov, D. (2001). On cost allocation in hub-like networks. Annals of Operations Research, 106:63–78.

Trudeau, C. (2012). A new stable and more responsible cost sharing solution for mcst problems. Games and Economic Behavior, 75(1): 402–412.

Trudeau, C. and Vidal-Puga, J. (2017). On the set of extreme core allocations for minimal cost spanning tree problems. Journal of Economic Theory, 169:425–452.

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