多智能体在线问题中，用预测提升算法性能，兼顾准确与鲁棒性。
On multiagent online problems with predictions
- 引入双预测器框架：自预测+他预测，分别预判自身与他人行为。
- 在滑雪租赁问题中，完美他预测下自预测算法最优，但易受误判影响。
- 提出更鲁棒的算法并实证其性能，适合需协作的多智能体场景。
我们研究多智能体环境下具有预测能力的（竞争性）算法的性能。引入双预测器框架，假设智能体使用一个预测器预测自身未来行为，另一个预测器预测其他参与者的行为。核心问题是：在不同预测质量假设下，能实现的最佳竞争比是多少？以多智能体滑雪租赁问题为例进行分析：智能体可合作集资获取长期许可证；若未达标，则需按日支付单位价格租赁。当其他智能体预测完美时，遵循自身预测的算法达到最优，但对自身行为预测错误不鲁棒；我们提出一种更具鲁棒性的算法并进行基准测试。
原文摘要 · Abstract (English)
We study the power of (competitive) algorithms with predictions in a multiagent setting. We introduce a two predictor framework, that assumes that agents use one predictor for their future (self) behavior, and one for the behavior of the other players. The main problem we are concerned with is understanding what are the best competitive ratios that can be achieved by employing such predictors, under various assumptions on predictor quality. As an illustration of our framework, we introduce and analyze a multiagent version of the ski-rental problem. In this problem agents can collaborate by pooling resources to get a group license for some asset. If the license price is not met then agents have to rent the asset individually for the day at a unit price. Otherwise the license becomes available forever to everyone at no extra cost. In the particular case of perfect other predictions the algorithm that follows the self predictor is optimal but not robust to mispredictions of agent's future behavior; we give an algorithm with better robustness properties and benchmark it.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。