Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T14:11:43.244Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximizing the variance of the time to ruin in a multiplayer game with selection

Part of: Stochastic processes Combinatorial probability Game theory Stochastic systems and control

Published online by Cambridge University Press:  10 June 2016

Ilie Grigorescu  and
Yi-Ching Yao
Ilie Grigorescu*
Affiliation:
University of Miami
Yi-Ching Yao*
Affiliation:
Academia Sinica and National Chengchi University
*
* Postal address: Department of Mathematics, University of Miami, 1365 Memorial Drive, Coral Gables, FL 33124-4250, USA. Email address: [email protected]
** Postal address: Institute of Statistical Science, Academia Sinica, Taipei 115, Taiwan, R.O.C.. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a game with K ≥ 2 players, each having an integer-valued fortune. On each round, a pair (i,j) among the players with nonzero fortunes is chosen to play and the winner is decided by flipping a fair coin (independently of the process up to that time). The winner then receives a unit from the loser. All other players' fortunes remain the same. (Once a player's fortune reaches 0, this player is out of the game.) The game continues until only one player wins all. The choices of pairs represent the control present in the problem. While it is known that the expected time to ruin (i.e. expected duration of the game) is independent of the choices of pairs (i,j) (the strategies), our objective is to find a strategy which maximizes the variance of the time to ruin. We show that the maximum variance is uniquely attained by the (optimal) strategy, which always selects a pair of players who have currently the largest fortunes. An explicit formula for the maximum value function is derived. By constructing a simple martingale, we also provide a short proof of a result of Ross (2009) that the expected time to ruin is independent of the strategies. A brief discussion of the (open) problem of minimizing the variance of the time to ruin is given.

Keywords

Gambler's ruinmartingaledynamic programmingstochastic control

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory
Secondary: 91A60: Probabilistic games; gambling 93E20: Optimal stochastic control 60C05: Combinatorial probability
Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 2 , June 2016 , pp. 610 - 630
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Amano, K.,Tromp, J.,Vitányi, P. M. B. and Watanabe, O. (2001).On a generalized ruin problem. In Approximation, Randomization, and Combinatorial Optimization (Lecture Notes Comput. Sci.2129),Springer,Berlin, pp.181–191.Google Scholar
[2]Bach, E. (2007).Bounds for the expected duration of the monopolist game.Inform. Process. Lett. 101,86–92.Google Scholar
[3]Blackwell, D. (1970).On stationary policies.J. R. Statist. Soc. Ser. A 133,33–37.Google Scholar
[4]Bruss, F. T.,Louchard, G. and Turner, J. W. (2003).On the N-tower problem and related problems.Adv. Appl. Prob. 35,278–294.Google Scholar
[5]Bürger, R. and Ewens, W. J. (1995).Fixation probabilities of additive alleles in diploid populations.J. Math. Biol. 33,557–575.CrossRefGoogle Scholar
[6]Engel, A. (1993).The computer solves the three tower problem.Amer. Math. Monthly 100,62–64.Google Scholar
[7]Felsenstein, J. (1974).The evolutionary advantage of recombination.Genetics 78,737–756.Google Scholar
[8]Harik, G.,Cantú-Paz, E.,Goldberg, D. E. and Miller, B. L. (1999).The gambler's ruin problem, genetic algorithms, and the sizing of populations.Evolutionary Computation 7,231–253.CrossRefGoogle ScholarPubMed
[9]Knuth, D. E. (1998).The Art of Computer Programming, Vol. 2,3rd edn.Addison-Wesley,Reading, MA.Google Scholar
[10]Ross, S. M. (2009).A simple solution to a multiple player gambler's ruin problem.Amer. Math. Monthly 116,77–81.Google Scholar
[11]Ross, S. M. (2011).The multiple-player ante one game.Prob. Eng. Inf. Sci. 25,343–353.Google Scholar
[12]Stirzaker, D. (1994).Tower problems and martingales.Math. Scientist 19,52–59.Google Scholar
[13]Swan, Y. C. and Bruss, F. T. (2006).A matrix-analytic approach to the N-player ruin problem.J. Appl. Prob. 43,755–766.Google Scholar