Eric Bach(University of Wisconsin, Madison):
Bounds for the Expected Duration of the Monopolist Game
Amano, Tromp, Vitanyi, and Watanabe have recently studied
a ruin problem of the following type. Each of k players
starts with an initial stake I. At each round, the m players
that are sufficiently solvent each pay an ante of 1/m. These are
combined into a pot that is awarded to a randomly chosen active
player. Eventually, all players are bankrupted save one
(the ``monopolist''), and the game stops.
For n=2 this is equivalent to a symmetric random walk with absorbing
barriers, and the mean duration of the game is well known to
be Theta(I^2). Based on experimental evidence,
Amano et al. conjectured that the expected duration of the
k-player game, that is, the expected time at
which the monopolist emerges, is Theta(k^2 I^2).
In this talk I will prove their conjecture.