IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v228y2013i1p158-168.html
   My bibliography  Save this article

Sharing costs in highways: A game theoretic approach

Author

Listed:
  • Kuipers, Jeroen
  • Mosquera, Manuel A.
  • Zarzuelo, José M.

Abstract

This paper introduces a new class of games, highway games, which arise from situations where there is a common resource that agents will jointly use. That resource is an ordered set of several indivisible sections, where each section has an associated fixed cost and each agent requires some consecutive sections. We present an easy formula to calculate the Shapley value, and we present an efficient procedure to calculate the nucleolus for this class of games.

Suggested Citation

  • Kuipers, Jeroen & Mosquera, Manuel A. & Zarzuelo, José M., 2013. "Sharing costs in highways: A game theoretic approach," European Journal of Operational Research, Elsevier, vol. 228(1), pages 158-168.
    • Handle: RePEc:eee:ejores:v:228:y:2013:i:1:p:158-168
    DOI: 10.1016/j.ejor.2013.01.018
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713000453
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.01.018?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Nimrod Megiddo, 1978. "Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree," Mathematics of Operations Research, INFORMS, vol. 3(3), pages 189-196, August.
    2. Castano-Pardo, Alberto & Garcia-Diaz, Alberto, 1995. "Highway cost allocation: An application of the theory of nonatomic games," Transportation Research Part A: Policy and Practice, Elsevier, vol. 29(3), pages 187-203, May.
    3. Rodica Brânzei & Vito Fragnelli & Stef Tijs, 2002. "Tree-connected peer group situations and peer group games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 55(1), pages 93-106, March.
    4. William H. Sandholm, 2002. "Evolutionary Implementation and Congestion Pricing," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 69(3), pages 667-689.
    5. Potters, Jos & Reijnierse, Hans & Biswas, Amit, 2006. "The nucleolus of balanced simple flow networks," Games and Economic Behavior, Elsevier, vol. 54(1), pages 205-225, January.
    6. Rodica Brânzei & Tamás Solymosi & Stef Tijs, 2005. "Strongly essential coalitions and the nucleolus of peer group games," International Journal of Game Theory, Springer;Game Theory Society, vol. 33(3), pages 447-460, September.
    7. Dong, Baomin & Guo, Guixia & Wang, Yuntong, 2012. "Highway toll pricing," European Journal of Operational Research, Elsevier, vol. 220(3), pages 744-751.
    8. Muto, S. & Nakayama, M. & Potters, J.A.M. & Tijs, S.H., 1988. "On big boss games," Other publications TiSEM 488a314a-179c-4628-91e6-7, Tilburg University, School of Economics and Management.
    9. M. Koster & H. Reijnierse & M. Voorneveld, 2003. "Voluntary Contributions to Multiple Public Projects," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 5(1), pages 25-50, January.
    10. Algaba, E. & Bilbao, J. M. & Fernandez Garcia, J. R. & Lopez, J. J., 2003. "Computing power indices in weighted multiple majority games," Mathematical Social Sciences, Elsevier, vol. 46(1), pages 63-80, August.
    11. Jeroen Kuipers & Ulrich Faigle & Walter Kern, 2001. "On the computation of the nucleolus of a cooperative game," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(1), pages 79-98.
    12. Çiftçi, BarIs & Borm, Peter & Hamers, Herbert, 2010. "Highway games on weakly cyclic graphs," European Journal of Operational Research, Elsevier, vol. 204(1), pages 117-124, July.
    13. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Curiel, I. & Pederzoli, G. & Tijs, S.H., 1989. "Sequencing games," Other publications TiSEM cd695be5-0f54-4548-a952-2, Tilburg University, School of Economics and Management.
    15. Solymosi, Tamas & Raghavan, Tirukkannamangai E S, 1994. "An Algorithm for Finding the Nucleolus of Asignment Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 23(2), pages 119-143.
    16. S.C. Littlechild & G.F. Thompson, 1977. "Aircraft Landing Fees: A Game Theory Approach," Bell Journal of Economics, The RAND Corporation, vol. 8(1), pages 186-204, Spring.
    17. S. C. Littlechild & G. Owen, 1973. "A Simple Expression for the Shapley Value in a Special Case," Management Science, INFORMS, vol. 20(3), pages 370-372, November.
    18. Granot, D & Maschler, M & Owen, G & Zhu, W.R., 1996. "The Kernel/Nucleolus of a Standard Tree Game," International Journal of Game Theory, Springer;Game Theory Society, vol. 25(2), pages 219-244.
    19. Daniel Granot & Jeroen Kuipers & Sunil Chopra, 2002. "Cost Allocation for a Tree Network with Heterogeneous Customers," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 647-661, November.
    20. Arin, Javier & Inarra, Elena, 1998. "A Characterization of the Nucleolus for Convex Games," Games and Economic Behavior, Elsevier, vol. 23(1), pages 12-24, April.
    21. Curiel, Imma & Pederzoli, Giorgio & Tijs, Stef, 1989. "Sequencing games," European Journal of Operational Research, Elsevier, vol. 40(3), pages 344-351, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wu, Hao & van den Brink, René & Estévez-Fernández, Arantza, 2024. "Highway toll allocation," Transportation Research Part B: Methodological, Elsevier, vol. 180(C).
    2. Sudhölter, Peter & Zarzuelo, José M., 2015. "On highway problems," Discussion Papers on Economics 13/2015, University of Southern Denmark, Department of Economics.
    3. M. J. Albizuri & J. M. Echarri & J. M. Zarzuelo, 2018. "A Non-cooperative Mechanism Yielding the Nucleolus of Airport Problems," Group Decision and Negotiation, Springer, vol. 27(1), pages 153-163, February.
    4. Algaba, Encarnación & Fragnelli, Vito & Llorca, Natividad & Sánchez-Soriano, Joaquin, 2019. "Horizontal cooperation in a multimodal public transport system: The profit allocation problem," European Journal of Operational Research, Elsevier, vol. 275(2), pages 659-665.
    5. Béal, Sylvain & Ferrières, Sylvain & Rémila, Eric & Solal, Philippe, 2018. "The proportional Shapley value and applications," Games and Economic Behavior, Elsevier, vol. 108(C), pages 93-112.
    6. Fatemeh Babaei & Hamidreza Navidi & Stefano Moretti, 2022. "A bankruptcy approach to solve the fixed cost allocation problem in transport systems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(2), pages 332-358, July.
    7. Gómez-Rodríguez, Marcos & Davila-Pena, Laura & Casas-Méndez, Balbina, 2024. "Cost allocation problems on highways with grouped users," European Journal of Operational Research, Elsevier, vol. 316(2), pages 667-679.
    8. van Beek, Andries & Groote Schaarsberg, Mirjam & Borm, Peter & Hamers, Herbert & Veneman, Mattijs, 2023. "Cost Allocation in CO2 Transport for CCUS Hubs : A Multi-Actor Perspective," Discussion Paper 2023-008, Tilburg University, Center for Economic Research.
    9. Rosenthal, Edward C., 2017. "A cooperative game approach to cost allocation in a rapid-transit network," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 64-77.
    10. Ciftci, B.B. & Borm, P.E.M. & Hamers, H.J.M., 2008. "A Note on the Balancedness and the Concavity of Highway Games," Discussion Paper 2008-29, Tilburg University, Center for Economic Research.
    11. van Beek, Andries, 2023. "Solutions in multi-actor projects with collaboration and strategic incentives," Other publications TiSEM 3739c498-5edb-442f-87d8-c, Tilburg University, School of Economics and Management.
    12. Léa Munich, 2023. "Schedule Situations and their Cooperative Games," Working Papers of BETA 2023-08, Bureau d'Economie Théorique et Appliquée, UDS, Strasbourg.
    13. Li, Xun & Rey, David & Dixit, Vinayak V., 2018. "An axiomatic characterization of fairness in transport networks: Application to road pricing and spatial equity," Transport Policy, Elsevier, vol. 68(C), pages 142-157.
    14. Hao Wu & Rene van den Brink & Arantza Estevez-Fernandez, 2022. "Highway toll allocation," Tinbergen Institute Discussion Papers 22-036/II, Tinbergen Institute.
    15. Dan C. Popescu & Philip Kilby, 2020. "Approximation of the Shapley value for the Euclidean travelling salesman game," Annals of Operations Research, Springer, vol. 289(2), pages 341-362, June.
    16. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2020. "Manipulability in the cost allocation of transport systems," ThE Papers 20/08, Department of Economic Theory and Economic History of the University of Granada..
    17. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2019. "On how to allocate the fixed cost of transport networks," ThE Papers 19/03, Department of Economic Theory and Economic History of the University of Granada..
    18. M. Albizuri & J. Echarri & J. Zarzuelo, 2015. "A non-cooperative mechanism for the Shapley value of airport problems," Annals of Operations Research, Springer, vol. 235(1), pages 1-11, December.
    19. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2021. "On how to allocate the fixed cost of transport systems," Annals of Operations Research, Springer, vol. 301(1), pages 81-105, June.
    20. Munich, Léa, 2024. "Schedule situations and their cooperative game theoretic representations," European Journal of Operational Research, Elsevier, vol. 316(2), pages 767-778.
    21. Sudhölter, Peter & Zarzuelo, José M., 2017. "Characterizations of highway toll pricing methods," European Journal of Operational Research, Elsevier, vol. 260(1), pages 161-170.
    22. Léa Munich, 2023. "Schedule Situations and their Cooperative Game Theoretic Representations," Working Papers 2023-08, CRESE.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Peter Borm & Herbert Hamers & Ruud Hendrickx, 2001. "Operations research games: A survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 9(2), pages 139-199, December.
    2. Xiaotie Deng & Qizhi Fang & Xiaoxun Sun, 2009. "Finding nucleolus of flow game," Journal of Combinatorial Optimization, Springer, vol. 18(1), pages 64-86, July.
    3. Jeroen Kuipers & Dries Vermeulen & Mark Voorneveld, 2010. "A generalization of the Shapley–Ichiishi result," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(4), pages 585-602, October.
    4. Sudhölter, Peter & Zarzuelo, José M., 2017. "Characterizations of highway toll pricing methods," European Journal of Operational Research, Elsevier, vol. 260(1), pages 161-170.
    5. Balázs Sziklai & Tamás Fleiner & Tamás Solymosi, 2014. "On the Core of Directed Acyclic Graph Games," CERS-IE WORKING PAPERS 1418, Institute of Economics, Centre for Economic and Regional Studies.
    6. Tijs, S.H. & Brânzei, R., 2004. "Cases in Cooperation and Cutting the Cake," Discussion Paper 2004-108, Tilburg University, Center for Economic Research.
    7. repec:has:discpr:1321 is not listed on IDEAS
    8. Tamas Solymosi & Balazs Sziklai, 2015. "Universal Characterization Sets for the Nucleolus in Balanced Games," CERS-IE WORKING PAPERS 1512, Institute of Economics, Centre for Economic and Regional Studies.
    9. Csóka, Péter & Illés, Ferenc & Solymosi, Tamás, 2022. "On the Shapley value of liability games," European Journal of Operational Research, Elsevier, vol. 300(1), pages 378-386.
    10. Daniel Granot & Jeroen Kuipers & Sunil Chopra, 2002. "Cost Allocation for a Tree Network with Heterogeneous Customers," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 647-661, November.
    11. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions (extended version)," CERS-IE WORKING PAPERS 1914, Institute of Economics, Centre for Economic and Regional Studies.
    12. repec:ehu:ikerla:34464 is not listed on IDEAS
    13. Habis, Helga, 2012. "Sztochasztikus csődjátékok - avagy hogyan osszunk szét egy bizonytalan méretű tortát? [Stochastic bankruptcy games. How can a cake of uncertain dimensions be divided?]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(12), pages 1299-1310.
    14. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(4), pages 1087-1109, December.
    15. René Brink, 2017. "Games with a permission structure - A survey on generalizations and applications," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(1), pages 1-33, April.
    16. M. Meertens & J. Potters, 2006. "The nucleolus of trees with revenues," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 64(2), pages 363-382, October.
    17. van den Brink, René & González-Arangüena, Enrique & Manuel, Conrado & del Pozo, Mónica, 2014. "Order monotonic solutions for generalized characteristic functions," European Journal of Operational Research, Elsevier, vol. 238(3), pages 786-796.
    18. Csóka, Péter & Jean-Jacques Herings, P. & Kóczy, László Á. & Pintér, Miklós, 2011. "Convex and exact games with non-transferable utility," European Journal of Operational Research, Elsevier, vol. 209(1), pages 57-62, February.
    19. René Brink & Ilya Katsev & Gerard Laan, 2011. "A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(3), pages 591-616, August.
    20. Sanjith Gopalakrishnan & Daniel Granot & Frieda Granot, 2021. "Consistent Allocation of Emission Responsibility in Fossil Fuel Supply Chains," Management Science, INFORMS, vol. 67(12), pages 7637-7668, December.
    21. Flip Klijn & Stef Tijs & Marco Slikker, 2001. "A Dual Egalitarian Solution," Economics Bulletin, AccessEcon, vol. 3(10), pages 1-8.
    22. Elena Iñarra & Roberto Serrano & Ken-Ichi Shimomura, 2020. "The Nucleolus, the Kernel, and the Bargaining Set: An Update," Revue économique, Presses de Sciences-Po, vol. 71(2), pages 225-266.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:228:y:2013:i:1:p:158-168. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.