IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v367y2020ics0096300319307775.html
   My bibliography  Save this article

A distributed algorithm to obtain repeated games equilibria with discounting

Author

Listed:
  • Parras, Juan
  • Zazo, Santiago

Abstract

We introduce a distributed algorithm to negotiate equilibria on repeated games with discounting. It is based on the Folk Theorem, which allows obtaining better payoffs for all players by enforcing cooperation among players when possible. Our algorithm works on incomplete information games: each player needs not knowing the payoff function of the rest of the players. Also, it allows obtaining Pareto-efficient payoffs for all players using either Nash or correlated equilibrium concepts. We explain the main ideas behind the algorithm, explain the two key procedures on which algorithm relies on, provide a theoretical bound on the error introduced and show empirically the performance of the algorithm on four well-known repeated games.

Suggested Citation

  • Parras, Juan & Zazo, Santiago, 2020. "A distributed algorithm to obtain repeated games equilibria with discounting," Applied Mathematics and Computation, Elsevier, vol. 367(C).
    • Handle: RePEc:eee:apmaco:v:367:y:2020:i:c:s0096300319307775
    DOI: 10.1016/j.amc.2019.124785
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300319307775
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2019.124785?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. Robert J. Aumann, 1995. "Repeated Games with Incomplete Information," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262011476, April.
    2. Kalai, Ehud & Smorodinsky, Meir, 1975. "Other Solutions to Nash's Bargaining Problem," Econometrica, Econometric Society, vol. 43(3), pages 513-518, May.
    3. Kalai, Ehud, 1977. "Proportional Solutions to Bargaining Situations: Interpersonal Utility Comparisons," Econometrica, Econometric Society, vol. 45(7), pages 1623-1630, October.
    4. Abreu, Dilip, 1988. "On the Theory of Infinitely Repeated Games with Discounting," Econometrica, Econometric Society, vol. 56(2), pages 383-396, March.
    5. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    6. Nash, John, 1950. "The Bargaining Problem," Econometrica, Econometric Society, vol. 18(2), pages 155-162, April.
    7. Aumann, Robert J., 1974. "Subjectivity and correlation in randomized strategies," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 67-96, March.
    8. Sergiu Hart & Andreu Mas-Colell, 2013. "Simple Adaptive Strategies:From Regret-Matching to Uncoupled Dynamics," World Scientific Books, World Scientific Publishing Co. Pte. Ltd., number 8408, September.
    9. Mailath, George J. & Samuelson, Larry, 2006. "Repeated Games and Reputations: Long-Run Relationships," OUP Catalogue, Oxford University Press, number 9780195300796.
    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. Etro, Federico, 2017. "Research in economics and game theory. A 70th anniversary," Research in Economics, Elsevier, vol. 71(1), pages 1-7.
    2. Bergantiños, Gustavo & Moreno-Ternero, Juan D., 2022. "Monotonicity in sharing the revenues from broadcasting sports leagues," European Journal of Operational Research, Elsevier, vol. 297(1), pages 338-346.
    3. Yoshihara, Naoki, 2003. "Characterizations of bargaining solutions in production economies with unequal skills," Journal of Economic Theory, Elsevier, vol. 108(2), pages 256-285, February.
    4. Lea Melnikovová, 2017. "Can Game Theory Help to Mitigate Water Conflicts in the Syrdarya Basin?," Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis, Mendel University Press, vol. 65(4), pages 1393-1401.
    5. Daniele Cassese & Paolo Pin, 2018. "Decentralized Pure Exchange Processes on Networks," Papers 1803.08836, arXiv.org, revised Mar 2022.
    6. José-Manuel Giménez-Gómez & António Osório & Josep E. Peris, 2015. "From Bargaining Solutions to Claims Rules: A Proportional Approach," Games, MDPI, vol. 6(1), pages 1-7, March.
    7. Takeuchi, Ai & Veszteg, Róbert F. & Kamijo, Yoshio & Funaki, Yukihiko, 2022. "Bargaining over a jointly produced pie: The effect of the production function on bargaining outcomes," Games and Economic Behavior, Elsevier, vol. 134(C), pages 169-198.
    8. Hwang, Sung-Ha & Rey-Bellet, Luc, 2021. "Positive feedback in coordination games: Stochastic evolutionary dynamics and the logit choice rule," Games and Economic Behavior, Elsevier, vol. 126(C), pages 355-373.
    9. Vincent Martinet & Pedro Gajardo & Michel De Lara & Héctor Ramírez Cabrera, 2011. "Bargaining with intertemporal maximin payoffs," EconomiX Working Papers 2011-7, University of Paris Nanterre, EconomiX.
    10. Saglam, Ismail, 2022. "Two-player bargaining problems with unilateral pre-donation," MPRA Paper 115203, University Library of Munich, Germany.
    11. Ismail Saglam, 2017. "Iterated Kalai–Smorodinsky–Nash compromise," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 40(1), pages 335-349, November.
    12. Hwang, Sung-Ha & Lim, Wooyoung & Neary, Philip & Newton, Jonathan, 2018. "Conventional contracts, intentional behavior and logit choice: Equality without symmetry," Games and Economic Behavior, Elsevier, vol. 110(C), pages 273-294.
    13. Ismail Saglam, 2013. "Endogenously proportional bargaining solutions," Economics Bulletin, AccessEcon, vol. 33(2), pages 1521-1534.
    14. Bas Dietzenbacher & Hans Peters, 2022. "Characterizing NTU-bankruptcy rules using bargaining axioms," Annals of Operations Research, Springer, vol. 318(2), pages 871-888, November.
    15. Laurens Cherchye & Thomas Demuynck & Bram De Rock, 2013. "Nash‐Bargained Consumption Decisions: A Revealed Preference Analysis," Economic Journal, Royal Economic Society, vol. 123, pages 195-235, March.
    16. Shiran Rachmilevitch, 2017. "Axiomatizations of the equal-loss and weighted equal-loss bargaining solutions," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 49(1), pages 1-9, June.
    17. l'Haridon, Olivier & Malherbet, Franck & Pérez-Duarte, Sébastien, 2013. "Does bargaining matter in the small firms matching model?," Labour Economics, Elsevier, vol. 21(C), pages 42-58.
    18. Marco Mariotii, 1996. "Fair bargains: distributive justice and Nash Bargaining Theory," Game Theory and Information 9611003, University Library of Munich, Germany, revised 06 Dec 1996.
    19. KIbrIs, Özgür & TapkI, Ipek Gürsel, 2010. "Bargaining with nonanonymous disagreement: Monotonic rules," Games and Economic Behavior, Elsevier, vol. 68(1), pages 233-241, January.
    20. Forgo, F. & Szidarovszky, F., 2003. "On the relation between the Nash bargaining solution and the weighting method," European Journal of Operational Research, Elsevier, vol. 147(1), pages 108-116, May.

    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:eee:apmaco:v:367:y:2020:i:c:s0096300319307775. 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: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.