Maximal cooperation in repeated games on social networks

Published

Conference Paper

Standard results on and algorithms for repeated games assume that defections are instantly observable. In reality, it may take some time for the knowledge that a defection has occurred to propagate through the social network. How does this affect the structure of equilibria and algorithms for computing them? In this paper, we consider games with cooperation and defection. We prove that there exists a unique maximal set of forever cooperating agents in equilibrium and give an efficient algorithm for computing it. We then evaluate this algorithm on random graphs and find experimentally that there appears to be a phase transition between cooperation everywhere and defection everywhere, based on the value of cooperation and the discount factor. Finally, we provide a condition for when the equilibrium found is credible, in the sense that agents are in fact motivated to punish deviating agents. We find that this condition always holds in our experiments, provided the graphs are sufficiently large.

Duke Authors

Cited Authors

  • Moon, C; Conitzer, V

Published Date

  • January 1, 2015

Published In

Volume / Issue

  • 2015-January /

Start / End Page

  • 216 - 223

International Standard Serial Number (ISSN)

  • 1045-0823

International Standard Book Number 13 (ISBN-13)

  • 9781577357384

Citation Source

  • Scopus