Optimal Revenue Guarantees for Pricing in Large Markets

Abstract

Posted price mechanisms (PPM) constitute one of the pre-dominant practices to price goods in online marketplaces and their rev-enue guarantees have been a central object of study in the last decade. Weconsider a basic setting where the buyers’ valuations are independent andidentically distributed and there is a single unit on sale. It is well-knownthat this setting is equivalent to the so-called i.i.d. prophet inequality,for which optimal guarantees are known and evaluate to 0.745 in gen-eral (equivalent to a PPM with dynamic prices) and 1 − 1/e ≈ 0.632in the fixed threshold case (equivalent to a fixed price PPM). In thispaper we consider an additional assumption, namely, that the under-lying market is very large. This is modeled by first fixing a valuationdistribution F and then making the number of buyers grow large, ratherthan considering the worst distribution for each possible market size. Inthis setting Kennedy and Kertz [Ann. Probab. 1991] breaks the 0.745fraction achievable in general with a dynamic threshold policy. We provethat this large market benefit continue to hold when using fixed pricePPMs, and show that the guarantee of 0.632 actually improves to 0.712.We then move to study the case of selling k identical units and we provethat the revenue gap of the fixed price PPM approaches 1 −1/√2kπ.Asthis bound is achievable without the large market assumption, we obtainthe somewhat surprising result that the large market advantage vanishesas k grows.