Learning-Augmented Rent-or-Buy with Multiple Predictions

We study online algorithms with multiple predictions for two classical rent-or-buy problems: the Bahncard problem and dynamic TCP acknowledgment. In the Bahncard problem, a generalization of ski rental, trips of varying costs arrive online, and the algorithm may purchase a fixed-price card that discounts travel for a fixed duration; the objective is to minimize the total cost of cards and trips. In dynamic TCP acknowledgment, requests arrive online, and the algorithm may send a fixed-cost acknowledgment for all outstanding requests at any time; the objective is to minimize the total acknowledgment cost and request latency. Both problems are well-studied in both the classical online setting and the learning-augmented setting with a single prediction. But, unlike ski rental, they have not been studied when the algorithm has to choose between more than one prediction. In this paper, we address this gap by establishing tight consistency bounds for these problems for both deterministic and randomized algorithms with two predictions. For Bahncard with any discount factor $\beta \in [0,1]$, we show that the optimal deterministic consistency is $R_{\mathrm{BC}}^{\ast }(\beta )=\beta +\frac{1-\beta }{2}\left(\sqrt{{\beta }^2+2\beta +5}+1-\beta \right),$ which interpolates between the golden ratio at $\beta =0$ and $1$ at $\beta =1$. In contrast, we show that the optimal deterministic consistency for dynamic TCP acknowledgment is $\sqrt{2}$, revealing that the two problems behave differently. We obtain similar tight bounds for randomized algorithms for both problems, and further establish consistency–robustness tradeoffs when predictions may be inaccurate. Finally, we complement our theoretical results with numerical simulations on synthetically generated instances.