2005/01/01 by Hiroshi Fujiwara, Fujiwara, Hiroshi, Kazuo Iwama +1
Computer Science · Economics, Econometrics and Finance · #Economic theories and models #Game Theory and Voting Systems #Optimization and Search Problems #competitive analysis #online algorithm
paper · pdf · doi:10.4230/dagsemproc.05031.8
openalex publication_date 2005/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let s be the ratio of the cost for purchasing skis over the cost for renting them. Then the famous result for the ski-rental problem shows that skiers should buy their skis after renting them (s-1) times, which gives us an optimal competitive ratio of 2-(1)/(s). In practice, however, it appears that many skiers buy their skis before this optimal point of time and also many skiers keep renting them forever. In this paper we show that these behaviors of skiers are quite reasonable by using an \em average-case competitive ratio. For an exponential input distribution f(t) = λ e-λ t, optimal strategies are (i) if (1)/(λ) ≤ s, then skiers should rent their skis forever and (ii) otherwise should purchase them after renting approximately s2λ (