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 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.
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 Department of Business and Economics, University of Southern Denmark in its series Discussion Papers of Business and Economics with number 24/2012.
Length: 20 pages
Date of creation: 02 Dec 2012
Date of revision:
Contact details of provider:
Postal: Department of Business and Economics, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark
Phone: 65 50 32 33
Fax: 65 50 32 37
Web page: http://www.sdu.dk/ivoe
More information through EDIRC
Chinese postman problem; cooperative game; submodularity; balancedness;
Other versions of this item:
- 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.
- C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
This paper has been announced in the following NEP Reports:
- NEP-ALL-2012-12-15 (All new papers)
- NEP-GTH-2012-12-15 (Game Theory)
- NEP-HPE-2012-12-15 (History & Philosophy of Economics)
- NEP-TRE-2012-12-15 (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, 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.
- Hamers, Herbert, 1997. "On the concavity of delivery games," European Journal of Operational Research, Elsevier, vol. 99(2), pages 445-458, June.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Lene Holbæk).
If references are entirely missing, you can add them using this form.