相关奖励下，在线算法需更多额外奖励才能逼近最优解。
The Competition Complexity of Prophet Inequalities with Correlations
- 引入资源增强框架研究相关奖励的抢购不等式问题
- 额外奖励数量随原始奖励数增长，独立时最优算法可能失效
- 提出三种场景下的渐近最优算法，适用于块状或随机排列奖励
我们首次在奖励值存在相关性的场景下，通过资源增强框架研究抢购不等式问题。目标是确定在线算法为逼近原实例最大值所需额外奖励的数量。尽管独立奖励情形已有清晰理解，但本文拓展至奖励间存在相关性的情况。结果表明，与独立情形不同，所需额外奖励数量依赖于原始奖励数目；且在相关性存在时，独立情形下最优的块阈值算法可能需要无限多额外奖励。为此，我们针对三种情形设计了渐近最优算法：(1) 奖励按原始实例各副本分块到达；(2) 所有副本奖励任意打乱；(3) 奖励按副本分块到达，且每块内值仅两两独立而非完全相关。
原文摘要 · Abstract (English)
We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to determine the number of additional rewards an online algorithm requires to approximate the maximum value of the original instance. While the independent reward case is well understood, we extend this research to account for correlations among rewards. Our results demonstrate that, unlike in the independent case, the required number of additional rewards for approximation depends on the number of original rewards, and that block-threshold algorithms, which are optimal in the independent case, may require an infinite number of additional rewards when correlations are present. We develop asymptotically optimal algorithms for the following three scenarios: (1) where rewards arrive in blocks corresponding to the different copies of the original instance; (2) where rewards across all copies are arbitrarily shuffled; and (3) where rewards arrive in blocks corresponding to the different copies of the original instance, and values within each block are pairwise independent rather than fully correlated.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。