On The Chinese Postman Game

Daniel Granot (), Herbert Hamers (), Jeroen Kuipers () and Michael Maschler ()
Additional contact information
Daniel Granot: University of British Columbia, Faculty of Commerce
Herbert Hamers: Tilburg University, Center and Department of Econometrics
Jeroen Kuipers: University of Maastricht, Dept. of Mathematics
Michael Maschler: The Hebrew University of Jerusalem, Department of Mathematics and Center for Rationality and Interactive Decision Theory

A chapter in ICM Millennium Lectures on Games, 2003, pp 297-303 from Springer

Abstract: Summary The paper examines an extended model of the Chinese Postman (CP) game which allows for prizes and public edges, that is, edges not belonging to any of the players. The prizes, which are associated with the edges, are collected only upon the first traversal of the edges, and their inclusion in the model is analogous to the introduction of prizes in the traveling salesmen problem. A class of CP-games induced by Eulerian graphs, without public edges, having the 4-cut property is analyzed. In particular, it is shown that both the core and nucleolus are the Cartesian products of the cores and nucleoli of CP-games defined on cycle graphs, which are induced by elementary subpaths in the original graph. Moreover, for CP-games induced by Eulerian graphs having the 4-cut property, but without public edges, one can test core membership in linear time and the nucleolus can be computed in quadratic time.

Keywords: Travel Salesman Problem; Cooperative Game; Post Office; Cooperative Game Theory; Quadratic Time (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-3-662-05219-8_18

Ordering information: This item can be ordered from
http://www.springer.com/9783662052198

DOI: 10.1007/978-3-662-05219-8_18

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().