结合随机预测的在线竞价，实现最优一致性与鲁棒性权衡。
Learning-Augmented Online Bidding in Stochastic Settings
- 引入分布预测信息，设计帕累托最优的竞价算法
- 给出随机算法在一致性和鲁棒性间的上下界
- 突破传统确定性算法局限，适用于预测有随机性的场景
在线竞价是经典优化问题，广泛应用于在线决策、可中断系统设计及近似算法分析。本文研究在学习增强设定下含随机性的在线竞价，分两部分：第一部分研究基于分布预测的竞价，找到在一致性和鲁棒性之间最优权衡的帕累托最优算法；第二部分通过给出一致性与鲁棒性权衡的上下界，揭示随机竞价算法的能力与限制。此前工作多集中于不利用预测质量随机信息的预言机及确定性算法，本研究拓展了理论边界。
原文摘要 · Abstract (English)
Online bidding is a classic optimization problem, with several applications in online decision-making, the design of interruptible systems, and the analysis of approximation algorithms. In this work, we study online bidding under learning-augmented settings that incorporate stochasticity, in either the prediction oracle or the algorithm itself. In the first part, we study bidding under distributional predictions, and find Pareto-optimal algorithms that offer the best-possible tradeoff between the consistency and the robustness of the algorithm. In the second part, we study the power and limitations of randomized bidding algorithms, by presenting upper and lower bounds on the consistency/robustness tradeoffs. Previous works focused predominantly on oracles that do not leverage stochastic information on the quality of the prediction, and deterministic algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。