A simple game called ``Knock 'em Down'' can be played between two
players as follows. There are labeled bins, and each player is
given
tokens to be allocated freely (once and for all) among these
bins. Independently repeated draws are then made from a fixed
probability distribution
on the bins; when a
bin is drawn, each player may remove one of her or his tokens, if any,
from that bin. The object of the game is to be the first to remove all
of one's tokens from the bins. We present an analysis of the game for
fixed
, asymptotically as
becomes large; despite the game's
simple nature, there are some subtleties in its analysis. We will
discuss at least the following two variants: the payoff to the winner
is (i) the difference in the numbers of draws required to remove the
player's tokens; or (ii) one monetary unit (with no money exchanged
when the players tie). Our analysis both builds upon and diverges from
earlier analysis of Arthur T. Benjamin, Matthew T. Fluet, and Mark
L. Huber.
[Note: This talk is slighly off-topic for analysis of algorithms, but intentionally so. Wilson and I are unable at this time to complete the analysis of game (ii). It is quite possible that the fixed-point ideas with which the AofA community is familiar will help, and I look forward to interactions in Austria.]