{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T14:10:02Z","timestamp":1780495802389,"version":"3.54.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["CNS-2325956, CAREER-2045641, CPS-2136199, CNS-2102963, and CNS-2106299"],"award-info":[{"award-number":["CNS-2325956, CAREER-2045641, CPS-2136199, CNS-2102963, and CNS-2106299"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,5,27]]},"abstract":"<jats:p>\n            Motivated by the emerging paradigm of resource allocation that integrates classical objectives, such as cost minimization, with societal objectives, such as carbon awareness, this paper proposes a general framework for the online fair allocation of reusable resources. Within this framework, an online decision-maker seeks to allocate a finite resource with capacity\n            <jats:italic toggle=\"yes\">C<\/jats:italic>\n            to a sequence of requests arriving with unknown distributions of types, utilities, and resource usage durations. To accommodate diverse objectives, the framework supports multiple actions and utility types, and the goal is to achieve max-min fairness among utilities, i.e., maximize the minimum time-averaged utility across all utility types. Our performance metric is an (\u03b1,\u03b2)-competitive guarantee of the form: ALG \u2265 \u03b1 \u2022 OPT\n            <jats:sup>*<\/jats:sup>\n            - O(T\n            <jats:sup>\u03b2-1<\/jats:sup>\n            ),; \u03b1, \u03b2 \u2208 (0, 1], where OPT\n            <jats:sup>*<\/jats:sup>\n            and ALG are the time-averaged optimum and objective value achieved by the decision maker, respectively. We propose a novel algorithm that achieves a competitive guarantee of (1-O(\u221a(log C\/C)), 2\/3) under the bandit feedback. As resource capacity increases, the multiplicative competitive ratio term 1-O(\u221a logC\/C) asymptotically approaches optimality. Notably, when the resource capacity exceeds a certain threshold, our algorithm achieves an improved competitive guarantee of (1, 2\/3). Our algorithm employs an optimistic penalty-weight mechanism coupled with a dual exploration-discarding strategy to balance resource feasibility, exploration, and fairness among utilities.\n          <\/jats:p>","DOI":"10.1145\/3727121","type":"journal-article","created":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T09:43:35Z","timestamp":1749030215000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Fair Allocation of Reusable Resources"],"prefix":"10.1145","volume":"9","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, MA, 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, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,3]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1405","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms","author":"Agrawal Shipra","year":"2014","unstructured":"Shipra Agrawal and Nikhil R Devanur. Fast algorithms for online stochastic convex programming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1405--1424. SIAM, 2014."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2008.4738709"},{"key":"e_1_2_1_3_1","first-page":"32","article-title":"Linear stochastic bandits under safety constraints","author":"Amani Sanae","year":"2019","unstructured":"Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639043"},{"key":"e_1_2_1_5_1","volume-title":"Operations Research","author":"Baek Jackie","year":"2022","unstructured":"Jackie Baek and Will Ma. Bifurcating constraints to improve approximation ratios for network revenue management with reusable resources. Operations Research, 2022."},{"key":"e_1_2_1_6_1","first-page":"613","volume-title":"International Conference on Machine Learning","author":"Balseiro Santiago","year":"2020","unstructured":"Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In International Conference on Machine Learning, pages 613--628. PMLR, 2020."},{"key":"e_1_2_1_7_1","first-page":"630","volume-title":"International Conference on Machine Learning","author":"Balseiro Santiago","year":"2021","unstructured":"Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Regularized online allocation problems: Fairness and beyond. In International Conference on Machine Learning, pages 630--639. PMLR, 2021."},{"key":"e_1_2_1_8_1","volume-title":"Uniformly bounded regret in dynamic fair allocation. arXiv preprint arXiv:2205.12447","author":"Balseiro Santiago R","year":"2022","unstructured":"Santiago R Balseiro and Shangzhou Xia. Uniformly bounded regret in dynamic fair allocation. arXiv preprint arXiv:2205.12447, 2022."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2054"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745869"},{"key":"e_1_2_1_12_1","first-page":"13750","article-title":"Group-fair online allocation in continuous time","volume":"33","author":"Cayci Semih","year":"2020","unstructured":"Semih Cayci, Swati Gupta, and Atilla Eryilmaz. Group-fair online allocation in continuous time. Advances in Neural Information Processing Systems, 33:13750--13761, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1111\/poms.12672"},{"key":"e_1_2_1_14_1","volume-title":"Cost-effective online multi-llm selection with versatile reward models. arXiv preprint arXiv:2405.16587","author":"Dai Xiangxiang","year":"2024","unstructured":"Xiangxiang Dai, Jin Li, Xutong Liu, Anqi Yu, and John Lui. Cost-effective online multi-llm selection with versatile reward models. arXiv preprint arXiv:2405.16587, 2024."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993581"},{"key":"e_1_2_1_16_1","volume-title":"Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66(1):1--41","author":"Devanur Nikhil R","year":"2019","unstructured":"Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66(1):1--41, 2019."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530893"},{"key":"e_1_2_1_18_1","volume-title":"Online assortment of reusable resources with exogenous replenishment. Available at SSRN 3795056","author":"Feng Yiding","year":"2021","unstructured":"Yiding Feng, Rad Niazadeh, and Amin Saberi. Online assortment of reusable resources with exogenous replenishment. Available at SSRN 3795056, 2021."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538320"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2021.4134"},{"key":"e_1_2_1_21_1","volume-title":"Asymptotically optimal competitive ratio for online allocation of reusable resources. arXiv preprint arXiv:2002.02430","author":"Goyal Vineet","year":"2020","unstructured":"Vineet Goyal, Garud Iyengar, and Rajan Udwani. Asymptotically optimal competitive ratio for online allocation of reusable resources. arXiv preprint arXiv:2002.02430, 2020."},{"key":"e_1_2_1_22_1","volume-title":"Online allocation of reusable resources via algorithms guided by fluid approximations. arXiv preprint arXiv:2010.03983","author":"Goyal Vineet","year":"2020","unstructured":"Vineet Goyal, Garud Iyengar, and Rajan Udwani. Online allocation of reusable resources via algorithms guided by fluid approximations. arXiv preprint arXiv:2010.03983, 2020."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626570.3626590"},{"key":"e_1_2_1_24_1","volume-title":"The unpaid toll: Quantifying the public health impact of ai. arXiv preprint arXiv:2412.06288","author":"Han Yuelin","year":"2024","unstructured":"Yuelin Han, Zhifeng Wu, Pengfei Li, Adam Wierman, and Shaolei Ren. The unpaid toll: Quantifying the public health impact of ai. arXiv preprint arXiv:2412.06288, 2024."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604930.3605709"},{"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. 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. Online reusable resource assortment planning with customer-dependent usage durations. Available at SSRN 4504713, 2023."},{"key":"e_1_2_1_28_1","first-page":"4830","article-title":"Online learning and pricing for network revenue management with reusable resources","volume":"35","author":"Jia Huiwen","year":"2022","unstructured":"Huiwen Jia, Cong Shi, and Siqian Shen. Online learning and pricing for network revenue management with reusable resources. Advances in Neural Information Processing Systems, 35:4830--4842, 2022.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2381"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15714-1_30"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1906"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2954310"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632775.3661938"},{"key":"e_1_2_1_35_1","first-page":"37159","article-title":"Nonstationary dual averaging and online fair allocation","volume":"35","author":"Liao Luofeng","year":"2022","unstructured":"Luofeng Liao, Yuan Gao, and Christian Kroer. Nonstationary dual averaging and online fair allocation. Advances in Neural Information Processing Systems, 35:37159--37172, 2022.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656007"},{"key":"e_1_2_1_37_1","first-page":"24075","article-title":"An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints","volume":"34","author":"Liu Xin","year":"2021","unstructured":"Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints. Advances in Neural Information Processing Systems, 34:24075--24086, 2021.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_38_1","volume-title":"A modern introduction to online learning. arXiv preprint arXiv:1912.13213","author":"Orabona Francesco","year":"2019","unstructured":"Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019."},{"issue":"174","key":"e_1_2_1_39_1","first-page":"1","article-title":"Achieving fairness in the stochastic multi-armed bandit problem","volume":"22","author":"Patil Vishakha","year":"2021","unstructured":"Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Yadati Narahari. Achieving fairness in the stochastic multi-armed bandit problem. Journal of Machine Learning Research, 22(174):1--31, 2021.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1142\/12135"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2019.3346"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570606"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547353.3526951"},{"key":"e_1_2_1_44_1","volume-title":"The 40th Conference on Uncertainty in Artificial Intelligence","author":"Sinha Abhishek","year":"2024","unstructured":"Abhishek Sinha. Banditq: Fair bandits with guaranteed rewards. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024."},{"key":"e_1_2_1_45_1","first-page":"48083","article-title":"gorithms for fair resource allocation","volume":"36","author":"Sinha Abhishek","year":"2023","unstructured":"Abhishek Sinha, Ativ Joshi, Rajarshi Bhattacharjee, Cameron Musco, andMohammad Hajiesmaili. No-regret algorithms for fair resource allocation. Advances in Neural Information Processing Systems, 36:48083--48109, 2023.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3224431"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i14.29489"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6847983"},{"key":"e_1_2_1_49_1","volume-title":"Reinforcement learning algorithm for reusable resource allocation with time-varying reward. Available at SSRN 4680309","author":"Wang Ziwei","year":"2023","unstructured":"Ziwei Wang, Jingtong Zhao, Yixuan Liu, and Jie Song. Reinforcement learning algorithm for reusable resource allocation with time-varying reward. Available at SSRN 4680309, 2023."},{"key":"e_1_2_1_50_1","volume-title":"Online resource allocation for reusable resources. arXiv preprint arXiv:2212.02855","author":"Zhang Xilin","year":"2022","unstructured":"Xilin Zhang and Wang Chi Cheung. Online resource allocation for reusable resources. arXiv preprint arXiv:2212.02855, 2022."},{"key":"e_1_2_1_51_1","volume-title":"The Thirty-eighth Annual Conference on Neural Information Processing Systems.","author":"Zhang Xuechen","unstructured":"Xuechen Zhang, Zijian Huang, Ege Onur Taga, Carlee Joe-Wong, Samet Oymak, and Jiasi Chen. Efficient contextual llm cascades through budget-constrained policy learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_2_1_52_1","volume-title":"SSRN","author":"Zhong Yueyang","year":"2022","unstructured":"Yueyang Zhong, John R Birge, and Amy Ward. Learning the scheduling policy in time-varying multiclass many server queues with abandonment, volume 6. SSRN, 2022."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727121","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:30:52Z","timestamp":1755898252000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,27]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,27]]}},"alternative-id":["10.1145\/3727121"],"URL":"https:\/\/doi.org\/10.1145\/3727121","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,27]]},"assertion":[{"value":"2025-06-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}