{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T18:14:11Z","timestamp":1651169651904},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["CCF-1750436"]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC Advanced Grant 788893 AMDROMA"],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["MIUR PRIN projectALGADIMAR"],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2022,4]]},"abstract":"Abstract<\/jats:title>Efficient and truthful mechanisms to price resources on servers\/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers revenue maximization in the online stochastic setting with non-preemptive jobs and a unit capacity server. One agent\/job arrives at every time step, with parameters drawn from the underlying distribution. We design a posted-price mechanism which can be efficiently computed and is revenue-optimal in expectation and in retrospect, up to additive error. The prices are posted prior to learning the agent\u2019s type, and the computed pricing scheme is deterministic, depending only on the length of the allotted time interval and on the earliest time the server is available. We also prove that the proposed pricing strategy is robust to imprecise knowledge of the job distribution and that a distribution learned from polynomially many samples is sufficient to obtain a near-optimal truthful pricing strategy.<\/jats:p>","DOI":"10.1007\/s10458-022-09544-y","type":"journal-article","created":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T07:02:46Z","timestamp":1642834966000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online revenue maximization for server pricing"],"prefix":"10.1007","volume":"36","author":[{"given":"Shant","family":"Boodaghians","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0001-6250-945X","authenticated-orcid":false,"given":"Federico","family":"Fusco","sequence":"additional","affiliation":[]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[]},{"given":"Ruta","family":"Mehta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,22]]},"reference":[{"key":"9544_CR1","doi-asserted-by":"crossref","unstructured":"Azar, Y., Kalp-Shaltiel, I., Lucier, B., Menache, I., Naor, J., & Yaniv, J. (2015). Truthful online scheduling with commitments. In EC (pp. 715\u2013732). ACM.","DOI":"10.1145\/2764468.2764535"},{"key":"9544_CR2","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Mansour, Y., Nisan, N., Noti, G., Curino, C., Ganapathy, N., Menache, I., Reingold, O., Tennenholtz, M., & Timnat, E. (2017). ERA: A framework for economic resource allocation for the cloud. In WWW (companion volume) (pp. 635\u2013642). ACM.","DOI":"10.1145\/3041021.3054186"},{"key":"9544_CR3","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Kleinberg, R., & Slivkins, A. (2018). Bandits with knapsacks. Journal of ACM,65(3), 13:1\u201313:55.","DOI":"10.1145\/3164539"},{"issue":"2","key":"9544_CR4","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s00199-004-0514-4","volume":"26","author":"M Bagnoli","year":"2005","unstructured":"Bagnoli, M., & Bergstrom, T. (2005). Log-concave probability and its applications. Economic Theory, 26(2), 445\u2013469.","journal-title":"Economic Theory"},{"key":"9544_CR5","doi-asserted-by":"crossref","unstructured":"Blumrosen, L., & Holenstein, T. (2008). Posted prices vs. negotiations: An asymptotic analysis. In EC (p.\u00a049). ACM.","DOI":"10.1145\/1386790.1386801"},{"key":"9544_CR6","doi-asserted-by":"crossref","unstructured":"Carroll, T. E., & Grosu, D. (2008). An incentive-compatible mechanism for scheduling non-malleable parallel jobs with individual deadlines. In ICPP (pp. 107\u2013114). IEEE Computer Society.","DOI":"10.1109\/ICPP.2008.27"},{"key":"9544_CR7","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., Cesari, T. R., Colomboni, R., Fusco, F., & Leonardi, S. (2021). A regret analysis of bilateral trade. In EC (pp. 289\u2013309). ACM.","DOI":"10.1145\/3465456.3467645"},{"key":"9544_CR8","doi-asserted-by":"crossref","unstructured":"Chawla, S., Devanur, N. R., Holroyd, A. E., Karlin, A. R., Martin, J. B., & Sivan, B. (2017). Stability of service under time-of-use pricing. In STOC (pp. 184\u2013197). ACM.","DOI":"10.1145\/3055399.3055455"},{"key":"9544_CR9","doi-asserted-by":"crossref","unstructured":"Chawla, S., Hartline, J. D., Malec, D. L., & Sivan, B. (2010). Multi-parameter mechanism design and sequential posted pricing. In STOC (pp. 311\u2013320). ACM","DOI":"10.1145\/1807406.1807428"},{"key":"9544_CR10","doi-asserted-by":"crossref","unstructured":"Cole, R., & Roughgarden, T. (2014). The sample complexity of revenue maximization. In STOC (pp. 243\u2013252). ACM.","DOI":"10.1145\/2591796.2591867"},{"key":"9544_CR11","doi-asserted-by":"crossref","unstructured":"Dierks, L., & Seuken, S. (2019). Cloud pricing: The spot market strikes back. In EC (p. 593). ACM.","DOI":"10.2139\/ssrn.3383420"},{"key":"9544_CR12","doi-asserted-by":"crossref","unstructured":"Dierks, L., & Seuken, S. (2020). The competitive effects of variance-based pricing. In IJCAI (pp. 362\u2013370). ijcai.org.","DOI":"10.24963\/ijcai.2020\/51"},{"key":"9544_CR13","doi-asserted-by":"crossref","unstructured":"den Boer, A. V. (2015). Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in O.R. and management science,20(1), 1\u201318.","DOI":"10.1016\/j.sorms.2015.03.001"},{"key":"9544_CR14","doi-asserted-by":"crossref","unstructured":"D\u00fctting, P., Fusco, F., Lazos, P., Leonardi, S., & Reiffenh\u00e4user, R. (2021). Efficient two-sided markets with limited information. In STOC (pp. 1452\u20131465). ACM.","DOI":"10.1145\/3406325.3451076"},{"key":"9544_CR15","doi-asserted-by":"crossref","unstructured":"D\u00fctting, P., & Kleinberg, R. (2015). Polymatroid prophet inequalities. In: ESA, Lecture notes in computer science (Vol. 9294, pp. 437\u2013449). Springer.","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"9544_CR16","doi-asserted-by":"crossref","unstructured":"Feldman, M., Gravin, N., & Lucier, B. (2015). Combinatorial auctions via posted prices. In SODA (pp. 123\u2013135). SIAM.","DOI":"10.1137\/1.9781611973730.10"},{"key":"9544_CR17","doi-asserted-by":"crossref","unstructured":"Gaitonde, J., & Tardos, \u00c9. (2020). Stability and learning in strategic queuing systems. In EC (pp. 319\u2013347). ACM.","DOI":"10.1145\/3391403.3399491"},{"key":"9544_CR18","doi-asserted-by":"crossref","unstructured":"Gonczarowski, Y. A., & Weinberg, S. M. (2021). The sample complexity of up-to-$\\epsilon $ multi-dimensional revenue maximization. Journal of ACM,68(1), 15:1\u201315:28.","DOI":"10.1145\/3439722"},{"key":"9544_CR19","unstructured":"Guo, C., Huang, Z., Tang, Z. G., & Zhang, X. (2021). Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora\u2019s problem. In COLT, proceedings of machine learning research (Vol. 134, pp. 2248\u20132288). PMLR."},{"issue":"3","key":"9544_CR20","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/s00224-013-9449-0","volume":"54","author":"N Jain","year":"2014","unstructured":"Jain, N., Menache, I., Naor, J., & Yaniv, J. (2014). A truthful mechanism for value-based scheduling in cloud computing. Theory of Computing Systems, 54(3), 388\u2013406.","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"9544_CR21","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1109\/MIC.2016.4","volume":"20","author":"IA Kash","year":"2016","unstructured":"Kash, I. A., & Key, P. B. (2016). Pricing the cloud. IEEE Internet Computing, 20(1), 36\u201343.","journal-title":"IEEE Internet Computing"},{"key":"9544_CR22","doi-asserted-by":"crossref","unstructured":"Kash, I. A., Key, P. B., & Suksompong, W. (2019). Simple pricing schemes for the cloud. ACM Transactions on Economics and Computation7(2), 7:1\u20137:27.","DOI":"10.1145\/3327973"},{"key":"9544_CR23","doi-asserted-by":"crossref","unstructured":"Kash, I. A., Key, P. B., & Zoumpoulis, S. I. (2018). Optimal pricing and introduction timing of new virtual machines. In EC (pp. 51\u201352). ACM.","DOI":"10.2139\/ssrn.3137038"},{"key":"9544_CR24","doi-asserted-by":"crossref","unstructured":"Kilcioglu, C., & Rao, J. M. (2016). Competition on price and quality in cloud computing. In WWW (pp. 1123\u20131132). ACM.","DOI":"10.1145\/2872427.2883043"},{"key":"9544_CR25","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., & Weinberg, S.M. (2012) Matroid prophet inequalities. In STOC (pp. 123\u2013136). ACM.","DOI":"10.1145\/2213977.2213991"},{"key":"9544_CR26","doi-asserted-by":"crossref","unstructured":"Kleinberg, R. D., & Leighton, F. T. (2003). The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In FOCS (pp. 594\u2013605). IEEE Computer Society.","DOI":"10.1109\/SFCS.2003.1238232"},{"key":"9544_CR27","unstructured":"Mitzenmacher, M., & Upfal, E. (2017). Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press."},{"key":"9544_CR28","unstructured":"Morgenstern, J., & Roughgarden, T. (2015). On the pseudo-dimension of nearly optimal auctions. In NIPS (pp. 136\u2013144)."},{"key":"9544_CR29","unstructured":"Morgenstern, J., & Roughgarden, T. (2016). Learning simple auctions. In COLT, JMLR workshop and conference proceedings (Vol.\u00a049, pp. 1298\u20131318). JMLR.org."},{"issue":"1","key":"9544_CR30","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"RB Myerson","year":"1981","unstructured":"Myerson, R. B. (1981). Optimal auction design. Mathematical Operations Research, 6(1), 58\u201373.","journal-title":"Mathematical Operations Research"},{"key":"9544_CR31","doi-asserted-by":"crossref","unstructured":"Nisan, N., & Ronen, A. (1999). Algorithmic mechanism design (extended abstract). In STOC (pp. 129\u2013140). ACM.","DOI":"10.1145\/301250.301287"},{"key":"9544_CR32","doi-asserted-by":"crossref","unstructured":"Porter, R. (2004). Mechanism design for online real-time scheduling. In EC (pp. 61\u201370). ACM.","DOI":"10.1145\/988772.988783"},{"key":"9544_CR33","unstructured":"Puterman, M. L. (2005). Markov decision processes: Discrete stochastic dynamic programming (Wiley Series in Probability and Statistics). Wiley-Interscience."},{"key":"9544_CR34","doi-asserted-by":"crossref","unstructured":"Sandholm, T., & Gilpin, A. (2006). Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation. In AAMAS (pp. 1127\u20131134). ACM.","DOI":"10.1145\/1160633.1160839"},{"key":"9544_CR35","unstructured":"Str\u00f6hle, P., Gerding, E.H., de\u00a0Weerdt, M., Stein, S., & Robu, V. (2014). Online mechanism design for scheduling non-preemptive jobs under uncertain supply and demand. In AAMAS (pp. 437\u2013444). IFAAMAS\/ACM."},{"key":"9544_CR36","doi-asserted-by":"crossref","unstructured":"Tang, X., Li, X., & Fu, Z. (2017). Budget-constraint stochastic task scheduling on heterogeneous cloud systems. Concurrency and Computation: Practice and Experience 29(19).","DOI":"10.1002\/cpe.4210"},{"issue":"1","key":"9544_CR37","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W Vickrey","year":"1961","unstructured":"Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1), 8\u201337.","journal-title":"The Journal of Finance"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09544-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-022-09544-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09544-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T17:40:35Z","timestamp":1651167635000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-022-09544-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,22]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["9544"],"URL":"https:\/\/doi.org\/10.1007\/s10458-022-09544-y","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,22]]},"assertion":[{"value":"8 January 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"11"}}