On Games Arising From Multi-Depot Chinese Postman Problems
AbstractThis 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 di erent 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 di erent 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
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Tilburg University, Center for Economic Research in its series Discussion Paper with number 2013-005.
Date of creation: 2013
Date of revision:
Contact details of provider:
Web page: http://center.uvt.nl
Chinese postman problem; cooperative game; submodularity; bal- ancedness;
Other versions of this item:
- Platz, Trine Tornøe & Hamers, Herbert, 2012. "On games arising from multi-depot Chinese postman problems," Discussion Papers of Business and Economics 24/2012, Department of Business and Economics, University of Southern Denmark.
- C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
This paper has been announced in the following NEP Reports:
- NEP-ALL-2013-02-08 (All new papers)
- NEP-GTH-2013-02-08 (Game Theory)
- NEP-TRE-2013-02-08 (Transport Economics)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Hamers, Herbert, 1997. "On the concavity of delivery games," European Journal of Operational Research, Elsevier, vol. 99(2), pages 445-458, June.
- 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.
- Yoshio Okamoto, 2003. "Submodularity of some classes of the combinatorial optimization games," Computational Statistics, Springer, vol. 58(1), pages 131-139, 09.
- 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.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Richard Broekman).
If references are entirely missing, you can add them using this form.