Online assortment optimization for two-sided matching platforms

Motivated by online labor markets, we consider the online assortment optimization problem faced by a twosided 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 algorithms to maximize the expected number of matches in such twosided settings. We show that, when suppliers do not immediately accept/reject match requests, our problem is fundamentally different from standard (onesided) 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, no randomized algorithm can achieve a better competitive ratio, even in asymptotic regimes. To advance beyond this general impossibility, we consider structured settings where suppliers' preferences are described by the Multinomial Logit and Nested Logit choice models. We develop specialized balancing algorithms, called preferenceaware, that leverage general information about the suppliers' choice models. In certain settings, the resulting competitive ratios are provably larger than the standard "barrier" of 11/e in the adversarial arrival model. Overall, our analytical results suggest that the shape and timing of suppliers' choices play critical roles in designing online twosided assortment algorithms