Competitive Algorithms for Multi-Agent Ski-Rental Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909736417361920 |
|---|---|
| author | Wang, Xuchuang Sun, Bo Beyhaghi, Hedyeh Lui, John C. S. Hajiesmaili, Mohammad Wierman, Adam |
| author_facet | Wang, Xuchuang Sun, Bo Beyhaghi, Hedyeh Lui, John C. S. Hajiesmaili, Mohammad Wierman, Adam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15727 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Competitive Algorithms for Multi-Agent Ski-Rental Problems Wang, Xuchuang Sun, Bo Beyhaghi, Hedyeh Lui, John C. S. Hajiesmaili, Mohammad Wierman, Adam Machine Learning Computer Science and Game Theory Multiagent Systems 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. |
| title | Competitive Algorithms for Multi-Agent Ski-Rental Problems |
| topic | Machine Learning Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2507.15727 |