Fault Reporting in Partially Known Networks and Folk Theorems

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.
Type de document :
Article dans une revue
Operations Research, INFORMS, 2011, 59 (3), pp.754-763. 〈10.1287/opre.1110.0936〉
Liste complète des métadonnées

https://hal-hec.archives-ouvertes.fr/hal-00632806
Contributeur : Amaury Bouvet <>
Soumis le : samedi 15 octobre 2011 - 20:14:18
Dernière modification le : jeudi 11 janvier 2018 - 06:19:31

Identifiants

Collections

Citation

Tristan Tomala. Fault Reporting in Partially Known Networks and Folk Theorems. Operations Research, INFORMS, 2011, 59 (3), pp.754-763. 〈10.1287/opre.1110.0936〉. 〈hal-00632806〉

Partager

Métriques

Consultations de la notice

199