IDEAS home Printed from https://ideas.repec.org/p/tin/wpaper/20180081.html
   My bibliography  Save this paper

Chinese postman games with repeated players

Author

Listed:
  • Arantza (M.A.) Estevez-Fernandez

    (VU Amsterdam)

  • Herbert Hamers

    (Tilburg University)

Abstract

This paper analyses Chinese postman games with repeated players, which generalize Chinese postman games by dropping the one-to-one relation between edges and players. In our model, we allow players to own more than one edge, but each edge belongs to at most one player. 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 Granot et al. (1999). 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 repeated players. Therefore, we focus on sufficient conditions on the assignment of players to edges to ensure submodularity of Chinese postman games with repeated 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

  • Arantza (M.A.) Estevez-Fernandez & Herbert Hamers, 2018. "Chinese postman games with repeated players," Tinbergen Institute Discussion Papers 18-081/II, Tinbergen Institute.
    • Handle: RePEc:tin:wpaper:20180081
    as

    Download full text from publisher

    File URL: https://papers.tinbergen.nl/18081.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Calleja, P. & Estevez Fernandez, M.A. & Borm, P.E.M. & Hamers, H.J.M., 2004. "Job Scheduling, Cooperation and Control," Discussion Paper 2004-65, Tilburg University, Center for Economic Research.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    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. 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.
    2. Marieke Quant & Marc Meertens & Hans Reijnierse, 2008. "Processing games with shared interest," Annals of Operations Research, Springer, vol. 158(1), pages 219-228, February.
    3. Estevez Fernandez, M.A. & Mosquera, M.A. & Borm, P.E.M. & Hamers, H.J.M., 2006. "Proportionate Flow Shop Games," Discussion Paper 2006-63, Tilburg University, Center for Economic Research.
    4. Platz, Trine Tornøe, 2017. "On the submodularity of multi-depot traveling salesman games," Discussion Papers on Economics 8/2017, University of Southern Denmark, Department of Economics.
    5. 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.
    6. Estévez-Fernández, Arantza, 2012. "A game theoretical approach to sharing penalties and rewards in projects," European Journal of Operational Research, Elsevier, vol. 216(3), pages 647-657.
    7. van Beek, Andries & Malmberg, Benjamin & Borm, Peter & Quant, Marieke & Schouten, Jop, 2021. "Cooperation and Competition in Linear Production and Sequencing Processes," Discussion Paper 2021-011, Tilburg University, Center for Economic Research.
    8. 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.
    9. Reijnierse, Hans & Borm, Peter & Quant, Marieke & Meertens, Marc, 2010. "Processing games with restricted capacities," European Journal of Operational Research, Elsevier, vol. 202(3), pages 773-780, May.
    10. Lorenzo Castelli & Raffaele Pesenti & Andrea Ranieri, 2009. "Allocating Air Traffic Flow Management Slots," Working Papers 191, Department of Applied Mathematics, Università Ca' Foscari Venezia.
    11. Flip Klijn & Marco Slikker, 2004. "Distribution Center Consolidation Games," UFAE and IAE Working Papers 602.04, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    12. Munich, Léa, 2024. "Schedule situations and their cooperative game theoretic representations," European Journal of Operational Research, Elsevier, vol. 316(2), pages 767-778.
    13. Gerichhausen, M. & Hamers, H.J.M., 2007. "Partitioning Sequencing Situations and Games," Other publications TiSEM 2bddbf5c-c56d-4b10-ba47-5, Tilburg University, School of Economics and Management.
    14. 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.
    15. 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.
    16. Barry Charles Ezell & Steven P. Bennett & Detlof Von Winterfeldt & John Sokolowski & Andrew J. Collins, 2010. "Probabilistic Risk Analysis and Terrorism Risk," Risk Analysis, John Wiley & Sons, vol. 30(4), pages 575-589, April.
    17. Fragnelli, V. & Llorca, N. & Sánchez-Soriano, J. & Tijs, S.H., 2006. "Convex Games with Countable Number of Players and Sequencing Situations," Discussion Paper 2006-119, Tilburg University, Center for Economic Research.
    18. Özen, Ulas & Norde, Henk & Slikker, Marco, 2011. "On the convexity of newsvendor games," International Journal of Production Economics, Elsevier, vol. 133(1), pages 35-42, September.
    19. Gustavo Bergantiños & Juan Vidal-Puga, 2021. "A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 12(1), pages 73-100, March.
    20. M. Fiestras-Janeiro & Ignacio García-Jurado & Manuel Mosquera, 2011. "Cooperative games and cost allocation problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 19(1), pages 1-22, July.

    More about this item

    Keywords

    Chinese postman games with repeated players; balanced game; totally balanced game; submodular game; assignment function;
    All these keywords.

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:tin:wpaper:20180081. 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: Tinbergen Office +31 (0)10-4088900 (email available below). General contact details of provider: https://edirc.repec.org/data/tinbenl.html .

    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.