{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T16:47:26Z","timestamp":1755794846774,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,8,3]]},"DOI":"10.1145\/3711896.3737071","type":"proceedings-article","created":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T21:05:41Z","timestamp":1754255141000},"page":"2138-2149","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimising Budget Management via Primal-Dual Approximation with Constrained Polynomial Weights Update"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-4582-7931","authenticated-orcid":false,"given":"Dmitrii","family":"Moor","sequence":"first","affiliation":[{"name":"Spotify, London, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-3807-8777","authenticated-orcid":false,"given":"Per","family":"Berglund","sequence":"additional","affiliation":[{"name":"Spotify, Gothenburg, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2598-129X","authenticated-orcid":false,"given":"Hannes","family":"Karlbom","sequence":"additional","affiliation":[{"name":"Spotify, Stockholm, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2061-4977","authenticated-orcid":false,"given":"Zhenwen","family":"Dai","sequence":"additional","affiliation":[{"name":"Spotify, London, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1257-1703","authenticated-orcid":false,"given":"Kyle","family":"Kretschman","sequence":"additional","affiliation":[{"name":"Spotify, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3531-3096","authenticated-orcid":false,"given":"Mounia","family":"Lalmas","sequence":"additional","affiliation":[{"name":"Spotify, London, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2025,8,3]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"253","volume-title":"ESA'07","author":"Buchbinder N.","year":"2007","unstructured":"N. Buchbinder, K. Jain, and J. S. Naor, ''Online primal-dual algorithms for maximizing ad-auctions revenue,'' in Proceedings of the 15th Annual European Conference on Algorithms, ESA'07(Berlin, Heidelberg), p. 253-264, Springer-Verlag, 2007."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"e_1_3_2_2_3_1","unstructured":"E. Kevi and K. T. Nguyen ''Primal-dual algorithms with predictions for online bounded allocation and ad-auctions problems '' in Proceedings of The 34th International Conference on Algorithmic Learning Theory (S. Agrawal and F. Orabona eds.) vol. 201 of Proceedings of Machine Learning Research pp. 891-908 PMLR 20 Feb-23 Feb 2023."},{"key":"e_1_3_2_2_4_1","first-page":"232","volume-title":"AAAI'13","author":"Ding W.","year":"2013","unstructured":"W. Ding, T. Qiny, X.-D. Zhang, and T.-Y. Liu, ''Multi-armed bandit with budget constraint and variable costs,'' in Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, AAAI'13, p. 232-238, AAAI Press, 2013."},{"key":"e_1_3_2_2_5_1","first-page":"531","volume-title":"WWW '07","author":"Borgs C.","unstructured":"C. Borgs, J. Chayes, N. Immorlica, K. Jain, O. Etesami, and M. Mahdian, ''Dynamics of bid optimization in online advertisement auctions,'' in Proceedings of the 16th International Conference on World Wide Web, WWW '07(New York, NY, USA), p. 531-540, Association for Computing Machinery, 2007."},{"key":"e_1_3_2_2_6_1","volume-title":"Epsilon-first policies for budget-limited multi-armed bandits,'' in AAAI Conference on Artificial Intelligence","author":"Tran-Thanh L.","year":"2010","unstructured":"L. Tran-Thanh, A. C. Chapman, E. M. de Cote, A. Rogers, and N. R. Jennings, ''Epsilon-first policies for budget-limited multi-armed bandits,'' in AAAI Conference on Artificial Intelligence, 2010."},{"key":"e_1_3_2_2_7_1","first-page":"47","volume-title":"WSDM '24","author":"Brantley K.","unstructured":"K. Brantley, Z. Fang, S. Dean, and T. Joachims, ''Ranking with long-term constraints,'' in Proceedings of the 17th ACM International Conference on Web Search and Data Mining, WSDM '24(New York, NY, USA), p. 47-56, Association for Computing Machinery, 2024."},{"key":"e_1_3_2_2_8_1","first-page":"2217","volume-title":"KDD '15","author":"Xu J.","unstructured":"J. Xu, K.-c. Lee, W. Li, H. Qi, and Q. Lu, ''Smart pacing for effective online ad campaign optimization,'' in Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15(New York, NY, USA), p. 2217-2226, Association for Computing Machinery, 2015."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3406463"},{"key":"e_1_3_2_2_10_1","first-page":"06840","article-title":"Ranking with fairness constraints","volume":"1704","author":"Celis L. E.","year":"2017","unstructured":"L. E. Celis, D. Straszak, and N. K. Vishnoi, ''Ranking with fairness constraints,'' ArXiv, vol. abs\/1704.06840, 2017.","journal-title":"ArXiv"},{"key":"e_1_3_2_2_11_1","first-page":"2219","volume-title":"KDD '18","author":"Singh A.","unstructured":"A. Singh and T. Joachims, ''Fairness of exposure in rankings,'' in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18(New York, NY, USA), p. 2219-2228, Association for Computing Machinery, 2018."},{"key":"e_1_3_2_2_12_1","volume-title":"WWW '17(Republic and Canton of Geneva, CHE), p. 15-23, International World Wide Web Conferences Steering Committee","author":"Balseiro S.","year":"2017","unstructured":"S. Balseiro, A. Kim, M. Mahdian, and V. Mirrokni, ''Budget management strategies in repeated auctions,'' in Proceedings of the 26th International Conference on World Wide Web, WWW '17(Republic and Canton of Geneva, CHE), p. 15-23, International World Wide Web Conferences Steering Committee, 2017."},{"key":"e_1_3_2_2_13_1","volume-title":"NIPS '21","author":"Balseiro S.","year":"2021","unstructured":"S. Balseiro, Y. Deng, J. Mao, V. Mirrokni, and S. Zuo, ''Robust auction design in the auto-bidding world,'' in Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21(Red Hook, NY, USA), Curran Associates Inc., 2021."},{"key":"e_1_3_2_2_14_1","unstructured":"S. R. Balseiro K. Bhawalkar Z. Feng H. Lu V. Mirrokni B. Sivan and D. Wang ''A field guide for pacing budget and ROS constraints '' in Proceedings of the 41st International Conference on Machine Learning (R. Salakhutdinov Z. Kolter K. Heller A. Weller N. Oliver J. Scarlett and F. Berkenkamp eds.) vol. 235 of Proceedings of Machine Learning Research pp. 2607-2638 PMLR 21-27 Jul 2024."},{"key":"e_1_3_2_2_15_1","unstructured":"S. Agrawal M. Zadimoghaddam and V. Mirrokni ''Proportional allocation: Simple distributed and diverse matching with high entropy '' in Proceedings of the 35th International Conference on Machine Learning (J. Dy and A. Krause eds.) vol. 80 of Proceedings of Machine Learning Research pp. 99-108 PMLR 10-15 Jul 2018."},{"key":"e_1_3_2_2_16_1","volume-title":"NIPS '23","author":"Spaeh F.","year":"2024","unstructured":"F. Spaeh and A. Ene, ''Online ad allocation with predictions,'' in Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23(Red Hook, NY, USA), Curran Associates Inc., 2024."},{"key":"e_1_3_2_2_17_1","volume-title":"Knowledge Discovery and Data Mining (AdKDD 2023)","author":"Nguyen H.","year":"2023","unstructured":"H. Nguyen, D. Gligorijevic, A. Borah, G. Adalinge, and A. Bagherjeiran, ''Practical budget pacing algorithms and simulation test bed for ebay marketplace sponsored search,'' in AdKDD Workshop 2023 at the 29th ACM SIGKDD Conf. Knowledge Discovery and Data Mining (AdKDD 2023), 2023."},{"key":"e_1_3_2_2_18_1","first-page":"328","volume-title":"WWW '24","author":"Chen Q.","unstructured":"Q. Chen, P. H. Nguyen, and D. Gligorijevic, ''Optimization-based budget pacing in ebay sponsored search,'' in Companion Proceedings of the ACM Web Conference 2024, WWW '24(New York, NY, USA), p. 328-337, Association for Computing Machinery, 2024."},{"key":"e_1_3_2_2_19_1","first-page":"2024","article-title":"Mystique: A budget pacing system for performance optimization in online advertising","author":"Stram R.","year":"2024","unstructured":"R. Stram, R. Abboud, A. Shtoff, O. Somekh, A. Raviv, and Y. Koren, ''Mystique: A budget pacing system for performance optimization in online advertising,'' in Proceedings of the ACM Web Conference 2024, 2024.","journal-title":"Proceedings of the ACM Web Conference"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_2_21_1","first-page":"68","volume-title":"Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm,'' in 28th Annual Symposium on Foundations of Computer Science (sfcs","author":"Littlestone N.","year":"1987","unstructured":"N. Littlestone, ''Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm,'' in 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pp. 68-77, 1987."},{"key":"e_1_3_2_2_22_1","volume-title":"Cambridge University Press","author":"Theory Algorithmic Game","year":"2007","unstructured":"Algorithmic Game Theory. Cambridge University Press, 2007."},{"issue":"47","key":"e_1_3_2_2_23_1","first-page":"1307","article-title":"From external to internal regret","volume":"8","author":"Blum A.","year":"2007","unstructured":"A. Blum and Y. Mansour, ''From external to internal regret,'' Journal of Machine Learning Research, vol. 8, no. 47, pp. 1307-1324, 2007.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_24_1","volume-title":"Patern Recognition and Machine Learning","author":"Bishop C. M.","year":"2007","unstructured":"C. M. Bishop, Patern Recognition and Machine Learning. New York, NY, USA: Springer, 2007."},{"key":"e_1_3_2_2_25_1","volume-title":"Discrete Choice Methods with Simulation","author":"Train K. E.","year":"2009","unstructured":"K. E. Train, Discrete Choice Methods with Simulation. Cambridge University Press, 2 ed., 2009."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"}],"event":{"name":"KDD '25: The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"],"location":"Toronto ON Canada","acronym":"KDD '25"},"container-title":["Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3711896.3737071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T14:33:50Z","timestamp":1755354830000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711896.3737071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,3]]},"references-count":26,"alternative-id":["10.1145\/3711896.3737071","10.1145\/3711896"],"URL":"https:\/\/doi.org\/10.1145\/3711896.3737071","relation":{},"subject":[],"published":{"date-parts":[[2025,8,3]]},"assertion":[{"value":"2025-08-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}