Abstract
We explore the revenue capabilities of truthful, monotone (“fair”) allocation and pricing functions for resource-constrained auction mechanisms within a general framework that encompasses unlimited supply auctions, knapsack auctions, and auctions with general non-decreasing convex production cost functions. We study and compare the revenue obtainable in each fair pricing scheme to the profit obtained by the ideal omniscient multi-price auction. We show (1) for capacitated knapsack auctions, no constant pricing scheme can achieve any approximation to the optimal profit, but proportional pricing is as powerful as general monotone pricing, and (2) for auction settings with arbitrary bounded non-decreasing convex production cost functions, we present a proportional pricing mechanism which achieves a poly-logarithmic approximation. Unlike existing approaches, all of our mechanisms have fair (monotone) prices, and all of our competitive analysis is with respect to the optimal profit extraction.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Streitfeld, D.: On the web, price tags blur: What you pay could depend on who you are (2000), http://www.washingtonpost.com/ac2/wp-dyn/A15159-2000Sep25
Wolverton, T.: Amazon backs away from test prices (2000), http://news.cnet.com/2100-1017-245631.html
Ramasastry, A.: Web sites change prices based on customers’ habits (2005), http://www.cnn.com/2005/LAW/06/24/ramasastry.website.prices/
Aggarwal, G., Hartline, J.: Knapsack Auctions. In: Proceedings of the Symposium on Discrete Algorithms (2006)
Goldberg, A., Hartline, J.: Envy-free auctions for digital goods. In: Proceedings of the 4th ACM conference on Electronic commerce, pp. 29–35. ACM, New York (2003)
Goldberg, A., Hartline, J., Karlin, A., Saks, M., Wright, A.: Competitive auctions. Games and Economic Behavior 55, 242–269 (2006)
Fiat, A., Goldberg, A., Hartline, J., Karlin, A.: Competitive generalized auctions. In: Proceedings of the thiry-fourth annual ACM symposium on Theory of Computing, pp. 72–81. ACM, New York (2002)
Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: SODA 2005: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1164–1173. Society for Industrial and Applied Mathematics, Philadelphia (2005)
Babaioff, M., Blumrosen, L., Roth, A.: Auctions with Online Supply (2009)
Balcan, M.F., Blum, A., Mansour, Y.: Item pricing for revenue maximization. In: EC 2008: Proceedings of the 9th ACM conference on Electronic commerce (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chung, C., Ligett, K., Pruhs, K., Roth, A.L. (2010). The Power of Fair Pricing Mechanisms. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_48
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)