Learning Prices for Repeated Auctions with Strategic Buyers

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.Wemodel 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 --thelostrevenueasmeasured 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 discountingweakens and shows, in particular, that any seller algorithm will suffer linear strategic regret if there is no discounting.