arXiv:2605.12111cs.AIcs.DS2026-05中稿 · ICML被引 2

解决资源有限时的多轮招募分配问题,兼顾随机推荐与收益递减。

Adaptive Multi-Round Allocation with Stochastic Arrivals

论文配图:Adaptive Multi-Round Allocation with Stochastic Arrivals
图 1 · 摘自论文原文
  • 用边际存活概率设计贪心策略,实现单轮最优分配。
  • 引入群体级代理价值函数,使多轮规划复杂度降至多项式级别。
  • 理论证明误差可分解,适合对鲁棒性要求高的实际招募场景。

我们研究了一个源于自适应网络招募的序列资源分配问题:在有限预算下,需在多轮中向具有随机推荐能力的个体分配相同资源。成功的推荐会内生产生未来决策机会,而对同一人持续投入则呈现收益递减。首先,我们证明单轮分配问题可通过基于边际存活概率的贪心算法精确求解。在多轮设定下,由于前沿状态的随机高维演化,导致贝尔曼递归难以求解。为此,我们提出仅依赖剩余预算和前沿规模的群体级代理价值函数,结合截断概率生成函数,实现精确动态规划,规划复杂度为总预算的多项式。进一步分析模型误设下的鲁棒性,证明了多轮误差可分解为紧致的单轮前沿误差与群体级转移误差。最后,在真实世界启发的招募场景中评估了该方法。

原文摘要 · Abstract (English)

We study a sequential resource allocation problem motivated by adaptive network recruitment, in which a limited budget of identical resources must be allocated over multiple rounds to individuals with stochastic referral capacity. Successful referrals endogenously generate future decision opportunities while allocating additional resources to an individual exhibits diminishing returns. We first show that the single-round allocation problem admits an exact greedy solution based on marginal survival probabilities. In the multi-round setting, the resulting Bellman recursion is intractable due to the stochastic, high-dimensional evolution of the frontier. To address this, we introduce a population-level surrogate value function that depends only on the remaining budget and frontier size. This surrogate enables an exact dynamic program via truncated probability generating functions, yielding a planning algorithm with polynomial complexity in the total budget. We further analyze robustness under model misspecification, proving a multi-round error bound that decomposes into a tight single-round frontier error and a population-level transition error. Finally, we evaluate our method on real-world inspired recruitment scenarios.

资源分配动态规划随机优化招募模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。