‘Tis the season when ski enthusiasts look to the skies and pray for snow. But if you only hit the slopes a few times a year, is it more economical to buy or simply rent skis, boots, and poles?
That’s a question not only for powder hounds but also for computer scientists, who have been grappling for years with this “rent or buy” dilemma. In their case, it has nothing to do with winter sports and everything to do with decision-making in computer systems. For example, in “snoopy caching,” an operating system needs to decide whether to continually store a requested page in its cache (“renting”) or to invalidate the page to save the update cost, paying a larger price on its next request (“buying”).
“This is a classic and foundational problem in online algorithms,” said Michael Dinitz, an associate professor in the Department of Computer Science at Johns Hopkins Whiting School of Engineering and an instructor in its Engineering for Professionals’ computer science program. “It forms the basis of almost all of the more advanced online algorithms that have been developed over the past 30 years.”
Recently, a team that included Dinitz took a fresh look at this classic problem, shedding new light on something he said, “We thought we knew everything about.”
The team’s paper, “Controlling Tail Risk in Online Ski-Rental,” appears on arXiv and will be presented early next month at the ACM-SIAM Symposium on Discrete Algorithms.
In the past, computer scientists tackled the ski rental problem using two types of algorithms: deterministic and randomized. Deterministic algorithms are step-by-step procedures that produce the same results every time. For instance, a deterministic algorithm might conclude that you should rent skis for the first four days and then buy them on day five if you are still skiing. Randomized algorithms include some element of unpredictability and are analyzed based on their expected behavior. For example, the randomized algorithm might recommend flipping a coin daily to decide whether to buy or rent.
For more than 30 years, computer scientists have understood that the best randomized algorithm performs better on average than the best deterministic one. But here’s a twist: Just because you use the classic randomized approach doesn’t guarantee that you won’t end up with an extremely unfavorable outcome. (Imagine that the coin flip tells you to buy equipment the first day and you break your leg in the bathroom before heading to the slopes.) For example, researchers found that the best randomized method is actually worse than the best deterministic one around 37% of the time—despite being better on average, according to Dinitz.
This observation led the researchers to a question: How could they reduce the chances of such extremely unfavorable outcomes?
“In other words, what if we put limits—called “tail bounds”— on how poorly the algorithm could perform? For instance, we could require that the randomized algorithm be worse than the best deterministic algorithm at most 5% of the time, rather than 37%,” Dinitz said.
The team discovered that once they added such limits, they needed to create some new and surprisingly complex algorithms to solve the classic ski rental problem. These new algorithms optimize the expected performance given these limits and can even handle arbitrary combinations of limits.
The most surprising thing about these algorithms, though, is their structure, according to Dinitz.
“These new algorithms have properties that are dramatically different from either the deterministic or classical randomized algorithms,” he said. “Given how classical and foundational the ski rental problem is, we thought everything was already known about it, or at least that everything remaining was just a slight variation on what was known. But now we realize that’s not true, that there are still surprises to be discovered.”
But can the team’s new approach settle the real-life issue of renting versus buying skis once and for all?
“I’m a theorist, so I’m the wrong person to ask!” he said.