Technical Note-A Stochastic Assignment Problem with Unknown Eligibility Probabilities

• 成果类型: Article
• 署名作者: Ross, Sheldon M.; Weiss, Gideon; Zhang, Zhengyu
• 署名单位: University of Southern California; University of Haifa
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.1988
• 发表日期: 2021
• 页码: 266-272
• 关键词: allocation

摘要

Consider n initially empty boxes, numbered 1 through n. Balls arrive sequentially. Each ball has a binary n-vector attached to it, with the interpretation that the ball is eligible to be put in box i if component i of its vector is equal to 1. An arriving ball can be put in any empty box for which it is eligible. Assuming that components of the vector are independent Bernoulli random variables with initially unknown probabilities, our primary interest is to compare several policies to determine which leads to a stochastically smaller number of observed balls until all boxes are filled.