Repeated Contextual Auctions with Strategic Buyers
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 (Õ(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.
This paper introduces the problem of repeated auctions with contextual information. Specifically, the auctioneer interacts with a single agent (at least in their initial model) who has a context vector x, corresponding to observable attributes, and a privately held weight vector w, such that the agent’s value for the good is x*w. The goal of the auctioneer is to maximize the revenue from the posted price auction by learning w over time. However, the agent understand that the auctioneer may be adjusting prices based off of the his purchasing behavior, so he may lie (that is, not purchase the product even though it would give him positive surplus) in order to lower the price in future rounds. The authors present an algorithm based on stochastic gradient descent. The authors prove that the number of “lies” by an agent is mitigated b the agent’s discount factor for future utility and use existing results to show that these bounded number of lies do not affect the learning algorithm too much, thereby bounding the “strategic regret” in this model. I like this paper and I view its main contribution as introducing the use of contextual information to repeated auctions. The authors make a good point that the reason that so many auctions on the web have only a single participant is because of targeting, so it seems natural that the mechanism itself should be able to use targeted information (i.e. context) to set prices.I think this model (or at least this family of models) is very compelling and raises a lot of interesting questions. This paper does a good job at beginning to address this model and will inspire more work to be done on this area.The technical strength of this paper is solid, primarily consisting of extending existing techniques to the details of this model (although this is not a trivial task) and the exposition is relatively clear. The technical strength could have been improved via discussion of regret lower bounds in this model. It would have been nice to have a deeper understanding of regret lower bounds in this model versus similar models without context (e.g. Amin et al 2013). However this seems like significant extra work and is reasonably outside the scope of this paper. I found the section on multiple buyers a little unconvincing, which is not to imply that I believe it is wrong, but rather that the extension from posted-pricing to a reserve price auction is not straightforward and warrants more exposition/exploration. Its not obvious how the LEAP algorithm extends in the case of multiple buyers during the exploit phase. Presumably, the algorithm realizes the context vectors for all agents and then posts a reserve price of max_{i in N} x_i * w_t but this is not actually stated. As the authors note, the “market value” assumption seems a little odd; its not clear that one can simply convert between the two settings (that is, taking the maximum of a number of agents versus just acting as if there were one agent that always had the maximum value). Personally, I’m more interested in expanding this case than I am in the extension of non-linear valuation functions and I wish the paper had expanded more on these details rather than showing kernelized extension. Beyond these small confusions, it seems that the multiple bidder setting has more complexity and nuance than presented in this paper. For example, it seems that more buyers should decrease regret in a number of ways. First, more buyers should increase the effect of the discount factor because, all else being equal, a buyer will expect to wait a longer time to purchase in the future (because now he needs to take into consideration the probability that he has the highest valuation amongst the group of agents that show up in any given round). Under the assumption of IID valuations, this should increase his expected wait time by a factor K (the number of players), hence decreasing his future utility exponentially (due to discounting). So it seems that lying should become less of an issue. In terms of related work, the authors could connect better to the study of contextual multi-armed bandits as the settings are similar. In summary, I think this work is a valuable contribution because this is a good model, in the sense that is practically relevant and is an interesting example of the intersection of machine learning and algorithmic game theory. The case of multiple bidders case is more complex than the current work considers and deserves future work but the work is technically strong enough with the single agent model.