CoChat

Competitive Analysis for Multi-Commodity Ski-Rental Problem

Open access
Wu, Binghan, Bao, Wei, Yuan, Dong, Zhou, Bing · 2022 · Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence

The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index; none of the 4 sources its claims cite is checked for support yet.

Abstract

We investigate an extended version of the classical ski-rental problem with multiple commodities. A customer uses a set of commodities altogether, and he/she needs to choose payment options to cover the usage of each commodity without the knowledge of the future. The payment options of each commodity include (1) renting: to pay for an on-demand usage and (2) buying: to pay for the lifetime usage. It is a novel extension of the classical ski-rental problem which deals with only one commodity. To address this problem, we propose a new online algorithm called the Multi-Object Break-Even (MOBE) algorithm and conduct competitive analysis. We show that the tight lower and upper bounds of MOBE algorithm's competitive ratio are e/e-1 and 2 respectively against adaptive adversary under arbitrary renting and buying prices. We further prove that MOBE algorithm is an optimal online algorithm if commodities have the same rent-to-buy ratio. Numerical results verify our theoretical conclusion and demonstrate the advantages of MOBE in a real-world scenario.

Overview

CoChat Summary

TL;DR

The paper extends the classical ski-rental problem to multiple commodities used together and proposes the Multi-Object Break-Even (MOBE) algorithm. It proves competitive-ratio bounds of \(e/(e-1)\) and 2, optimality under equal rent-to-buy ratios, and demonstrates improved average cost in a trace-driven cloud-service experiment.

Key findings

  • MOBE’s competitive ratio is bounded between \(e/(e-1)\) and 2 against an adaptive adversary under arbitrary renting and buying prices; \(e/(e-1) \approx 1.582\) is the tight lower bound and 2 is the upper bound. For homogeneous commodities with \(|S|=10,20,50,100\), numerical competitive ratios are 1.631, 1.606, 1.592, and 1.587, respectively, approaching \(e/(e-1)\).
  • When all commodities share the same rent-to-buy ratio (\(S \in S_r\)), \(e/(e-1)\) is the optimal competitive-ratio lower bound for any deterministic online algorithm, and Algorithm 2 returns optimal thresholds, making MOBE optimal.
  • The threshold computation in Algorithm 2 runs in \(O(|S|^2)\).
  • In the trace-driven cloud service acquisition experiment, MOBE’s accumulated cost is smaller than all online benchmarks in all three groups; MOBE may reserve more service components than the classical ski-rental and offline optimal algorithms, balancing under-reservation and over-reservation.

Methods

  • Online competitive analysis: a commodity set \(S\) is used altogether each time; each commodity can be rented at cost \(d_i\) per use or bought at cost \(c_i\). The offline optimal algorithm knows the total number of uses \(x\), and the competitive ratio is the maximum ratio of online cost to offline optimal cost over all inputs, under an adaptive adversary.
  • MOBE uses thresholds \(\Theta\); it buys commodity \(s_i\) when its typical rental cost \(\sigma_i\) reaches \(\theta_i\), otherwise rents. The Threshold Solver separates commodities by descending rent-to-buy ratio, sorts each subset by ascending buying cost, and calls the Sub Threshold Solver, which binary-searches \(\theta_1\) and computes \(\theta_2,\dots,\theta_N\) via formula (9), stopping when \(\theta_N\) is close to \(c_N\).
  • Evaluation includes numerical verification for homogeneous and same/nonuniform rent-to-buy ratio commodities, plus a trace-driven experiment using forest-fire counts from India 2008–2011 and AWS Fargate/SageMaker pricing, with three groups, 100 repeats, and comparisons against OP, MB, SR, AP, and AR.

Limitations

  • The paper states that early reservation brings risks of over-reservation.
  • Evident from the text: the optimality proof applies only when commodities have the same rent-to-buy ratio; for arbitrary ratios, MOBE is bounded but not proven optimal.
  • Evident from the text: the trace-driven evaluation uses one real-world dataset/application and AWS pricing, so broader empirical validation is not provided.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.24963/ijcai.2022/648

Cites

18 of 18 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 1 Not valid · 4 Not checked · 35 Own results and interpretations

20 more claims

Create a free account to see all 40 claims and every source verdict.

See all claims — free account
  • Probably not a substantial claim. 5
  • The quote only partly states this claim. 1
  • It may state two separate claims as one. 10

Create a free account to see these claims.

Citations

Cites

Show all 18 references

Cited by

See all 5

Metadata

Authors
Wu, B., Bao, W., Yuan, D., & Zhou, B.
Affiliations
The University of Sydney (AU)
Venue
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Published
2022-07
Pages
4672-4678
OpenAlex
W4285605875
Cited by
5
References
12
Citations by year
2026: 1 · 2024: 4
FWCI
1.03
Type
conference paper
Language
en
Open access
Locations
International Joint Conference on Artificial Intelligence (publishedVersion)
Topics
  • Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems
  • Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
Keywords
ski rental problem, online algorithms, competitive ratio, adaptive adversaries, optimal online algorithms, lower bounds, online decision making

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Competitive Analysis for Multi-Commodity Ski-Rental Problem. https://app.cochat.ai/papers/10.24963/ijcai.2022/648
The paper
Wu, B., Bao, W., Yuan, D., & Zhou, B. (2022). Competitive Analysis for Multi-Commodity Ski-Rental Problem. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. https://doi.org/10.24963/ijcai.2022/648

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.