2016/02/11 by Xavier Vilaça, Vilaça, Xavier, Luı́s Rodrigues +1
Computer Science · Decision Sciences · Physics and Astronomy · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Opinion Dynamics and Social Influence #Peer-to-Peer Network Technologies
paper · pdf · doi:10.48550/arxiv.1602.03885
openalex publication_date 2016/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We take a game theoretical approach to determine necessary and sufficient conditions under which we can persuade rational agents to exchange messages in pairwise exchanges over links of a dynamic network, by holding them accountable for deviations with punishments. We make three contributions: (1) we provide a new game theoretical model of repeated interactions in dynamic networks, where agents have incomplete information of the topology, (2) we define a new solution concept for this model, and (3) we identify necessary and sufficient conditions for enforcing accountability, i.e., for persuading agents to exchange messages in the aforementioned model. Our results are of technical interest but also of practical relevance. We show that we cannot enforce accountability if the dynamic network does not allow for timely punishments. In practice, this means for instance that we cannot enforce accountability in some networks formed in file-sharing applications such as Bittorrent \citeCohen:03. We also show that for applications such as secret exchange, where the benefits of the exchanges significantly surpass the communication costs, timely punishments are enough to enforce accountability. However, we cannot in general enforce accountability if agents do not possess enough information about the network topology. Nevertheless, we can enforce accountability in a wide variety of networks that satisfy 1-connectivity \citeKuhn:10 with minimal knowledge about the network topology, including overlays for gossip dissemination such as \citeLi:06,Li:08.