extended-abstract

The menu-size complexity of auctions

Authors:

Sergiu Hart,

Noam NisanAuthors Info & Claims

EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

Pages 565 - 566

https://doi.org/10.1145/2492002.2482544

Published: 16 June 2013 Publication History

Get Access

Abstract

We consider the menu size of auctions as a measure of auction complexity and study how it affects revenue. Our setting has a single revenue-maximizing seller selling two or more heterogeneous items to a single buyer whose private values for the items are drawn from a (possibly correlated) known distribution, and whose valuation is additive over the items. We show that the revenue may increase arbitrarily with menu size and that a bounded menu size can not ensure any positive fraction of the optimal revenue. The menu size turns out to "nail down" the revenue properties of deterministic auctions: their menu size may be at most exponential in the number of items and indeed their revenue may be larger than that achievable by the simplest types of auctions by a factor that is exponential in the number of items but no larger. Our model is related to a previously studied "unit-demand" model and our results also answer an open problem in that model.

Cited By

View all

Shan LZhang SZhang JWang ZChua TNgo CKa-Wei Lee RKumar RLauw H(2024)On Truthful Item-Acquiring Mechanisms for Reward MaximizationProceedings of the ACM Web Conference 202410.1145/3589334.3645345(25-35)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645345
Balseiro SDeng YMao JMirrokni VZuo S(2023)Optimal Mechanisms for a Value Maximizer: The Futility of Screening TargetsSSRN Electronic Journal10.2139/ssrn.4351927Online publication date: 2023
https://doi.org/10.2139/ssrn.4351927
Gonczarowski YWeinberg S(2021)The Sample Complexity of Up-to-ε Multi-dimensional Revenue MaximizationJournal of the ACM10.1145/343972268:3(1-28)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3439722
Show More Cited By

Index Terms

The menu-size complexity of auctions
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics

Recommendations

The menu-size complexity of auctions
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We consider the menu size of auctions as a measure of auction complexity and study how it affects revenue. Our setting has a single revenue-maximizing seller selling two or more heterogeneous items to a single buyer whose private values for the items ...
Procurement Auctions for Differentiated Goods

We consider two mechanisms to procure differentiated goods: a sealed-bid buyer-determined auction and a dynamic-bid price-based auction with bidding credits. The sealed-bid buyer-determined auction is analogous to the “request for quote” procedure ...
Lower bounds on revenue of approximately optimal auctions
WINE'12: Proceedings of the 8th international conference on Internet and Network Economics

We obtain revenue guarantees for the simple pricing mechanism of a single posted price, in terms of a natural parameter of the distribution of buyers' valuations. Our revenue guarantee applies to the single item n buyers setting, with values drawn from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

June 2013

924 pages

ISBN:9781450319621

DOI:10.1145/2492002

General Chair:
Michael Kearns
University of Pennsylvania., USA
,
Program Chairs:
Preston McAfee
Google, USA
,
Éva Tardos
Cornell University, USA

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.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2013

Check for updates

Author Tags

Qualifiers

Extended-abstract

Conference

EC '13

Sponsor:

SIGecom

EC '13: ACM Conference on Electronic Commerce

June 16 - 20, 2013

Pennsylvania, Philadelphia, USA

Acceptance Rates

EC '13 Paper Acceptance Rate 72 of 223 submissions, 32%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
167
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shan LZhang SZhang JWang ZChua TNgo CKa-Wei Lee RKumar RLauw H(2024)On Truthful Item-Acquiring Mechanisms for Reward MaximizationProceedings of the ACM Web Conference 202410.1145/3589334.3645345(25-35)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645345
Balseiro SDeng YMao JMirrokni VZuo S(2023)Optimal Mechanisms for a Value Maximizer: The Futility of Screening TargetsSSRN Electronic Journal10.2139/ssrn.4351927Online publication date: 2023
https://doi.org/10.2139/ssrn.4351927
Gonczarowski YWeinberg S(2021)The Sample Complexity of Up-to-ε Multi-dimensional Revenue MaximizationJournal of the ACM10.1145/343972268:3(1-28)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3439722
Chen JLi BLi YLu P(2021)Bayesian Auctions with Efficient QueriesArtificial Intelligence10.1016/j.artint.2021.103630(103630)Online publication date: Nov-2021
https://doi.org/10.1016/j.artint.2021.103630
Devanur NHaghpanah NPsomas A(2020)Optimal Multi-Unit Mechanisms with Private DemandsGames and Economic Behavior10.1016/j.geb.2020.03.007Online publication date: Apr-2020
https://doi.org/10.1016/j.geb.2020.03.007
Shen WTang PZuo SElkind EVeloso MAgmon NTaylor M(2019)Automated Mechanism Design via Neural NetworksProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331696(215-223)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331696
Gravin NLu P(2019)Correlation-robust mechanism designACM SIGecom Exchanges10.1145/3331041.333104716:2(45-52)Online publication date: 7-May-2019
https://dl.acm.org/doi/10.1145/3331041.3331047
Cai YZhao M(2019)Simple mechanisms for subadditive buyers via dualityACM SIGecom Exchanges10.1145/3331033.333103717:1(39-53)Online publication date: 7-May-2019
https://dl.acm.org/doi/10.1145/3331033.3331037
Chawla STeng YTzamos CKarlin AImmorlica NJohari R(2019)Buy-Many Mechanisms are Not Much Better than Item PricingProceedings of the 2019 ACM Conference on Economics and Computation10.1145/3328526.3329583(237-238)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3328526.3329583
Psomas ASchvartzman AWeinberg SKarlin AImmorlica NJohari R(2019)Smoothed Analysis of Multi-Item Auctions with Correlated ValuesProceedings of the 2019 ACM Conference on Economics and Computation10.1145/3328526.3329563(417-418)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3328526.3329563
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

The menu-size complexity of auctions

Procurement Auctions for Differentiated Goods

Lower bounds on revenue of approximately optimal auctions