The Competition Complexity of Dynamic Pricing: For ε > 0, m ≥ ϕ(ε)n Buyers Give (1 + ε)Aₘ(F) ≥ Mₙ(F) for Every F, Asymptotically Tight, with ϕ(ε) = Θ(log log 1/ε)Research Paper
A seller with one item faces buyers whose values are drawn i.i.d. from a distribution . The welfare-optimal mechanism is an auction: it allocates to the highest bidder and achieves , the expected maximum of values. Dynamic pricing, which offers the item to the buyers one at a time at prices that may depend on the remaining number of buyers, is…