Online assortment optimization for two-sided matching platforms.

We show that, when suppliers do not immediately accept/reject match requests, our problem is fundamentally different from standard (one-sided) assortment problems, where customers choose over a set of commodities. We establish that a greedy algorithm, that offers to each arriving customer the assortment that maximizes the expected increase in matches, is 1/2 competitive when compared against the clairvoyant algorithm that knows in advance the full sequence of customers’ arrivals.  In contrast with related online assortment problems, we show that there is no randomized algorithm that can achieve a better competitive ratio, even in asymptotic regimes. Next, we introduce a class of algorithms, termed {\em preference-aware balancing algorithms}, that achieve significantly better competitive ratios when suppliers’ preferences follow the Multinomial Logit and the Nested Logit choice models. Using prior knowledge about the “shape’’ of suppliers’ preferences, these algorithms are calibrated to “balance” optimally the match requests received by suppliers. Overall, our results suggest that the timing of suppliers’ decisions and the structure of suppliers’ preferences play a fundamental role in designing online two-sided assortment algorithms. (joint work with Ali Aouad)

Posted on Sep 7, 2020 in ACGO, Seminars