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

Congestion Games with Player-Specific Payoff Functions: The Case of Two Resources, Computation and Algorithms. First version

Author

Listed:
  • Fatima Khanchouche

    (Department of Mathematics, Laboratory of Fundamental and Numerical Mathematics, Faculty of Sciences, University of Ferhat Abbas, Setif-1, Algeria)

  • Samir Sbabou

    (CNRS, CREM - UNICAEN - University of Caen Normandy - NU - Normandy University, France)

  • Hatem Smaoui

    (Center of Economics and Management of the Indian Ocean, University of La Réunion)

  • Ziad Abderrahmane

    (CNRS, CREM - UNICAEN - University of Caen Normandy - NU - Normandy University, France and Laboratory of Computer Science and Mathematics, Ferhat Abbas University of Setif 1, Setif, Algeria)

Abstract

We study the class of congestion games with player-specic payoff functions Milchtaich (1996). Focusing on a case where the number of resources is equal to two, we give a short and simple method for identifying the exact number of Nash equilibria in pure strategies. We propose an algorithmic method, first to find one or more Nash equilibria; second, to compare the optimal Nash equilibrium, in which the social cost is minimized, with the worst Nash equilibrium, in which the converse is true; third, to identify the time associated to the computations when the number of players increases.

Suggested Citation

  • Fatima Khanchouche & Samir Sbabou & Hatem Smaoui & Ziad Abderrahmane, 2023. "Congestion Games with Player-Specific Payoff Functions: The Case of Two Resources, Computation and Algorithms. First version," Economics Working Paper Archive (University of Rennes & University of Caen) 2023-08, Center for Research in Economics and Management (CREM), University of Rennes, University of Caen and CNRS.
    • Handle: RePEc:tut:cremwp:2023-08
    as

    Download full text from publisher

    File URL: https://ged.univ-rennes1.fr/nuxeo/site/esupversions/9ce404fb-208c-4775-8185-0cc86c071b1a
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Milchtaich, Igal, 1996. "Congestion Games with Player-Specific Payoff Functions," Games and Economic Behavior, Elsevier, vol. 13(1), pages 111-124, March.
    2. Mark Voorneveld & Peter Borm & Freek Van Megen & Stef Tijs & Giovanni Facchini, 1999. "Congestion Games And Potentials Reconsidered," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 1(03n04), pages 283-299.
    3. repec:fth:tilbur:9998 is not listed on IDEAS
    4. Samir Sbabou & Hatem Smaoui & Abderrahmane Ziad, 2013. "A formula for Nash equilibria in monotone singleton congestion games," Economics Bulletin, AccessEcon, vol. 33(1), pages 334-339.
    5. Deutsch, Yael & Golany, Boaz & Rothblum, Uriel G., 2011. "Determining all Nash equilibria in a (bi-linear) inspection game," European Journal of Operational Research, Elsevier, vol. 215(2), pages 422-430, December.
    6. Konishi, Hideo & Le Breton, Michel & Weber, Shlomo, 1997. "Equilibria in a Model with Partial Rivalry," Journal of Economic Theory, Elsevier, vol. 72(1), pages 225-237, January.
    7. Holzman, Ron & Law-Yone, Nissan, 1997. "Strong Equilibrium in Congestion Games," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 85-101, October.
    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. Le Breton, Michel & Shapoval, Alexander & Weber, Shlomo, 2021. "A game-theoretical model of the landscape theory," Journal of Mathematical Economics, Elsevier, vol. 92(C), pages 41-46.
    2. Nikolai Kukushkin, 2007. "Congestion games revisited," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(1), pages 57-83, September.
    3. Ryo Kawasaki & Hideo Konishi & Junki Yukawa, 2023. "Equilibria in bottleneck games," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 649-685, September.
    4. Tobias Harks & Max Klimm & Rolf Möhring, 2013. "Strong equilibria in games with the lexicographical improvement property," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 461-482, May.
    5. Arnold, Tone & Wooders, Myrna, 2002. "Dynamic Club Formation with Coordination," Economic Research Papers 269414, University of Warwick - Department of Economics.
    6. Zhan Wang & Jinpeng Ma & Hongwei Zhang, 2023. "Object-based unawareness: Theory and applications," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 8(1), pages 1-55, December.
    7. Kukushkin, Nikolai S., 2018. "A universal construction generating potential games," Games and Economic Behavior, Elsevier, vol. 108(C), pages 331-340.
    8. Kukushkin, Nikolai S., 2014. "Strong equilibrium in games with common and complementary local utilities," MPRA Paper 55499, University Library of Munich, Germany.
    9. Samir Sbabou & Hatem Smaoui & Abderrahmane Ziad, 2013. "A formula for Nash equilibria in monotone singleton congestion games," Economics Bulletin, AccessEcon, vol. 33(1), pages 334-339.
    10. Milchtaich, Igal, 2006. "Network topology and the efficiency of equilibrium," Games and Economic Behavior, Elsevier, vol. 57(2), pages 321-346, November.
    11. Nikolai Kukushkin, 2011. "Acyclicity of improvements in finite game forms," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(1), pages 147-177, February.
    12. Samir Sbabou & Hatem Smaoui & Abderrahmane Ziad, 2013. "Jeux de congestion finis à choix unique : Théorie, Equilibres, Applications -Calculs et Complexités-," Economics Working Paper Archive (University of Rennes & University of Caen) 201303, Center for Research in Economics and Management (CREM), University of Rennes, University of Caen and CNRS.
    13. Kukushkin, Nikolai S., 2017. "Strong Nash equilibrium in games with common and complementary local utilities," Journal of Mathematical Economics, Elsevier, vol. 68(C), pages 1-12.
    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. Holzman, Ron & Law-Yone, Nissan, 1997. "Strong Equilibrium in Congestion Games," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 85-101, October.
    16. Fatima Khanchouche & Samir Sbabou & Hatem Smaoui & Abderrahmane Ziad, 2024. "Nash Equilibria in Two-Resource Congestion Games with Player-Specific Payoff Functions," Games, MDPI, vol. 15(2), pages 1-10, February.
    17. Kukushkin, Nikolai S., 2014. "Rosenthal's potential and a discrete version of the Debreu--Gorman Theorem," MPRA Paper 54171, University Library of Munich, Germany.
    18. Krzysztof R. Apt & Bart Keijzer & Mona Rahn & Guido Schäfer & Sunil Simon, 2017. "Coordination games on graphs," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(3), pages 851-877, August.
    19. Anna Bogomolnaia & Herve Moulin, 2023. "Fair congested assignment problem," Papers 2301.12163, arXiv.org, revised Feb 2024.
    20. Harks, Tobias & Klimm, Max, 2015. "Equilibria in a class of aggregative location games," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 211-220.

    More about this item

    Keywords

    Congestions games; Nash equilibria computations; price of anarchy; price of stability.;
    All these keywords.

    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:tut:cremwp: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: GERMAIN Lucie (email available below). General contact details of provider: https://edirc.repec.org/data/crmrefr.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.