Repeated Contextual Auctions with Strategic Buyers
Venue
Advances in Neural Information Processing Systems (2014)
Publication Year
2014
Authors
Kareem Amin, Afshin Rostamizadeh, Umar Syed
BibTeX
Abstract
Motivated by real-time advertising exchanges, we analyze the problem of pricing
inventory in a repeated posted-price auction. We consider both the cases of a
truthful and surplus-maximizing buyer, where the former makes decisions myopically
on every round, and the latter may strategically react to our algorithm, forgoing
short-term surplus in order to trick the algorithm into setting better prices in
the future. We further assume a buyer’s valuation of a good is a function of a
context vector that describes the good being sold. We give the first algorithm
attaining sublinear (O(T^{ 2/3})) regret in the contextual setting against a
surplus-maximizing buyer. We also extend this result to repeated second-price
auctions with multiple buyers.
