# On multiagent online problems with predictions

arXiv: https://arxiv.org/abs/2507.12486 · HTML: https://mlsanity.com/paper/2507.12486/

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Multiplayer Performative Prediction: Learning in Decision-Dependent Games](https://mlsanity.com/paper/2201.03398/) (2022)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location](https://mlsanity.com/paper/2204.01120/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Improved Price of Anarchy via Predictions](https://mlsanity.com/paper/2205.04252/) (2022)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [Mechanism Design with Predictions](https://mlsanity.com/paper/2205.11313/) (2022)
- [Algorithms with Calibrated Machine Learning Predictions](https://mlsanity.com/paper/2502.02861/) (2025)
- [Mechanism Design With Predictions for Obnoxious Facility Location](https://mlsanity.com/paper/2212.09521/) (2022)
- [Perfect Prediction in Normal Form: Superrational Thinking Extended to Non-Symmetric Games](https://mlsanity.com/paper/1712.05723/) (2017)
- [Online Mechanism Design with Predictions](https://mlsanity.com/paper/2310.02879/) (2023)
- [Randomized learning-augmented auctions with revenue guarantees](https://mlsanity.com/paper/2401.13384/) (2024)
- [Game-Theoretic Models of Moral and Other-Regarding Agents (extended abstract)](https://mlsanity.com/paper/2106.11503/) (2021)
- [Complexity Classes for Online Problems with and without Predictions](https://mlsanity.com/paper/2406.18265/) (2024)

## 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.