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 1 & University of Caen) 2023-08, Center for Research in Economics and Management (CREM), University of Rennes 1, 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. 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.
    2. 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.
    3. 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.
    4. Milchtaich, Igal, 1996. "Congestion Games with Player-Specific Payoff Functions," Games and Economic Behavior, Elsevier, vol. 13(1), pages 111-124, March.
    5. 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.
    6. repec:fth:tilbur:9998 is not listed on IDEAS
    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. 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.
    2. 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.
    3. 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.
    4. Nikolai Kukushkin, 2007. "Congestion games revisited," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(1), pages 57-83, September.
    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. 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.
    8. Kukushkin, Nikolai S., 2018. "A universal construction generating potential games," Games and Economic Behavior, Elsevier, vol. 108(C), pages 331-340.
    9. Kukushkin, Nikolai S., 2014. "Strong equilibrium in games with common and complementary local utilities," MPRA Paper 55499, University Library of Munich, Germany.
    10. 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 1 & University of Caen) 201303, Center for Research in Economics and Management (CREM), University of Rennes 1, University of Caen and CNRS.
    11. 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.
    12. Milchtaich, Igal, 2006. "Network topology and the efficiency of equilibrium," Games and Economic Behavior, Elsevier, vol. 57(2), pages 321-346, November.
    13. 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.
    14. Le Breton, Michel & Weber, Shlomo, 2009. "Existence of Pure Strategies Nash Equilibria in Social Interaction Games with Dyadic Externalities," CEPR Discussion Papers 7279, C.E.P.R. Discussion Papers.
    15. 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.
    16. Hideo Konishi, 2004. "Uniqueness of User Equilibrium in Transportation Networks with Heterogeneous Commuters," Transportation Science, INFORMS, vol. 38(3), pages 315-330, August.
    17. Igal Milchtaich, 2000. "Generic Uniqueness of Equilibrium in Large Crowding Games," Mathematics of Operations Research, INFORMS, vol. 25(3), pages 349-364, August.
    18. Olivier Tercieux & Mark Voorneveld, 2010. "The cutting power of preparation," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 71(1), pages 85-101, February.
    19. Abderrahmane ZIAD & Samir SBABOU & Hatem SMAOUI, CEMOI, 2011. "Nonsymmetric singleton congestion games: case of two resources," Economics Working Paper Archive (University of Rennes 1 & University of Caen) 201113, Center for Research in Economics and Management (CREM), University of Rennes 1, University of Caen and CNRS.
    20. Kukushkin, Nikolai S., 2004. "Best response dynamics in finite games with additive aggregation," Games and Economic Behavior, Elsevier, vol. 48(1), pages 94-110, July.

    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/cccrmfr.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.