CAREER: Parameterized Robustness for Reliable Online Decision-Making

Modern digital platforms increasingly rely on automated decision systems to allocate resources and opportunities in real time. Examples include matching riders with drivers in ride-hailing services, assigning tasks to workers in online labor markets, allocating advertisements on search platforms, and selecting offers in digital marketplaces. These systems must make immediate decisions under uncertainty, often without knowing future demand, arrivals, or market conditions. While decades of research have produced powerful algorithms for such problems, most theoretical analyses rely on unrealistic assumptions that rarely hold in practice, such as unlimited connectivity between participants or extreme variability in economic values. In real systems, decisions are constrained by geography, market design, and predictable patterns of user behavior. This project develops new algorithmic principles for reliable online decision-making that explicitly account for these realistic constraints. The results aim to improve the stability, transparency, and reliability of automated decision systems used in digital platforms and resource allocation systems. The project establishes a theoretical framework for parameterized robustness in online decision algorithm. The work studies how realistic structural parameters, including bounded connectivity, constrained value ranges, and predictable variance, affect algorithm performance traditionally analyzed only under worst-case assumptions. The project develops parameter-dependent analyses that characterize algorithm guarantees as functions of these parameters, introduces a smoothed competitiveness framework that evaluates algorithms under structured stochastic environments, and studies algorithms that incorporate machine learning predictions while maintaining robustness when predictions are inaccurate. In addition, variance-based analysis will quantify the stability of algorithmic outcomes beyond expected performance. Together, these directions advance the theoretical foundations of reliable decision-making algorithms for large-scale digital systems operating under uncertainty. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.