Optimal and asymptotically optimal decision rules for sequential screening and resource allocation
Optimal and asymptotically optimal decision rules for sequential screening and resource allocation
复制标题
顺序筛选和资源分配的最优和渐近最优决策规则
DOI：
--
复制
发表时间：
2001
影响因子：
6.8
通讯作者：
L. Pronzato
中科院分区：
文献类型：
--
作者：
L. Pronzato
我们考虑在长度为n的i.i.d序列中依次选择的n个变量X/sub k/的期望和最大化问题，它相当于以下资源分配问题：n台机器必须分配给顺序到达的n个值为X/sub k/ （k=1，…，n）的作业，第i台机器有（已知的）概率p/sub i/成功完成该作业，并且总期望奖励必须最大化。当X/sub k/s的分布已知时，导出了这个随机动态规划问题的最优解：接受X/sub k/或将第i台机器分配给工作k的最优阈值由一个向后递归方程给出。将该最优解与阈值为常数的更简单的（但次优的）开环反馈最优解进行了比较，并研究了它们的渐近行为。利用最优阈值的渐近特性，导出了一个简单的开环解，证明了对于X/sub k/的一大类分布，该解是渐近最优的（N/spl rarr//spl infin/， N固定）。
We consider the problem of maximizing the expected sum of n variables X/sub k/ chosen sequentially in an i.i.d. sequence of length N. It is equivalent to the following resource allocation problem: n machines have to be allocated to N jobs of value X/sub k/ (k=1,...,N) arriving sequentially, the ith machine has a (known) probability p/sub i/ to perform the job successfully and the total expected reward must be maximized. The optimal solution of this stochastic dynamic-programming problem is derived when the distribution of the X/sub k/s is known: the optimal threshold for accepting X/sub k/, or allocating the ith machine to job k, is given by a backward recurrence equation. This optimal solution is compared to the simpler (but suboptimal) open-loop feedback-optimal solution for which the threshold is constant, and their asymptotic behaviors are investigated. The asymptotic behavior of the optimal threshold is used to derive a simple open-loop solution, which is proved to be asymptotically optimal (N/spl rarr//spl infin/ with n fixed) for a large class of distributions for X/sub k/.