“Online Assortment
Optimization for Two-sided Matching Platforms”
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 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)
Daniela Saban is an associate professor of Operations, Information, and Technology
at Stanford University’s Graduate School of Business. Her research explores
issues related to the design and operations of online marketplaces, including
online matching markets and procurement platforms. Prior to joining Stanford,
Daniela spent a semester as a visiting scholar in the Simons Institute for the
Theory of Computing at UC Berkeley. She received her PhD in Decision, Risk, and
Operations from Columbia Business School and holds a B.Sc. and an M.Sc. in
Computer Science from Universidad de Buenos Aires.