IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v97y2021i3d10.1007_s11134-020-09681-9.html
   My bibliography  Save this article

Non-cooperative queueing games on a network of single server queues

Author

Listed:
  • Corine M. Laan

    (University of Twente
    TNO
    Netherlands Defence Academy, Faculty of Military Sciences)

  • Judith Timmer

    (University of Twente)

  • Richard J. Boucherie

    (University of Twente)

Abstract

This paper introduces non-cooperative games on a network of single server queues with fixed routes. A player has a set of routes available and has to decide which route(s) to use for its customers. Each player’s goal is to minimize the expected sojourn time of its customers. We consider two cases: a continuous strategy space, where each player is allowed to divide its customers over multiple routes, and a discrete strategy space, where each player selects a single route for all its customers. For the continuous strategy space, we show that a unique pure-strategy Nash equilibrium exists that can be found using a best-response algorithm. For the discrete strategy space, we show that the game has a Nash equilibrium in mixed strategies, but need not have a pure-strategy Nash equilibrium. We show the existence of pure-strategy Nash equilibria for four subclasses: (i) N-player games with equal arrival rates for the players, (ii) 2-player games with identical service rates for all nodes, (iii) 2-player games on a $$2\times 2$$ 2 × 2 -grid, and (iv) 2-player games on an $$A\times B$$ A × B -grid with small differences in the service rates.

Suggested Citation

  • Corine M. Laan & Judith Timmer & Richard J. Boucherie, 2021. "Non-cooperative queueing games on a network of single server queues," Queueing Systems: Theory and Applications, Springer, vol. 97(3), pages 279-301, April.
  • Handle: RePEc:spr:queues:v:97:y:2021:i:3:d:10.1007_s11134-020-09681-9
    DOI: 10.1007/s11134-020-09681-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-020-09681-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s11134-020-09681-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Igal Milchtaich, 2015. "Network topology and equilibrium existence in weighted network congestion games," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(3), pages 515-541, August.
    2. Colin E. Bell & Shaler Stidham, Jr., 1983. "Individual versus Social Optimization in the Allocation of Customers to Alternative Servers," Management Science, INFORMS, vol. 29(7), pages 831-839, July.
    3. Milchtaich, Igal, 1996. "Congestion Games with Player-Specific Payoff Functions," Games and Economic Behavior, Elsevier, vol. 13(1), pages 111-124, March.
    4. Laan, Corine M. & van der Mijden, Tom & Barros, Ana Isabel & Boucherie, Richard J. & Monsuur, Herman, 2017. "An interdiction game on a queueing network with multiple intruders," European Journal of Operational Research, Elsevier, vol. 260(3), pages 1069-1080.
    5. Tobias Harks & Max Klimm, 2012. "On the Existence of Pure Nash Equilibria in Weighted Congestion Games," Mathematics of Operations Research, INFORMS, vol. 37(3), pages 419-436, August.
    6. Judith Timmer & Werner Scheinhardt, 2018. "Customer and Cost Sharing in a Jackson Network," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 20(03), pages 1-10, September.
    7. Francisco Facchinei & Christian Kanzow, 2010. "Generalized Nash Equilibrium Problems," Annals of Operations Research, Springer, vol. 175(1), pages 177-211, March.
    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. Tsai, Eline R. & Demirtas, Derya & Tintu, Andrei N. & de Jonge, Robert & de Rijke, Yolanda B. & Boucherie, Richard J., 2023. "Design of fork-join networks of First-In-First-Out and infinite-server queues applied to clinical chemistry laboratories," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1101-1117.

    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. Le Zhang & Lijing Lyu & Shanshui Zheng & Li Ding & Lang Xu, 2022. "A Q-Learning-Based Approximate Solving Algorithm for Vehicular Route Game," Sustainability, MDPI, vol. 14(19), pages 1-14, September.
    2. Stefano Coniglio & Mathias Sirvent & Martin Weibelzahl, 2021. "Airport capacity extension, fleet investment, and optimal aircraft scheduling in a multilevel market model: quantifying the costs of imperfect markets," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(2), pages 367-408, June.
    3. Anita Schöbel & Silvia Schwarze, 2013. "Finding delay-resistant line concepts using a game-theoretic approach," Netnomics, Springer, vol. 14(3), pages 95-117, November.
    4. Vasilis Gkatzelis & Konstantinos Kollias & Tim Roughgarden, 2016. "Optimal Cost-Sharing in General Resource Selection Games," Operations Research, INFORMS, vol. 64(6), pages 1230-1238, December.
    5. Tobias Harks & Max Klimm, 2016. "Congestion Games with Variable Demands," Mathematics of Operations Research, INFORMS, vol. 41(1), pages 255-277, February.
    6. Tami Tamir, 2023. "Cost-sharing games in real-time scheduling systems," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 273-301, March.
    7. Harks, Tobias & von Falkenhausen, Philipp, 2014. "Optimal cost sharing for capacitated facility location games," European Journal of Operational Research, Elsevier, vol. 239(1), pages 187-198.
    8. Philipp von Falkenhausen & Tobias Harks, 2013. "Optimal Cost Sharing for Resource Selection Games," Mathematics of Operations Research, INFORMS, vol. 38(1), pages 184-208, February.
    9. Oliver Stein & Nathan Sudermann-Merx, 2016. "The Cone Condition and Nonsmoothness in Linear Generalized Nash Games," Journal of Optimization Theory and Applications, Springer, vol. 170(2), pages 687-709, August.
    10. Nadja Harms & Tim Hoheisel & Christian Kanzow, 2015. "On a Smooth Dual Gap Function for a Class of Player Convex Generalized Nash Equilibrium Problems," Journal of Optimization Theory and Applications, Springer, vol. 166(2), pages 659-685, August.
    11. Lorenzo Lampariello & Simone Sagratella, 2015. "It is a matter of hierarchy: a Nash equilibrium problem perspective on bilevel programming," DIAG Technical Reports 2015-07, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    12. Parlakturk, Ali & Kumar, Sunil, 2004. "Self-Interested Routing in Queueing Networks," Research Papers 1782r, Stanford University, Graduate School of Business.
    13. Arnold, Tone & Wooders, Myrna, 2002. "Dynamic Club Formation with Coordination," Economic Research Papers 269414, University of Warwick - Department of Economics.
    14. Hideo Konishi, 2004. "Uniqueness of User Equilibrium in Transportation Networks with Heterogeneous Commuters," Transportation Science, INFORMS, vol. 38(3), pages 315-330, August.
    15. Alexey Izmailov & Mikhail Solodov, 2014. "On error bounds and Newton-type methods for generalized Nash equilibrium problems," Computational Optimization and Applications, Springer, vol. 59(1), pages 201-218, October.
    16. Milchtaich, Igal, 2009. "Weighted congestion games with separable preferences," Games and Economic Behavior, Elsevier, vol. 67(2), pages 750-757, November.
    17. Migot, Tangi & Cojocaru, Monica-G., 2020. "A parametrized variational inequality approach to track the solution set of a generalized nash equilibrium problem," European Journal of Operational Research, Elsevier, vol. 283(3), pages 1136-1147.
    18. Denizalp Goktas & Jiayi Zhao & Amy Greenwald, 2023. "T\^atonnement in Homothetic Fisher Markets," Papers 2306.04890, arXiv.org.
    19. Bavly, Gilad & Heller, Yuval & Schreiber, Amnon, 2022. "Social welfare in search games with asymmetric information," Journal of Economic Theory, Elsevier, vol. 202(C).
    20. Amir Gandomi & Amirhossein Bazargan & Saeed Zolfaghari, 2019. "Designing competitive loyalty programs: a stochastic game-theoretic model to guide the choice of reward structure," Annals of Operations Research, Springer, vol. 280(1), pages 267-298, September.

    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:spr:queues:v:97:y:2021:i:3:d:10.1007_s11134-020-09681-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.