The Life of the Party
Diffusion in networks under random sequential participation.
Final Paper for ECON284/CS360: Simplicity and Complexity in Economic Theory
Abstract
We study a model of party attendance in which guests arrive in a uniformly random order and irrevocably decide whether to stay based on how many friends are already present. The final party is determined by the interaction between the social network, the arrival order, and a threshold rule. For threshold k = 1, we show the final party equals the reachable set from the hosts in the permutation-induced directed acyclic graph. This equivalence yields a path-counting framework that produces exact, closed-form expressions for the expected party size over time on trees, rings, and complete bipartite graphs. We show that party success depends not on the number of connections but on their structure. For the seed selection problem (sending initial invites), we prove that when k = 1, the expected party size is submodular in the seed set, so greedy host selection would achieve at least a (1 − 1/e)-approximation, but when k ≥ 2, submodularity fails in this diffusion model.
Authors
- Lyle Goodyear
- Annika Younge