Competitive optimal on-line leasing

Consider an on-line player who needs same equipment (e.g., a computer) for an initially unknown number of periods. At the start of each period it is d etermined whether the player will need the equipment during the current per iod and the player has two options: to pay a leasing fee c and rent the equ ipment for the period, or to buy it for a larger amount P. The total cost i ncurred by the player is the sum of all leasing fees and perhaps one purcha se. The above problem, called the leasing problem (in computer science folklore it is known as the ski-rental problem), has received considerable attentio n in the economic literature. Using the competitive ratio as a performance measure this paper is concerned with determining the optimal competitive on -line policy for the leasing problem. For the simplest version of the leasing problem (as described above) it is known and readily derived that the optimal deterministic competitive perfor mance is achieved by leasing for the first k - 1 times and then buying, whe re k = P/c. This strategy Days at most 2 - l/k times the optimal off-line c ost. When considering alternative financial transactions one must consider their net present value. Thus, accounting for the interest rate is an essential feature of any reasonable financial model. In this paper we determine both deterministic and randomized optimal on-line leasing strategies while accou nting for the interest rate factor. It is shown here, for the leasing problem, that the interest rate factor re duces the uncertainty involved. We Rnd that the optimal deterministic compe titive ratio is 1 + (1 + i)(l - l/k)(l - k(i/l + i)), a decreasing function of the interest i (for all reasonable values of i). For some applications, realistic values of interest rates result in relatively low competitive ra tios. By using randomization the on-line player can further boost up the pe rformance. In particular, against an oblivious adversary the on-line player can attain a strictly smaller competitive ratio of 2 - ((k/(k - 1))(y) - 2 )/((k/(k - l))(v) - 1) where y = In (1 - k(l - 1/(1 + i)))/ln(l/(1+ i). Her e again, this competitive ratio strictly decreases with i. We also study the leasing problem against a distributional adversary called "Nature." This adversary chooses the probability distribution of the numbe r of leasing periods and announces this distribution before the on-line pla yer chooses a strategy. Although at the outset this adversary appears to be weaker than the oblivious adversary, it is shown that the optimal competit ive ratio against Nature equals the optimal ratio against the oblivious adv ersary.