The Winner Takes It All

Abstract

The winner-takes-all process takes place on an arbitrary graph. There is an agent on each vertex of the graph, and active agents at neighboring vertices play games. In each game, a randomly chosen agent wins, while the loser is eliminated from subsequent games. The games are played at random times, finishing instantaneously, and ceasing when each active agent has only losers among its neighbors. On the one-dimensional lattice, the fraction of winners in the final state is $e^{-1}$; we also determine the fractions $w_j$ of winners who won $j=0,1,2$ games. For finite segments, we determine statistics of the total number of winners (the average, the variance, and all higher cumulants), the probabilities of attaining the minimum or maximum possible number of winners, and establish the behavior near the boundaries. For infinite regular trees with vertices of degree $d$, i.e., Bethe lattices with coordination number $d$, we show that the fraction of winners is $(2/d{)}^{d/(d-2)}$.

14 pages, 3 figures; v2:minor improvements