Ali Aouad – Mathematics and Decision

$\begin{quote} \begin{center} \textbf{A nonparametric framework for online stochastic matching with correlated arrivals} \end{center} \medskip Matching decisions are important operational controls for online marketplaces, with applications including order fulfillment, ride-hailing, and service platforms. Existing stochastic models often rely on an assumption of ``serial independence" which implies that demand is approximately Poisson-distributed and low-variance. By relaxing this assumption, we develop a nonparametric framework for online matching that can represent high-variance and correlated arrivals, which are prevalent in real-world demand predictions. Specifically, we propose models that combine a nonparametric distribution for the demand with standard assumptions on the arrival patterns -adversarial or random-order. We demonstrate that fluid relaxations, which rely solely on expected demand information, have arbitrarily bad performance guarantees. Instead, we propose tighter linear programming relaxations that leverage distribution knowledge and use a novel rounding scheme to obtain matching algorithms that achieve optimal (worst-case) performance guarantees. This is joint work with Will Ma (Columbia GSB), and ongoing work with Weizhong Zhang (Tepper, CMU) \end{quote}$