Prior-Free Mechanism with Welfare Guarantees
Pages 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.
Supplemental Material
WEBM File
Supplemental video
- Download
- 7.73 MB
References
[1]
Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. 2022. Learning-augmented mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference on Economics and Computation. 497--528.
[2]
Pablo Daniel Azar, Robert Kleinberg, and S. Matthew Weinberg. 2014. Prophet Inequalities with Limited Information. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 1358--1377.
[3]
Nir Bachrach and Inbal Talgam-Cohen. 2022. Distributional Robustness: From Pricing to Auctions. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC '22). Association for Computing Machinery, 150.
[4]
Ethan Che. 2022. Robustly Optimal Auction Design under Mean Constraints. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC '22). Association for Computing Machinery, 153--181.
[5]
Ning Chen, Nick Gravin, and Pinyan Lu. 2014. Optimal competitive auctions. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 253--262.
[6]
Richard Cole and Tim Roughgarden. 2014. The sample complexity of revenue maximization. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 243--252.
[7]
José R. Correa, Paul Dütting, Felix A. Fischer, and Kevin Schewior. 2019. Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution. In Proceedings of the 2019 ACM Conference on Economics and Computation. 3--17.
[8]
Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan. 2015. Revenue maximization with a single sample. Games Econ. Behav. 91 (2015), 318--333.
[9]
Jack Edmonds. 1971. Matroids and the greedy algorithm. Mathematical programming 1 (1971), 127--136.
[10]
Amos Fiat, Andrew V Goldberg, Jason D Hartline, and Anna R Karlin. 2002. Competitive generalized auctions. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. 72--81.
[11]
Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. 2022. Improved price of anarchy via predictions. In Proceedings of the 23rd ACM Conference on Economics and Computation. 529--557.
[12]
Andrew V Goldberg and Jason D Hartline. 2001. Competitive auctions for multiple digital goods. In European Symposium on Algorithms. Springer, 416--427.
[13]
Andrew V Goldberg, Jason D Hartline, Anna R Karlin, Michael Saks, and Andrew Wright. 2006. Competitive auctions. Games and Economic behavior 55, 2 (2006), 242--269.
[14]
Parikshit Gopalan, Noam Nisan, and Tim Roughgarden. 2018. Public projects, boolean functions, and the borders of border's theorem. ACM Transactions on Economics and Computation (TEAC) 6, 3--4 (2018), 1--21.
[15]
Jason Hartline. 2011. Mechanism Design and Approximation. self-published. https://jasonhartline.com/MDnA/.
[16]
Robert Kleinberg and Tom Leighton. 2003. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 594--605.
[17]
Robert Kleinberg and Yang Yuan. 2013. On the ratio of revenue to welfare in single-parameter mechanism design. In Proceedings of the fourteenth ACM conference on Electronic commerce. 589--602.
[18]
Stefano Leonardi and Tim Roughgarden. 2012. Prior-free auctions with ordered bidders. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing. 427--434.
[19]
Michael Mitzenmacher and Sergei Vassilvitskii. 2022. Algorithms with predictions. Commun. ACM 65, 7 (2022), 33--35.
[20]
Roger B Myerson. 1981. Optimal auction design. Mathematics of operations research 6, 1 (1981), 58--73.
[21]
Robert Wilson. 1985. Game-theoretic analyses of trading processes. Institute for Mathematical Studies in the Social Sciences, Stanford University.
Index Terms
- Prior-Free Mechanism with Welfare Guarantees
Recommendations
Price Competition, Fluctuations and Welfare Guarantees
EC '15: Proceedings of the Sixteenth ACM Conference on Economics and ComputationIn various markets where sellers compete in price, price oscillations are observed rather than convergence to equilibrium. Such fluctuations have been empirically observed in the retail market for gasoline, in airline pricing and in the online sale of ...
Welfare guarantees for combinatorial auctions with item bidding
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithmsWe analyze the price of anarchy (POA) in a simple and practical non-truthful combinatorial auction when players have subadditive valuations for goods. We study the mechanism that sells every good in parallel with separate second-price auctions. We first ...
Positive results for mechanism design without money
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systemsConsider the problem of allocating multiple divisible goods to two agents in a strategy-proof fashion without the use of payments or priors. Previous work has aimed at implementing allocations that are competitive with respect to an appropriately ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
4826 pages
ISBN:9798400701719
DOI:10.1145/3589334
- General Chairs:
- Tat-Seng Chua,
- Chong-Wah Ngo,
- Proceedings Chair:
- Roy Ka-Wei Lee,
- Program Chairs:
- Ravi Kumar,
- Hady W. Lauw
Copyright © 2024 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
WWW '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 155Total Downloads
- Downloads (Last 12 months)155
- Downloads (Last 6 weeks)23
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in