Competitive optimal on-line leasing (Q1818280)

This paper regards the leasing or leasing-or-buy problem. In computer science this is known as the ski-rental problem. Using the competitive ratio as a performance measure this paper is concerned with determining the optimal competitive on-line policy. It regards both the deterministic and randomized optimal on-line leasing strategies while accounting for the interest rate factor. It is shown, that the interest rate factor reduces the uncertainty involved. The optimal competitive ratio is a decreasing function of the interest. For some applications, realistic values of interest rates result in relatively low competitive rates. By using randomization the on-line player can boost up the performance. The leasing problem against a distributional adversary called ``Nature'' is also studied. It is shown that the optimal competitive ratio against the Nature equals the optimal ratio against the oblivious adversary.