Asymptotically Efficient Multi-Unit Auctions via Posted Prices
share
We study the asymptotic average-case efficiency of static and anonymous posted prices for n agents and m(n) multiple identical items with m(n)=o(n/ n). When valuations are drawn i.i.d from some fixed continuous distribution (each valuation is a vector in _+^m and independence is assumed only across agents) we show: (a) for any "upper mass" distribution there exist posted prices such that the expected revenue and welfare of the auction approaches the optimal expected welfare as n goes to infinity; specifically, the ratio between the expected revenue of our posted prices auction and the expected optimal social welfare is 1-O(m(n) n/n), and (b) there do not exist posted prices that asymptotically obtain full efficiency for most of the distributions that do not satisfy the upper mass condition. When valuations are complete-information and only the arrival order is adversarial, we provide a "tiefree" condition that is sufficient and necessary for the existence of posted prices that obtain the maximal welfare. This condition is generically satisfied, i.e., it is satisfied with probability 1 if the valuations are i.i.d. from some continuous distribution.
READ FULL TEXT