More Web Proxy on the site http://driver.im/

Article

Designing and learning optimal finite support auctions

Author:

Edith ElkindAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 736 - 745

Published: 07 January 2007 Publication History

Abstract

A classical paper of Myerson [18] shows how to construct an optimal (revenue-maximizing) auction in a model where bidders' values are drawn from known continuous distributions. In this paper we show how to adapt this approach to finite support distributions that may be partially unknown. We demonstrate that a Myerson-style auction can be constructed in time polynomial in the number of bidders and the size of the support sets. Next, we consider the scenario where the mechanism designer knows the support sets, but not the probability of each value. In this situation, we show that the optimal auction may be learned in polynomial time using a weak oracle that, given two candidate auctions, returns one with a higher expected revenue. To study this problem, we introduce a new class of truthful mechanisms which we call order-based auctions. We show that the optimal mechanism is an order-based auction and use the internal structure of this class to prove the correctness of our learning algorithm as well as to bound its running time.

References

[1]

G. Aggarwal and J. Hartline, Knapsack auctions. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1083--1092, 2006

Digital Library

[2]

M.-F Balcan, A. Blum, J. Hartline, and Y. Man-sour, Mechanism design via machine learning. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 605--614, 2005

Digital Library

[3]

A. Blum and J. Hartline, Near-optimal online auctions. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1156--1163, 2005

Digital Library

[4]

Z. Bar-Yossef, K. Hildrum, and F. Wu, Incentive-compatible online auctions for digital goods. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 964--970, 2002

Digital Library

[5]

D. Bergemann and M. Pesendorfer, Information structures in optimal auctions. Cowles Foundation Discussion Papers 1323, Cowles Foundation, Yale University, 2001

[6]

A. Blum, V. Kumar, A. Rudra, and F. Wu, Online learning in online auctions. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 202--204, 2003

Digital Library

[7]

J. Bulow and J. Roberts, The simple economics of optimal auctions. The Journal of Political Economy, 97:1060--90, 1989

[8]

H. Cheng, Optimal auction design with discrete bidding. Working paper, May 2004

[9]

J. Cremer and R. Mclean, Full extraction of the surplus in bayesian and dominant strategy auctions. Econometrica, 56:1247--1257, 1988

[10]

E. Elkind, Computational Issues in Optimal Auction Design. PhD thesis, Princeton University, 2005

Digital Library

[11]

E. Elkind, Optimal auctions with finite support. In DIMACS Workshop on Computational Issues in Auction Design, 2004

[12]

A. Fiat, A. Goldberg, J. Hartline, and A. Karlin, Competitive generalized auctions. In Proceedings of the 34th Annual ACM Symposium on Theory of Computation, pages 72--81, 2002

Digital Library

[13]

A. Goldberg, J. Hartline, and A. Wright, Competitive auctions and digital goods. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 735--744, 2001

Digital Library

[14]

M. Hajiaghayi, R. Kleinberg, and D. Parkes, Adaptive limited-supply online auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 71--80, 2004

Digital Library

[15]

R. Kleinberg, F. Leighton, 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, pages 594--605, 2003

Digital Library

[16]

V. Krishna, Auction Theory. Academic Press, 2002

[17]

H. Lipmaa, N. Asokan, and V. Niemi, Secure Vickrey auctions without threshold trust. In Proceedings of the 6th Annual Conference on Financial Cryptography, pages 87--101, 2002

Digital Library

[18]

R. Myerson, Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981

[19]

M. Naor, B. Pinkas, and R. Sumner, Privacy preserving auctions and mechanism design. In ACM Conference on Electronic Commerce pages 129--139, 1999

Digital Library

[20]

A. Ronen, On approximating optimal auctions. In ACM Conference on Electronic Commerce, pages 11--17, 2001

Digital Library

[21]

A. Ronen and A. Saberi, On the hardness of optimal auctions. In Proceedings of the 43rd Symposium on Foundations of Computer Science, pages 396--405, 2002

Digital Library

[22]

W. Vickrey, Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961

Cited By

Cai YWu JSaha BServedio R(2023)On the Optimal Fixed-Price Mechanism in Bilateral TradeProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585171(737-750)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585171
Bubeck SDevanur NHuang ZNiazadeh R(2021)Multi-scale online learningThe Journal of Machine Learning Research10.5555/3322706.336200320:1(2248-2284)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.5555/3322706.3362003
Alon TDütting PTalgam-Cohen IBiró PChawla SEchenique F(2021)Contracts with Private Cost per Unit-of-EffortProceedings of the 22nd ACM Conference on Economics and Computation10.1145/3465456.3467651(52-69)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465456.3467651
Show More Cited By

Recommendations

Simple, Credible, and Approximately-Optimal Auctions
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

We present a general framework for designing approximately revenue-optimal mechanisms for multi-item additive auctions. Our approach adapts the duality framework of Cai, Devanur and Weinberg (STOC 2016) and applies to both truthful and non-truthful ...
Optimal auctions for partially rational bidders
IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence

We investigate the problem of revenue optimal mechanism design [Myerson, 1981] under the context of the partial rationality model, where buyers randomize between two modes: rational and irrational. When a buyer is irrational (can be thought of as lazy), ...
Incentive-Compatible Learning of Reserve Prices for Repeated Auctions
How can an auctioneer optimize revenue by learning the reserve prices from the bids in the previous auctions? How should the long-term incentives and strategic behavior of the bidders be taken into account? Motivated in part by applications in online ...
Large fractions of online advertisements are sold via repeated second-price auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
284
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)7

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cai YWu JSaha BServedio R(2023)On the Optimal Fixed-Price Mechanism in Bilateral TradeProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585171(737-750)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585171
Bubeck SDevanur NHuang ZNiazadeh R(2021)Multi-scale online learningThe Journal of Machine Learning Research10.5555/3322706.336200320:1(2248-2284)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.5555/3322706.3362003
Alon TDütting PTalgam-Cohen IBiró PChawla SEchenique F(2021)Contracts with Private Cost per Unit-of-EffortProceedings of the 22nd ACM Conference on Economics and Computation10.1145/3465456.3467651(52-69)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465456.3467651
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
Daskalakis CZampetakis MBiró PHartline JOstrovsky MProcaccia A(2020)More Revenue from Two Samples via Factor Revealing SDPsProceedings of the 21st ACM Conference on Economics and Computation10.1145/3391403.3399543(257-272)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.1145/3391403.3399543
Brustle JCai YDaskalakis CBiró PHartline JOstrovsky MProcaccia A(2020)Multi-Item Mechanisms without Item-Independence: Learnability via RobustnessProceedings of the 21st ACM Conference on Economics and Computation10.1145/3391403.3399541(715-761)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.1145/3391403.3399541
Abernethy JCummings RKumar BMorgenstern JTaggart SWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Learning auctions with robust incentive guaranteesProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455327(11591-11601)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455327
Hartline JTaggart SKarlin AImmorlica NJohari R(2019)Sample Complexity for Non-Truthful MechanismsProceedings of the 2019 ACM Conference on Economics and Computation10.1145/3328526.3329632(399-416)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3328526.3329632
Guo CHuang ZZhang XCharikar MCohen E(2019)Settling the sample complexity of single-parameter revenue maximizationProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316325(662-673)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316325
Gopalan PNisan NRoughgarden T(2018)Public Projects, Boolean Functions, and the Borders of Border’s TheoremACM Transactions on Economics and Computation10.1145/32746456:3-4(1-21)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3274645
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents