research-article

Efficient empirical revenue maximization in single-parameter auction environments

Authors:

Yannai A. Gonczarowski,

Noam NisanAuthors Info & Claims

STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

Pages 856 - 868

https://doi.org/10.1145/3055399.3055427

Published: 19 June 2017 Publication History

Get Access

Abstract

We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.

Supplementary Material

MP4 File (d3_sb_t6.mp4)

Download
159.42 MB

References

[1]

Yakov Babichenko, Siddharth Barman, and Ron Peretz. 2017. Empirical distribution of equilibrium play and its testing application. Mathematics of Operations Research 42, 1 (2017), 15–29. Preliminary version (“Simple approximate equilibria in large games”) in Proceedings of the 15th ACM Conference on Economics and Computation (EC), 2014.

Digital Library

Google Scholar

[2]

Truthful approximation mechanisms for restricted combinatorial auctions. Games and Economic Behavior 64, 2 (2008), 612–631. Roger Myerson. 1981. Optimal auction design. Mathematics of Operations Research 6, 1 (1981), 58–73. Tim Roughgarden. 2016.

Google Scholar

[3]

Twenty Lectures on Algorithmic Game Theory. Cambridge University Press.

Digital Library

Google Scholar

Cited By

View all

Dütting PFeng ZNarasimhan HParkes DRavindranath S(2024)Optimal Auctions through Deep Learning: Advances in Differentiable EconomicsJournal of the ACM10.1145/363074971:1(1-53)Online publication date: 11-Feb-2024
https://dl.acm.org/doi/10.1145/3630749
Cai YFeng ZLiaw CMehta AVelegkas GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)User Response in Ad Auctions: An MDP Formulation of Long-term Revenue OptimizationProceedings of the ACM Web Conference 202410.1145/3589334.3645495(111-122)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645495
Ammann SStiller S(2024)Near-Optimal Auctions on Independence SystemsTheory of Computing Systems10.1007/s00224-024-10189-568:5(1160-1179)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00224-024-10189-5
Show More Cited By

Index Terms

Efficient empirical revenue maximization in single-parameter auction environments
1. Theory of computation
  1. Design and analysis of algorithms
  2. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
    2. Machine learning theory
      1. Sample complexity and generalization bounds

Recommendations

The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization
We consider the sample complexity of revenue maximization for multiple bidders in unrestricted multi-dimensional settings. Specifically, we study the standard model of additive bidders whose values for heterogeneous items are drawn independently. For ...
Differentially private spectrum auction with approximate revenue maximization
MobiHoc '14: Proceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing

Dynamic spectrum redistribution---under which spectrum owners lease out under-utilized spectrum to users for financial gain---is an effective way to improve spectrum utilization. Auction is a natural way to incentivize spectrum owners to share their idle ...
Revenue Guarantees in the Generalized Second Price Auction
Special Issue on Pricing and Incentives in Networks and Systems and Regular Papers

Sponsored search auctions are the main source of revenue for search engines. In such an auction, a set of utility maximizing advertisers competes for a set of ad slots. The assignment of advertisers to slots depends on the bids they submit; these bids ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

June 2017

1268 pages

ISBN:9781450345286

DOI:10.1145/3055399

General Chairs:
Hamed Hatami
McGill University
,
Pierre McKenzie
Université de Montréal
,
Program Chair:
Valerie King
University of Victoria

Permission to make digital or hard copies of all or part 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 components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Israel Academy of Sciences and Humanities
Israel Science Foundation
United States-Israel Binational Science Foundation

Conference

STOC '17

Sponsor:

SIGACT

STOC '17: Symposium on Theory of Computing

June 19 - 23, 2017

Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
128
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)3

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dütting PFeng ZNarasimhan HParkes DRavindranath S(2024)Optimal Auctions through Deep Learning: Advances in Differentiable EconomicsJournal of the ACM10.1145/363074971:1(1-53)Online publication date: 11-Feb-2024
https://dl.acm.org/doi/10.1145/3630749
Cai YFeng ZLiaw CMehta AVelegkas GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)User Response in Ad Auctions: An MDP Formulation of Long-term Revenue OptimizationProceedings of the ACM Web Conference 202410.1145/3589334.3645495(111-122)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645495
Ammann SStiller S(2024)Near-Optimal Auctions on Independence SystemsTheory of Computing Systems10.1007/s00224-024-10189-568:5(1160-1179)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00224-024-10189-5
Mashiah EAttias IMansour YWilliams BChen YNeville J(2023)Learning revenue maximization using posted prices for stochastic strategic patient buyersProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i8.26091(9090-9098)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i8.26091
Chen ZHuang ZMajdi DYan ZLeyton-Brown KSamuelson LHartline J(2023)Strong Revenue (Non-)Monotonicity of Single-parameter AuctionsProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597745(452-471)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597745
Cai LWeinberg SWildenhain EZhang S(2023)Selling to Multiple No-Regret BuyersWeb and Internet Economics10.1007/978-3-031-48974-7_7(113-129)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-48974-7_7
Ivanov DSafiulin IFilippov IBalabaeva KKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Optimal-er auctions through attentionProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602787(34734-34747)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602787
Vitercik EYan TRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Revenue maximization via machine learning with noisy dataProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541065(10510-10523)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3541065
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
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

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 Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization

Differentially private spectrum auction with approximate revenue maximization

Revenue Guarantees in the Generalized Second Price Auction