Technical Note—Assortment Planning for Two-Sided Sequential Matching Markets

Itai Ashlagi (), Anilesh K. Krishnaswamy (), Rahul Makhijani (), Daniela Saban () and Kirankumar Shiragur ()
Additional contact information
Itai Ashlagi: Stanford University, Stanford, California 94305
Anilesh K. Krishnaswamy: Duke University, Durham, North Carolina 27708
Rahul Makhijani: Facebook, Menlo Park, California 94025
Daniela Saban: Stanford Graduate School of Business, Stanford, California 94305
Kirankumar Shiragur: Stanford University, Stanford, California 94305

Operations Research, 2022, vol. 70, issue 5, 2784-2803

Abstract: Two-sided matching platforms provide users with menus of match recommendations. To maximize the number of realized matches between the two sides (referred to herein as customers and suppliers), the platform must balance the inherent tension between recommending more suppliers to customers to increase the chances that they like one of them and avoiding the conflicts that arise when customers, who are given more options, end up choosing the same suppliers. We introduce a stylized model to study the above tradeoff. The platform offers each customer a menu of suppliers, and customers choose, simultaneously and independently, to either select a supplier from their menu or remain unmatched. Suppliers then see the set of customers that have selected them and choose to either match with one of these customers or remain unmatched. A match occurs if a customer and a supplier choose each other (in sequence). Agents’ choices are probabilistic and proportional to the public scores of agents in their menu and a score that is associated with the outside option of remaining unmatched. The platform’s problem is to construct menus for customers, so as to maximize the total number of matches. We first show that this problem is strongly NP-hard. Then, we provide an intuitive efficient algorithm that achieves a constant-factor approximation to the optimal expected number of matches. Our algorithm uses bucketing (grouping similar suppliers into buckets) together with linear-programming-based relaxations and rounding techniques.

Keywords: Revenue Management and Market Analytics; networks/graphs; matchings; analysis of algorithms; utility/preference; applications (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2327 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:5:p:2784-2803

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().