Non-Additive Two-Option Ski Rental

We consider a generalization of the classical problem of ski rental. There is a game that ends at an unknown time, and the algorithm needs to decide how to pay for the time until the game ends. There are two "payment plans" or "options," such that the cost of t time units under option i (for i = 1,2) is given by a i t + b i , where b i is a one-time cost to start using option i, and a i is the ongoing cost per time unit. We assume w.l.o.g. that a 1 > a 2 and b 1 < b 2. (The classical version is b 1 = 0 and a 2 = 0, so that option 1 is "pure rent" and option 2 is "pure buy.") We give deterministic and randomized algorithms for the general setting and prove matching lower bounds on the competitive ratios for the problem. This is the first non-trivial result for the non-additive model of ski rental, which models non-refundable one-time costs.