{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:30Z","timestamp":1750309590265,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:00:00Z","timestamp":1744156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>This article provides threshold policies with tight guarantees for online selection with convex cost (OSCC). In OSCC, a seller wants to sell some asset to a sequence of buyers with the goal of maximizing her profit. The seller can produce additional units of the asset, but at non-decreasing marginal costs. Each time, a buyer arrives and offers a price. The seller must make an immediate and irrevocable decision in terms of whether to accept the offer and produce\/sell one unit of the asset to this buyer. The goal is to develop an online algorithm that selects a subset of buyers to maximize the seller\u2019s profit, namely, the total selling revenue minus the total production cost. Our main result is the development of a class of simple threshold policies that are logistically simple and easy to implement but have provable optimality guarantees among all deterministic algorithms. We also derive a lower bound on competitive ratios of randomized algorithms and prove that the competitive ratio of our threshold policy asymptotically converges to this lower bound when the total production output is sufficiently large. Our results generalize and unify various online search, pricing, and auction problems, and provide a new perspective on the impact of non-decreasing marginal costs on real-world online resource allocation problems.<\/jats:p>","DOI":"10.1145\/3723351","type":"journal-article","created":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T11:30:01Z","timestamp":1741779001000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Threshold Policies with Tight Guarantees for Online Selection with Convex Costs"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5339-3245","authenticated-orcid":false,"given":"Xiaoqi","family":"Tan","sequence":"first","affiliation":[{"name":"University of Alberta, Edmonton, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-3750-1042","authenticated-orcid":false,"given":"Siyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"University of Alberta, Edmonton, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7936-6862","authenticated-orcid":false,"given":"Raouf","family":"Boutaba","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9888-0389","authenticated-orcid":false,"given":"Alberto","family":"Leon-Garcia","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}]}],"member":"320","published-online":{"date-parts":[[2025,4,9]]},"reference":[{"issue":"1","key":"e_1_3_3_2_2","first-page":"11","article-title":"Admission control to minimize rejections and online set cover with repetitions","volume":"6","author":"Alon Noga","year":"2010","unstructured":"Noga Alon, Yossi Azar, and Shai Gutner. 2010. Admission control to minimize rejections and online set cover with repetitions. ACM Trans. Algorithms 6, 1, Article 11 (Dec2010), 13 pages.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/110825959"},{"key":"e_1_3_3_4_2","volume-title":"Proceedings of the 34th International Conference on Neural Information Processing Systems (NIPS\u201920)","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. 2020. Secretary and online matching problems with machine learned advice. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NIPS\u201920). Curran Associates Inc., Red Hook, NY, USA, Article 665, 12 pages."},{"key":"e_1_3_3_5_2","first-page":"148","volume-title":"Proocedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916)","year":"2016","unstructured":"Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, and Debmalya Panigrahi. 2016. Online algorithms for covering and packing problems with convex objectives. In Proocedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916). 148\u2013157."},{"key":"e_1_3_3_6_2","first-page":"630","volume-title":"Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research)","volume":"139","author":"Balseiro Santiago","year":"2021","unstructured":"Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. 2021. Regularized online allocation problems: Fairness and beyond. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research), Marina Meila and Tong Zhang (Eds.), Vol. 139. PMLR, 630\u2013639."},{"key":"e_1_3_3_7_2","first-page":"20083","volume-title":"Advances in Neural Information Processing Systems","author":"Bamas Etienne","year":"2020","unstructured":"Etienne Bamas, Andreas Maggiori, and Ola Svensson. 2020. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 20083\u201320094. https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/e834cb114d33f729dbc9c7fb0c6bb607-Paper.pdf"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846250"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.68"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-31256-9"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9854-4"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.39"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC42340.2020.9303856"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/3112656.3112890"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213992"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_3_3_20_2","first-page":"811","volume-title":"The 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201911)","author":"Gerding Enrico H.","year":"2011","unstructured":"Enrico H. Gerding, Valentin Robu, Sebastian Stein, David C. Parkes, Alex Rogers, and Nicholas R. Jennings. 2011. Online mechanism design for electric vehicle charging. In The 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201911). 811\u2013818."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435.015"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.03.003"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2020.102134"},{"key":"e_1_3_3_24_2","first-page":"2733","volume-title":"Advances in Neural Information Processing Systems","author":"Im Sungjin","year":"2021","unstructured":"Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. 2021. Online knapsack with frequency predictions. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 2733\u20132743."},{"key":"e_1_3_3_25_2","first-page":"5002","volume-title":"Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research)","volume":"139","author":"Jiang Zhihao","year":"2021","unstructured":"Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang. 2021. Online selection problems against constrained adversary. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research), Marina Meila and Tong Zhang (Eds.), Vol. 139. PMLR, 5002\u20135012. https:\/\/proceedings.mlr.press\/v139\/jiang21h.html"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.872880"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_3_3_28_2","first-page":"630","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Kleinberg Robert","year":"2005","unstructured":"Robert Kleinberg. 2005. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). Society for Industrial and Applied Mathematics, Philadelphia, PA, 630\u2013631."},{"issue":"1","key":"e_1_3_3_29_2","article-title":"Competitive online optimization under inventory constraints","volume":"3","author":"Lin Qiulin","year":"2019","unstructured":"Qiulin Lin, Hanling Yi, John Pang, Minghua Chen, Adam Wierman, Michael Honig, and Yuanzhang Xiao. 2019. Competitive online optimization under inventory constraints. Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS\u201919) 3, 1 (March2019).","journal-title":"Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS\u201919)"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9217-8"},{"key":"e_1_3_3_31_2","first-page":"179","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201995)","author":"Lueker George S.","year":"1995","unstructured":"George S. Lueker. 1995. Average-case analysis of off-line and on-line knapsack problems. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201995). Society for Industrial and Applied Mathematics, Philadelphia, PA, 179\u2013188."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1957"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585758"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_3_3_36_2","first-page":"10339","volume-title":"Annual Conference on Neural Information Processing Systems 2021 (NeurIPS\u201921), December 6\u201314, 2021","author":"Sun Bo","year":"2021","unstructured":"Bo Sun, Russell Lee, Mohammad H. Hajiesmaili, Adam Wierman, and Danny H. K. Tsang. 2021. Pareto-optimal learning-augmented algorithms for online conversion problems. In Annual Conference on Neural Information Processing Systems 2021 (NeurIPS\u201921), December 6\u201314, 2021. 10339\u201310350."},{"issue":"3","key":"e_1_3_3_37_2","first-page":"51","article-title":"Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging","volume":"4","author":"Sun Bo","year":"2020","unstructured":"Bo Sun, Ali Zeynali, Tongxin Li, Mohammad Hajiesmaili, Adam Wierman, and Danny H. K. Tsang. 2020. Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS\u201921) 4, 3, Article 51 (Nov.2020), 32 pages.","journal-title":"Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS\u201921)"},{"issue":"2","key":"e_1_3_3_38_2","first-page":"24","article-title":"Mechanism design for online resource allocation: A unified approach","volume":"4","author":"Tan Xiaoqi","year":"2020","unstructured":"Xiaoqi Tan, Bo Sun, Alberto Leon-Garcia, Yuan Wu, and D. H. K. Tsang. 2020. Mechanism design for online resource allocation: A unified approach. Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS\u201920) 4, 2, Article 24 (June2020), 46 pages.","journal-title":"Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS\u201920)"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5062123"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745855"},{"issue":"1","key":"e_1_3_3_41_2","article-title":"Optimal posted prices for online cloud resource allocation","volume":"1","author":"Zhang Z.","year":"2017","unstructured":"Z. Zhang, Z. Li, and C. Wu. 2017. Optimal posted prices for online cloud resource allocation. Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS\u201917) 1, 1 (June2017).","journal-title":"Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS\u201917)"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367747"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723351","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3723351","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:56:48Z","timestamp":1750298208000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723351"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,9]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3723351"],"URL":"https:\/\/doi.org\/10.1145\/3723351","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,4,9]]},"assertion":[{"value":"2024-01-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}