Jim Fill: Knockin' 'em Down, One After Another

This is a joint work with David Bruce Wilson (Microsoft Research).

A simple game called ``Knock 'em Down'' can be played between two players as follows. There are $k$ labeled bins, and each player is given $n$ tokens to be allocated freely (once and for all) among these bins. Independently repeated draws are then made from a fixed probability distribution $p = (p_1, \ldots, p_k)$ 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 $p$, asymptotically as $n$ 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.]

Bibliography

BF99

Arthur T. Benjamin and Matthew T. Fluet.
The best way to Knock'm Down.
The UMAP Journal, 20(1):11-20, 1999.

BF00

Arthur T. Benjamin and Matthew T. Fluet.
What's best?
Amer. Math. Monthly, 107(6):560-562, 2000.

BFH01

Arthur T. Benjamin, Matthew T. Fluet, and Mark L. Huber.
Optimal token allocations in Solitaire knock 'm down.
Electron. J. Combin., 8(2):Research Paper 2, 8 pp. (electronic), 2001.
In honor of Aviezri Fraenkel on the occasion of his 70th birthday.

Back to the Index