Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios
Copyright: © 2020 INFORMS Motivated by the dynamic assortment offerings and item pricings occurring in e-commerce, we study a general problem of allocating finite inventories to heterogeneous customers arriving sequentially. We analyze this problem under the framework of competitive analysis, where...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148643 |
| _version_ | 1826189724273868800 |
|---|---|
| author | Ma, Will Simchi-Levi, David |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Ma, Will Simchi-Levi, David |
| author_sort | Ma, Will |
| collection | MIT |
| description | Copyright: © 2020 INFORMS Motivated by the dynamic assortment offerings and item pricings occurring in e-commerce, we study a general problem of allocating finite inventories to heterogeneous customers arriving sequentially. We analyze this problem under the framework of competitive analysis, where the sequence of customers is unknown and does not necessarily follow any pattern. Previous work in this area, studying online matching, advertising, and assortment problems, has focused on the case where each item can only be sold at a single price, resulting in algorithms which achieve the best-possible competitive ratio of 1−1/e. In this paper, we extend all of these results to allow for items having multiple feasible prices. Our algorithms achieve the best-possible weight-dependent competitive ratios, which depend on the sets of feasible prices given in advance. Our algorithms are also simple and intuitive; they are based on constructing a class of universal value functions that integrate the selection of items and prices offered. Finally, we test our algorithms on the publicly available hotel data set of Bodea et al. [Bodea T, Ferguson M, Garrow L (2009) Data set-Choice-based revenue management: Data from a major hotel chain. Manufacturing Service Oper. Management 11(2):356-361.], where there are multiple items (hotel rooms), each with multiple prices (fares at which the room could be sold). We find that applying our algorithms, as a hybrid with algorithms that attempt to forecast and learn the future transactions, results in the best performance. |
| first_indexed | 2024-09-23T08:20:02Z |
| format | Article |
| id | mit-1721.1/148643 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:20:02Z |
| publishDate | 2023 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1486432023-03-22T03:52:42Z Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios Ma, Will Simchi-Levi, David Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Institute for Data, Systems, and Society Copyright: © 2020 INFORMS Motivated by the dynamic assortment offerings and item pricings occurring in e-commerce, we study a general problem of allocating finite inventories to heterogeneous customers arriving sequentially. We analyze this problem under the framework of competitive analysis, where the sequence of customers is unknown and does not necessarily follow any pattern. Previous work in this area, studying online matching, advertising, and assortment problems, has focused on the case where each item can only be sold at a single price, resulting in algorithms which achieve the best-possible competitive ratio of 1−1/e. In this paper, we extend all of these results to allow for items having multiple feasible prices. Our algorithms achieve the best-possible weight-dependent competitive ratios, which depend on the sets of feasible prices given in advance. Our algorithms are also simple and intuitive; they are based on constructing a class of universal value functions that integrate the selection of items and prices offered. Finally, we test our algorithms on the publicly available hotel data set of Bodea et al. [Bodea T, Ferguson M, Garrow L (2009) Data set-Choice-based revenue management: Data from a major hotel chain. Manufacturing Service Oper. Management 11(2):356-361.], where there are multiple items (hotel rooms), each with multiple prices (fares at which the room could be sold). We find that applying our algorithms, as a hybrid with algorithms that attempt to forecast and learn the future transactions, results in the best performance. 2023-03-21T14:59:34Z 2023-03-21T14:59:34Z 2020 2023-03-21T14:55:17Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/148643 Ma, Will and Simchi-Levi, David. 2020. "Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios." Operations Research, 68 (6). en 10.1287/OPRE.2019.1957 Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Ma, Will Simchi-Levi, David Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios |
| title | Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios |
| title_full | Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios |
| title_fullStr | Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios |
| title_full_unstemmed | Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios |
| title_short | Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios |
| title_sort | algorithms for online matching assortment and pricing with tight weight dependent competitive ratios |
| url | https://hdl.handle.net/1721.1/148643 |
| work_keys_str_mv | AT mawill algorithmsforonlinematchingassortmentandpricingwithtightweightdependentcompetitiveratios AT simchilevidavid algorithmsforonlinematchingassortmentandpricingwithtightweightdependentcompetitiveratios |