Tata Institute of Fundamental Research
Learning Optimal Bids in Second Price Auctions with Temporal and Overlapping Targeting Constraints
STCS Seminar
Speaker:
Ravi R. Mazumdar (University of Waterloo)
Organiser:
Abhishek Sinha
Date:
Monday, 25 Jul 2022, 16:00 to 17:00
Venue:
A-201 and Zoom
(Scan to add to calendar)
Abstract:
Ad placement in web-browsing and wireless mobiles is an increasingly important component of the advertisement market. The market size is over $ 100 billion and counting. The mechanism is as follows: when a user opens a webpage or mobile ap a message is sent to an exchange where multiple bidders have the possibility of placing an ad that would target the right user, eg. age, sex, location, etc. The ad that is displayed corresponds to the bidder who bids the highest while the cost is calculated according to a first or second price. Typically bidders are DSP (Demand Side Platforms) that aggregate bids on behalf of clients who wish to run a campaign for a given length of time with certain targeting criteria. The goal is to minimize the total cost of obtaining the required number of impressions (ads that meet targeting criteria) over the duration of a contract. The real time constraint is that bidding must be done within 100ms.
In this talk I will build upon the theory that we had earlier developed for computing the least cost bids in the second price context. This involves the notion of an information state for the problem. There is a very rich primal-dual theory that emerges, one in the so called impressions space and the other in the contracts space. Computationally and structurally the primal and dual views of the optimization have different properties that can be exploited to come up with fast algorithms.
The optimal solutions depend on solving a constrained convex optimization problem when the information state is known. However this is not readily available and thus there is the problem of learning the information state. We show that in the second price case, stochastic approximation (SA) algorithms that operate on censored data (prices are only known by a bidder when the bidder wins) can be devised that solve the constrained optimization problem without learning the information state explicitly and we prove their convergence. Finally I will present the dynamic behaviour through simulations.
Joint work with Ryan Kinnear (Waterloo) and Peter Marbach (Toronto). We thank Addictive Mobility Inc., a Pelmorex company for having proposed the problem and to Addictive Mobility, Ontario OCE VIP II, and NSERC funding the work.
Bio: The speaker was educated at the Indian Institute of Technology, Bombay (B.Tech, 1977), Imperial College, London (MSc, DIC, 1978) and obtained his PhD in Control Theory under A. V. Balakrishnan at UCLA in 1983. He is currently a University Research Chair Professor in the Dept. of ECE at the University of Waterloo, Ont., Canada where he has been since September 2004. Prior to this he was Professor of ECE at Purdue University, West Lafayette, USA. Since 2012 he is a D.J. Gandhi Distinguished Visiting Professor at the Indian Institute of Technology, Bombay, India and since May 2019 an Adjunct Professor at the Tata Institute of Fundamental Research (TIFR), Mumbai. He is a Fellow of the IEEE and the Royal Statistical Society. He is a recipient of the INFOCOM 2006 Best Paper Award, the ITC-27 2015 Best Paper Award, the Performance 2015 Best Paper Award and was runner-up for the Best Paper Award at INFOCOM 1998. His research interests are in stochastic modelling and analysis applied to complex networks and statistical inference.
YouTube Link: https://youtu.be/dA44DA8gQDM
| Speaker: | Ravi R. Mazumdar (University of Waterloo) |
| Organiser: | Abhishek Sinha |
| Date: | Monday, 25 Jul 2022, 16:00 to 17:00 |
| Venue: | A-201 and Zoom |
(Scan to add to calendar)
Abstract:
Ad placement in web-browsing and wireless mobiles is an increasingly important component of the advertisement market. The market size is over $ 100 billion and counting. The mechanism is as follows: when a user opens a webpage or mobile ap a message is sent to an exchange where multiple bidders have the possibility of placing an ad that would target the right user, eg. age, sex, location, etc. The ad that is displayed corresponds to the bidder who bids the highest while the cost is calculated according to a first or second price. Typically bidders are DSP (Demand Side Platforms) that aggregate bids on behalf of clients who wish to run a campaign for a given length of time with certain targeting criteria. The goal is to minimize the total cost of obtaining the required number of impressions (ads that meet targeting criteria) over the duration of a contract. The real time constraint is that bidding must be done within 100ms.
In this talk I will build upon the theory that we had earlier developed for computing the least cost bids in the second price context. This involves the notion of an information state for the problem. There is a very rich primal-dual theory that emerges, one in the so called impressions space and the other in the contracts space. Computationally and structurally the primal and dual views of the optimization have different properties that can be exploited to come up with fast algorithms.
The optimal solutions depend on solving a constrained convex optimization problem when the information state is known. However this is not readily available and thus there is the problem of learning the information state. We show that in the second price case, stochastic approximation (SA) algorithms that operate on censored data (prices are only known by a bidder when the bidder wins) can be devised that solve the constrained optimization problem without learning the information state explicitly and we prove their convergence. Finally I will present the dynamic behaviour through simulations.
Joint work with Ryan Kinnear (Waterloo) and Peter Marbach (Toronto). We thank Addictive Mobility Inc., a Pelmorex company for having proposed the problem and to Addictive Mobility, Ontario OCE VIP II, and NSERC funding the work.
Bio: The speaker was educated at the Indian Institute of Technology, Bombay (B.Tech, 1977), Imperial College, London (MSc, DIC, 1978) and obtained his PhD in Control Theory under A. V. Balakrishnan at UCLA in 1983. He is currently a University Research Chair Professor in the Dept. of ECE at the University of Waterloo, Ont., Canada where he has been since September 2004. Prior to this he was Professor of ECE at Purdue University, West Lafayette, USA. Since 2012 he is a D.J. Gandhi Distinguished Visiting Professor at the Indian Institute of Technology, Bombay, India and since May 2019 an Adjunct Professor at the Tata Institute of Fundamental Research (TIFR), Mumbai. He is a Fellow of the IEEE and the Royal Statistical Society. He is a recipient of the INFOCOM 2006 Best Paper Award, the ITC-27 2015 Best Paper Award, the Performance 2015 Best Paper Award and was runner-up for the Best Paper Award at INFOCOM 1998. His research interests are in stochastic modelling and analysis applied to complex networks and statistical inference.
YouTube Link: https://youtu.be/dA44DA8gQDM
In this talk I will build upon the theory that we had earlier developed for computing the least cost bids in the second price context. This involves the notion of an information state for the problem. There is a very rich primal-dual theory that emerges, one in the so called impressions space and the other in the contracts space. Computationally and structurally the primal and dual views of the optimization have different properties that can be exploited to come up with fast algorithms.
The optimal solutions depend on solving a constrained convex optimization problem when the information state is known. However this is not readily available and thus there is the problem of learning the information state. We show that in the second price case, stochastic approximation (SA) algorithms that operate on censored data (prices are only known by a bidder when the bidder wins) can be devised that solve the constrained optimization problem without learning the information state explicitly and we prove their convergence. Finally I will present the dynamic behaviour through simulations.
Joint work with Ryan Kinnear (Waterloo) and Peter Marbach (Toronto). We thank Addictive Mobility Inc., a Pelmorex company for having proposed the problem and to Addictive Mobility, Ontario OCE VIP II, and NSERC funding the work.
Bio: The speaker was educated at the Indian Institute of Technology, Bombay (B.Tech, 1977), Imperial College, London (MSc, DIC, 1978) and obtained his PhD in Control Theory under A. V. Balakrishnan at UCLA in 1983. He is currently a University Research Chair Professor in the Dept. of ECE at the University of Waterloo, Ont., Canada where he has been since September 2004. Prior to this he was Professor of ECE at Purdue University, West Lafayette, USA. Since 2012 he is a D.J. Gandhi Distinguished Visiting Professor at the Indian Institute of Technology, Bombay, India and since May 2019 an Adjunct Professor at the Tata Institute of Fundamental Research (TIFR), Mumbai. He is a Fellow of the IEEE and the Royal Statistical Society. He is a recipient of the INFOCOM 2006 Best Paper Award, the ITC-27 2015 Best Paper Award, the Performance 2015 Best Paper Award and was runner-up for the Best Paper Award at INFOCOM 1998. His research interests are in stochastic modelling and analysis applied to complex networks and statistical inference.
YouTube Link: https://youtu.be/dA44DA8gQDM