Discussion Papers on Economics,
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

JEL-codes: C71

20 pages, December 2, 2012

Full text files

dpbe24_2012.pdf  Full text

Download statistics

• University of Southern Denmark, Department of Economics
• Home page for this series

Questions (including download problems) about the papers in this series should be directed to Astrid Holm Nielsen ()
Report other problems with accessing this service to Sune Karlsson ().

This page generated on 2024-02-05 17:13:32.