The probability of nontrivial common knowledge

► We study the probability that two or more agents attain nontrivial common knowledge. ► Each agent has a random knowledge partition consistent with his cognitive capacity. ► When the size of the state space grows, nontrivial common knowledge undergoes a phase transition. ► Our proofs rely on a novel graph-theoretic characterization of common knowledge.