IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v64y2016i3p680-704.html
   My bibliography  Save this article

Distributed Algorithms for Aggregative Games on Graphs

Author

Listed:
  • Jayash Koshal

    (Department of Industrial and Enterprise Systems Engineering, University of Illinois, Urbana, Illinois 61801)

  • Angelia Nedić

    (Department of Industrial and Enterprise Systems Engineering, University of Illinois, Urbana, Illinois 61801)

  • Uday V. Shanbhag

    (Department of Industrial and Manufacturing Engineering, Pennsylvania State University, University Park, Pennsylvania 16802)

Abstract

We consider a class of Nash games, termed as aggregative games, being played over a networked system. In an aggregative game, a player’s objective is a function of the aggregate of all the players’ decisions. Every player maintains an estimate of this aggregate, and the players exchange this information with their local neighbors over a connected network. We study distributed synchronous and asynchronous algorithms for information exchange and equilibrium computation over such a network. Under standard conditions, we establish the almost-sure convergence of the obtained sequences to the equilibrium point. We also consider extensions of our schemes to aggregative games where the players’ objectives are coupled through a more general form of aggregate function. Finally, we present numerical results that demonstrate the performance of the proposed schemes.

Suggested Citation

  • Jayash Koshal & Angelia Nedić & Uday V. Shanbhag, 2016. "Distributed Algorithms for Aggregative Games on Graphs," Operations Research, INFORMS, vol. 64(3), pages 680-704, June.
    • Handle: RePEc:inm:oropre:v:64:y:2016:i:3:p:680-704
    DOI: 10.1287/opre.2016.1501
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2016.1501
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2016.1501?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
    ---><---

    References listed on IDEAS

    as
    1. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May.
    2. William Novshek, 1985. "On the Existence of Cournot Equilibrium," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 52(1), pages 85-98.
    3. Carlos Alós-Ferrer & Ana Ania, 2005. "The evolutionary stability of perfectly competitive behavior," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 26(3), pages 497-516, October.
    4. Martin Kaae Jensen, 2018. "Aggregative games," Chapters, in: Luis C. Corchón & Marco A. Marini (ed.), Handbook of Game Theory and Industrial Organization, Volume I, chapter 4, pages 66-92, Edward Elgar Publishing.
    5. Dubey, Pradeep & Haimanko, Ori & Zapechelnyuk, Andriy, 2006. "Strategic complements and substitutes, and potential games," Games and Economic Behavior, Elsevier, vol. 54(1), pages 77-94, January.
    6. Martimort, David & Stole, Lars, 2011. "Aggregate Representations of Aggregate Games," MPRA Paper 32871, University Library of Munich, Germany.
    7. Martin Jensen, 2010. "Aggregative games and best-reply potentials," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 43(1), pages 45-66, April.
    8. Herbert A. Simon, 1996. "The Sciences of the Artificial, 3rd Edition," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262691914, April.
    9. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945, April.
    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. Jun Tong & Jian-Qiang Hu & Jianxin You, 2019. "Asynchronous Algorithms for Computing Equilibrium Prices in a Capital Asset Pricing Model," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(05), pages 1-17, October.
    2. Jinlong Lei & Uday V. Shanbhag, 2020. "Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization," Operations Research, INFORMS, vol. 68(6), pages 1742-1766, November.
    3. Lina Mallozzi & Roberta Messalli, 2017. "Multi-Leader Multi-Follower Model with Aggregative Uncertainty," Games, MDPI, vol. 8(3), pages 1-14, June.
    4. Edward Anderson & David Gamarnik & Anton Kleywegt & Asuman Ozdaglar, 2016. "Preface to the Special Issue on Information and Decisions in Social and Economic Networks," Operations Research, INFORMS, vol. 64(3), pages 561-563, June.
    5. Le Cadre, Hélène & Mou, Yuting & Höschle, Hanspeter, 2022. "Parametrized Inexact-ADMM based coordination games: A normalized Nash equilibrium approach," European Journal of Operational Research, Elsevier, vol. 296(2), pages 696-716.
    6. Parise, Francesca & Ozdaglar, Asuman, 2019. "A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis," Games and Economic Behavior, Elsevier, vol. 114(C), pages 47-82.
    7. Simone Balmelli & Francesco Moresino, 2023. "Coordination of Plug-In Electric Vehicle Charging in a Stochastic Framework: A Decentralized Tax/Incentive-Based Mechanism to Reach Global Optimality," Mathematics, MDPI, vol. 11(4), pages 1-24, February.

    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. Acemoglu, Daron & Jensen, Martin Kaae, 2013. "Aggregate comparative statics," Games and Economic Behavior, Elsevier, vol. 81(C), pages 27-49.
    2. Christian Ewerhart, 2020. "Ordinal potentials in smooth games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(4), pages 1069-1100, November.
    3. Martin Jensen, 2010. "Aggregative games and best-reply potentials," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 43(1), pages 45-66, April.
    4. Kukushkin, Nikolai S., 2018. "Better response dynamics and Nash equilibrium in discontinuous games," Journal of Mathematical Economics, Elsevier, vol. 74(C), pages 68-78.
    5. Volker Nocke & Nicolas Schutz, 2018. "Multiproduct‐Firm Oligopoly: An Aggregative Games Approach," Econometrica, Econometric Society, vol. 86(2), pages 523-557, March.
    6. Carlos Alós-Ferrer & Fei Shi, 2012. "Imitation with asymmetric memory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 49(1), pages 193-215, January.
    7. Schipper, Burkhard C., 2009. "Imitators and optimizers in Cournot oligopoly," Journal of Economic Dynamics and Control, Elsevier, vol. 33(12), pages 1981-1990, December.
    8. Harks, Tobias & Klimm, Max, 2015. "Equilibria in a class of aggregative location games," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 211-220.
    9. Bayer, Péter & Herings, P. Jean-Jacques & Peeters, Ronald & Thuijsman, Frank, 2019. "Adaptive learning in weighted network games," Journal of Economic Dynamics and Control, Elsevier, vol. 105(C), pages 250-264.
    10. Kukushkin, Nikolai S., 2016. "Nash equilibrium with discontinuous utility functions: Reny's approach extended," MPRA Paper 75862, University Library of Munich, Germany.
    11. Abheek Ghosh & Paul W. Goldberg, 2023. "Best-Response Dynamics in Lottery Contests," Papers 2305.10881, arXiv.org.
    12. Nikolai Kukushkin, 2015. "The single crossing conditions for incomplete preferences," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(1), pages 225-251, February.
    13. Kukushkin, Nikolai S., 2013. "Approximate Nash equilibrium under the single crossing conditions," MPRA Paper 44320, University Library of Munich, Germany.
    14. Martimort, David & Stole, Lars, 2012. "Representing equilibrium aggregates in aggregate games with applications to common agency," Games and Economic Behavior, Elsevier, vol. 76(2), pages 753-772.
    15. Kukushkin, Nikolai S., 2015. "Cournot tatonnement and potentials," Journal of Mathematical Economics, Elsevier, vol. 59(C), pages 117-127.
    16. Lina Mallozzi & Roberta Messalli, 2017. "Multi-Leader Multi-Follower Model with Aggregative Uncertainty," Games, MDPI, vol. 8(3), pages 1-14, June.
    17. Nikolai S. Kukushkin, 2016. "Cournot Tatonnement in Aggregative Games with Monotone Best Responses," Springer Series in Game Theory, in: Pierre von Mouche & Federico Quartieri (ed.), Equilibrium Theory for Cournot Oligopolies and Related Games, pages 31-45, Springer.
    18. Burkhard C. Schipper, 2021. "The evolutionary stability of optimism, pessimism, and complete ignorance," Theory and Decision, Springer, vol. 90(3), pages 417-454, May.
    19. Yakov Babichenko, 2018. "Fast Convergence of Best-Reply Dynamics in Aggregative Games," Mathematics of Operations Research, INFORMS, vol. 43(1), pages 333-346, February.
    20. Ratul Lahkar, 2020. "Convergence to Walrasian equilibrium with minimal information," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 15(3), pages 553-578, July.

    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:inm:oropre:v:64:y:2016:i:3:p:680-704. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.