Online Matching Frameworks Under Stochastic Rewards, Product Ranking, and Unknown Patience

Brian Brubach (), Nathaniel Grammel (), Will Ma () and Aravind Srinivasan ()
Additional contact information
Brian Brubach: Computer Science Department, Wellesley College, Wellesley, Massachusetts 02481
Nathaniel Grammel: Department of Computer Science, University of Maryland, College Park, Maryland 20742
Will Ma: Graduate School of Business and Data Science Institute, Columbia University, New York, New York 10027
Aravind Srinivasan: Department of Computer Science, University of Maryland, College Park, Maryland 20742

Operations Research, 2025, vol. 73, issue 2, 995-1010

Abstract: We study generalizations of online bipartite matching in which each arriving vertex (customer) views a ranked list of offline vertices (products) and matches to (purchases) the first one they deem acceptable. The number of products that the customer has patience to view can be stochastic and dependent on the products seen. We develop a framework that views the interaction with each customer as an abstract resource consumption process and derive new results for these online matching problems under the adversarial, nonstationary, and independent and identically-distributed arrival models, assuming we can (approximately) solve the product ranking problem for each single customer. To that end, we show new results for product ranking under two cascade-click models: an optimal algorithm when each item has its own hazard rate for making the customer depart and a 1/2-approximate algorithm when the customer has a general item-independent patience distribution. We also present a constant-factor 0.027-approximate algorithm in a new model where items are not initially available and arrive over time. We complement these positive results by presenting three additional negative results relating to these problems.

Keywords: Optimization; online algorithms; competitive ratio; online matching; product ranking (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0371 (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:73:y:2025:i:2:p:995-1010

Access Statistics for this article

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