Timezone: »
Dynamic mechanisms offer powerful techniques to improve on both revenue and efficiency by linking sequential auctions using state information, but these techniques rely on exact distributional information of the buyers’ valuations (present and future), which limits their use in learning settings. In this paper, we consider the problem of contextual auctions where the seller gradually learns a model of the buyer's valuation as a function of the context (e.g., item features) and seeks a pricing policy that optimizes revenue. Building on the concept of a bank account mechanism---a special class of dynamic mechanisms that is known to be revenue-optimal---we develop a non-clairvoyant dynamic mechanism that is robust to both estimation errors in the buyer's value distribution and strategic behavior on the part of the buyer. We then tailor its structure to achieve a policy with provably low regret against a constant approximation of the optimal dynamic mechanism in contextual auctions. Our result substantially improves on previous results that only provide revenue guarantees against static benchmarks.
Author Information
Yuan Deng (Duke University)
Sébastien Lahaie (Google Research)
Vahab Mirrokni (Google Research NYC)
More from the Same Authors
-
2021 Poster: Robust Auction Design in the Auto-bidding World »
Santiago Balseiro · Yuan Deng · Jieming Mao · Vahab Mirrokni · Song Zuo -
2021 Poster: Prior-independent Dynamic Auctions for a Value-maximizing Buyer »
Yuan Deng · Hanrui Zhang -
2021 Poster: Synthetic Design: An Optimization Approach to Experimental Design with Synthetic Controls »
Nick Doudchenko · Khashayar Khosravi · Jean Pouget-Abadie · Sébastien Lahaie · Miles Lubin · Vahab Mirrokni · Jann Spiess · guido imbens -
2020 Poster: Optimal Approximation - Smoothness Tradeoffs for Soft-Max Functions »
Alessandro Epasto · Mohammad Mahdian · Vahab Mirrokni · Emmanouil Zampetakis -
2020 Spotlight: Optimal Approximation - Smoothness Tradeoffs for Soft-Max Functions »
Alessandro Epasto · Mohammad Mahdian · Vahab Mirrokni · Emmanouil Zampetakis -
2020 Poster: Smoothly Bounding User Contributions in Differential Privacy »
Alessandro Epasto · Mohammad Mahdian · Jieming Mao · Vahab Mirrokni · Lijie Ren -
2020 Poster: Contextual Reserve Price Optimization in Auctions via Mixed Integer Programming »
Joey Huchette · Haihao Lu · Hossein Esfandiari · Vahab Mirrokni -
2020 : Clustering At Scale »
Vahab Mirrokni -
2020 Expo Workshop: Mining and Learning with Graphs at Scale »
Vahab Mirrokni · Bryan Perozzi · Jakub Lacki · Jonathan Halcrow · Jaqui C Herman -
2020 : Introduction »
Vahab Mirrokni -
2019 Poster: Prior-Free Dynamic Auctions with Low Regret Buyers »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Poster: Contextual Bandits with Cross-Learning »
Santiago Balseiro · Negin Golrezaei · Mohammad Mahdian · Vahab Mirrokni · Jon Schneider -
2019 Poster: Dynamic Incentive-Aware Learning: Robust Pricing in Contextual Auctions »
Negin Golrezaei · Adel Javanmard · Vahab Mirrokni -
2019 Poster: Strategizing against No-regret Learners »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Oral: Strategizing against No-regret Learners »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Poster: Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond »
Lin Chen · Hossein Esfandiari · Gang Fu · Vahab Mirrokni -
2019 Poster: Variance Reduction in Bipartite Experiments through Correlation Clustering »
Jean Pouget-Abadie · Kevin Aydin · Warren Schudy · Kay Brodersen · Vahab Mirrokni -
2017 Poster: Dynamic Revenue Sharing »
Santiago Balseiro · Max Lin · Vahab Mirrokni · Renato Leme · IIIS Song Zuo -
2017 Poster: Affinity Clustering: Hierarchical Clustering at Scale »
Mohammadhossein Bateni · Soheil Behnezhad · Mahsa Derakhshan · MohammadTaghi Hajiaghayi · Raimondas Kiveris · Silvio Lattanzi · Vahab Mirrokni -
2016 Poster: Bi-Objective Online Matching and Submodular Allocations »
Hossein Esfandiari · Nitish Korula · Vahab Mirrokni -
2016 Poster: Linear Relaxations for Finding Diverse Elements in Metric Spaces »
Aditya Bhaskara · Mehrdad Ghadiri · Vahab Mirrokni · Ola Svensson -
2014 Poster: Distributed Balanced Clustering via Mapping Coresets »
Mohammadhossein Bateni · Aditya Bhaskara · Silvio Lattanzi · Vahab Mirrokni