Relaxing Common Belief for Social Networks

on YouTube ↗24m

" summary

Paper defines common P_mu belief (a factional-belief relaxations of common belief) and proves it undergirds partial approximate coordination in threshold revolt games. Exact revolt decision is NP‑hard, but the promised revolt problem admits a polynomial‑time algorithm when maximum degree is bounded and delta(N)→0. A surprising corollary is a degree-sequence-only algorithm that needs no edge list. Methods combine equilibrium characterization, reductions, and simulations that map how equilibrium revolt sizes vary with network and model parameters.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 1:35Network Revolt Games: Example
3. 5:58Limitations of Previous Work
4. 10:20Our Network Revolt Game Model: The Network
5. 10:33Our Model: The Agents
6. 12:33Our Model: The Solution Concept
7. 13:03Motivating Example: Model
8. 13:52Motivating Example: Proposition
9. 14:23Motivating Example: Intuition
10. 16:04An Algorithmic Perspective: The Fundamental Case
11. 17:33A Formal Problem: REVOLT
12. 18:14A Relaxed Problem: PROMISE REVOLT
13. 19:13Illustrating PROMISE REVOLT
14. 20:09Relating REVOLT, PROMISE REVOLT to Factional Be
15. 20:36Main Technical Result
16. 21:17Surprising Corollary to our Analysis
17. 21:38Extensions of the Fundamental Case
18. 22:24Future Work and Open Questions