On games arising from multi-depot Chinese postman problems

Trine Platz and Herbert Hamers
Additional contact information
Herbert Hamers: Department of Econometrics & OR and CentER, Postal: Tilburg University, P.O. Box 90153, 5000 LE, Tilburg, The Netherlands

No 24/2012, Discussion Papers on Economics from University of Southern Denmark, Department of Economics

Abstract: 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 different 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 different 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.

Keywords: Chinese postman problem; cooperative game; submodularity; balancedness (search for similar items in EconPapers)
JEL-codes: C71 (search for similar items in EconPapers)
Pages: 20 pages
Date: 2012-12-02
New Economics Papers: this item is included in nep-gth, nep-hpe and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.sdu.dk/-/media/files/om_sdu/institutte ... 2012/dpbe24_2012.pdf Full text (application/pdf)

Related works:
Journal Article: On games arising from multi-depot Chinese postman problems (2015)
Working Paper: On Games Arising From Multi-Depot Chinese Postman Problems (2013)
Working Paper: On Games Arising From Multi-Depot Chinese Postman Problems (2013)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhs:sdueko:2012_024

Access Statistics for this paper

More papers in Discussion Papers on Economics from University of Southern Denmark, Department of Economics Department of Economics, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Astrid Holm Nielsen ().