Geodesic
Optimal stopping in the balls-and-bins problem
Contributions to game theory and management, Tome 14 (2021), pp. 183-191.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper considers a multistage balls-and-bins problem with optimal stopping connected with the job allocation model. There are $N$ steps. The player drops balls (tasks) randomly one at a time into available bins (servers). The game begins with only one empty bin. At each step, a new bin can appear with probability $p$. At step $n$ ($n=1,\ldots,N$), the player can choose to stop and receive the payoff or continue the process and move to the next step. If the player stops, then he/she gets $1$ for every bin with exactly one ball and loses $1/2$ for every bin with two or more balls. Empty bins do not count. At the last step, the player must stop the process. The player's aim is to find the stopping rule which maximizes the expected payoff. The optimal payoffs at each step are calculated. An approximate strategy depending on the number of steps is proposed. It is demonstrated that the payoff when using this strategy is close to the optimal payoff.
Keywords: optimal stopping, job allocation, balls-and-bins problem. 
@article{CGTM_2021_14_a14,
     author = {Anna A. Ivashko},
     title = {Optimal stopping in the balls-and-bins problem},
     journal = {Contributions to game theory and management},
     pages = {183--191},
     publisher = {mathdoc},
     volume = {14},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2021_14_a14/}
}
TY  - JOUR
AU  - Anna A. Ivashko
TI  - Optimal stopping in the balls-and-bins problem
JO  - Contributions to game theory and management
PY  - 2021
SP  - 183
EP  - 191
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2021_14_a14/
LA  - en
ID  - CGTM_2021_14_a14
ER  - 
%0 Journal Article
%A Anna A. Ivashko
%T Optimal stopping in the balls-and-bins problem
%J Contributions to game theory and management
%D 2021
%P 183-191
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2021_14_a14/
%G en
%F CGTM_2021_14_a14
Anna A. Ivashko. Optimal stopping in the balls-and-bins problem. Contributions to game theory and management, Tome 14 (2021), pp. 183-191. http://geodesic.mathdoc.fr/item/CGTM_2021_14_a14/

[1] Bearden J. N., “A new secretary problem with rank-based selection and cardinal payoffs”, Journal of Mathematical Psychology, 50:1 (2006), 58–59 | MR | Zbl

[2] Kolchin V. F., Random allocations, Winston, Washington, 1978 | MR | Zbl

[3] Shepp L. A., “Explicit solutions to some problems of optimal stopping”, Ann. Math. Statist., 40 (1969), 993–1010 | MR | Zbl

[4] Tamaki M., “Optimal stopping on trajectories and the ballot problem”, Journal of Applied Probability, 38 (2001), 946–959 | MR | Zbl

[5] Tijms H., “One-Step Improvement Ideas and Computational Aspects”, Markov Decision Processes in Practice, International Series in Operations Research Management Science, 248, eds. Boucherie R., N. Dijk van, Springer, Cham, 2017, 3–32 | MR | Zbl