Online Assortment Optimization for Two-Sided Matching Platforms
Abstract:
Motivated by online labor markets, we consider the online assortment optimization problem faced by a two-sided matching platform that hosts a set of suppliers waiting to match with a customer. Arriving customers are shown an assortment of suppliers, and may choose to issue a match request to one of them. Before leaving the platform, each supplier reviews all the match requests he has received, and based on his preferences, he chooses whether to match with a customer or to leave unmatched. We study how platforms should design online assortment algorithms to maximize the expected number of matches in such two-sided settings.
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)
