LIPIcs.ITCS.2021.45.pdf
- Filesize: 0.63 MB
- 20 pages
Document
Relaxing Common Belief for Social Networks
Authors
Noah Burrell 
,
Grant Schoenebeck
-
Part of:
Volume:
12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2021-02-04
File
Document Identifiers
Author Details
Cite AsGet BibTex
Noah Burrell and Grant Schoenebeck. Relaxing Common Belief for Social Networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 45:1-45:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.45
https://doi.org/10.4230/LIPIcs.ITCS.2021.45
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Social networks
- Theory of computation → Network games
- Theory of computation → Algorithmic game theory
Keywords
- Social networks
- network revolt games
- common belief
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Robert J. Aumann. Agreeing to disagree. The Annals of Statistics, 4(6):1236-1239, 1976. URL: http://www.jstor.org/stable/2958591.
- Cristina Bicchieri. The Grammar of Society: The Nature and Dynamics of Social Norms. Cambridge University Press, 2005. URL: https://doi.org/10.1017/CBO9780511616037.
- Michael Suk-Young Chwe. Structure and strategy in collective action. American Journal of Sociology, 105(1):128-156, 1999. URL: https://doi.org/10.1086/210269.
- Michael Suk-Young Chwe. Communication and Coordination in Social Networks. The Review of Economic Studies, 67(1):1-16, January 2000. URL: https://doi.org/10.1111/1467-937X.00118.
-
Michael Suk-Young Chwe. Rational Ritual: Culture, Coordination, and Common Knowledge. Princeton University Press, 41 William Street, Princeton, New Jersey 08540, 2013.
- Benjamin Golub and Stephen Morris. Expectations, networks, and conventions, 2017. URL: https://doi.org/10.2139/ssrn.2979086.
- Benjamin Golub and Stephen Morris. Higher-order expectations, 2017. URL: https://doi.org/10.2139/ssrn.2979089.
- Dov Monderer and Dov Samet. Approximating common knowledge with common beliefs. Games and Economic Behavior, 1(2):170-190, 1989. URL: https://doi.org/10.1016/0899-8256(89)90017-1.
- Stephen Morris. Approximate common knowledge revisited. International Journal of Game Theory, 28(3):385-408, August 1999. URL: https://doi.org/10.1007/s001820050116.
- Stephen Morris. Contagion. The Review of Economic Studies, 67(1):57-78, January 2000. URL: https://doi.org/10.1111/1467-937X.00121.
- Stephen Morris. Coordination, Communication, and Common Knowledge: A Retrospective on the Electronic-mail Game. Oxford Review of Economic Policy, 18(4):433-445, December 2002. URL: https://doi.org/10.1093/oxrep/18.4.433.
- Stephen Morris. Coordination, timing and common knowledge. Research in Economics, 68(4):306-314, 2014. URL: https://doi.org/10.1016/j.rie.2014.04.004.
- Stephen Morris and Hyun Song Shin. Approximate common knowledge and co-ordination: Recent lessons from game theory. Journal of Logic, Language and Information, 6(2):171-190, April 1997. URL: https://doi.org/10.1023/A:1008270519000.
- Stephen Morris, Hyun Song Shin, and Muhamet Yildiz. Common belief foundations of global games. Journal of Economic Theory, 163:826-848, 2016. URL: https://doi.org/10.1016/j.jet.2016.03.007.
- Ariel Rubinstein. The electronic mail game: Strategic behavior under "almost common knowledge". The American Economic Review, 79(3):385-391, 1989. URL: http://www.jstor.org/stable/1806851.