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

Fault Reporting in Partially Known Networks and Folk Theorems

Author

Listed:
  • Tristan Tomala

    (Economics and Decision Sciences Department, HEC Paris, 78351 Jouy-en-Josas Cedex, France)

Abstract

We consider a group of players who perform tasks repeatedly. The players are nodes of a communication network and observe their neighbors' actions. Players have partial knowledge of the network and only know their set of neighbors. We study the existence of protocols for fault reporting: whenever a player chooses a faulty action, the communication protocol starts and the output publicly reveals the identity of the faulty player. We consider two setups. In the first one, players do not share authentication keys. We show that existence of a protocol for fault reporting is equivalent to the 2-vertex-connectedness of the network: no single vertex deletion disconnects the graph. In the second setup, we allow players to share authentication keys. We show that existence of a distribution of the keys and of a protocol for fault reporting is equivalent to the 2-edge-connectedness of the network: no single edge deletion disconnects the graph. We give applications to the implementation of socially optimal outcomes in repeated games.

Suggested Citation

  • Tristan Tomala, 2011. "Fault Reporting in Partially Known Networks and Folk Theorems," Operations Research, INFORMS, vol. 59(3), pages 754-763, June.
    • Handle: RePEc:inm:oropre:v:59:y:2011:i:3:p:754-763
    DOI: 10.1287/opre.1110.0936
    as

    Download full text from publisher

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

    Other versions of this item:

    References listed on IDEAS

    as
    1. R.J. Aumann & S. Hart (ed.), 2002. "Handbook of Game Theory with Economic Applications," Handbook of Game Theory with Economic Applications, Elsevier, edition 1, volume 3, number 3.
    2. JÊrÆme Renault & Tristan Tomala, 1998. "Repeated proximity games," International Journal of Game Theory, Springer;Game Theory Society, vol. 27(4), pages 539-559.
    3. Drew Fudenberg & David Levine & Eric Maskin, 2008. "The Folk Theorem With Imperfect Public Information," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 12, pages 231-273, World Scientific Publishing Co. Pte. Ltd..
    4. Aumann, Robert J., 1974. "Subjectivity and correlation in randomized strategies," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 67-96, March.
    5. Drew Fudenberg & Eric Maskin, 2008. "The Folk Theorem In Repeated Games With Discounting Or With Incomplete Information," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 11, pages 209-230, World Scientific Publishing Co. Pte. Ltd..
    6. Sorin, Sylvain, 1992. "Repeated games with complete information," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 1, chapter 4, pages 71-107, Elsevier.
    7. Ben-Porath, Elchanan & Kahneman, Michael, 1996. "Communication in Repeated Games with Private Monitoring," Journal of Economic Theory, Elsevier, vol. 70(2), pages 281-297, August.
    8. Tristan Tomala, 2008. "Probabilistic Reliability and Privacy of Communication Using Multicast in General Neighbor Networks," Post-Print hal-00464542, HAL.
    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. Laclau, M., 2014. "Communication in repeated network games with imperfect monitoring," Games and Economic Behavior, Elsevier, vol. 87(C), pages 136-160.
    2. Renault, Jérôme & Renou, Ludovic & Tomala, Tristan, 2014. "Secure message transmission on directed networks," Games and Economic Behavior, Elsevier, vol. 85(C), pages 1-18.
    3. Laclau, Marie, 2012. "A folk theorem for repeated games played on a network," Games and Economic Behavior, Elsevier, vol. 76(2), pages 711-737.
    4. Somayeh Kokabisaghi & Eric J Pauwels & Andre B Dorsman, 2019. "To snipe or not to snipe, that is the question! Transitions in sniping behaviour among competing algorithmic traders," Papers 1912.04012, arXiv.org, revised Sep 2020.
    5. Laclau, M., 2013. "Repeated games with local monitoring and private communication," Economics Letters, Elsevier, vol. 120(2), pages 332-337.
    6. Marie Laclau & Ludovic Renou & Xavier Venel, 2020. "Robust communication on networks," Papers 2007.00457, arXiv.org, revised Oct 2020.
    7. Laclau, Marie & Renou, Ludovic & Venel, Xavier, 2024. "Communication on networks and strong reliability," Journal of Economic Theory, Elsevier, vol. 217(C).
    8. Marie Laclau & Ludovic Renou & Xavier Venel, 2024. "Communication on networks and strong reliability," Working Papers hal-03099678, HAL.

    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. Laclau, M., 2013. "Repeated games with local monitoring and private communication," Economics Letters, Elsevier, vol. 120(2), pages 332-337.
    2. Jérôme Renault & Tristan Tomala, 2011. "General Properties of Long-Run Supergames," Dynamic Games and Applications, Springer, vol. 1(2), pages 319-350, June.
    3. Laclau, M., 2014. "Communication in repeated network games with imperfect monitoring," Games and Economic Behavior, Elsevier, vol. 87(C), pages 136-160.
    4. Laclau, Marie, 2012. "A folk theorem for repeated games played on a network," Games and Economic Behavior, Elsevier, vol. 76(2), pages 711-737.
    5. Markus Kinateder, 2006. "Repeated Games Played in a Network," UFAE and IAE Working Papers 674.06, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    6. Laclau, Marie & Renou, Ludovic & Venel, Xavier, 2024. "Communication on networks and strong reliability," Journal of Economic Theory, Elsevier, vol. 217(C).
    7. Tomala, Tristan, 2009. "Perfect communication equilibria in repeated games with imperfect monitoring," Games and Economic Behavior, Elsevier, vol. 67(2), pages 682-694, November.
    8. Contou-Carrère, Pauline & Tomala, Tristan, 2011. "Finitely repeated games with semi-standard monitoring," Journal of Mathematical Economics, Elsevier, vol. 47(1), pages 14-21, January.
    9. Du, Chuang, 2012. "Solving payoff sets of perfect public equilibria: an example," MPRA Paper 38622, University Library of Munich, Germany.
    10. Olivier Gossner & Tristan Tomala, 2007. "Secret Correlation in Repeated Games with Imperfect Monitoring," Mathematics of Operations Research, INFORMS, vol. 32(2), pages 413-424, May.
    11. Ben-Porath, Elchanan & Kahneman, Michael, 2003. "Communication in repeated games with costly monitoring," Games and Economic Behavior, Elsevier, vol. 44(2), pages 227-250, August.
    12. Dasgupta, Ani & Ghosh, Sambuddha, 2022. "Self-accessibility and repeated games with asymmetric discounting," Journal of Economic Theory, Elsevier, vol. 200(C).
    13. Blume, Andreas & Heidhues, Paul, 2006. "Private monitoring in auctions," Journal of Economic Theory, Elsevier, vol. 131(1), pages 179-211, November.
    14. Kimmo Berg & Markus Kärki, 2018. "Critical Discount Factor Values in Discounted Supergames," Games, MDPI, vol. 9(3), pages 1-17, July.
    15. Laclau, Marie & Tomala, Tristan, 2017. "Repeated games with public deterministic monitoring," Journal of Economic Theory, Elsevier, vol. 169(C), pages 400-424.
    16. Tomala, Tristan, 1999. "Nash Equilibria of Repeated Games with Observable Payoff Vectors," Games and Economic Behavior, Elsevier, vol. 28(2), pages 310-324, August.
    17. Ashkenazi-Golan, Galit & Lehrer, Ehud, 2019. "Blackwell's comparison of experiments and discounted repeated games," Games and Economic Behavior, Elsevier, vol. 117(C), pages 163-194.
    18. Luca Anderlini (Georgetown University), Dino Gerardi (Yale University), Roger Lagunoff (Georgetown University), 2004. "The Folk Theorem in Dynastic Repeated Games," Working Papers gueconwpa~04-04-09, Georgetown University, Department of Economics.
    19. Sugaya, Takuo & Wolitzky, Alexander, 2017. "Bounding equilibrium payoffs in repeated games with private monitoring," Theoretical Economics, Econometric Society, vol. 12(2), May.
    20. Ichiro Obara, 2005. "Informational Smallness and Private Monitoring in Repeated Games (with R. McLean and A. Postlewaite)," UCLA Economics Online Papers 365, UCLA Department of Economics.

    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:59:y:2011:i:3:p:754-763. 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.