IDEAS home Printed from https://ideas.repec.org/p/wis/wpaper/2202.html
   My bibliography  Save this paper

Queueing games with an endogenous number of machines

Author

Listed:
  • Ata Atay

    (Department of Mathematical Economics, Finance and Actuarial Sciences, and Barcelona Economic Analysis Team (BEAT), University of Barcelona, Spain)

  • Christian Trudeau

    (Department of Economics, University of Windsor)

Abstract

This paper studies queueing problems with an endogenous number of machines with and without an initial queue, the novelty being that coalitions not only choose how to queue, but also on how many machines. For a given problem, agents can (de)activate as many machines as they want, at a cost. After minimizing the total cost (processing costs and machine costs), we use a game theoretical approach to share to proceeds of this cooperation, and study the existence of stable allocations. First, we study queueing problems with an endogenous number of machines, and examine how to share the total cost. We provide an upper bound and a lower bound on the cost of a machine to guarantee the non-emptiness of the core (the set of stable allocations). Next, we study requeueing problems with an endogenous number of machines, where there is an existing queue. We examine how to share the cost savings compared to the initial situation, when optimally requeueing/changing the number of machines. Although, in general, stable allocation may not exist, we guarantee the existence of stable allocations when all machines are considered public goods, and we start with an initial schedule that might not have the optimal number of machines, but in which agents with large waiting costs are processed first.

Suggested Citation

  • Ata Atay & Christian Trudeau, 2022. "Queueing games with an endogenous number of machines," Working Papers 2202, University of Windsor, Department of Economics.
    • Handle: RePEc:wis:wpaper:2202
    as

    Download full text from publisher

    File URL: http://web2.uwindsor.ca/economics/RePEc/wis/pdf/2202.pdf
    File Function: First version, 2022
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Atay, Ata & Calleja, Pedro & Soteras, Sergio, 2021. "Open shop scheduling games," European Journal of Operational Research, Elsevier, vol. 295(1), pages 12-21.
    2. Bahel, Eric & Trudeau, Christian, 2019. "Stability and fairness in the job scheduling problem," Games and Economic Behavior, Elsevier, vol. 117(C), pages 1-14.
    3. Herbert Hamers & Flip Klijn & Bas Velzen, 2005. "On the Convexity of Precedence Sequencing Games," Annals of Operations Research, Springer, vol. 137(1), pages 161-175, July.
    4. Curiel, I. & Potters, J.A.M. & Rajendra Prasad, V. & Tijs, S.H. & Veltman, B., 1993. "Cooperation in one machine scheduling," Other publications TiSEM 9c5ceec5-2080-4b5c-98d5-0, Tilburg University, School of Economics and Management.
    5. M. Musegaas & P. E. M. Borm & M. Quant, 2018. "On the convexity of step out–step in sequencing games," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(1), pages 68-109, April.
    6. Youngsub Chun, 2016. "Queueing Problems with Two Parallel Servers," Studies in Choice and Welfare, in: Fair Queueing, chapter 0, pages 141-157, Springer.
    7. Musegaas, M. & Borm, P.E.M. & Quant, M., 2015. "Step out–Step in sequencing games," European Journal of Operational Research, Elsevier, vol. 246(3), pages 894-906.
    8. Imma Curiel & Jos Potters & Rajendra Prasad & Stef Tijs & Bart Veltman, 1994. "Sequencing and Cooperation," Operations Research, INFORMS, vol. 42(3), pages 566-568, June.
    9. Curiel, I. & Potters, J.A.M. & Rajendra Prasad, V. & Tijs, S.H. & Veltman, B., 1994. "Sequencing and cooperation," Other publications TiSEM be67f9e9-7a4a-47f1-9fb9-7, Tilburg University, School of Economics and Management.
    10. Maniquet, Francois, 2003. "A characterization of the Shapley value in queueing problems," Journal of Economic Theory, Elsevier, vol. 109(1), pages 90-103, March.
    11. Slikker, Marco, 2006. "Balancedness of multiple machine sequencing games revisited," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1944-1949, November.
    12. Hamers, Herbert & Klijn, Flip & Suijs, Jeroen, 1999. "On the balancedness of multiple machine sequencing games," European Journal of Operational Research, Elsevier, vol. 119(3), pages 678-691, December.
    13. Youngsub Chun, 2006. "No-envy in queueing problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 29(1), pages 151-162, September.
    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. Atay, Ata & Calleja, Pedro & Soteras, Sergio, 2021. "Open shop scheduling games," European Journal of Operational Research, Elsevier, vol. 295(1), pages 12-21.
    2. René Brink & Gerard Laan & Valeri Vasil’ev, 2007. "Component efficient solutions in line-graph games with applications," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 33(2), pages 349-364, November.
    3. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, G., 2020. "Sequencing Situations and Games with Non-Linear Cost Functions," Other publications TiSEM 3e1db5c9-0f77-4f91-a075-c, Tilburg University, School of Economics and Management.
    4. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, G., 2020. "Sequencing Situations and Games with Non-Linear Cost Functions," Discussion Paper 2020-006, Tilburg University, Center for Economic Research.
    5. van Velzen, S. & Hamers, H.J.M., 2002. "On the Balancedness of Relaxed Sequencing Games," Discussion Paper 2002-49, Tilburg University, Center for Economic Research.
    6. Ciftci, B.B. & Borm, P.E.M. & Hamers, H.J.M. & Slikker, M., 2008. "Batch Sequencing and Cooperation," Other publications TiSEM ed1f8fce-da76-41a6-9a9e-9, Tilburg University, School of Economics and Management.
    7. Gerichhausen, M. & Hamers, H.J.M., 2007. "Partitioning Sequencing Situations and Games," Discussion Paper 2007-40, Tilburg University, Center for Economic Research.
    8. René Brink & Chris Dietz, 2014. "Games with a local permission structure: separation of authority and value generation," Theory and Decision, Springer, vol. 76(3), pages 343-361, March.
    9. Imma Curiel, 2010. "Multi-stage sequencing situations," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(1), pages 151-162, March.
    10. Slikker, Marco, 2023. "The stable gain splitting rule for sequencing situations," European Journal of Operational Research, Elsevier, vol. 310(2), pages 902-913.
    11. Gerichhausen, Marloes & Hamers, Herbert, 2009. "Partitioning sequencing situations and games," European Journal of Operational Research, Elsevier, vol. 196(1), pages 207-216, July.
    12. van Velzen, S., 2003. "Sequencing Games with Controllable Processing Time," Discussion Paper 2003-105, Tilburg University, Center for Economic Research.
    13. van Velzen, Bas & Hamers, Herbert & Solymosi, Tamas, 2008. "Core stability in chain-component additive games," Games and Economic Behavior, Elsevier, vol. 62(1), pages 116-139, January.
    14. Gerichhausen, M. & Hamers, H.J.M., 2007. "Partitioning Sequencing Situations and Games," Other publications TiSEM 2bddbf5c-c56d-4b10-ba47-5, Tilburg University, School of Economics and Management.
    15. Imma Curiel & Herbert Hamers & Stef Tijs & Jos Potters, 1997. "Restricted component additive games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 45(2), pages 213-220, June.
    16. Pedro Calleja & Peter Borm & Herbert Hamers & Flip Klijn & Marco Slikker, 2002. "On a New Class of Parallel Sequencing Situations and Related Games," Annals of Operations Research, Springer, vol. 109(1), pages 265-277, January.
    17. Min Ji & Sai Liu & Xiaolin Zhang & Keke Cao & T. C. E. Cheng, 2017. "Sequencing Games with Slack Due Windows and Group Technology Considerations," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(2), pages 121-133, February.
    18. Herbert Hamers & Flip Klijn & Bas Velzen, 2005. "On the Convexity of Precedence Sequencing Games," Annals of Operations Research, Springer, vol. 137(1), pages 161-175, July.
    19. Herbert Hamers & Flip Klijn & Bas van Velzen, 2002. "On Games corresponding to Sequencing Situations with Precedence Relations," UFAE and IAE Working Papers 553.02, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    20. van Velzen, S. & Hamers, H.J.M., 2002. "On the Balancedness of Relaxed Sequencing Games," Other publications TiSEM 14e21ac6-26af-438e-943b-9, Tilburg University, School of Economics and Management.

    More about this item

    Keywords

    queueing problems; convexity; cost sharing; allocation problems.;
    All these keywords.

    JEL classification:

    • C44 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods: Special Topics - - - Operations Research; Statistical Decision Theory
    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • D61 - Microeconomics - - Welfare Economics - - - Allocative Efficiency; Cost-Benefit Analysis
    • D63 - Microeconomics - - Welfare Economics - - - Equity, Justice, Inequality, and Other Normative Criteria and Measurement

    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:wis:wpaper:2202. 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: Christian Trudeau (email available below). General contact details of provider: https://edirc.repec.org/data/dwindca.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.