(Virtual) Seminar Series | Robust online selection with uncertain offer acceptance

Sebastian Perez-Salazar, Ph.D. Candidate

Georgia Institute of Technology

Online advertising has motivated a renewed interest in multiple online selection problems. Displaying ads to the right users benefits both the platform (e.g., via pay- per-click) and the advertisers (by increasing their reach). However, in practice, not all users click on displayed ads, while the platform’s algorithm may miss the users most disposed to do so. This mismatch decreases the platform’s revenue and the advertiser’s chances to reach the right customers. With this motivation, we examine a secretary problem where a candidate may or may not accept an offer according to a known probability p. Because we do not know the top candidate willing to accept an offer, we aim to maximize a robust objective defined as the minimum over k of the probability of choosing one of the top k candidates, given that one of these candidates will accept an offer. In this talk, we present a linear program for this max-min objective whose solution encodes an optimal policy. We further relax this LP into an infinite counterpart, which we use to provide bounds for the objective and closed-form policies.

Sebastian Perez-Salazar is a Ph.D. Candidate in the Algorithms, Combinatorics, and Optimization (ACO) program at the Georgia Institute of Technology, advised by Mohit Singh and Alejandro Toriello. His research interests lie at the intersection of optimization under uncertainty and dynamic resource allocation with applications in optimization problems arising in cloud computing, online advertising, and scheduling problems. Sebastian received the 2021 Shabbir Ahmed Fellowship from Georgia Tech and the 2021 LATinE Trailblazer Fellowship from Purdue University. In addition, his paper “Dynamic Resource Allocation in the Cloud” (with. I. Menache, M. Singh, and A. Toriello) was a runner-up for the 2019 INFORMS Computing Society Student Paper Prize.

Category: Seminars