Abstract

Motivated by the use of non-truthful auctions in practice (e.g. GSP, GFP) where bidders often offload their bidding strategy to a black-box optimizer, we consider the problem of selling a single item to a learning buyer. More specifically, each round the buyer draws a valuation v from D, chooses a bid b, and the seller then selects an allocation probability x and price \leq xb. The buyer's choice of bids will satisfy no-regret (in the sense that their final utility will be competitive with the best fixed bid mapping b(\cdot) in hindsight). We show the following:

1) There exists a no-regret learning strategy guaranteeing that the seller cannot extract revenue exceed the monopoly revenue from D (i.e. the best thing the seller can do against this strategy is to just post the same price every round).

2) If the bidder instead uses typical learning strategies like EXP3 or MWU, the seller has a strategy that can extract an unbounded multiplicative increase in revenue beyond the monopoly revenue.

Joint work with Mark Braverman, Jieming Mao, and Jon Schneider.