IDEAS home Printed from https://ideas.repec.org/p/ulp/sbbeta/2023-08.html
   My bibliography  Save this paper

Schedule Situations and their Cooperative Games

Author

Listed:
  • Léa Munich

Abstract

We introduce a new problem of cost allocation resulting from a scheduling problem, and we study it by a new class of cooperative games, the schedule situations and the associated games. In a schedule situation several players share a non-rival common-pool infrastructure. Its consumption is possible during several periods. The consumption needs of each player are described by the set of minimal schedules satisfying this player. The use of this infrastructure induces a fixed per-period cost normalized to one unit. Therefore, one objective is to minimize the overall total number of consumption time periods in order to satisfy all players. For this purpose, the schedule game gives for each coalition of players the minimal number of time periods needed to satisfy the consumption needs of all its members. We provide a characterization of the class of schedule games: a game is a schedule game if and only if it is monotonic, sub-additive, integer-valued and all nonempty coalitions have positive worths. Moreover, specific schedule games can be linked to other classes of operational research games: the airport games and the carpool games. We also introduce Equal pooling allocations, which in some cases coincide with the Shapley value. Next we develop a natural sufficient condition to guarantee the non-emptiness of the core of a schedule game. Finally, we provide an application of the the schedule situations and the associated games to the allocation of cost of the mail carrier route in France.

Suggested Citation

  • Léa Munich, 2023. "Schedule Situations and their Cooperative Games," Working Papers of BETA 2023-08, Bureau d'Economie Théorique et Appliquée, UDS, Strasbourg.
  • Handle: RePEc:ulp:sbbeta:2023-08
    as

    Download full text from publisher

    File URL: http://beta.u-strasbg.fr/WP/2023/2023-08.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Tijs, S.H. & Driessen, T.S.H., 1986. "Game theory and cost allocation problems," Other publications TiSEM 376c24c5-c95d-4d29-96b6-4, Tilburg University, School of Economics and Management.
    2. Peter Borm & Herbert Hamers & Ruud Hendrickx, 2001. "Operations research games: A survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 9(2), pages 139-199, December.
    3. Graham, Daniel A & Marshall, Robert C & Richard, Jean-Francois, 1990. "Differential Payments within a Bidder Coalition and the Shapley Value," American Economic Review, American Economic Association, vol. 80(3), pages 493-510, June.
    4. S.C. Littlechild & G.F. Thompson, 1977. "Aircraft Landing Fees: A Game Theory Approach," Bell Journal of Economics, The RAND Corporation, vol. 8(1), pages 186-204, Spring.
    5. S. C. Littlechild & G. Owen, 1973. "A Simple Expression for the Shapley Value in a Special Case," Management Science, INFORMS, vol. 20(3), pages 370-372, November.
    6. Dehez, Pierre & Ferey, Samuel, 2013. "How to share joint liability: A cooperative game approach," Mathematical Social Sciences, Elsevier, vol. 66(1), pages 44-50.
    7. M. Fiestras-Janeiro & Ignacio García-Jurado & Manuel Mosquera, 2011. "Rejoinder on: 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 33-34, July.
    8. Rosenthal, Edward C., 2017. "A cooperative game approach to cost allocation in a rapid-transit network," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 64-77.
    9. 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.
    10. Kuipers, Jeroen & Mosquera, Manuel A. & Zarzuelo, José M., 2013. "Sharing costs in highways: A game theoretic approach," European Journal of Operational Research, Elsevier, vol. 228(1), pages 158-168.
    11. S. H. Tijs & T. S. H. Driessen, 1986. "Game Theory and Cost Allocation Problems," Management Science, INFORMS, vol. 32(8), pages 1015-1028, August.
    12. Hou, Dongshuang & Sun, Hao & Sun, Panfei & Driessen, Theo, 2018. "A note on the Shapley value for airport cost pooling game," Games and Economic Behavior, Elsevier, vol. 108(C), pages 162-169.
    Full references (including those not matched with items on IDEAS)

    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. Munich, Léa, 2024. "Schedule situations and their cooperative game theoretic representations," European Journal of Operational Research, Elsevier, vol. 316(2), pages 767-778.
    2. Léa Munich, 2023. "Schedule Situations and their Cooperative Game Theoretic Representations," Working Papers 2023-08, CRESE.
    3. Alparslan-Gok, S.Z. & Brânzei, R. & Tijs, S.H., 2008. "Cooperative Interval Games Arising from Airport Situations with Interval Data," Other publications TiSEM 5ded50b5-2a11-4d25-8511-b, Tilburg University, School of Economics and Management.
    4. 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.
    5. Alparslan-Gok, S.Z. & Brânzei, R. & Tijs, S.H., 2008. "Cooperative Interval Games Arising from Airport Situations with Interval Data," Discussion Paper 2008-57, Tilburg University, Center for Economic Research.
    6. Algaba, Encarnación & Béal, Sylvain & Fragnelli, Vito & Llorca, Natividad & Sánchez-Soriano, Joaquin, 2019. "Relationship between labeled network games and other cooperative games arising from attributes situations," Economics Letters, Elsevier, vol. 185(C).
    7. Vásquez-Brage, M. & van den Nouweland, C.G.A.M. & García-Jurado, I., 1995. "Owen's coalitional value and aircraft landing fees," Discussion Paper 1995-104, Tilburg University, Center for Economic Research.
    8. Vásquez-Brage, M. & van den Nouweland, C.G.A.M. & García-Jurado, I., 1995. "Owen's coalitional value and aircraft landing fees," Other publications TiSEM 3f2bc27b-b5c8-4517-8ffd-8, Tilburg University, School of Economics and Management.
    9. Dongshuang Hou & Aymeric Lardon & Panfei Sun & Genjiu Xu, 2019. "Sharing a Polluted River under Waste Flow Control," GREDEG Working Papers 2019-23, Groupe de REcherche en Droit, Economie, Gestion (GREDEG CNRS), Université Côte d'Azur, France.
    10. Paula González & Carmen Herrero, 2004. "Optimal sharing of surgical costs in the presence of queues," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 59(3), pages 435-446, July.
    11. Hou, Dongshuang & Sun, Hao & Sun, Panfei & Driessen, Theo, 2018. "A note on the Shapley value for airport cost pooling game," Games and Economic Behavior, Elsevier, vol. 108(C), pages 162-169.
    12. Gómez-Rodríguez, Marcos & Davila-Pena, Laura & Casas-Méndez, Balbina, 2024. "Cost allocation problems on highways with grouped users," European Journal of Operational Research, Elsevier, vol. 316(2), pages 667-679.
    13. Casas-Mendez, Balbina & Garcia-Jurado, Ignacio & van den Nouweland, Anne & Vazquez-Brage, Margarita, 2003. "An extension of the [tau]-value to games with coalition structures," European Journal of Operational Research, Elsevier, vol. 148(3), pages 494-513, August.
    14. Vazquez-Brage, M. & van den Nouweland, A. & Garcia-Jurado, I., 1997. "Owen's coalitional value and aircraft landing fees," Mathematical Social Sciences, Elsevier, vol. 34(3), pages 273-286, October.
    15. Sylvain Béal & Marc Deschamps & Catherine Refait-Alexandre & Guillaume Sekli, 2022. "Early contributors, cooperation and fair rewards in crowdfunding," Working Papers hal-04222321, HAL.
    16. 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.
    17. García-Martínez, Jose A. & Mayor-Serra, Antonio J. & Meca, Ana, 2020. "Efficient Effort Equilibrium in Cooperation with Pairwise Cost Reduction," MPRA Paper 105604, University Library of Munich, Germany.
    18. Dan C. Popescu & Philip Kilby, 2020. "Approximation of the Shapley value for the Euclidean travelling salesman game," Annals of Operations Research, Springer, vol. 289(2), pages 341-362, June.
    19. Stefano Moretti & Henk Norde, 2022. "Some new results on generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 51(1), pages 87-118, March.
    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

    Schedule; OR-game; Cost allocation; Equal pooling allocations; Core.;
    All these keywords.

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • L87 - Industrial Organization - - Industry Studies: Services - - - Postal and Delivery Services

    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:ulp:sbbeta:2023-08. 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: the person in charge (email available below). General contact details of provider: https://edirc.repec.org/data/bestrfr.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.