IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v47y2022i1p29-49.html

Optimal Stopping of a Random Sequence with Unknown Distribution

Author

Listed:
  • Alexander Goldenshluger

    (Department of Statistics, University of Haifa, Haifa, 3498838, Israel)

  • Assaf Zeevi

    (Graduate School of Business, Columbia University, New York, New York 10027)

Abstract

The subject of this paper is the problem of optimal stopping of a sequence of independent and identically distributed random variables with unknown distribution. We propose a stopping rule that is based on relative ranks and study its performance as measured by the maximal relative regret over suitable nonparametric classes of distributions. It is shown that the proposed rule is first-order asymptotically optimal and nearly rate optimal in terms of the rate at which the relative regret converges to zero. We also develop a general method for numerical solution of sequential stopping problems with no distributional information and use it in order to implement the proposed stopping rule. Some numerical experiments illustrating performance of the rule are presented as well.

Suggested Citation

  • Alexander Goldenshluger & Assaf Zeevi, 2022. "Optimal Stopping of a Random Sequence with Unknown Distribution," Mathematics of Operations Research, INFORMS, vol. 47(1), pages 29-49, February.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:1:p:29-49
    DOI: 10.1287/moor.2020.1109
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2020.1109
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2020.1109?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Boshuizen, Frans A. & Hill, T. P., 1992. "Moment-based minimax stopping functions for sequences of random variables," Stochastic Processes and their Applications, Elsevier, vol. 43(2), pages 303-316, December.
    2. Cyrus Derman & Gerald J. Lieberman & Sheldon M. Ross, 1972. "A Sequential Stochastic Assignment Problem," Management Science, INFORMS, vol. 18(7), pages 349-355, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Pieter Kleer & Johan van Leeuwaarden, 2022. "Optimal Stopping Theory for a Distributionally Robust Seller," Papers 2206.02477, arXiv.org, revised Jun 2022.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Adrian Lee & Sheldon Jacobson, 2011. "Sequential stochastic assignment under uncertainty: estimation and convergence," Statistical Inference for Stochastic Processes, Springer, vol. 14(1), pages 21-46, February.
    2. Xuhan Tian & Junmin (Jim) Shi & Xiangtong Qi, 2022. "Stochastic Sequential Allocations for Creative Crowdsourcing," Production and Operations Management, Production and Operations Management Society, vol. 31(2), pages 697-714, February.
    3. Meghan Shanks & Ge Yu & Sheldon H. Jacobson, 2023. "Approximation algorithms for stochastic online matching with reusable resources," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 98(1), pages 43-56, August.
    4. Alexander G. Nikolaev & Sheldon H. Jacobson, 2010. "Technical Note ---Stochastic Sequential Decision-Making with a Random Number of Jobs," Operations Research, INFORMS, vol. 58(4-part-1), pages 1023-1027, August.
    5. Arash Khatibi & Sheldon H. Jacobson, 2016. "Doubly Stochastic Sequential Assignment Problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 124-137, March.
    6. Baris Ata & Yichuan Ding & Stefanos Zenios, 2021. "An Achievable-Region-Based Approach for Kidney Allocation Policy Design with Endogenous Patient Choice," Manufacturing & Service Operations Management, INFORMS, vol. 23(1), pages 36-54, 1-2.
    7. Pengyu Yan & Xiaoqiang Cai & Feng Chu & Debing Ni & Heng He, 2023. "An Incentive Mechanism for Private Parking-Sharing Programs in an Imperfect Information Setting," Service Science, INFORMS, vol. 15(1), pages 3-21, March.
    8. Yizhaq Minchuk & Aner Sela, 2018. "Asymmetric sequential search under incomplete information," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 27(2), pages 315-325, June.
    9. Golshid Baharian & Sheldon H. Jacobson, 2013. "Limiting behavior of the stochastic sequential assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(4), pages 321-330, June.
    10. Gershkov, Alex & Moldovanu, Benny, 2013. "Non-Bayesian optimal search and dynamic implementation," Economics Letters, Elsevier, vol. 118(1), pages 121-125.
    11. Yen‐Ming Lee & Sheldon M. Ross, 2013. "Bayesian selling problem with partial information," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(7), pages 557-570, October.
    12. Chun, Young H. & Sumichrast, Robert T., 2006. "A rank-based approach to the sequential selection and assignment problem," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1338-1344, October.
    13. Marlo Raveendran & Phanish Puranam & Massimo Warglien, 2022. "Division of Labor Through Self-Selection," Organization Science, INFORMS, vol. 33(2), pages 810-830, March.
    14. Hak Chun, Young, 1996. "Selecting the best choice in the weighted secretary problem," European Journal of Operational Research, Elsevier, vol. 92(1), pages 135-147, July.
    15. So, Mee Chi & Thomas, Lyn C. & Huang, Bo, 2016. "Lending decisions with limits on capital available: The polygamous marriage problem," European Journal of Operational Research, Elsevier, vol. 249(2), pages 407-416.
    16. Járai, Antal A., 2022. "Asymptotics of the optimum in discrete sequential assignment," Stochastic Processes and their Applications, Elsevier, vol. 148(C), pages 267-277.
    17. Alexander Alvarez & Sebastian Ferrando, 2014. "Trajectory Based Models, Arbitrage and Continuity," Papers 1403.5685, arXiv.org, revised Jan 2015.
    18. Richard G. Anderson & Suresh K. Nair, 2005. "A specialized inventory problem in banks: optimizing retail sweeps," Working Papers 2005-023, Federal Reserve Bank of St. Louis.
    19. Arieh Gavious & Ella Segev, 2017. "Price Discrimination Based on Buyers’ Purchase History," Dynamic Games and Applications, Springer, vol. 7(2), pages 229-265, June.
    20. Arash Khatibi & Golshid Baharian & Banafsheh Behzad & Sheldon Jacobson, 2015. "Extensions of the sequential stochastic assignment problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(3), pages 317-340, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:47:y:2022:i:1:p:29-49. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.