IDEAS home Printed from
   My bibliography  Save this paper

On Games Arising From Multi-Depot Chinese Postman Problems


  • Platz, T.T.
  • Hamers, H.J.M.

    (Tilburg University, Center For Economic Research)


This paper introduces cooperative games arising from multi-depot Chinese postman problems and explores the properties of these games. A multi-depot Chinese postman problem (MDCP) is represented by a connected (di)graph G, a set of k depots that is a subset of the vertices of G, and a non-negative weight function on the edges of G. A solution to the MDCP is a minimum weight tour of the (di)graph that visits all edges (arcs) of the graph and that consists of a collection of subtours such that the subtours originate from dierent depots, and each subtour starts and ends at the same depot. A cooperative Chinese postman (CP) game is induced by a MDCP by associating every edge of the graph with a dierent player. This paper characterizes globally and locally k-CP balanced and submodular (di)graphs. A (di)graph G is called globally (locally) k-CP balanced (respectively submodular), if the induced CP game of the corresponding MDCP problem on G is balanced (respectively submodular) for any (some) choice of the locations of the k depots and every non-negative weight function

Suggested Citation

  • Platz, T.T. & Hamers, H.J.M., 2013. "On Games Arising From Multi-Depot Chinese Postman Problems," Discussion Paper 2013-005, Tilburg University, Center for Economic Research.
  • Handle: RePEc:tiu:tiucen:6f68c9c0-75bc-4060-9ee3-462d53105427

    Download full text from publisher

    File URL:
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    1. Hamers, Herbert, 1997. "On the concavity of delivery games," European Journal of Operational Research, Elsevier, vol. 99(2), pages 445-458, June.
    2. Marco Slikker, 2005. "Balancedness of Sequencing Games with Multiple Parallel Machines," Annals of Operations Research, Springer, vol. 137(1), pages 177-189, July.
    3. 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.
    4. Fiestras-Janeiro, M.G. & García-Jurado, I. & Meca, A. & Mosquera, M.A., 2011. "Cooperative game theory and inventory management," European Journal of Operational Research, Elsevier, vol. 210(3), pages 459-466, May.
    5. Herbert Hamers & Flip Klijn & Bas Velzen, 2005. "On the Convexity of Precedence Sequencing Games," Annals of Operations Research, Springer, vol. 137(1), pages 161-175, July.
    6. Stefan Engevall & Maud Göthe-Lundgren & Peter Värbrand, 1998. "The traveling salesman game: An application ofcost allocation in a gas and oil company," Annals of Operations Research, Springer, vol. 82(0), pages 203-218, August.
    7. Dezső Bednay, 2014. "Stable sets in one-seller assignment games," Annals of Operations Research, Springer, vol. 222(1), pages 143-152, November.
    8. 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.
    9. repec:spr:compst:v:58:y:2003:i:1:p:131-139 is not listed on IDEAS
    10. Hamers, H.J.M. & Miquel, S. & Norde, H.W., 2011. "Monotonic Stable Solutions for Minimum Coloring Games," Discussion Paper 2011-016, Tilburg University, Center for Economic Research.
    11. Potters, J.A.M. & Curiel, I. & Tijs, S.H., 1992. "Traveling salesman games," Other publications TiSEM 0dd4cf3d-25fa-4179-80f6-6, Tilburg University, School of Economics and Management.
    12. Yoshio Okamoto, 2003. "Submodularity of some classes of the combinatorial optimization games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 58(1), pages 131-139, September.
    Full references (including those not matched with items on IDEAS)


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

    Cited by:

    1. 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.
    2. Arantza (M.A.) Estevez-Fernandez & Herbert Hamers, 2018. "Chinese postman games with repeated players," Tinbergen Institute Discussion Papers 18-081/II, Tinbergen Institute.
    3. Platz, Trine Tornøe, 2017. "On the submodularity of multi-depot traveling salesman games," Discussion Papers of Business and Economics 8/2017, University of Southern Denmark, Department of Business and Economics.

    More about this item


    Chinese postman problem; cooperative game; submodularity; bal- ancedness;

    JEL classification:

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


    Access and download statistics


    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:tiu:tiucen:6f68c9c0-75bc-4060-9ee3-462d53105427. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Richard Broekman). General contact details of provider: .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.