Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
Abstract
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.
Related
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Arithmetic purity of strong approximation for toric varieties with constant global sections
- Beyond Constant Truncations: The Bounded Sobolev Approximation Gap
- From Trees to Binary Trees: Approximation Algorithms and a PTAS
- Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information
BibTeX
@misc{akchen2026dynamic,
title = {{Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms}},
author = {Yi-Chun Akchen and Sena Asli Bozkurt and Chen-An Lin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30812},
eprint = {2609.30812},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30812},
}
RIS
TY - UNPB
TI - Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
AU - Yi-Chun Akchen
AU - Sena Asli Bozkurt
AU - Chen-An Lin
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.30812
UR - https://arxiv.org/abs/2609.30812
AB - 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.
ER -