arXiv (Cornell University) · 2013 · 74 citations · 16 references
BusinessBusiness EconomicsEconomicsAuction TheoryGame TheoryMicroeconomicsDiscounted Reward OptimizationSequential AuctionsAd ExchangesLearning In Repeated AuctionsOnline Ad AuctionsOnline Display AdvertisingPosted PricingRegret Optimization
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 define the natural notion of strategic regret --- the lost revenue as measured against a truthful (non-strategic) buyer. We present seller algorithms that are no-(strategic)-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 strategic regret that increases as the buyer's discounting weakens and shows, in particular, that any seller algorithm will suffer linear strategic regret if there is no discounting.
16
The Nonstochastic Multiarmed Bandit Problem
Peter Auer, Nicolò Cesa‐Bianchi, Yoav Freund et al. · SIAM Journal on Computing · 2002 · 2.3K citations
Conditioning Prices on Purchase History
Alessandro Acquisti, Hal R. Varian · Marketing Science · 2005 · 712 citations