{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T21:09:56Z","timestamp":1780088996835,"version":"3.54.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T00:00:00Z","timestamp":1780012800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["2045641,2325956, 2512128, 2533814"],"award-info":[{"award-number":["2045641,2325956, 2512128, 2533814"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2026,5,29]]},"abstract":"<jats:p>This paper studies an online resource allocation problem, where resources are reusable, allocated in combinatorial bundles, and subject to endogenous performance deterioration. Unlike existing models that assume singleton decisions or stationary or exogenous dynamics, we consider a combinatorial decision structure where decisions involve selecting among resource-bundled options, while capturing a self-induced feedback loop in which system performance, like rewards, activation probabilities, and service times, degrade as a function of cumulative resource usage. This setting naturally arises in systems such as inference serving, routing, and content recommendation. We propose a unified framework that subsumes a broad class of existing models as special cases, and develop a ranking-like online policy, termed IPRANK, which employs an indicator-perturbation mechanism to induce a randomized ranking over configurations based on their size-penalized rewards. Our analysis is based on a queue-coupling argument and shows that under adversarial arrivals, the greedy policy inevitably suffers a competitive ratio with linear dependence on reward heterogeneity, whereas IPRANK achieves a competitive ratio with only logarithmic dependence, making it far more robust in heterogeneous environments. We further study several special cases with additional structural assumptions and demonstrate that IPRANK can leverage such structures to obtain sharper competitive guarantees.<\/jats:p>","DOI":"10.1145\/3805625","type":"journal-article","created":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:34:18Z","timestamp":1780086858000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Unified Framework for Online Combinatorial Allocation of Reusable Resources under Endogenous Deterioration"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-5016-4281","authenticated-orcid":false,"given":"Qingsong","family":"Liu","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, Massachusetts, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9278-2254","authenticated-orcid":false,"given":"Mohammad","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, Massachusetts, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,5,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0368"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/msom.2023.1221"},{"key":"e_1_2_1_3_1","first-page":"117","volume-title":"18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24)","author":"Agrawal Amey","year":"2024","unstructured":"Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, Alexey Tumanov, and Ramachandran Ramjee. 2024. Taming {Throughput-Latency} tradeoff in {LLM} inference with {Sarathi-Serve}. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). 117-134."},{"key":"e_1_2_1_4_1","volume-title":"Can dynamic ride-sharing reduce traffic congestion? Transportation research part B: methodological 145","author":"Alisoltani Negin","year":"2021","unstructured":"Negin Alisoltani, Ludovic Leclercq, and Mahdi Zargayouna. 2021. Can dynamic ride-sharing reduce traffic congestion? Transportation research part B: methodological 145 (2021), 212-246."},{"key":"e_1_2_1_5_1","volume-title":"International Conference on Machine Learning. PMLR, 404-413","author":"Atsidakou Alexia","year":"2021","unstructured":"Alexia Atsidakou, Orestis Papadigenopoulos, Soumya Basu, Constantine Caramanis, and Sanjay Shakkottai. 2021. Combinatorial blocking bandits with stochastic delays. In International Conference on Machine Learning. PMLR, 404-413."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2282"},{"key":"e_1_2_1_7_1","volume-title":"Leveraging reusability: Improved competitive ratio of greedy for reusable resources. arXiv preprint arXiv:2304.03377","author":"Baek Jackie","year":"2023","unstructured":"Jackie Baek and ShixinWang. 2023. Leveraging reusability: Improved competitive ratio of greedy for reusable resources. arXiv preprint arXiv:2304.03377 (2023)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0654"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2023.2441"},{"key":"e_1_2_1_10_1","volume-title":"Dynamic pricing for reusable resources: The power of two prices. Operations Research","author":"Balseiro Santiago R","year":"2025","unstructured":"Santiago R Balseiro, Will Ma, and Wenxin Zhang. 2025. Dynamic pricing for reusable resources: The power of two prices. Operations Research (2025)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3606376.3593558"},{"key":"e_1_2_1_12_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 271-279","author":"Basu Soumya","year":"2021","unstructured":"Soumya Basu, Orestis Papadigenopoulos, Constantine Caramanis, and Sanjay Shakkottai. 2021. Contextual blocking bandits. In International Conference on Artificial Intelligence and Statistics. PMLR, 271-279."},{"key":"e_1_2_1_13_1","volume-title":"Blocking bandits. Advances in Neural Information Processing Systems 32","author":"Basu Soumya","year":"2019","unstructured":"Soumya Basu, Rajat Sen, Sujay Sanghavi, and Sanjay Shakkottai. 2019. Blocking bandits. Advances in Neural Information Processing Systems 32 (2019)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0364"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/msom.2022.0260"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538328"},{"key":"e_1_2_1_17_1","volume-title":"Online job assignment. arXiv preprint arXiv:2506.06893","author":"Ekbatani Farbod","year":"2025","unstructured":"Farbod Ekbatani, Yiding Feng, Ian Kash, and Rad Niazadeh. 2025. Online job assignment. arXiv preprint arXiv:2506.06893 (2025)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530893"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538320"},{"key":"e_1_2_1_20_1","volume-title":"Online Query-Based Data Pricing with Time-Discounting Valuations. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 3449-3461","author":"Fu Yicheng","year":"2024","unstructured":"Yicheng Fu, Xiaoye Miao, Huanhuan Peng, Chongning Na, Shuiguang Deng, and Jianwei Yin. 2024. Online Query-Based Data Pricing with Time-Discounting Valuations. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 3449-3461."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Guillermo Gallego Huseyin Topaloglu et al. 2019. Revenue management and pricing analytics. Vol. 209. Springer.","DOI":"10.1007\/978-1-4939-9606-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2014.1939"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2021.4134"},{"key":"e_1_2_1_24_1","volume-title":"Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research","author":"Goyal Vineet","year":"2025","unstructured":"Vineet Goyal, Garud Iyengar, and Rajan Udwani. 2025. Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research (2025)."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. 1562-1570","author":"Heidari Hoda","year":"2017","unstructured":"Hoda Heidari, Michael Kearns, and Aaron Roth. 2017. Tight policy regret bounds for improving and decaying bandits. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. 1562-1570."},{"key":"e_1_2_1_26_1","volume-title":"Online reusable resource allocations with multi-class arrivals. Available at SSRN 4320423","author":"Huo Tianming","year":"2022","unstructured":"Tianming Huo and Wang Chi Cheung. 2022. Online reusable resource allocations with multi-class arrivals. Available at SSRN 4320423 (2022)."},{"key":"e_1_2_1_27_1","volume-title":"Online reusable resource assortment planning with customer-dependent usage durations. Available at SSRN 4504713","author":"Huo Tianming","year":"2023","unstructured":"Tianming Huo and Wang Chi Cheung. 2023. Online reusable resource assortment planning with customer-dependent usage durations. Available at SSRN 4504713 (2023)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/smj.3347"},{"key":"e_1_2_1_29_1","volume-title":"International journal of industrial mathematics 15, 1","author":"Karimi MB","year":"2023","unstructured":"MB Karimi. 2023. A Systematic Review of the Combinatorial Methods of Service Composition in the Cloud Computing Environment. International journal of industrial mathematics 15, 1 (2023)."},{"key":"e_1_2_1_30_1","volume-title":"Rotting bandits. Advances in neural information processing systems 30","author":"Levine Nir","year":"2017","unstructured":"Nir Levine, Koby Crammer, and Shie Mannor. 2017. Rotting bandits. Advances in neural information processing systems 30 (2017)."},{"key":"e_1_2_1_31_1","first-page":"1241","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Li Shaohong","year":"2020","unstructured":"Shaohong Li, Xi Wang, Xiao Zhang, Vasileios Kontorinis, Sreekumar Kodakara, David Lo, and Parthasarathy Ranganathan. 2020. Thunderbolt:{Throughput-Optimized},{Quality-of-Service-Aware} power capping at scale. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 1241-1255."},{"key":"e_1_2_1_32_1","first-page":"80","volume-title":"On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching. In 31st Annual European Symposium on Algorithms (ESA","author":"Liang Jingxun","year":"2023","unstructured":"Jingxun Liang, Zhihao Gavin Tang, Yixuan Even Xu, Yuhao Zhang, and Renfei Zhou. 2023. On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching. In 31st Annual European Symposium on Algorithms (ESA 2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 80-1."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3727121"},{"key":"e_1_2_1_34_1","volume-title":"International Conference on Machine Learning. PMLR, 22559-22593","author":"Liu Xutong","year":"2023","unstructured":"Xutong Liu, Jinhang Zuo, Siwei Wang, John CS Lui, Mohammad Hajiesmaili, Adam Wierman, and Wei Chen. 2023. Contextual combinatorial bandits with probabilistically triggered arms. In International Conference on Machine Learning. PMLR, 22559-22593."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1957"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1931"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745848"},{"key":"e_1_2_1_39_1","volume-title":"Online Rounding Schemes for ??-Rental Problems. arXiv preprint arXiv:2507.19649","author":"Nekouyan Hossein","year":"2025","unstructured":"Hossein Nekouyan, Bo Sun, Raouf Boutaba, and Xiaoqi Tan. 2025. Online Rounding Schemes for ??-Rental Problems. arXiv preprint arXiv:2507.19649 (2025)."},{"key":"e_1_2_1_40_1","first-page":"23334","article-title":"Recurrent submodular welfare and matroid blocking semi-bandits","volume":"34","author":"Papadigenopoulos Orestis","year":"2021","unstructured":"Orestis Papadigenopoulos and Constantine Caramanis. 2021. Recurrent submodular welfare and matroid blocking semi-bandits. Advances in Neural Information Processing Systems 34 (2021), 23334-23346.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/inte.2020.1047"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16713"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2019.3346"},{"key":"e_1_2_1_44_1","volume-title":"Revenue management with heterogeneous resources: Unit resource capacities, advance bookings, and itineraries over time intervals. Operations research 71, 6","author":"Rusmevichientong Paat","year":"2023","unstructured":"Paat Rusmevichientong, Mika Sumida, Huseyin Topaloglu, and Yicheng Bai. 2023. Revenue management with heterogeneous resources: Unit resource capacities, advance bookings, and itineraries over time intervals. Operations research 71, 6 (2023), 2196-2216."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3539618.3592044"},{"key":"e_1_2_1_46_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2564-2572","author":"Seznec Julien","year":"2020","unstructured":"Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. 2020. Rotting bandits are no harder than stochastic ones. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2564-2572."},{"key":"e_1_2_1_47_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2564-2572","author":"Seznec Julien","year":"2021","unstructured":"Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. 2021. Rotting bandits are no harder than stochastic ones. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2564-2572."},{"key":"e_1_2_1_48_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 3784-3794","author":"Seznec Julien","year":"2020","unstructured":"Julien Seznec, Pierre Menard, Alessandro Lazaric, and Michal Valko. 2020. A single algorithm for both restless and rested rotting bandits. In International Conference on Artificial Intelligence and Statistics. PMLR, 3784-3794."},{"key":"e_1_2_1_49_1","volume-title":"On greedy-like policies in online matching with reusable network resources and decaying rewards. Management Science","author":"Simchi-Levi David","year":"2025","unstructured":"David Simchi-Levi, Zeyu Zheng, and Feng Zhu. 2025. On greedy-like policies in online matching with reusable network resources and decaying rewards. Management Science (2025)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3676641.3716025"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627703.3629578"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570618"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3736252.3742628"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0597"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613149"},{"key":"e_1_2_1_56_1","volume-title":"Blind and Near-Optimal Dynamic Assortment Optimization with Reusable Resources. Available at SSRN 5340627","author":"Wu Zerui","year":"2025","unstructured":"Zerui Wu, Ran Liu, and Xu Sun. 2025. Blind and Near-Optimal Dynamic Assortment Optimization with Reusable Resources. Available at SSRN 5340627 (2025)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1287\/msom.2023.1188"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3805625","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3805625","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:37:53Z","timestamp":1780087073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3805625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,29]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,29]]}},"alternative-id":["10.1145\/3805625"],"URL":"https:\/\/doi.org\/10.1145\/3805625","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,29]]},"assertion":[{"value":"2026-05-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}