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. 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.
This paper explores the problem of online learning 
      near-optimal posted-prices when facing the same strategic buyer in 
      repeated auctions. Assuming the buyer’s discount factor is large enough, 
      when the buyer value is an unknown fixed value, the authors propose an 
      algorithm which monotonically decrease posted-prices and show that the 
      algorithm only suffers sublinear regrets. When the buyer value is drawn 
      from a distribution, the authors propose a multi-phase 
      exploration-exploitation algorithm with no-regret. The exploration is not 
      just for estimating the buyer value, it also discourages buyers to 
      manipulate the algorithm. In the end, the authors also show that if the 
      buyer discount factor is not *large enough*, it’s impossible to have any 
      no-regret algorithms. In general, I like this paper and think it 
      addresses a very interesting problem. Most other online pricing papers 
      usually assume buyers are myopic or just participate once. It’s nice to 
      see that given some conditions, no-regret algorithms are still possible 
      even if the buyer participates multiple times and are strategic. 
      Below are some detailed comments. - In the stochastic 
      value setting, you assume the set of possible prices is finite. Although I 
      think it’s fine to assume finite possible prices (if we consider the 
      minimum unit of currency), the result is still slightly unsatisfying 
      especially your regret bound depends on both the number of possible prices 
      and \Delta_p (\Delta_p would be very small if the prices are close.) That 
      being said, I still like the current result. I just think it would be much 
      nicer to see discussion for infinite or large number of possible prices. 
      - The analysis is sometimes hard to follow. In particular, some 
      notations are used without being defined (e.g., c_{beta,gamma} and 
      d_{beta,gamma} in Theorem 1.) I know they are defined in the appendix, but 
      it would be helpful to mentioned it in the main text. It would also be 
      helpful to put more intuitions in the main paper. For example, there are 
      some nice proof intuitions in the appendix (e.g., the proof in Appendix 
      B). I think it would help to put some of them in the main text if space 
      allows.