Learning Optimal Reserve Price against Non-myopic Bidders
We consider the problem of learning optimal reserve price in repeated auctions against non-myopic bidders, who may bid strategically in order to gain in future rounds even if the single-round auctions are truthful. Previous algorithms, e.g., empirical pricing, do not provide non-trivial regret rounds in this setting in general. We introduce algorithms that obtain a small regret against non-myopic bidders either when the market is large, i.e., no single bidder appears in more than a small constant fraction of the rounds, or when the bidders are impatient, i.e., they discount future utility by some factor mildly bounded away from one. Our approach carefully controls what information is revealed to each bidder, and builds on techniques from differentially private online learning as well as the recent line of works on jointly differentially private algorithms.
Summary:  This paper studies the interesting and important problem of online learning for pricing problems when the buyers are strategic. There is a seller who interacts with a set of buyers over a series of time steps. The seller has a fresh copy of the good for sale every day. She sets a price at the beginning of each day. Then, a bidder arrives and submits a bid: If the bid is higher than the price of the day, he gets the item and pays the price. The question is: how should the seller set the price? He could use an off-the-shelf no-regret learning algorithm. However, if the same buyer returns several times, she might be incentivized to misreport her value in order to fool the learning algorithm into giving her a lower price. Much of the existing literature on this topic assumes the buyers are myopic, which means they do not take future rounds into account when bidding in the current round. This paper does not make this assumption.  This paper presents a no-regret pricing algorithm that satisfies a relaxed version of incentive compatibility. It works under one of two assumptions: Either the bidders discount utility in future rounds by some discount factor bounded away from 1, or any one bidder comes in only a small fraction of the rounds. Their algorithm discretizes the set of prices and treats each discretized point as an expert. At each round, each expert’s reward equals their corresponding price if the bidder bid above their price, and zero otherwise. The algorithm uses an existing differentially privacy tool called “tree-aggregation” to keep track of noisy estimates of each expert’s gain. The algorithm picks a reserve on each day using follow-the-perturbed-leader. The authors generalize to multiple bidders and multiple units of items for sale, too.  Comments:  According to the authors, one of the key insights is to use joint differential privacy rather than differential privacy itself. However, joint differential privacy is not mentioned in Section 3 as far as I can tell, which is a little confusing. Perhaps this is because Section 3 is a simplified version of their main algorithm. In my experience, take-it-or-leave-it auctions, which are commonly referred to as posted price mechanisms, do not take bids as input. The buyer either buys the good and pays the price, or does not buy the good. In what scenario would he be required to submit a bid?   The authors write that online learning for auction design has only been studied “very recently” (line 16), which is not true. For example, see the following paper and subsequent work. Kleinberg and Leighton. The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. FOCS 2003.  The authors write that “typical mechanism design approach may seek to design online learning mechanisms such that truthful bidding forms an equilibrium (or even better, are dominating strategies) even if bidders are non-myopic, and to get small regret given truthful bids. However, designing truthful mechanisms that learn in repeated auctions seems beyond the scope of existing techniques.” Can the author comment on what they mean by “beyond the scope of existing techniques?” Isn’t the point of research to come up with new techniques? :-) I think it’s fine to pursue the path the authors chose, but I’d recommend finding a better argument.  In the related work, the authors write that “most previous work achieved approximate incentive compatibility so that misreporting cannot increases a bidder’s utility by more than an epsilon amount.” In contrast, the authors’ relaxed version of incentive compatibility ensures that “bidders would only submit ‘reasonable’ bids within a small neighborhood of the true values.” What are the pros and cons of both relaxations to incentive compatibility? This might be helpful for understanding why there ought to be another paper on this topic.  =====================After rebuttal===================== Thanks for the clarifications!