Timezone: »

 
Poster
A Robust Non-Clairvoyant Dynamic Mechanism for Contextual Auctions
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #215
in Theory -- Game Theory and Computational Economics »

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.

Keywords: Game Theory and Computational Economics · Theory
[ Paper]  [ Poster] 

Author Information

Yuan Deng (Duke University)
Sébastien Lahaie (Google Research)
Vahab Mirrokni (Google Research NYC)

More from the Same Authors