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, December.
    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. Nash, John, 1950. "The Bargaining Problem," Econometrica, Econometric Society, vol. 18(2), pages 155-162, April.
    6. Aumann, Robert J., 1974. "Subjectivity and correlation in randomized strategies," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 67-96, March.
    7. 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..
    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, January.
    9. Mailath, George J. & Samuelson, Larry, 2006. "Repeated Games and Reputations: Long-Run Relationships," OUP Catalogue, Oxford University Press, number 9780195300796, Decembrie.
    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. 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.
    4. Daniele Cassese & Paolo Pin, 2018. "Decentralized Pure Exchange Processes on Networks," Papers 1803.08836, arXiv.org, revised Mar 2022.
    5. 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.
    6. 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.
    7. 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.
    8. Saglam, Ismail, 2022. "Two-player bargaining problems with unilateral pre-donation," MPRA Paper 115203, University Library of Munich, Germany.
    9. 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.
    10. Ismail Saglam, 2013. "Endogenously proportional bargaining solutions," Economics Bulletin, AccessEcon, vol. 33(2), pages 1521-1534.
    11. Bas Dietzenbacher & Hans Peters, 2022. "Characterizing NTU-bankruptcy rules using bargaining axioms," Annals of Operations Research, Springer, vol. 318(2), pages 871-888, November.
    12. 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.
    13. 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.
    14. 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.
    15. Shiran Rachmilevitch, 2019. "Egalitarianism, utilitarianism, and the Nash bargaining solution," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 52(4), pages 741-751, April.
    16. Dufwenberg, Martin & Servátka, Maroš & Vadovič, Radovan, 2017. "Honesty and informal agreements," Games and Economic Behavior, Elsevier, vol. 102(C), pages 269-285.
    17. Lombardi, Michele & Yoshihara, Naoki, 2010. "Alternative characterizations of the proportional solution for nonconvex bargaining problems with claims," Economics Letters, Elsevier, vol. 108(2), pages 229-232, August.
    18. Sung-Ha Hwang & Jonathan Newton, 2017. "Payoff-dependent dynamics and coordination games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 64(3), pages 589-604, October.
    19. Ronghuo Zheng & Tinglong Dai & Katia Sycara & Nilanjan Chakraborty, 2016. "Automated Multilateral Negotiation on Multiple Issues with Private Information," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 612-628, November.
    20. Karos, Dominik & Rachmilevitch, Shiran, 2018. "The Midpoint-Constrained Egalitarian Bargaining Solution," Research Memorandum 007, Maastricht University, Graduate School of Business and Economics (GSBE).

    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.