# Competitive Algorithms for Multi-Agent Ski-Rental Problems

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

## Key facts

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

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

- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Data-driven Competitive Algorithms for Online Knapsack and Set Cover](https://mlsanity.com/paper/2012.05361/) (2020)
- [The Multi-shop Ski Rental Problem](https://mlsanity.com/paper/1404.2671/) (2014)
- [Peak-Aware Online Economic Dispatching for Microgrids](https://mlsanity.com/paper/1508.03996/) (2015)
- [Controlling Tail Risk in Online Ski-Rental](https://mlsanity.com/paper/2308.05067/) (2023)
- [Barely Random Algorithms and Collective Metrical Task Systems](https://mlsanity.com/paper/2403.11267/) (2024)
- [Equilibria in multiagent online problems with predictions](https://mlsanity.com/paper/2405.11873/) (2024)

## Abstract (arXiv)

This paper introduces a novel multi-agent ski-rental problem that generalizes the classical ski-rental dilemma to a group setting where agents incur individual and shared costs. In our model, each agent can either rent at a fixed daily cost, or purchase a pass at an individual cost, with an additional third option of a discounted group pass available to all. We consider scenarios in which agents' active days differ, leading to dynamic states as agents drop out of the decision process. To address this problem from different perspectives, we define three distinct competitive ratios: overall, state-dependent, and individual rational. For each objective, we design and analyze optimal deterministic and randomized policies. Our deterministic policies employ state-aware threshold functions that adapt to the dynamic states, while our randomized policies sample and resample thresholds from tailored state-aware distributions. The analysis reveals that symmetric policies, in which all agents use the same threshold, outperform asymmetric ones. Our results provide competitive ratio upper and lower bounds and extend classical ski-rental insights to multi-agent settings, highlighting both theoretical and practical implications for group decision-making under uncertainty.