Chinese Postman Games on a Class of Eulerian Graphs

D. Granot (), H. Hamers (), J. Kuipers () and M. Maschler ()

Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem

Abstract: The extended Chinese postman (CP) enterprize is induced by a connected and undirected graph G. A server is located at some fixed vertex of G, to be referred to as the post office. Each player resides in a single edge, and each edge contains at most one player. Thus, some of the edges can be “public”. Each edge has a cost and a prize attached to it. The players need some service, e.g., mail delivery, which requires the server to travel from the post office and visit all edges wherein players reside, before returning to the post office. The server collects the prize attached to an edge upon the first traversal of this edge, but the cost of an edge is incurred every time it is traversed. The cost of a cheapest tour for each coalition defines a CP cost game. The issue is how to allocate, among the players, the cost that the server incurs. We study the class of extended CP enterprizes which are induced by Eulerian graphs satisfying two properties: The 4-cut property (Definition 4.4) and completeness (Definition 4.8). For this class we prove that the core, resp., the nucleolus when the core is not empty, are Cartesian products of the cores, resp., nucleoli of CP enterprizes whose graphs are simple cycles generated from G by identifying therein the end points of each elementary path (Definition 4.3). Finally, for the class of extended complete Eulerian graphs having the 4-cut property, we are able to test core membership in O(n) time, and when the core is not empty, we show how to calculate the nucleolus in O(n^2) time, n being the number of players.

Keywords: cooperative games; cost allocation; core; nucleolus; Chinese postman (search for similar items in EconPapers)
JEL-codes: C61 C63 C71 (search for similar items in EconPapers)
Pages: 25 pages
Date: 2004-07
New Economics Papers: this item is included in nep-sea and nep-tra
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://ratio.huji.ac.il/sites/default/files/publications/dp366.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp366.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp366.pdf)

Related works:
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:huj:dispap:dp366

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin ().