Bandit Sequential Posted Pricing via Half-Concavity
Sahil Singla Yifan Wang
Sequential posted pricing auctions are popular because of their simplicity in
practice and their tractability in theory. A usual assumption in their study is
that the Bayesian prior distributions of the buyers are known to the seller,
while in reality these priors can only be accessed from historical data. To
overcome this assumption, we study sequential posted pricing in the bandit
learning model, where the seller interacts with $n$ buyers over $T$ rounds: In
each round the seller posts $n$ prices for the $n$ buyers and the first buyer
with a valuation higher than the price takes the item. The only feedback that
the seller receives in each round is the revenue.
  Our main results obtain nearly-optimal regret bounds for single-item
sequential posted pricing in the bandit learning model. In particular, we
achieve an $\tilde{O}(\mathsf{poly}(n)\sqrt{T})$ regret for buyers with
(Myerson's) regular distributions and an
$\tilde{O}(\mathsf{poly}(n)T^{{2}/{3}})$ regret for buyers with general
distributions, both of which are tight in the number of rounds $T$. Our result
for regular distributions was previously not known even for the single-buyer
setting and relies on a new half-concavity property of the revenue function in
the value space. For $n$ sequential buyers, our technique is to run a
generalized single-buyer algorithm for all the buyers and to carefully bound
the regret from the sub-optimal pricing of the suffix buyers.