{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T11:19:17Z","timestamp":1718882357281},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"NSERC Strategic Partnerships","award":["506319-7"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,6,9]]},"abstract":"This paper concerns the mechanism design for online resource allocation in a strategic setting. In this setting, a single supplier allocates capacity-limited resources to requests that arrive in a sequential and arbitrary manner. Each request is associated with an agent who may act selfishly to misreport the requirement and valuation of her request. The supplier charges payment from agents whose requests are satisfied, but incurs a load-dependent supply cost. The goal is to design an incentive compatible online mechanism, which determines not only the resource allocation of each request, but also the payment of each agent, so as to (approximately) maximize the social welfare (i.e., aggregate valuations minus supply cost). We study this problem under the framework of competitive analysis. The major contribution of this paper is the development of a unified approach that achieves the best-possible competitive ratios for setups with different supply costs. Specifically, we show that when there is no supply cost or the supply cost function is linear, our model is essentially a standard 0-1 knapsack problem, for which our approach achieves logarithmic competitive ratios that match the state-of-the-art (which is optimal). For the more challenging setup when the supply cost is strictly-convex, we provide online mechanisms, for the first time, that lead to the optimal competitive ratios as well. To the best of our knowledge, this is the first approach that unifies the characterization of optimal competitive ratios in online resource allocation for different setups including zero, linear and strictly-convex supply costs.<\/jats:p>","DOI":"10.1145\/3392142","type":"journal-article","created":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T22:10:12Z","timestamp":1591740612000},"page":"1-46","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Mechanism Design for Online Resource Allocation"],"prefix":"10.1145","volume":"4","author":[{"given":"Xiaoqi","family":"Tan","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"given":"Bo","family":"Sun","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong, China"}]},{"given":"Alberto","family":"Leon-Garcia","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"given":"Yuan","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Macau, Macau, China"}]},{"given":"Danny H.K.","family":"Tsang","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2020,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Ravi P. Agarwal and V. Lakshmikantham. 1993. Uniqueness and Nonuniqueness Criteria for Ordinary Differential Equations .World Scientific. Ravi P. Agarwal and V. Lakshmikantham. 1993. Uniqueness and Nonuniqueness Criteria for Ordinary Differential Equations .World Scientific.","DOI":"10.1142\/1988"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/110825959"},{"key":"e_1_2_1_3_1","volume-title":"Ordinary differential equations","author":"Arnold Vladimir","unstructured":"Vladimir Arnold . 1973. Ordinary differential equations . MIT Press . Vladimir Arnold. 1973. Ordinary differential equations. MIT Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_2_1_5_1","volume-title":"Online Algorithms for Covering and Packing Problems with Convex Objectives. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)","volume":"00","author":"Azar Y.","unstructured":"Y. Azar , N. Buchbinder , T. H. Chan , S. Chen , I. R. Cohen , A. Gupta , Z. Huang , N. Kang , V. Nagarajan , J. Naor , and D. Panigrahi . 2016 . Online Algorithms for Covering and Packing Problems with Convex Objectives. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , Vol. 00 . 148--157. Y. Azar, N. Buchbinder, T. H. Chan, S. Chen, I. R. Cohen, A. Gupta, Z. Huang, N. Kang, V. Nagarajan, J. Naor, and D. Panigrahi. 2016. Online Algorithms for Covering and Packing Problems with Convex Objectives. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , Vol. 00. 148--157."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386802"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846250"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.68"},{"key":"e_1_2_1_9_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","unstructured":"Allan Borodin and Ran El-Yaniv . 1998. Online Computation and Competitive Analysis . Cambridge University Press , New York, NY, USA . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis .Cambridge University Press, New York, NY, USA."},{"key":"e_1_2_1_10_1","volume-title":"Lewis","author":"Borwein Jonathan M.","year":"2006","unstructured":"Jonathan M. Borwein and Adrian S . Lewis . 2006 . Convex Analysis and and Nonlinear Optimization .Springer. Jonathan M. Borwein and Adrian S. Lewis. 2006. Convex Analysis and and Nonlinear Optimization .Springer."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9854-4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.39"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_2_1_15_1","volume-title":"Mathematical Programming","volume":"131","author":"Chen Ying-Ju","year":"2012","unstructured":"Ying-Ju Chen and Jiawei Zhang . 2012 . Design of price mechanisms for network resource allocation via price of anarchy . Mathematical Programming , Vol. 131 , 1 (01 Feb 2012), 333--364. Ying-Ju Chen and Jiawei Zhang. 2012. Design of price mechanisms for network resource allocation via price of anarchy. Mathematical Programming , Vol. 131, 1 (01 Feb 2012), 333--364."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060600"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085137"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.3.284.16077"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 10th ACM Conference on Electronic Commerce (EC '09)","author":"Nikhil","unstructured":"Nikhil R. Devanur and Thomas P. Hayes. 2009. The Adwords Problem: Online Keyword Matching with Budgeted Bidders Under Random Permutations . In Proceedings of the 10th ACM Conference on Electronic Commerce (EC '09) . ACM, New York, NY, USA, 71--78. Nikhil R. Devanur and Thomas P. Hayes. 2009. The Adwords Problem: Online Keyword Matching with Budgeted Bidders Under Random Permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC '09). ACM, New York, NY, USA, 71--78."},{"key":"e_1_2_1_20_1","article-title":"Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms","volume":"14","author":"Devanur Nikhil R.","year":"2017","unstructured":"Nikhil R. Devanur and Zhiyi Huang . 2017 . Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms . ACM Trans. Algorithms , Vol. 14 , 1, Article 5 (Dec. 2017). Nikhil R. Devanur and Zhiyi Huang. 2017. Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms. ACM Trans. Algorithms , Vol. 14, 1, Article 5 (Dec. 2017).","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing (STOC '12)","author":"Nikhil","unstructured":"Nikhil R. Devanur and Kamal Jain. 2012. Online Matching with Concave Returns . In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing (STOC '12) . ACM, New York, NY, USA, 137--144. Nikhil R. Devanur and Kamal Jain. 2012. Online Matching with Concave Returns. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing (STOC '12). ACM, New York, NY, USA, 137--144."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1086\/695529"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_24_1","volume-title":"Approximation and Online Algorithms","author":"Gupta Anupam","unstructured":"Anupam Gupta , Ravishankar Krishnaswamy , and Kirk Pruhs . 2013. Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling . In Approximation and Online Algorithms . Springer Berlin Heidelberg , Berlin, Heidelberg , 173--186. Anupam Gupta, Ravishankar Krishnaswamy, and Kirk Pruhs. 2013. Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling. In Approximation and Online Algorithms. Springer Berlin Heidelberg, Berlin, Heidelberg, 173--186."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.6"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9449-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322205.3311081"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329636"},{"key":"e_1_2_1_30_1","volume-title":"Green","author":"Mas-Colell Andreu","year":"1995","unstructured":"Andreu Mas-Colell , Michael D. Whinston , and Jerry R . Green . 1995 . Microeconomic Theory .Oxford University Press . Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. 1995. Microeconomic Theory .Oxford University Press."},{"key":"e_1_2_1_31_1","first-page":"4","article-title":"Online Matching and Ad Allocation","volume":"8","author":"Mehta Aranyak","year":"2013","unstructured":"Aranyak Mehta . 2013 . Online Matching and Ad Allocation . Found. Trends Theor. Comput. Sci. , Vol. 8 , 4 (Oct. 2013), 265--368. Aranyak Mehta. 2013. Online Matching and Ad Allocation. Found. Trends Theor. Comput. Sci. , Vol. 8, 4 (Oct. 2013), 265--368.","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_2_1_33_1","volume-title":"Pevc ari\u0107 , and A. M. Fink","author":"Mitrinovi\u0107 D. S.","year":"1991","unstructured":"D. S. Mitrinovi\u0107 , J. E. Pevc ari\u0107 , and A. M. Fink . 1991 . Inequalities Involving Functions and Their Integrals and Derivatives. Springer Netherlands . D. S. Mitrinovi\u0107 , J. E. Pevc ari\u0107 , and A. M. Fink. 1991. Inequalities Involving Functions and Their Integrals and Derivatives. Springer Netherlands."},{"key":"e_1_2_1_34_1","volume-title":"Vazirani","author":"Nisan Noam","year":"2007","unstructured":"Noam Nisan , Tim Roughgarden , \u00c9va Tardos , and Vijay V . Vazirani . 2007 . Algorithmic Game Theory .Cambridge University Press , Cambridge, UK. Noam Nisan, Tim Roughgarden, \u00c9va Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory .Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_35_1","volume-title":"Differential Equations and Dynamical Systems","author":"Perko Lawrence","unstructured":"Lawrence Perko . 2001. Differential Equations and Dynamical Systems . Springer New York , New York, NY . Lawrence Perko. 2001. Differential Equations and Dynamical Systems. Springer New York, New York, NY."},{"key":"e_1_2_1_36_1","volume-title":"Zaitsev","author":"Polyanin Andrei D.","year":"2003","unstructured":"Andrei D. Polyanin and Valentin F . Zaitsev . 2003 . Handbook of Exact Solutions for Ordinary Differential Equations. Chapman & Hall\/CRC. Andrei D. Polyanin and Valentin F. Zaitsev. 2003. Handbook of Exact Solutions for Ordinary Differential Equations. Chapman & Hall\/CRC."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1633736100"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988783"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3374888.3374893"},{"key":"e_1_2_1_40_1","first-page":"838","article-title":"Auctions versus Posted-Price Selling","volume":"83","author":"Wang Ruqu","year":"1993","unstructured":"Ruqu Wang . 1993 . Auctions versus Posted-Price Selling . The American Economic Review , Vol. 83 , 4 (1993), 838 -- 851 . Ruqu Wang. 1993. Auctions versus Posted-Price Selling . The American Economic Review , Vol. 83, 4 (1993), 838--851.","journal-title":"The American Economic Review"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133894"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367747"}],"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\/3392142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T11:14:06Z","timestamp":1672571646000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3392142"}},"subtitle":["A Unified Approach"],"short-title":[],"issued":{"date-parts":[[2020,6,9]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,9]]}},"alternative-id":["10.1145\/3392142"],"URL":"https:\/\/doi.org\/10.1145\/3392142","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,9]]},"assertion":[{"value":"2020-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}