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 wj 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).
Related
- m-Set Adversarial Bandits with Winner Feedback
- Kelly's conjectures on Condorcet winner probabilities for odd electorates
- A Winner Classification for Rooted Partizan Edge Geography on Heterogeneous Bouquets of Cycles
- Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise
- Certified Alpha Capacity: Statistical Arbitrage When Learning Takes Time
BibTeX
@misc{krapivsky2026winner,
title = {{The Winner Takes It All}},
author = {P. L. Krapivsky},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.16885},
eprint = {2606.16885},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.16885},
}
RIS
TY - UNPB
TI - The Winner Takes It All
AU - P. L. Krapivsky
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2606.16885
UR - https://arxiv.org/abs/2606.16885
AB - 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).
ER -