Chinese postman games with multi-located players

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

This paper analyses Chinese postman games with multi-located players, which generalize Chinese postman games by dropping the one-to-one relation between edges and players. In our model, we allow players to be located on more than one edge, but at most one player is located on each edge. The one-to-one relation between edges and players is essential for the equivalence between Chinese postman-totally balanced and Chinese postman-submodular graphs shown in the literature. We illustrate the invalidity of this result in our model. Besides, the location of the post office has a relevant role in the submodularity and totally balancedness of Chinese postman games with multi-located players. Therefore, we focus on sufficient conditions on the assignment of players to edges to ensure submodularity of Chinese postman games with multi-located players, independently of the associated travel costs. Moreover, we provide some insights on the difficulty of finding necessary conditions on assignment functions to this end.
Original languageEnglish
Pages (from-to)458-469
Number of pages12
JournalEuropean Journal of Operational Research
Volume285
Issue number2
DOIs
Publication statusPublished - 1 Sep 2020

Keywords

  • Assignment function
  • Chinese postman games with multi-located players
  • Game theory
  • Submodular game
  • Totally balanced game

Fingerprint Dive into the research topics of 'Chinese postman games with multi-located players'. Together they form a unique fingerprint.

  • Cite this