License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.45
URN: urn:nbn:de:0030-drops-135841
Go to the corresponding LIPIcs Volume Portal

Burrell, Noah ; Schoenebeck, Grant

Relaxing Common Belief for Social Networks

LIPIcs-ITCS-2021-45.pdf (0.6 MB)


We propose a relaxation of common belief called factional belief that is suitable for the analysis of strategic coordination on social networks. We show how this definition can be used to analyze revolt games on general graphs, including by giving an efficient algorithm that characterizes a structural result about the possible equilibria of such games.
This extends prior work on common knowledge and common belief, which has been too restrictive for use in understanding strategic coordination and cooperation in social network settings.

BibTeX - Entry

  author =	{Noah Burrell and Grant Schoenebeck},
  title =	{{Relaxing Common Belief for Social Networks}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{45:1--45:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-135841},
  doi =		{10.4230/LIPIcs.ITCS.2021.45},
  annote =	{Keywords: Social networks, network revolt games, common belief}

Keywords: Social networks, network revolt games, common belief
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI