Scholarlink

<p>We introduce and investigate the group rent-or-buy problem, a generalization of the classical ski rental problem. In contrast to the classical version, where a single consumer decides when to switch from renting to buying based on an uncertain usage period, the group must jointly decide how to minimize their total rent and buy cost over the period. While grouping does not reduce the optimal total cost in the offline setting, we explore its impact on making best possible online decisions. We design both optimal randomized and deterministic algorithms for the group version and show that grouping does not improve the optimal randomized algorithm, with its competitive ratio remaining <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_590_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(\frac{e}{e-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>e</mi> <mrow> <mi>e</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </math></EquationSource> </InlineEquation>. However, grouping benefits the deterministic case, where the optimal competitive ratio is strictly smaller than 2, which is the best competitive ratio achievable in the classical problem. Additionally, as the group size increases, the optimal competitive ratio of the deterministic algorithm decreases, approaching <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_590_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(\frac{e}{e-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>e</mi> <mrow> <mi>e</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </math></EquationSource> </InlineEquation> in the limit.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Group Rent-or-Buy: the Benefits of Having Grouped Consumers

  • 期刊论文

  • 发表日期：

    2025年5月21日

查看全文
  • Li-Yuan Meng,
  • Chang-Jun Wang,
  • Qing-Jie Ye

摘要

We introduce and investigate the group rent-or-buy problem, a generalization of the classical ski rental problem. In contrast to the classical version, where a single consumer decides when to switch from renting to buying based on an uncertain usage period, the group must jointly decide how to minimize their total rent and buy cost over the period. While grouping does not reduce the optimal total cost in the offline setting, we explore its impact on making best possible online decisions. We design both optimal randomized and deterministic algorithms for the group version and show that grouping does not improve the optimal randomized algorithm, with its competitive ratio remaining \(\frac{e}{e-1}\) e e - 1 . However, grouping benefits the deterministic case, where the optimal competitive ratio is strictly smaller than 2, which is the best competitive ratio achievable in the classical problem. Additionally, as the group size increases, the optimal competitive ratio of the deterministic algorithm decreases, approaching \(\frac{e}{e-1}\) e e - 1 in the limit.