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

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

Abstract

We study hub problems where a set of nodes send and receive data from each other. In order to reduce costs, the nodes use a network with a given set of hubs. We address the cost sharing aspect by assuming that nodes are only interested in either sending or receiving data, but not both (one-way flow) or that nodes are interested in both sending and receiving data (two-way flow). In both cases, we study the non-emptiness of the core and the Shapley value of the corresponding cost game.

• Item Type: MPRA Paper
• Language: English
• Keywords: 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ómez-Rúa, 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.

Aykin, T. (1994). Lagrangean relaxation based approaches to capacitated hub-and-spoke network design problem. European Journal of Operational Research, 79(3):501–523.

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.

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.

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

Ernst, A. and Krishnamoorthy, M. (1999). Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research, 86:141–159.

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.

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.

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

Labbé, M., Yaman, H., and Gourdin, E. (2005). A branch and cut algorithm for the hub location problems with single assignment. Mathematical Programming, 102:371–405.

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.

Sasaki, M. and Fukushima, M. (2003). On the hub-and-spoke model with arc capacity constraints. Journal of the Operations Research Society of Japan, 46(4):409–428.

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. New developments on hub location.

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. (2014). Minimum cost spanning tree problems with indifferent agents. Games and Economic Behavior, 84:137–151.

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