Prior-Free Mechanism with Welfare Guarantees
Open Access
- 13 May 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 135-143
Abstract
We consider the problem of designing prior-free revenue-maximizing mechanisms for allocating items to n buyers when the mechanism is additionally provided with an estimate for the optimal welfare (which is guaranteed to be correct to within a multiplicative factor of 1/α). In the digital goods setting (where we can allocate items to an arbitrary subset of the buyers), we demonstrate a mechanism that achieves revenue that is O(log n/α)-competitive with the optimal welfare. In the public goods setting (where we either must allocate the item to all buyers or to no buyers), we demonstrate a mechanism which is O(n log 1/α) competitive. In both settings, we show the dependence on α and n is tight. Finally, we discuss generalizations to broader classes of allocation constraints.Keywords
This publication has 17 references indexed in Scilit:
- Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location2022
- Improved Price of Anarchy via Predictions2022
- Robustly Optimal Auction Design under Mean Constraints2022
- Algorithms with predictionsCommunications of the ACM, 2022
- Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution2019
- Revenue maximization with a single sampleGames and Economic Behavior, 2015
- Optimal competitive auctions2014
- The sample complexity of revenue maximization2014
- Prior-free auctions with ordered bidders2012
- The value of knowing a demand curve: bounds on regret for online posted-price auctions2004