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

Chinese postman games with multi-located players

Author

Listed:
  • Estévez-Fernández, Arantza
  • Hamers, Herbert

Abstract

This paper analyses Chinese postman games with multi-located players, which generalize Chinese postman games by dropping the one-to-one relation between edges and players. In our model, we allow players to be located on more than one edge, but at most one player is located on each edge. The one-to-one relation between edges and players is essential for the equivalence between Chinese postman-totally balanced and Chinese postman-submodular graphs shown in the literature. We illustrate the invalidity of this result in our model. Besides, the location of the post office has a relevant role in the submodularity and totally balancedness of Chinese postman games with multi-located players. Therefore, we focus on sufficient conditions on the assignment of players to edges to ensure submodularity of Chinese postman games with multi-located players, independently of the associated travel costs. Moreover, we provide some insights on the difficulty of finding necessary conditions on assignment functions to this end.

Suggested Citation

  • Estévez-Fernández, Arantza & Hamers, Herbert, 2020. "Chinese postman games with multi-located players," European Journal of Operational Research, Elsevier, vol. 285(2), pages 458-469.
    • Handle: RePEc:eee:ejores:v:285:y:2020:i:2:p:458-469
    DOI: 10.1016/j.ejor.2020.01.062
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720301004
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.01.062?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. Granot, D. & Hamers, H.J.M. & Tijs, S.H., 1999. "On some balanced, totally balanced and submodular delivery games," Other publications TiSEM e0496604-0162-4a27-992c-a, Tilburg University, School of Economics and Management.
    2. Hamers, Herbert, 1997. "On the concavity of delivery games," European Journal of Operational Research, Elsevier, vol. 99(2), pages 445-458, June.
    3. Granot, Daniel & Hamers, Herbert & Kuipers, Jeroen & Maschler, Michael, 2011. "On Chinese postman games where residents of each road pay the cost of their road," Games and Economic Behavior, Elsevier, vol. 72(2), pages 427-438, June.
    4. 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.
    5. Hamers, Herbert & Borm, Peter & van de Leensel, Robert & Tijs, Stef, 1999. "Cost allocation in the Chinese postman problem," European Journal of Operational Research, Elsevier, vol. 118(1), pages 153-163, October.
    6. Arantza Estévez-Fernández & Peter Borm & Pedro Calleja & Herbert Hamers, 2008. "Sequencing games with repeated players," Annals of Operations Research, Springer, vol. 158(1), pages 189-203, February.
    7. Lloyd S. Shapley, 1967. "On balanced sets and cores," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 14(4), pages 453-460.
    8. Silvia Miquel & Bas Van Velzen & Herbert Hamers & Henk Norde, 2009. "Assignment Situations With Multiple Ownership And Their Games," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 11(01), pages 1-13.
    9. Arantza Estévez-Fernández & Peter Borm & Pedro Calleja & Herbert Hamers, 2008. "Sequencing games with repeated players," Annals of Operations Research, Springer, vol. 158(1), pages 189-203, February.
    Full references (including those not matched with items on IDEAS)

    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. Arantza (M.A.) Estevez-Fernandez & Herbert Hamers, 2018. "Chinese postman games with repeated players," Tinbergen Institute Discussion Papers 18-081/II, Tinbergen Institute.
    2. Trine Platz & Herbert Hamers, 2015. "On games arising from multi-depot Chinese postman problems," Annals of Operations Research, Springer, vol. 235(1), pages 675-692, December.
    3. Schouten, Jop, 2022. "Cooperation, allocation and strategy in interactive decision-making," Other publications TiSEM d5d41448-8033-4f6b-8ec0-c, Tilburg University, School of Economics and Management.
    4. 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.
    5. Hamers, H.J.M. & Josune Albizuri, M., 2013. "Graphs Inducing Totally Balanced and Submodular Chinese Postman Games," Other publications TiSEM b1fbd78c-1207-4d55-8313-2, Tilburg University, School of Economics and Management.
    6. Hamers, H.J.M. & Josune Albizuri, M., 2013. "Graphs Inducing Totally Balanced and Submodular Chinese Postman Games," Discussion Paper 2013-006, Tilburg University, Center for Economic Research.
    7. Behzad Hezarkhani & Marco Slikker & Tom Woensel, 2016. "A competitive solution for cooperative truckload delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 51-80, January.
    8. Marieke Quant & Marc Meertens & Hans Reijnierse, 2008. "Processing games with shared interest," Annals of Operations Research, Springer, vol. 158(1), pages 219-228, February.
    9. Alparslan-Gok, S.Z. & Miquel, S. & Tijs, S.H., 2008. "Cooperation under Interval Uncertainty," Other publications TiSEM 9a01bd57-964d-4e71-8508-7, Tilburg University, School of Economics and Management.
    10. Luis A. Guardiola & Ana Meca & Justo Puerto, 2022. "The effect of consolidated periods in heterogeneous lot-sizing games," 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 380-404, July.
    11. Hamers, H.J.M. & Miquel, S. & Norde, H.W., 2011. "Monotonic Stable Solutions for Minimum Coloring Games," Other publications TiSEM efae8d09-83e6-4fe4-9623-e, Tilburg University, School of Economics and Management.
    12. Heuvel, Wilco van den & Borm, Peter & Hamers, Herbert, 2007. "Economic lot-sizing games," European Journal of Operational Research, Elsevier, vol. 176(2), pages 1117-1130, January.
    13. Ç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.
    14. Davila-Pena, Laura & Borm, Peter & Garcia-Jurado, Ignacio & Schouten, Jop, 2023. "An Allocation Rule for Graph Machine Scheduling Problems," Other publications TiSEM 17013f33-1d65-4294-802c-b, Tilburg University, School of Economics and Management.
    15. D. Granot & H. Hamers & J. Kuipers & M. Maschler, 2004. "Chinese Postman Games on a Class of Eulerian Graphs," Discussion Paper Series dp366, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    16. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, G., 2020. "Sequencing Situations and Games with Non-Linear Cost Functions," Other publications TiSEM 3e1db5c9-0f77-4f91-a075-c, Tilburg University, School of Economics and Management.
    17. Okan Örsan Özener & Özlem Ergun, 2008. "Allocating Costs in a Collaborative Transportation Procurement Network," Transportation Science, INFORMS, vol. 42(2), pages 146-165, May.
    18. Jin, Xuefeng & Park, Kang Tae & Kim, Kap Hwan, 2019. "Storage space sharing among container handling companies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 111-131.
    19. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, G., 2020. "Sequencing Situations and Games with Non-Linear Cost Functions," Discussion Paper 2020-006, Tilburg University, Center for Economic Research.
    20. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, M. Gloria, 2021. "Sequencing situations and games with non-linear cost functions under optimal order consistency," European Journal of Operational Research, Elsevier, vol. 294(2), pages 734-745.

    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:285:y:2020:i:2:p:458-469. 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.