Robert Kleinberg
ABSTRACT
What fraction of the potential social surplus in an environment can be extracted by a revenue-maximizing monopolist? We investigate this problem in Bayesian single-parameter environments with independent private values. The precise answer to the question obviously depends on the particulars of the environment: the feasibility constraint and the distributions from which the bidders' private values are sampled. Rather than solving the problem in particular special cases, our work aims to provide universal lower bounds on the revenue-to-welfare ratio that hold under the most general hypotheses that allow for non-trivial such bounds.
Our results can be summarized as follows. For general feasibility constraints, the revenue-to-welfare ratio is at least a constant times the inverse-square-root of the number of agents, and this is tight up to constant factors. For downward-closed feasibility constraints, the revenue-to-welfare ratio is bounded below by a constant. Both results require the bidders' distributions to satisfy hypotheses somewhat stronger than regularity; we show that the latter result cannot avoid this requirement.
- Abhishek, V. and Hajek, B. E. 2010. Efficiency loss in revenue optimal auctions. In Proceedings of the 49th IEEE Conference on Decision and Control, CDC 2010. 1082--1087.Google Scholar
- Aggarwal, G., Goel, G., and Mehta, A. 2009. Efficiency of (revenue-)optimal mechanisms. In Proceedings 10th ACM Conference on Electronic Commerce (EC-2009). 235--242. Google ScholarDigital Library
- Bulow, J. and Klemperer, P. 1996. Auctions versus negotiations. American Economic Review 86, 1, 180--94.Google Scholar
- Daskalakis, C. and Pierrakos, G. 2011. Simple, optimal and efficient auctions. In Proceedings of the 7th International Workshop on Internet and Network Economics (WINE-2011). Springer-Verlag, Berlin, Heidelberg, 109--121. Google ScholarDigital Library
- Dhangwatnotai, P., Roughgarden, T., and Yan, Q. 2010. Revenue maximization with a single sample. In Proceedings of the 11th ACM Conference on Electronic Commerce (EC-2010). ACM, New York, NY, USA, 129--138. Google ScholarDigital Library
- Erd\Hos, P. 1945. On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 52, 898--902.Google Scholar
- Fink, A. M. and Jodeit, M. 1984. On Chebyshev's other inequality. In Inequalities in Statistics and Probability: Proceedings of the Symposium on Inequalities in Statistics and Probability, October 27-30, 1982, Lincoln, Nebraska, Y. L. Tong and S. S. Gupta, Eds. Institute of Mathematical Statistics Lecture Notes - Monograph Series Series, vol. 5. 115--120.Google Scholar
- Hartline, J. D. and Roughgarden, T. 2009. Simple versus optimal mechanisms. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC-2009). 225--234. Google ScholarDigital Library
- Karlin, A. R., Nguyen, T., and Peres, Y. 2013. Selling in exclusive markets: Some observations on prior-free mechanism design. In ACM Transactions on Economics and Computation. Google ScholarDigital Library
- Littlewood, J. E. and Offord, A. C. 1943. On the number of real roots of a random algebraic equation. iii. Rec. Math. {Mat. Sbornik} N.S. 12, 277--286.Google Scholar
- Myerson, R. B. 1981. Optimal auction design. Mathematics of Operations Research 6, 1, pp. 58--73.Google ScholarDigital Library
- Sperner, E. 1928. Ein satz uber untermengen einer endlichen menge. Math. Zeitschrift 27, 544--548.Google ScholarCross Ref
Index Terms
- On the ratio of revenue to welfare in single-parameter mechanism design
Recommendations
On the ratio of revenue to welfare in single-parameter mechanism design
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerceWhat fraction of the potential social surplus in an environment can be extracted by a revenue-maximizing monopolist? We investigate this problem in Bayesian single-parameter environments with independent private values. The precise answer to the ...
Dynamic and Nonuniform Pricing Strategies for Revenue Maximization
† Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)We consider the item pricing problem for revenue maximization, where a single seller with multiple distinct items caters to multiple buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the prices on individual items, ...
Pricing to Maximize Revenue and Welfare Simultaneously in Large Markets
WINE 2016: Proceedings of the 12th International Conference on Web and Internet Economics - Volume 10123We study large markets with a single seller who can produce many types of goods, and many multi-minded buyers. The seller chooses posted prices for its many items, and the buyers purchase bundles to maximize their utility. For this setting, we consider ...
Comments