Chung, Christine and Ligett, Katrina and Pruhs, Kirk and Roth, Aron (2012) The Power of Fair Pricing Mechanisms. Algorithmica, 63 (3). pp. 634-644. ISSN 0178-4617 http://resolver.caltech.edu/CaltechAUTHORS:20120319-102934819
Full text not available from this repository.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120319-102934819
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 that 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. In addition, 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.
|Additional Information:||© 2011 Springer Science. Received: 5 August 2010. Accepted: 15 October 2011. Published online: 18 November 2011. We would like to thank several anonymous referees for thoughtful and helpful comments on earlier versions of this work.|
|Official Citation:||The Power of Fair Pricing Mechanisms 634-644 Christine Chung, Katrina Ligett, Kirk Pruhs and Aaron Roth|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Ruth Sustaita|
|Deposited On:||19 Mar 2012 17:50|
|Last Modified:||19 Mar 2012 17:50|
Repository Staff Only: item control page