IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-00632806.html

Fault Reporting in Partially Known Networks and Folk Theorems

Author

Listed:
  • Tristan Tomala

    (GREGH - Groupement de Recherche et d'Etudes en Gestion à HEC - HEC Paris - Ecole des Hautes Etudes Commerciales - CNRS - Centre National de la Recherche Scientifique)

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," Post-Print hal-00632806, HAL.
    • Handle: RePEc:hal:journl:hal-00632806
    DOI: 10.1287/opre.1110.0936
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a
    for a similarly titled item that would be available.

    Other versions of this item:

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. Laclau, Marie, 2012. "A folk theorem for repeated games played on a network," Games and Economic Behavior, Elsevier, vol. 76(2), pages 711-737.
    3. 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.
    4. Marie Laclau & Ludovic Renou & Xavier Venel, 2024. "Communication on networks and strong reliability," Post-Print hal-04836057, HAL.
    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. Laclau, M., 2014. "Communication in repeated network games with imperfect monitoring," Games and Economic Behavior, Elsevier, vol. 87(C), pages 136-160.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;

    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:hal:journl:hal-00632806. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.