多人滑雪租赁问题中,如何在自用与团购间权衡决策。
Competitive Algorithms for Multi-Agent Ski-Rental Problems
- 设计动态阈值策略,根据成员变化实时调整租购选择。
- 对称策略(全员同阈值)比异步策略性能更优。
- 适用于团队出行、资源分配等不确定环境下的集体决策。
本文提出一种新型多智能体滑雪租赁问题,将经典单人租赁难题推广至群体场景,其中每个智能体面临个人租金、个人购买或团体优惠票三种选择。由于各智能体活跃天数不同,系统状态随时间动态变化。针对该问题,定义了整体、状态依赖和个体合理性三类竞争比,并为每类目标设计最优确定性与随机策略。确定性策略采用感知状态的阈值函数,随机策略则从定制的分布中采样重采样阈值。分析表明,所有智能体使用相同阈值的对称策略优于非对称策略。研究给出了竞争比上下界,将经典滑雪租赁理论扩展至多智能体场景,对不确定性下的群体决策具有理论与实践意义。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。