Greedy algorithms and Zipf laws

Abstract

We consider a simple model of firm/city/etc. growth based on a multi-item criterion: whenever entity B fares better that entity A on a subset of $M$ items out of $K$, the agent originally in A moves to B. We solve the model analytically in the cases $K=1$ and $K\to \infty$. The resulting stationary distribution of sizes is generically a Zipf-law provided $M>K/2$. When $M\le K/2$, no selection occurs and the size distribution remains thin-tailed. In the special case $M=K$, one needs to regularise the problem by introducing a small "default" probability $\varphi$. We find that the stationary distribution has a power-law tail that becomes a Zipf-law when $\varphi \to 0$. The approach to the stationary state can also been characterized, with strong similarities with a simple "aging" model considered by Barrat & Mézard.

References in corpus (1)

• Sample space reducing cascading processes produce the full spectrum of scaling exponents