Contributions to Game Theory and Management
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Contributions to Game Theory and Management:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Contributions to Game Theory and Management, 2021, Volume 14, Pages 183–191
DOI: https://doi.org/10.21638/11701/spbu31.2021.14
(Mi cgtm396)
 

This article is cited in 2 scientific papers (total in 2 papers)

Optimal stopping in the balls-and-bins problem

Anna A. Ivashko

Institute of Applied Mathematical Research, Karelian Research Centre RAS, Pushkinskaya str. 11, Petrozavodsk, 185910, Russia
Full-text PDF (528 kB) Citations (2)
References:
Abstract: 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.
Funding agency Grant number
Ministry of Science and Higher Education of the Russian Federation
The study was carried out under state order to the Karelian Research Centre of the Russian Academy of Sciences (Institute of Applied Mathematical Research KarRC RAS).
Document Type: Article
Language: English
Citation: Anna A. Ivashko, “Optimal stopping in the balls-and-bins problem”, Contributions to Game Theory and Management, 14 (2021), 183–191
Citation in format AMSBIB
\Bibitem{Iva21}
\by Anna~A.~Ivashko
\paper Optimal stopping in the balls-and-bins problem
\jour Contributions to Game Theory and Management
\yr 2021
\vol 14
\pages 183--191
\mathnet{http://mi.mathnet.ru/cgtm396}
\crossref{https://doi.org/10.21638/11701/spbu31.2021.14}
Linking options:
  • https://www.mathnet.ru/eng/cgtm396
  • https://www.mathnet.ru/eng/cgtm/v14/p183
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024