Online Assortment Optimization for Two-sided Matching Platforms

Miscellaneous Talk
Speaker Name
Daniela H. Saban
Date and Time
Talk will be virtual on Zoom
Duke-Fuqua Decision Sciences Seminar

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 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, no randomized algorithm can achieve a better competitive ratio even in asymptotic regimes. To advance beyond this impossibility, we consider settings where suppliers' preferences are described by the Multinomial Logit and Nested Logit choice models. We show that preference-aware balancing algorithms can be developed by leveraging information about suppliers' choice models. Overall, our analytical results suggest that the shape and timing of suppliers' choices play critical roles in designing online two-sided assortment algorithms. (Joint work with Ali Aouad)


Seminar poster:

Short Biography

Daniela H. Saban is an Assistant Professor of Operations, Information, and Technology at Stanford University’s Graduate School of Business. (Effective 1/1/2021: Associate Professor of Operations, Information, and Technology)

Fuqua School of Business