IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2210.04774.html
   My bibliography  Save this paper

Online Resource Allocation with Samples

Author

Listed:
  • Negin Gorlezaei
  • Patrick Jaillet
  • Zijie Zhou

Abstract

We study an online resource allocation problem under uncertainty about demand and about the reward of each type of demand (agents) for the resource. Even though dealing with demand uncertainty in resource allocation problems has been the topic of many papers in the literature, the challenge of not knowing rewards has been barely explored. The lack of knowledge about agents' rewards is inspired by the problem of allocating units of a new resource (e.g., newly developed vaccines or drugs) with unknown effectiveness/value. For such settings, we assume that we can \emph{test} the market before the allocation period starts. During the test period, we sample each agent in the market with probability $p$. We study how to optimally exploit the \emph{sample information} in our online resource allocation problem under adversarial arrival processes. We present an asymptotically optimal algorithm that achieves $1-\Theta(1/(p\sqrt{m}))$ competitive ratio, where $m$ is the number of available units of the resource. By characterizing an upper bound on the competitive ratio of any randomized and deterministic algorithm, we show that our competitive ratio of $1-\Theta(1/(p\sqrt{m}))$ is tight for any $p =\omega(1/\sqrt{m})$. That asymptotic optimality is possible with sample information highlights the significant advantage of running a test period for new resources. We demonstrate the efficacy of our proposed algorithm using a dataset that contains the number of COVID-19 related hospitalized patients across different age groups.

Suggested Citation

  • Negin Gorlezaei & Patrick Jaillet & Zijie Zhou, 2022. "Online Resource Allocation with Samples," Papers 2210.04774, arXiv.org.
  • Handle: RePEc:arx:papers:2210.04774
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2210.04774
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Omar Besbes & Assaf Zeevi, 2012. "Blind Network Revenue Management," Operations Research, INFORMS, vol. 60(6), pages 1537-1550, December.
    2. Yingjie Lan & Huina Gao & Michael O. Ball & Itir Karaesmen, 2008. "Revenue Management with Limited Demand Information," Management Science, INFORMS, vol. 54(9), pages 1594-1609, September.
    3. Negin Golrezaei & Hamid Nazerzadeh & Paat Rusmevichientong, 2014. "Real-Time Optimization of Personalized Assortments," Management Science, INFORMS, vol. 60(6), pages 1532-1551, June.
    4. Stefanus Jasin, 2015. "Performance of an LP-Based Control for Revenue Management with Unknown Demand Parameters," Operations Research, INFORMS, vol. 63(4), pages 909-915, August.
    5. Georgia Perakis & Guillaume Roels, 2010. "Robust Controls for Network Revenue Management," Manufacturing & Service Operations Management, INFORMS, vol. 12(1), pages 56-76, November.
    6. Berend, Daniel & Kontorovich, Aryeh, 2013. "A sharp estimate of the binomial mean absolute deviation with applications," Statistics & Probability Letters, Elsevier, vol. 83(4), pages 1254-1259.
    7. Shipra Agrawal & Zizhuo Wang & Yinyu Ye, 2014. "A Dynamic Near-Optimal Algorithm for Online Linear Programming," Operations Research, INFORMS, vol. 62(4), pages 876-890, August.
    8. Michael O. Ball & Maurice Queyranne, 2009. "Toward Robust Revenue Management: Competitive Analysis of Online Booking," Operations Research, INFORMS, vol. 57(4), pages 950-963, August.
    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. Dawsen Hwang & Patrick Jaillet & Vahideh Manshadi, 2021. "Online Resource Allocation Under Partially Predictable Demand," Operations Research, INFORMS, vol. 69(3), pages 895-915, May.
    2. Wang, Charles X. & Webster, Scott & Zhang, Sidong, 2014. "Robust price-setting newsvendor model with interval market size and consumer willingness-to-pay," International Journal of Production Economics, Elsevier, vol. 154(C), pages 100-112.
    3. Gönsch, Jochen, 2017. "A survey on risk-averse and robust revenue management," European Journal of Operational Research, Elsevier, vol. 263(2), pages 337-348.
    4. Ming Chen & Zhi-Long Chen, 2018. "Robust Dynamic Pricing with Two Substitutable Products," Manufacturing & Service Operations Management, INFORMS, vol. 20(2), pages 249-268, May.
    5. Philipp Bartke & Natalia Kliewer & Catherine Cleophas, 2018. "Benchmarking filter-based demand estimates for airline revenue management," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(1), pages 57-88, March.
    6. Dirk Sierag & Rob Mei, 2016. "Single-leg choice-based revenue management: a robust optimisation approach," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 15(6), pages 454-467, December.
    7. Moshe Haviv & Ramandeep S. Randhawa, 2014. "Pricing in Queues Without Demand Information," Manufacturing & Service Operations Management, INFORMS, vol. 16(3), pages 401-411, July.
    8. An, Jaehyung & Mikhaylov, Alexey & Jung, Sang-Uk, 2021. "A Linear Programming approach for robust network revenue management in the airline industry," Journal of Air Transport Management, Elsevier, vol. 91(C).
    9. Catherine Cleophas & Daniel Kadatz & Sebastian Vock, 2017. "Resilient revenue management: a literature survey of recent theoretical advances," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 16(5), pages 483-498, October.
    10. Will Ma & David Simchi-Levi & Chung-Piaw Teo, 2021. "On Policies for Single-Leg Revenue Management with Limited Demand Information," Operations Research, INFORMS, vol. 69(1), pages 207-226, January.
    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. Ş. İlker Birbil & J. B. G. Frenk & Joaquim A. S. Gromicho & Shuzhong Zhang, 2014. "A Network Airline Revenue Management Framework Based on Decomposition by Origins and Destinations," Transportation Science, INFORMS, vol. 48(3), pages 313-333, August.
    13. Ayvaz-Cavdaroglu, Nur & Kachani, Soulaymane & Maglaras, Costis, 2016. "Revenue management with minimax regret negotiations," Omega, Elsevier, vol. 63(C), pages 12-22.
    14. 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.
    15. Wang, Jiamin & Xiao, Baichun, 2017. "A minmax regret price control model for managing perishable products with uncertain parameters," European Journal of Operational Research, Elsevier, vol. 258(2), pages 652-663.
    16. Huina Gao & Michael O. Ball & Itir Z. Karaesmen, 2016. "Distribution-free methods for multi-period, single-leg booking control," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 15(6), pages 425-453, December.
    17. Adam J. Mersereau & Dan Zhang, 2012. "Markdown Pricing with Unknown Fraction of Strategic Customers," Manufacturing & Service Operations Management, INFORMS, vol. 14(3), pages 355-370, July.
    18. David Simchi-Levi & Rui Sun & Huanan Zhang, 2022. "Online Learning and Optimization for Revenue Management Problems with Add-on Discounts," Management Science, INFORMS, vol. 68(10), pages 7402-7421, October.
    19. Markus Ettl & Pavithra Harsha & Anna Papush & Georgia Perakis, 2020. "A Data-Driven Approach to Personalized Bundle Pricing and Recommendation," Manufacturing & Service Operations Management, INFORMS, vol. 22(3), pages 461-480, May.
    20. Yuhang Ma & Paat Rusmevichientong & Mika Sumida & Huseyin Topaloglu, 2020. "An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals," Operations Research, INFORMS, vol. 68(3), pages 834-855, May.

    More about this item

    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:arx:papers:2210.04774. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.