A Nonparametric Framework for Online Stochastic Matching with Correlated Arrivals

Understand

The design of online algorithms for matching markets and revenue management settings is usually bound by the assumption that the demand process is formed by a fixed-length sequence of queries with unknown types, each drawn independently.

• This notion of serial independence implies that the demand of each type, i.e., the number of queries of a given type, has low variance and is approximately Poisson-distributed.
• This paper proposes a nonparametric framework for modeling arrival sequences in online stochastic matching that departs from the serial independent assumption.
• We propose two models, Indep and Correl, that capture different forms of serial correlations by combining a nonparametric distribution for the demand with standard assumptions on the arrival patterns -- adversarial or random order.