(Relaxing) Common Belief for Social Networks

          @misc{ scivideos_23046,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/23046},
            author = {},
            keywords = {},
            language = {en},
            title = {(Relaxing) Common Belief for Social Networks},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {dec},
            note = {23046 see, \url{https://scivideos.org/index.php/simons-institute/23046}}
          }
          

Abstract

Many social network phenomena such as norms and cascades depend not only on what agents believe but on what they believe other agents believe.   One important instantiation of agents’ beliefs about beliefs is knowledge commonly known by all agents.  However, current definitions that capture this idea such as common knowledge and common belief are too restrictive for use in understanding strategic coordination and cooperation in social network settings. In this talk, I will propose a relaxation of common belief called factional belief that is suitable for the analysis of social network phenomena.  I will then show how this definition can be used to analyze revolt games on sparse graphs.  In particular, I will show that for a certain natural class of revolt games, the degree sequence of a network almost entirely characterizes whether any equilibrium can often support a large revolt.  The proof is via an efficient algorithm for determining the same.  A key goal of this talk is to provide the background to start a conversation about where common knowledge (or its variants) can help us to reason about social network phenomena.