Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the core of routing games

  • Published:
International Journal of Game Theory Aims and scope Submit manuscript

Abstract

A repairman makes a round-trip along a set of customers. He starts in his home location, visits each customer exactly once, and returns home. The cost of his trip has to be shared by the customers. A cooperative cost game, calledrouting game, is associated with this allocation problem, and anO(n 2) algorithm is given which computes a core element of a routing game if the core is non-empty. The non-emptiness of the core depends on the tour which is traversed by the repairman. Several procedures are given to construct tours which guarantee the non-emptiness of the core.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aarts H, Solymosi T (1984) AnO(n 4) algorithm to determine the nucleolus of a routing game with non-empty core. Working paper, University of Twente, The Netherlands

    Google Scholar 

  2. Aumann RJ, Maschler M (1985) Game theoretic analysis of a bankruptcy problem from the talmuds. Journal of Economic Theory 36: 195–213

    Google Scholar 

  3. Curiel IJ, Pederzoli G, Tijs SH (1989) Sequencing games. European Journal of Operational Research 40: 344–351

    Google Scholar 

  4. Derks JJM, Gilles R, Kuipers J (1994) Coalition formation with limited communication. Working paper, RE Maastricht, The Netherlands

  5. Fishburn PC, Pollack HO (1983) Fixed route cost allocation. American Mathematical Monthly 90: 366–378

    Google Scholar 

  6. Fonlupt J, Naddef D (1992) The traveling salesman problem in graphs with some excluded minors. Mathematical Programming 53: 147–172

    Google Scholar 

  7. Granot D, Huberman G (1981) Minimum cost spanning tree games. Mathematical Programming 21: 1–18

    Google Scholar 

  8. Kuipers J (1994) Combinatorial methods in cooperative game theory. PhD Thesis, Maastricht

  9. Kuipers J (1991) A note on the 5-person traveling salesman game. Zeitschrift fur Operations Research 21: 339–351

    Google Scholar 

  10. Maschler M, Peleg B, Shapley ES (1979) Geometric properties of the kernel, nucleolus, and related solution concepts. Methods of Operations Research 4: 303–338

    Google Scholar 

  11. Owen G (1975) On the core of linear production games. Mathematical Programming 9: 358–370

    Google Scholar 

  12. Papadimitriou CH, Steiglitz K (1982) Combinatorial optimization: Algorithms and complexity. Prentice-Hall

  13. Potters JAM, Curiel IJ, Tijs SH (1992) Traveling salesman games. Mathematical Programming 53: 199–211

    Google Scholar 

  14. Shapley LS, Shubik M (1971) The assignment gamei: the core. International Journal of Game Theory 1: 111–130

    Google Scholar 

  15. Tamir A (1989) On the core of a traveling salesman cost allocation game. Operation Research Eetters 8: 31–34

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Faculty of General Sciences, University of Limburg, P.O. Box 616, 6200, MD Maastricht, The Netherlands

    Jean Derks & Jeroen Kuipers

Authors
  1. Jean Derks
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jeroen Kuipers
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Derks, J., Kuipers, J. On the core of routing games. Int J Game Theory 26, 193–205 (1997). https://doi.org/10.1007/BF01295848

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01295848

Keywords

Search

Navigation