mlsanityData to 7 Oct 2026

On multiagent online problems with predictions

arXiv 2507.12486 ↗First posted 15 Jul 2025cs.MA cs.AI cs.GTcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 53 references that are in the map. First posted on arXiv 15 Jul 2025.

Builds on

24 of 53 references.

References · 24

  1. 2020Performative Predictioncited by 318
  2. 2020Algorithms with Predictionscited by 152
  3. 2024Improving Online Algorithms via ML Predictionscited by 65
  4. 2019A Model for Learned Bloom Filters, and Optimizing by Sandwichingcited by 64
  5. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  6. 2019Online Computation with Untrusted Advicecited by 42
  7. 2022Multiplayer Performative Prediction: Learning in Decision-Dependent Gamescited by 42
  8. 2022Multi-agent Performative Prediction: From Global Stability and Optimality to Chaoscited by 33
  9. 2022Learning Augmented Binary Search Treescited by 31
  10. 2022Online Algorithms with Multiple Predictionscited by 22
  11. 2022Customizing ML Predictions for Online Algorithmscited by 21
  12. 2022Triangle and Four Cycle Counting with Predictions in Graph Streamscited by 20
12 more
  1. 2022Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Locationcited by 19
  2. 2022Algorithms with Prediction Portfolioscited by 19
  3. 2022Improved Price of Anarchy via Predictionscited by 9
  4. 2023Online Algorithms with Uncertainty-Quantified Predictionscited by 9
  5. 2022Mechanism Design with Predictionscited by 7
  6. 2025Algorithms with Calibrated Machine Learning Predictionscited by 7
  7. 2022Mechanism Design With Predictions for Obnoxious Facility Locationcited by 4
  8. 2017Perfect Prediction in Normal Form: Superrational Thinking Extended to Non-Symmetric Gamescited by 3
  9. 2023Online Mechanism Design with Predictionscited by 3
  10. 2024Randomized learning-augmented auctions with revenue guaranteescited by 2
  11. 2021Game-Theoretic Models of Moral and Other-Regarding Agents (extended abstract)cited by 1
  12. 2024Complexity Classes for Online Problems with and without Predictionscited by 1

Built on by

Not cited yet.