Two-Player Knock 'em Down

James Allen Fill (The Johns Hopkins University)
David B Wilson (Microsoft)

Abstract


We analyze the two-player game of Knock 'em Down, asymptotically as the number of tokens to be knocked down becomes large. Optimal play requires mixed strategies with deviations of order $\sqrt{n}$ from the naïve law-of-large numbers allocation. Upon rescaling by $\sqrt{n}$ and sending $n\to\infty$, we show that optimal play's random deviations always have bounded support and have marginal distributions that are absolutely continuous with respect to Lebesgue measure.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 198-212

Publication Date: February 14, 2008

DOI: 10.1214/EJP.v13-485

References

  1. Arthur T. Benjamin and Matthew T. Fluet. The best way to Knock 'm Down. The UMAP Journal, 20(1):11--20, 1999.
  2. Arthur T. Benjamin and Matthew T. Fluet. What's best? Amer. Math. Monthly, 107(6):560--562, 2000. MR1767066
  3. 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., 2001. In honor of Aviezri Fraenkel on the occasion of his 70th birthday. MR1853253
  4. Ky Fan. Minimax theorems. Proc. Nat. Acad. Sci. U.S.A., 39:42--47, 1953. MR0055678
  5. Matthew T. Fluet. Searching for optimal strategies in Knock 'm Down, 1999. Senior thesis, Harvey Mudd College, Claremont, CA.
  6. James A. Fill and David B. Wilson. Solitaire Knock 'em Down, 2006. Manuscript.
  7. Gordon Hunt. Knock 'm down. Teaching Stat., 20(2):59--62, 1998.
  8. Pertti Mattila. Geometry of Sets and Measures in Euclidean Spaces, fractals and rectifiability, volume 44 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995. MR1333890
  9. Daniel W. Stroock. Probability Theory, an analytic view. Cambridge University Press, Cambridge, 1993. MR1267569
  10. Maurice Sion and Philip Wolfe. On a game without a value. In Contributions to the theory of games, vol. 3, Annals of Mathematics Studies, no. 39, pages 299--306. Princeton University Press, Princeton, N. J., 1957. MR0093742
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.