Randomized Strategies for the 3-Slope Ski Rental Problem

The ski rental problem is arguably one of the fundamental problems in online computation. The dilemma of choosing between short term solution (renting) and long term solution (buying) is be relevant to many real life problems.

The multislope ski rental is an extended version of this problem, where several intermediate options are available. During the time of the game, the player can choose to move between different options, in order to minimize the total cost. While deterministic and randomized strategies for the classical ski rental problem are known, finding an optimal strategy to the multislope ski rental problem is much more challenging.

In this work we extend the previously known notion of profile which was used to described a randomized strategy for the additive multislope ski rental problem. 

Our extended definition of a profile is used to describe a randomized strategy for general multislope ski rental. 
We study the case of the non-additive 3-slope ski rental with entry fees and give a characterization of the optimal randomized strategy for this problem.
We also prove some properties of an optimal randomized strategy and explain how those properties can be used to obtain an algorithm that produces an optimal profile for any instance of the problem.

*M.Sc research supervised by Prof. Dror Rawitz