Chinese Postman Games on a Class of Eulerian Graphs

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.