{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:17Z","timestamp":1750220537979,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T00:00:00Z","timestamp":1639440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Natural Sciences and Engineering Research Council of Canada (NSERC) Canada Graduate Scholarships - Doctoral program","award":["518418-2018"],"award-info":[{"award-number":["518418-2018"]}]},{"name":"Natural Sciences and Engineering Research Council of Canada (NSERC) Collaborative Research and Development Grant"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2021,12,14]]},"abstract":"<jats:p>We study the optimal bids and allocations in a real-time auction for heterogeneous items subject to the requirement that specified collections of items of given types be acquired within given time constraints. The problem is cast as a continuous time optimization problem that can, under certain weak assumptions, be reduced to a convex optimization problem. Focusing on the standard first and second price auctions, we first show, using convex duality, that the optimal (infinite dimensional) bidding policy can be represented by a single finite vector of so-called ''pseudo-bids''. Using this result we are able to show that the optimal solution in the second price case turns out to be a very simple piecewise constant function of time. This contrasts with the first price case that is more complicated. Despite the fact that the optimal solution for the first price auction is genuinely dynamic, we show that there remains a close connection between the two cases and that, empirically, there is almost no difference between optimal behavior in either setting. This suggests that it is adequate to bid in a first price auction as if it were in fact second price. Finally, we detail methods for implementing our bidding policies in practice with further numerical simulations illustrating the performance.<\/jats:p>","DOI":"10.1145\/3491049","type":"journal-article","created":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T18:32:19Z","timestamp":1639593139000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Real-time Bidding for Time Constrained Impression Contracts in First and Second Price Auctions - Theory and Algorithms"],"prefix":"10.1145","volume":"5","author":[{"given":"Ryan J.","family":"Kinnear","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi R.","family":"Mazumdar","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Marbach","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,12,15]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1080\/23307706.2017.1397554"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1287\/mnsc.2014.2022"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1287\/mnsc.2018.3174"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/s10957-008-9393-3"},{"volume-title":"Convex Optimization","author":"Boyd Stephen","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization .Cambridge University Press. https:\/\/web.stanford.edu\/ boyd\/cvxbook\/","key":"e_1_2_1_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1287\/mnsc.2019.3365"},{"key":"e_1_2_1_7_1","volume-title":"Real-Time Bidding by Reinforcement Learning in Display Advertising. CoRR","author":"Cai Han","year":"2017","unstructured":"Han Cai, Kan Ren, and Weinan Zhang et. al. 2017. Real-Time Bidding by Reinforcement Learning in Display Advertising. CoRR , Vol. abs\/1701.02490 (2017). http:\/\/dblp.uni-trier.de\/db\/journals\/corr\/corr1701.html#CaiRZMWYG17"},{"key":"e_1_2_1_8_1","volume-title":"Devanur","author":"Chen Ye","year":"2011","unstructured":"Ye Chen, Pavel Berkhin, Bo Anderson, and Nikhil R. Devanur. 2011. Real-time bidding algorithms for performance-based display ad allocation.. In KDD , , Chid Apt\u00e9, Joydeep Ghosh, and Padhraic Smyth (Eds.). ACM, 1307--1315. http:\/\/dblp.uni-trier.de\/db\/conf\/kdd\/kdd2011.html#ChenBAD11"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1007\/978--1--4471--4820--3"},{"key":"e_1_2_1_10_1","volume-title":"On the LambertW function. Advances in Computational mathematics","author":"Corless Robert M","year":"1996","unstructured":"Robert M Corless, Gaston H Gonnet, and David EG Hare et. al. 1996. On the LambertW function. Advances in Computational mathematics , Vol. 5, 1 (1996), 329--359."},{"doi-asserted-by":"crossref","unstructured":"Ying Cui Ruofei Zhang Wei Li and Jianchang Mao. 2011. Bid landscape forecasting in online ad exchange marketplace.. In KDD Chid Apt\u00e9 Joydeep Ghosh and Padhraic Smyth (Eds.). ACM 265--273. http:\/\/dblp.uni-trier.de\/db\/conf\/kdd\/kdd2011.html#CuiZLM11","key":"e_1_2_1_11_1","DOI":"10.1145\/2020408.2020454"},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"CVXPY: A Python-embedded modeling language for convex optimization","volume":"17","author":"Diamond Steven","year":"2016","unstructured":"Steven Diamond and Stephen Boyd. 2016. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research , Vol. 17, 83 (2016), 1--5.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_13_1","first-page":"142","article-title":"Optimal real-time bidding strategies","volume":"2017","author":"Fernandez-Tapia Joaquin","year":"2017","unstructured":"Joaquin Fernandez-Tapia, Olivier Gu\u00e9ant, and Jean-Michel Lasry. 2017. Optimal real-time bidding strategies. Applied Mathematics Research eXpress , Vol. 2017, 1 (2017), 142--183.","journal-title":"Applied Mathematics Research eXpress"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/1113830.1113838"},{"key":"e_1_2_1_15_1","volume-title":"Scalable Bid Landscape Forecasting in Real-time Bidding. CoRR","author":"Ghosh Aritra","year":"2020","unstructured":"Aritra Ghosh, Saayan Mitra, and Somdeb Sarkhel et. al. 2020. Scalable Bid Landscape Forecasting in Real-time Bidding. CoRR , Vol. abs\/2001.06587 (2020). http:\/\/dblp.uni-trier.de\/db\/journals\/corr\/corr2001.html#abs-2001-06587"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1526709.1526744"},{"doi-asserted-by":"crossref","unstructured":"Nicolas Grislain Nicolas Perrin and Antoine Thabault. 2019. Recurrent Neural Networks for Stochastic Control in Real-Time Bidding.. In KDD Ankur Teredesai Vipin Kumar Ying Li R\u00f3mer Rosales Evimaria Terzi and George Karypis (Eds.). ACM 2801--2809. http:\/\/dblp.uni-trier.de\/db\/conf\/kdd\/kdd2019.html#GrislainPT19","key":"e_1_2_1_17_1","DOI":"10.1145\/3292500.3330749"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1109\/Allerton.2011.6120220"},{"unstructured":"IAB. 2018. IAB internet advertising revenue report conducted by PricewaterhouseCoopers (PWC). https:\/\/www.iab.com\/insights","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1287\/mnsc.2014.2018"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1109\/ACC.2014.6859107"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1016\/j.ejcon.2016.04.007"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/CDC.2017.8263968"},{"volume-title":"Auction Theory","author":"Krishna Vijay","unstructured":"Vijay Krishna. 2002. Auction Theory .Academic Press.","key":"e_1_2_1_24_1"},{"volume-title":"Receding horizon control: model predictive control for state models","author":"Kwon Wook Hyun","unstructured":"Wook Hyun Kwon and Soo Hee Han. 2006. Receding horizon control: model predictive control for state models .Springer Science & Business Media.","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1287\/trsc.8.4.344"},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"iPinYou Global RTB Bidding Algorithm Competition Dataset.. In ADKDD@KDD , , Esin Saka, Dou Shen, Kuang chih Lee, and Ying Li (Eds.)","volume":"6","author":"Liao Hairen","year":"2014","unstructured":"Hairen Liao, Lingxiao Peng, Zhenchuan Liu, and Xuehua Shen. 2014. iPinYou Global RTB Bidding Algorithm Competition Dataset.. In ADKDD@KDD , , Esin Saka, Dou Shen, Kuang chih Lee, and Ying Li (Eds.). ACM, 6:1--6:6. http:\/\/dblp.uni-trier.de\/db\/conf\/kdd\/adkdd2014.html#LiaoPLS14","journal-title":"ACM"},{"key":"e_1_2_1_28_1","volume-title":"Doubleclick Ad Exchange Auction. CoRR","author":"Mansour Yishay","year":"2012","unstructured":"Yishay Mansour, S. Muthukrishnan, and Noam Nisan. 2012. Doubleclick Ad Exchange Auction. CoRR , Vol. abs\/1204.0535 (2012). http:\/\/dblp.uni-trier.de\/db\/journals\/corr\/corr1204.html#abs-1204-0535"},{"doi-asserted-by":"crossref","unstructured":"Flavio M Menezes and Paulo Klinger Monteiro. 2005. An introduction to auction theory .OUP Oxford.","key":"e_1_2_1_29_1","DOI":"10.1093\/019927598X.001.0001"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1090\/S0002-9939-07-08887-9"},{"unstructured":"Art B. Owen. 2013. Monte Carlo theory methods and examples . http:\/\/statweb.stanford.edu\/ owen\/mc\/","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","volume-title":"Provost","author":"Perlich Claudia","year":"2012","unstructured":"Claudia Perlich, Brian Dalessandro, Rod Hook, Ori Stitelman, Troy Raeder, and Foster J. Provost. 2012. Bid optimizing and inventory scoring in targeted online advertising.. In KDD , , Qiang Yang, Deepak Agarwal, and Jian Pei (Eds.). ACM, 804--812. http:\/\/dblp.uni-trier.de\/db\/conf\/kdd\/kdd2012.html#PerlichDHSRP12"},{"key":"e_1_2_1_33_1","volume-title":"Heavlin","author":"Radovanovic Ana","year":"2012","unstructured":"Ana Radovanovic and William D. Heavlin. 2012. Risk-aware revenue maximization in display advertising.. In WWW , , Alain Mille, Fabien L. Gandon, Jacques Misselis, Michael Rabinovich, and Steffen Staab (Eds.). ACM, 91--100. http:\/\/dblp.uni-trier.de\/db\/conf\/www\/www2012.html#RadovanovicH12"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1002\/net.3230160411"},{"key":"e_1_2_1_35_1","volume-title":"A decomposition algorithm for solving the multifacility production-transportation problem with nonlinear production costs. Econometrica: Journal of the Econometric Society","author":"Sharp J Frank","year":"1970","unstructured":"J Frank Sharp, James C Snyder, and James H Greene. 1970. A decomposition algorithm for solving the multifacility production-transportation problem with nonlinear production costs. Econometrica: Journal of the Econometric Society (1970), 490--506."},{"volume-title":"Real analysis: measure theory, integration, and Hilbert spaces","author":"Stein Elias M","unstructured":"Elias M Stein and Rami Shakarchi. 2009. Real analysis: measure theory, integration, and Hilbert spaces .Princeton University Press.","key":"e_1_2_1_36_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/3366707"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1038\/s41592-019-0686-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1561\/9781680833119"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1007\/978-3-319-46128-1_8"},{"key":"e_1_2_1_41_1","volume-title":"Constant Regret Re-solving Heuristics for Price-based Revenue Management. arXiv preprint arXiv:2009.02861","author":"Wang Yining","year":"2020","unstructured":"Yining Wang and He Wang. 2020. Constant Regret Re-solving Heuristics for Price-based Revenue Management. arXiv preprint arXiv:2009.02861 (2020)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1007\/0--387--30623--4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1145\/3269206.3271748"},{"key":"e_1_2_1_44_1","volume-title":"KDD , , Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I","author":"Chi-Hsuan Wu Wush","year":"2015","unstructured":"Wush Chi-Hsuan Wu, Mi-Yen Yeh, and Ming-Syan Chen. 2015. Predicting Winning Price in Real Time Bidding with Censored Data.. In KDD , , Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams (Eds.). ACM, 1305--1314. http:\/\/dblp.uni-trier.de\/db\/conf\/kdd\/kdd2015.html#WuYC15"},{"unstructured":"Wush Chi-Hsuan Wu Mi-Yen Yeh and Ming-Syan Chen. 2018b. Deep Censored Learning of the Winning Price in the Real Time Bidding.. In KDD Yike Guo and Faisal Farooq (Eds.). ACM 2526--2535. http:\/\/dblp.uni-trier.de\/db\/conf\/kdd\/kdd2018.html#WuYC18","key":"e_1_2_1_45_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1145\/2501040.2501980"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1145\/2835776.2835843"},{"doi-asserted-by":"publisher","key":"e_1_2_1_48_1","DOI":"10.1145\/2783258.2783269"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1145\/2623330.2623633"},{"key":"e_1_2_1_50_1","volume-title":"Real-time bidding benchmarking with ipinyou dataset. arXiv preprint arXiv:1407.7073","author":"Zhang Weinan","year":"2014","unstructured":"Weinan Zhang, Shuai Yuan, Jun Wang, and Xuehua Shen. 2014b. Real-time bidding benchmarking with ipinyou dataset. arXiv preprint arXiv:1407.7073 (2014)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1145\/2939672.2939713"},{"doi-asserted-by":"publisher","key":"e_1_2_1_52_1","DOI":"10.1109\/BigData.2017.8258095"}],"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\/3491049","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:06Z","timestamp":1750195506000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,14]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,12,14]]}},"alternative-id":["10.1145\/3491049"],"URL":"https:\/\/doi.org\/10.1145\/3491049","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2021,12,14]]},"assertion":[{"value":"2021-12-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}