IDEAS home Printed from
   My bibliography  Save this article

A Sequential Stochastic Assignment Problem


  • Cyrus Derman

    (Columbia University)

  • Gerald J. Lieberman

    (Stanford University)

  • Sheldon M. Ross

    (University of California, Berkeley)


Suppose there are n men available to perform n jobs. The n jobs occur in sequential order with the value of each job being a random variable X. Associated with each man is a probability p. If a "p" man is assigned to an "X = x" job, the (expected) reward is assumed to be given by px. After a man is assigned to a job, he is unavailable for future assignments. The paper is concerned with the optimal assignment of the n men to the n jobs, so as to maximize the total expected reward. The optimal policy is characterized, and a recursive equation is presented for obtaining the necessary constants of this optimal policy. In particular, if p 1 \leqq p 2 \leqq \cdots \leqq p n the optimal choice in the initial stage of an n stage assignment problem is to use p i if x falls into an ith nonoverlapping interval comprising the real line. These intervals depend on n and the CDF of X, but are independent of the p's. The optimal policy is also presented for the generalized assignment problem, i.e., the assignment problem where the (expected) reward if a "p" man is assigned to an "x" job is given by a function r(p, x).

Suggested Citation

  • Cyrus Derman & Gerald J. Lieberman & Sheldon M. Ross, 1972. "A Sequential Stochastic Assignment Problem," Management Science, INFORMS, vol. 18(7), pages 349-355, March.
  • Handle: RePEc:inm:ormnsc:v:18:y:1972:i:7:p:349-355

    Download full text from publisher

    File URL:
    Download Restriction: no


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

    Cited by:

    1. Gershkov, Alex & Moldovanu, Benny, 2012. "Optimal search, learning and implementation," Journal of Economic Theory, Elsevier, vol. 147(3), pages 881-909.
    2. 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.
    3. David, Israel & Levi, Ofer, 2004. "A new algorithm for the multi-item exponentially discounted optimal selection problem," European Journal of Operational Research, Elsevier, vol. 153(3), pages 782-789, March.
    4. repec:pal:jorsoc:v:59:y:2008:i:12:d:10.1057_palgrave.jors.2602518 is not listed on IDEAS
    5. 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.
    6. Gershkov, Alex & Moldovanu, Benny, 2013. "Non-Bayesian optimal search and dynamic implementation," Economics Letters, Elsevier, vol. 118(1), pages 121-125.
    7. Stefanos A. Zenios & Glenn M. Chertow & Lawrence M. Wein, 2000. "Dynamic Allocation of Kidneys to Candidates on the Transplant Waiting List," Operations Research, INFORMS, vol. 48(4), pages 549-569, August.
    8. Grace Y. Lin & Yingdong Lu & David D. Yao, 2008. "The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing," Operations Research, INFORMS, vol. 56(4), pages 945-957, August.
    9. Laura A. McLay & Adrian J. Lee & Sheldon H. Jacobson, 2010. "Risk-Based Policies for Airport Security Checkpoint Screening," Transportation Science, INFORMS, vol. 44(3), pages 333-349, August.
    10. Francis Bloch & Nicolas Houy, 2012. "Optimal assignment of durable objects to successive agents," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 51(1), pages 13-33, September.
    11. Alexander G. Nikolaev & Sheldon H. Jacobson & Laura A. McLay, 2007. "A Sequential Stochastic Security System Design Problem for Aviation Security," Transportation Science, INFORMS, vol. 41(2), pages 182-194, May.
    12. Pancs, Romans, 2013. "Sequential negotiations with costly information acquisition," Games and Economic Behavior, Elsevier, vol. 82(C), pages 522-543.
    13. 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.
    14. David, Israel & Levi, Ofer, 2001. "Asset-selling problems with holding costs," International Journal of Production Economics, Elsevier, vol. 71(1-3), pages 317-321, May.
    15. Kang, Seungmo & Ouyang, Yanfeng, 2011. "The traveling purchaser problem with stochastic prices: Exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 209(3), pages 265-272, March.
    16. 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.
    17. Arieh Gavious & Ella Segev, 2017. "Price Discrimination Based on Buyers’ Purchase History," Dynamic Games and Applications, Springer, vol. 7(2), pages 229-265, June.
    18. Anton J. Kleywegt & Jason D. Papastavrou, 2001. "The Dynamic and Stochastic Knapsack Problem with Random Sized Items," Operations Research, INFORMS, vol. 49(1), pages 26-41, February.
    19. 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.
    20. Xuanming Su & Stefanos A. Zenios, 2005. "Patient Choice in Kidney Allocation: A Sequential Stochastic Assignment Model," Operations Research, INFORMS, vol. 53(3), pages 443-455, June.
    21. Benny Moldovanu & Alex Gershkov, 2008. "The Trade-off Between Fast Learning and Dynamic Efficiency," 2008 Meeting Papers 348, Society for Economic Dynamics.

    More about this item


    Access and download statistics


    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:ormnsc:v:18:y:1972:i:7:p:349-355. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: .

    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.

    We have no references for this item. You can help adding them by using 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.