IDEAS home Printed from https://ideas.repec.org/p/adl/wpaper/2015-09.html
   My bibliography  Save this paper

Coincidence of Cooperative Game Theoretic Solutions in the Appointment Problem

Author

Listed:
  • Youngsub Chun

    (Seoul National University)

  • Nari Park

    (Seoul National University)

  • Duygu Yengin

    (School of Economics, University of Adelaide)

Abstract

The fixed-route traveling salesman problem with appointments, simply the appointment problem, is concerned with the following situation. Starting from home, a traveller makes a scheduled visit to a set of sponsors and returns home. If a sponsor in the route cancels her appointment, the traveller returns home and waits for the next appointment. We are interested in finding a way of dividing the total traveling cost among sponsors in the appointment problem by applying solutions developed in the cooperative game theory. We show that the well-known solutions of the cooperative game theory, the Shapley value, the nucleolus (or the prenucleolus), and the t -value, coincide under a mild condition onthe traveling cost.

Suggested Citation

  • Youngsub Chun & Nari Park & Duygu Yengin, 2015. "Coincidence of Cooperative Game Theoretic Solutions in the Appointment Problem," School of Economics and Public Policy Working Papers 2015-09, University of Adelaide, School of Economics and Public Policy.
    • Handle: RePEc:adl:wpaper:2015-09
    as

    Download full text from publisher

    File URL: https://economics.adelaide.edu.au/research/papers/doc/wp2015-09.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Kar, Anirban & Mitra, Manipushpak & Mutuswami, Suresh, 2009. "On the coincidence of the prenucleolus and the Shapley value," Mathematical Social Sciences, Elsevier, vol. 57(1), pages 16-25, January.
    2. Tijs, S.H., 1987. "An axiomatization of the ô-value," Other publications TiSEM 5536ac66-86f3-49fb-9e7d-2, Tilburg University, School of Economics and Management.
    3. A. van den Nouweland & P. Borm & W. van Golstein Brouwers & R. Groot Bruinderink & S. Tijs, 1996. "A Game Theoretic Approach to Problems in Telecommunication," Management Science, INFORMS, vol. 42(2), pages 294-303, February.
    4. Tijs, S.H. & Lipperts, F.A.S., 1982. "The hypercube and the core cover of N-person cooperative games," Other publications TiSEM f86cf523-f36d-4652-b774-6, Tilburg University, School of Economics and Management.
    5. Maschler,Michael & Solan,Eilon & Zamir,Shmuel, 2013. "Game Theory," Cambridge Books, Cambridge University Press, number 9781107005488.
    6. Driessen, T.S.H. & Tijs, S.H., 1985. "The t-value, the core and semiconvex games," Other publications TiSEM 016b6b5d-a476-44ca-bd05-7, Tilburg University, School of Economics and Management.
    7. Duygu Yengin, 2012. "Characterizing the Shapley value in fixed-route traveling salesman problems with appointments," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(2), pages 271-299, May.
    8. Tijs, Stef H., 1987. "An axiomatization of the [tau]-value," Mathematical Social Sciences, Elsevier, vol. 13(2), pages 177-181, April.
    9. Xiaotie Deng & Christos H. Papadimitriou, 1994. "On the Complexity of Cooperative Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 257-266, May.
    10. Potters, J.A.M. & Curiel, I. & Tijs, S.H., 1992. "Traveling salesman games," Other publications TiSEM 0dd4cf3d-25fa-4179-80f6-6, Tilburg University, School of Economics and Management.
    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. Trudeau, Christian & Vidal-Puga, Juan, 2020. "Clique games: A family of games with coincidence between the nucleolus and the Shapley value," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 8-14.
    2. 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.
    3. repec:ehu:ikerla:34464 is not listed on IDEAS
    4. Rongwu Lu & Xinhua Wang & Hao Yu & Dan Li, 2018. "Multiparty Evolutionary Game Model in Coal Mine Safety Management and Its Application," Complexity, Hindawi, vol. 2018, pages 1-10, March.
    5. Matthias Deceuninck & Stijn Vuyst & Dieter Claeys & Dieter Fiems, 2021. "Appointment games with unobservable and observable schedules," Annals of Operations Research, Springer, vol. 307(1), pages 93-110, December.

    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. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2019. "Recent developments in the queueing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(1), pages 1-23, April.
    2. Branzei, Rodica & Dimitrov, Dinko & Tijs, Stef, 2004. "Hypercubes and compromise values for cooperative fuzzy games," European Journal of Operational Research, Elsevier, vol. 155(3), pages 733-740, June.
    3. Julio González-Díaz & Estela Sánchez-Rodríguez, 2014. "Understanding the coincidence of allocation rules: symmetry and orthogonality in TU-games," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 821-843, November.
    4. van den Brink, René & Chun, Youngsub & Funaki, Yukihiko & Zou, Zhengxing, 2023. "Balanced externalities and the proportional allocation of nonseparable contributions," European Journal of Operational Research, Elsevier, vol. 307(2), pages 975-983.
    5. Stef Tijs & Gert-Jan Otten, 1993. "Compromise values in cooperative game theory," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 1(1), pages 1-36, December.
    6. Bergantiños, Gustavo & Moreno-Ternero, Juan D., 2020. "Allocating extra revenues from broadcasting sports leagues," Journal of Mathematical Economics, Elsevier, vol. 90(C), pages 65-73.
    7. Trudeau, Christian & Vidal-Puga, Juan, 2020. "Clique games: A family of games with coincidence between the nucleolus and the Shapley value," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 8-14.
    8. Fukuda, E. & Tijs, S.H. & Brânzei, R. & Muto, S., 2002. "Compromising in Partition Function Form Games and Cooperation in Perfect Extensive Form," Other publications TiSEM 9374032a-efac-43dd-a3db-7, Tilburg University, School of Economics and Management.
    9. Fukuda, E. & Tijs, S.H. & Brânzei, R. & Muto, S., 2002. "Compromising in Partition Function Form Games and Cooperation in Perfect Extensive Form," Discussion Paper 2002-117, Tilburg University, Center for Economic Research.
    10. Rene van den Brink & Youngsub Chun & Yukihiko Funaki & Zhengxing Zou, 2021. "Balanced Externalities and the Proportional Allocation of Nonseparable Contributions," Tinbergen Institute Discussion Papers 21-024/II, Tinbergen Institute.
    11. Arroyo, Federico, 2024. "Cost Allocation in Vehicle Routing Problems with Time Windows," Junior Management Science (JUMS), Junior Management Science e. V., vol. 9(1), pages 1241-1268.
    12. Guang Zhang & Erfang Shan & Liying Kang & Yanxia Dong, 2017. "Two efficient values of cooperative games with graph structure based on $$\tau $$ τ -values," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 462-482, August.
    13. Giulia Cesari & Roberto Lucchetti & Stefano Moretti, 2017. "Generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(4), pages 919-939, November.
    14. Gustavo Bergantiños & Juan D. Moreno-Ternero, 2022. "On the axiomatic approach to sharing the revenues from broadcasting sports leagues," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(2), pages 321-347, February.
    15. Kai Zhang & Haishu Lu & Bin Wang, 2024. "Benefit Distribution Mechanism of a Cooperative Alliance for Basin Water Resources from the Perspective of Cooperative Game Theory," Sustainability, MDPI, vol. 16(16), pages 1-33, August.
    16. van den Brink, René & Rusinowska, Agnieszka, 2022. "The degree measure as utility function over positions in graphs and digraphs," European Journal of Operational Research, Elsevier, vol. 299(3), pages 1033-1044.
    17. José M. Jiménez Gómez & María del Carmen Marco Gil & Pedro Gadea Blanco, 2010. "Some game-theoretic grounds for meeting people half-way," Working Papers. Serie AD 2010-04, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
    18. Wenzhong Li & Genjiu Xu & Rene van den Brink, 2021. "Sharing the cost of cleaning up a polluted river," Tinbergen Institute Discussion Papers 21-028/II, Tinbergen Institute.
    19. Tobias Hiller, 2021. "Hierarchy and the size of a firm," International Review of Economics, Springer;Happiness Economics and Interpersonal Relations (HEIRS), vol. 68(3), pages 389-404, September.
    20. Béal, Sylvain & Ferrières, Sylvain & Rémila, Eric & Solal, Philippe, 2018. "The proportional Shapley value and applications," Games and Economic Behavior, Elsevier, vol. 108(C), pages 93-112.

    More about this item

    Keywords

    Fixed-route traveling salesman problem; appointment problem; Shapley value; prenucleolus; nucleolus; t-value; coincidence;
    All these keywords.

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:adl:wpaper:2015-09. 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: Qazi Haque (email available below). General contact details of provider: https://edirc.repec.org/data/decadau.html .

    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.