Timezone: »
Inspired by real-time ad exchanges for online display advertising, we consider the problem of inferring a buyer's value distribution for a good when the buyer is repeatedly interacting with a seller through a posted-price mechanism. We model the buyer as a strategic agent, whose goal is to maximize her long-term surplus, and we are interested in mechanisms that maximize the seller's long-term revenue. We present seller algorithms that are no-regret when the buyer discounts her future surplus --- i.e. the buyer prefers showing advertisements to users sooner rather than later. We also give a lower bound on regret that increases as the buyer's discounting weakens and shows, in particular, that any seller algorithm will suffer linear regret if there is no discounting.
Author Information
Kareem Amin (University of Pennsylvania)
Afshin Rostamizadeh (Google Research)
Umar Syed (Google Research)
More from the Same Authors
-
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2022 Poster: Private and Communication-Efficient Algorithms for Entropy Estimation »
Gecia Bravo-Hermsdorff · Róbert Busa-Fekete · Mohammad Ghavamzadeh · Andres Munoz Medina · Umar Syed -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 Poster: Batch Active Learning at Scale »
Gui Citovsky · Giulia DeSalvo · Claudio Gentile · Lazaros Karydas · Anand Rajagopalan · Afshin Rostamizadeh · Sanjiv Kumar -
2021 Poster: Learning with Labeling Induced Abstentions »
Kareem Amin · Giulia DeSalvo · Afshin Rostamizadeh -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2020 Poster: An Analysis of SVD for Deep Rotation Estimation »
Jake Levinson · Carlos Esteves · Kefan Chen · Noah Snavely · Angjoo Kanazawa · Afshin Rostamizadeh · Ameesh Makadia -
2017 Poster: Statistical Cost Sharing »
Eric Balkanski · Umar Syed · Sergei Vassilvitskii -
2015 Workshop: The 1st International Workshop "Feature Extraction: Modern Questions and Challenges" »
Dmitry Storcheus · Sanjiv Kumar · Afshin Rostamizadeh -
2014 Poster: Repeated Contextual Auctions with Strategic Buyers »
Kareem Amin · Afshin Rostamizadeh · Umar Syed -
2014 Poster: Multi-Class Deep Boosting »
Vitaly Kuznetsov · Mehryar Mohri · Umar Syed -
2009 Poster: Learning Non-Linear Combinations of Kernels »
Corinna Cortes · Mehryar Mohri · Afshin Rostamizadeh -
2008 Workshop: Kernel Learning: Automatic Selection of Optimal Kernels »
Corinna Cortes · Arthur Gretton · Gert Lanckriet · Mehryar Mohri · Afshin Rostamizadeh -
2008 Poster: Domain Adaptation with Multiple Sources »
Yishay Mansour · Mehryar Mohri · Afshin Rostamizadeh -
2008 Spotlight: Domain Adaptation with Multiple Sources »
Yishay Mansour · Mehryar Mohri · Afshin Rostamizadeh -
2008 Poster: Rademacher Complexity Bounds for Non-I.I.D. Processes »
Mehryar Mohri · Afshin Rostamizadeh -
2007 Poster: Stability Bounds for Non-i.i.d. Processes »
Mehryar Mohri · Afshin Rostamizadeh