IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v72y2011i2p427-438.html
   My bibliography  Save this article

On Chinese postman games where residents of each road pay the cost of their road

Author

Listed:
  • Granot, Daniel
  • Hamers, Herbert
  • Kuipers, Jeroen
  • Maschler, Michael

Abstract

We study the extended Chinese postman (CP) cooperative game induced by a connected, weighted, undirected graph G, wherein a postman, starting from a post office location, needs to traverse all edges wherein players reside, before returning to the post-office. We characterize the graphs associated with all CP games in which the players on a road pay exactly the cost of the road at each core point, regardless of the number of players residing on the road, the location of the post-office and the edge-weight functions. Here, a road is a maximal path all of whose interior vertices have a degree equal to two in G. For this class of games, the core and nucleolus are Cartesian products of CP games induced by simple cyclic graphs, the core is determined by at most 2n-1 constraints and the nucleolus can be computed in time.

Suggested Citation

  • Granot, Daniel & Hamers, Herbert & Kuipers, Jeroen & Maschler, Michael, 2011. "On Chinese postman games where residents of each road pay the cost of their road," Games and Economic Behavior, Elsevier, vol. 72(2), pages 427-438, June.
    • Handle: RePEc:eee:gamebe:v:72:y:2011:i:2:p:427-438
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825610000308
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hamers, Herbert, 1997. "On the concavity of delivery games," European Journal of Operational Research, Elsevier, vol. 99(2), pages 445-458, June.
    2. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Maschler, M & Potters, J A M & Tijs, S H, 1992. "The General Nucleolus and the Reduced Game Property," International Journal of Game Theory, Springer;Game Theory Society, vol. 21(1), pages 85-106.
    4. Hamers, Herbert & Borm, Peter & van de Leensel, Robert & Tijs, Stef, 1999. "Cost allocation in the Chinese postman problem," European Journal of Operational Research, Elsevier, vol. 118(1), pages 153-163, October.
    5. M. Maschler & B. Peleg & L. S. Shapley, 1979. "Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 303-338, November.
    6. Maschler, Michael, 1992. "The bargaining set, kernel, and nucleolus," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 1, chapter 18, pages 591-667, Elsevier.
    7. Maschler, M. & Potters, J.A.M. & Tijs, S.H., 1992. "The general nucleolus and the reduced game property," Other publications TiSEM ab187dab-1b5b-40c3-a673-8, Tilburg University, School of Economics and Management.
    8. Jeroen Kuipers & Ulrich Faigle & Walter Kern, 2001. "On the computation of the nucleolus of a cooperative game," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(1), pages 79-98.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Arantza (M.A.) Estevez-Fernandez & Herbert Hamers, 2018. "Chinese postman games with repeated players," Tinbergen Institute Discussion Papers 18-081/II, Tinbergen Institute.
    2. Estévez-Fernández, Arantza & Hamers, Herbert, 2020. "Chinese postman games with multi-located players," European Journal of Operational Research, Elsevier, vol. 285(2), pages 458-469.
    3. Tamas Solymosi & Balazs Sziklai, 2015. "Universal Characterization Sets for the Nucleolus in Balanced Games," CERS-IE WORKING PAPERS 1512, Institute of Economics, Centre for Economic and Regional Studies.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. D. Granot & H. Hamers & J. Kuipers & M. Maschler, 2004. "Chinese Postman Games on a Class of Eulerian Graphs," Discussion Paper Series dp366, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    2. Tamas Solymosi & Balazs Sziklai, 2015. "Universal Characterization Sets for the Nucleolus in Balanced Games," CERS-IE WORKING PAPERS 1512, Institute of Economics, Centre for Economic and Regional Studies.
    3. Rodica Brânzei & Tamás Solymosi & Stef Tijs, 2005. "Strongly essential coalitions and the nucleolus of peer group games," International Journal of Game Theory, Springer;Game Theory Society, vol. 33(3), pages 447-460, September.
    4. Slikker, Marco & Norde, Henk, 2011. "The monoclus of a coalitional game," Games and Economic Behavior, Elsevier, vol. 71(2), pages 420-435, March.
    5. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions (extended version)," CERS-IE WORKING PAPERS 1914, Institute of Economics, Centre for Economic and Regional Studies.
    6. Elena Iñarra & Roberto Serrano & Ken-Ichi Shimomura, 2020. "The Nucleolus, the Kernel, and the Bargaining Set: An Update," Revue économique, Presses de Sciences-Po, vol. 71(2), pages 225-266.
    7. Potters, Jos & Sudholter, Peter, 1999. "Airport problems and consistent allocation rules," Mathematical Social Sciences, Elsevier, vol. 38(1), pages 83-102, July.
    8. A. Estévez-Fernández & P. Borm & M. G. Fiestras-Janeiro & M. A. Mosquera & E. Sánchez-Rodríguez, 2017. "On the 1-nucleolus," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 86(2), pages 309-329, October.
      • Estévez-Fernández , M.A. & Borm, Peter & Fiestras, & Mosquera, & Sanchez,, 2017. "On the 1-nucleolus," Other publications TiSEM a8ce6687-c87a-4131-98f7-3, Tilburg University, School of Economics and Management.
    9. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(4), pages 1087-1109, December.
    10. Arin Aguirre, Francisco Javier, 2003. "Egalitarian distributions in coalitional models: The Lorenz criterion," IKERLANAK 6503, Universidad del País Vasco - Departamento de Fundamentos del Análisis Económico I.
    11. Slikker, M. & Norde, H.W., 2008. "The Monoclus of a Coalitional Game," Other publications TiSEM 8b2bae34-674a-4632-a64e-9, Tilburg University, School of Economics and Management.
    12. Reiner Wolff & Yavuz Karagök, 2012. "Consistent allocation of cabinet seats: the Swiss Magic Formula," Public Choice, Springer, vol. 150(3), pages 547-559, March.
    13. Márton Benedek & Jörg Fliege & Tri-Dung Nguyen, 2020. "Finding and verifying the nucleolus of cooperative games," CERS-IE WORKING PAPERS 2021, Institute of Economics, Centre for Economic and Regional Studies.
    14. Behzad Hezarkhani & Marco Slikker & Tom Woensel, 2016. "A competitive solution for cooperative truckload delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 51-80, January.
    15. Pedro Calleja & Francesc Llerena & Peter Sudhölter, 2020. "Monotonicity and Weighted Prenucleoli: A Characterization Without Consistency," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1056-1068, August.
    16. Ruiz, Luis M. & Valenciano, Federico & Zarzuelo, Jose M., 1998. "The Family of Least Square Values for Transferable Utility Games," Games and Economic Behavior, Elsevier, vol. 24(1-2), pages 109-130, July.
    17. Daniel Granot & Jeroen Kuipers & Sunil Chopra, 2002. "Cost Allocation for a Tree Network with Heterogeneous Customers," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 647-661, November.
    18. Arce M., Daniel G. & Sandler, Todd, 2003. "Health-promoting alliances," European Journal of Political Economy, Elsevier, vol. 19(2), pages 355-375, June.
    19. Péter Biró & Walter Kern & Daniël Paulusma, 2012. "Computing solutions for matching games," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(1), pages 75-90, February.
    20. M. Fiestras-Janeiro & Ignacio García-Jurado & Manuel Mosquera, 2011. "Cooperative games and cost allocation problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 19(1), pages 1-22, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:72:y:2011:i:2:p:427-438. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.