Thursday, April 8, 2021 - 4:15pm to 5:15pm
Event Calendar Category
ORC
Speaker Name
Jonathan Amar & Nicholas Renegar
Affiliation
MIT
Join Zoom meeting
https://mit.zoom.us/j/92677815530
Abstract
In many online advertisement (ad) exchanges ad slots are each sold via a separate second-price auction. This work considers the bidder’s problem of maximizing the value of ads they purchase in these auctions subject to budget constraints. This ’second-price knapsack’ problem presents challenges when devising a bidding strategy because of the uncertain resource consumption: bidders win if they bid the highest amount but pay the second-highest bid unknown a priori. This is in contrast to the traditional online knapsack problem where posted prices are revealed when ads arrive and for which there exists a rich literature of primal and dual algorithms. The main results of this paper establish general methods for adapting these primal and dual online knapsack selection algorithms to the second-price knapsack problem where the prices are revealed only after bidding. In particular, a methodology is provided for converting deterministic and randomized knapsack selection algorithms into second-price knapsack bidding strategies that purchase ads through an equivalent set of criteria and thereby achieve the same competitive guarantees. This shows a connection between the traditional knapsack selection algorithm and second-price auction bidding algorithms that have not previously been leveraged. Empirical analysis on real ad exchange data verifies the usefulness of this method and gives examples where it can outperform state-of-the-art techniques.
Biography
Jonathan Amar is joining Verily Life Sciences as a Data Scientist within Healthy at work. He is a recent graduate from the MIT Operations Research Center, where he was advised by Prof. Nikos Trichakis. He is widely interested in the interface between optimization with healthcare applications and management. In particular, his dissertation focused advancements in revenue management, using data-driven techniques and algorithm design. Prior to MIT, he received a Diplome d'ingenieur (M.Sc) from the Ecole Polytechnique.
Nicholas Renegar is a fifth-year PhD candidate at the MIT Operations Research Center, where he is advised by Prof. Retsef Levi. He is broadly interested in optimization and analytics-based approaches to inform regulatory policy and interventions related to public health. In particular, his research focuses on using data-driven analytics to reduce consumer health risks arising from agricultural supply chains. He has also done research on auction theory with a focus on internet advertising (online algorithms and mechanism design). Prior to MIT, he received a B.S. in Mathematics and a B.Sc. in Operations Research from Cornell University.