IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v73y2025i2p995-1010.html

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Brian Brubach & Nathaniel Grammel & Will Ma & Aravind Srinivasan, 2025. "Online Matching Frameworks Under Stochastic Rewards, Product Ranking, and Unknown Patience," Operations Research, INFORMS, vol. 73(2), pages 995-1010, March.
    • Handle: RePEc:inm:oropre:v:73:y:2025:i:2:p:995-1010
    DOI: 10.1287/opre.2021.0371
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2021.0371
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2021.0371?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Vineet Goyal & Rajan Udwani, 2023. "Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation," Operations Research, INFORMS, vol. 71(2), pages 563-580, March.
    2. Negin Golrezaei & Hamid Nazerzadeh & Paat Rusmevichientong, 2014. "Real-Time Optimization of Personalized Assortments," Management Science, INFORMS, vol. 60(6), pages 1532-1551, June.
    3. Will Ma, 2018. "Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 789-812, August.
    4. Mahsa Derakhshan & Negin Golrezaei & Vahideh Manshadi & Vahab Mirrokni, 2022. "Product Ranking on Online Platforms," Management Science, INFORMS, vol. 68(6), pages 4024-4041, June.
    5. Will Ma & David Simchi-Levi, 2020. "Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios," Operations Research, INFORMS, vol. 68(6), pages 1787-1803, November.
    6. Wang Chi Cheung & Will Ma & David Simchi-Levi & Xinshang Wang, 2022. "Inventory Balancing with Online Learning," Management Science, INFORMS, vol. 68(3), pages 1776-1807, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. David Simchi-Levi & Rui Sun & Xinshang Wang, 2025. "Technical Note—Online Matching with Bayesian Rewards," Operations Research, INFORMS, vol. 73(1), pages 278-289, January.
    2. Arlen Dean & Mohammad Zhalechian & Mark P. Van Oyen, 2025. "Dynamic Care Unit Placements Under Unknown Demand with Learning," Manufacturing & Service Operations Management, INFORMS, vol. 27(5), pages 1396-1414, September.
    3. Vahideh Manshadi & Scott Rodilitz & Daniela Saban & Akshaya Suresh, 2025. "Online Algorithms for Matching Platforms with Multichannel Traffic," Management Science, INFORMS, vol. 71(9), pages 7674-7691, September.
    4. Vahideh Manshadi & Scott Rodilitz, 2022. "Online Policies for Efficient Volunteer Crowdsourcing," Management Science, INFORMS, vol. 68(9), pages 6572-6590, September.
    5. Yanzhe (Murray) Lei & Stefanus Jasin & Joline Uichanco & Andrew Vakhutinsky, 2022. "Joint Product Framing (Display, Ranking, Pricing) and Order Fulfillment Under the Multinomial Logit Model for E-Commerce Retailers," Manufacturing & Service Operations Management, INFORMS, vol. 24(3), pages 1529-1546, May.
    6. Yiding Feng & Rad Niazadeh & Amin Saberi, 2024. "Two-Stage Stochastic Matching and Pricing with Applications to Ride Hailing," Operations Research, INFORMS, vol. 72(4), pages 1574-1594, July.
    7. Jacob Feldman & Danny Segev, 2022. "Technical Note—The Multinomial Logit Model with Sequential Offerings: Algorithmic Frameworks for Product Recommendation Displays," Operations Research, INFORMS, vol. 70(4), pages 2162-2184, July.
    8. Rajan Udwani, 2025. "Adwords with Unknown Budgets and Beyond," Management Science, INFORMS, vol. 71(2), pages 1009-1026, February.
    9. David Simchi-Levi & Zeyu Zheng & Feng Zhu, 2025. "On Greedy-Like Policies in Online Matching with Reusable Network Resources and Decaying Rewards," Management Science, INFORMS, vol. 71(10), pages 8908-8926, October.
    10. Zihao Li & Hao Wang & Zhenzhen Yan, 2026. "Fully Online Matching with General Stochastic Arrivals and Departures," Operations Research, INFORMS, vol. 74(2), pages 752-769, March.
    11. Wang Chi Cheung & Will Ma & David Simchi-Levi & Xinshang Wang, 2022. "Inventory Balancing with Online Learning," Management Science, INFORMS, vol. 68(3), pages 1776-1807, March.
    12. Xiao-Yue Gong & Vineet Goyal & Garud N. Iyengar & David Simchi-Levi & Rajan Udwani & Shuangyu Wang, 2022. "Online Assortment Optimization with Reusable Resources," Management Science, INFORMS, vol. 68(7), pages 4772-4785, July.
    13. Jacob Feldman & Danny Segev, 2025. "Dynamic Pricing with Menu Costs: Approximation Schemes and Applications to Grocery Retail," Manufacturing & Service Operations Management, INFORMS, vol. 27(4), pages 1087-1106, July.
    14. Mohammad Zhalechian & Esmaeil Keyvanshokooh & Cong Shi & Mark P. Van Oyen, 2022. "Online Resource Allocation with Personalized Learning," Operations Research, INFORMS, vol. 70(4), pages 2138-2161, July.
    15. Jingwei Zhang & Will Ma & Huseyin Topaloglu, 2025. "Technical Note—Leveraging the Degree of Dynamic Substitution in Assortment and Inventory Planning," Operations Research, INFORMS, vol. 73(3), pages 1248-1259, May.
    16. Santiago R. Balseiro & Omar Besbes & Dana Pizarro, 2024. "Survey of Dynamic Resource-Constrained Reward Collection Problems: Unified Model and Analysis," Operations Research, INFORMS, vol. 72(5), pages 2168-2189, September.
    17. Yilun Chen & Yash Kanoria & Akshit Kumar & Wenxin Zhang, 2026. "Feature-Based Dynamic Matching," Operations Research, INFORMS, vol. 74(2), pages 788-803, March.
    18. Ali Aouad & Daniela Saban, 2023. "Online Assortment Optimization for Two-Sided Matching Platforms," Management Science, INFORMS, vol. 69(4), pages 2069-2087, April.
    19. Yiding Feng & Rad Niazadeh, 2025. "Batching and Optimal Multistage Bipartite Allocations," Management Science, INFORMS, vol. 71(5), pages 4108-4130, May.
    20. Vineet Goyal & Rajan Udwani, 2023. "Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation," Operations Research, INFORMS, vol. 71(2), pages 563-580, March.

    More about this item

    Keywords

    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:73:y:2025:i:2:p:995-1010. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.