Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms

Modern service platforms often provide customers with real-time congestion information, such as anticipated waiting times, before they decide whether to use a service. This creates an intertemporal tradeoff in service recommendation: directing a customer to a service may generate immediate value, but the resulting congestion can make that service less attractive to future customers. We study this tradeoff through a finite-horizon stochastic optimization problem in which a platform dynamically recommends among multiple services, each represented by a queue, with customers' joining probabilities decreasing with congestion. We first formulate the problem as a Markov decision process and show that optimal decisions generally depend on the joint congestion state, giving rise to a prohibitively large state space. We develop two complementary approximation algorithms that overcome this curse of dimensionality. First, we provide a quasi-polynomial-time approximation scheme that uses truncation and rounding of the model primitives to compress the joint congestion state, while carefully accounting for how these approximations affect the stochastic evolution of the system to establish near-optimality. Second, we develop a polynomial-time LP-guided algorithm that replaces the joint-state representation with service-level marginal information and achieves a (1-1/e) approximation guarantee under substantially more general service and joining dynamics. Finally, we show that monotone joining behavior, whereby customers become less likely to join as a service becomes more congested, marks a fundamental tractability boundary: without monotonicity, the problem is NP-hard to approximate within any constant factor. This establishes monotonicity as a key behavioral property that enables tractable dynamic service recommendation despite the complexity introduced by congestion-dependent joining.