Optimal competitive auctions

DOI10.1145/2591796.2591855zbMATH Open1315.91025arXiv1401.0880OpenAlexW2077881254MaRDI QIDQ5259559FDOQ5259559

Authors: Ning Chen, Pinyan Lu, N. V. Gravin 

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: We study the design of truthful auctions for selling identical items in unlimited supply (e.g., digital goods) to n unit demand buyers. This classic problem stands out from profit-maximizing auction design literature as it requires no probabilistic assumptions on buyers' valuations and employs the framework of competitive analysis. Our objective is to optimize the worst-case performance of an auction, measured by the ratio between a given benchmark and revenue generated by the auction. We establish a sufficient and necessary condition that characterizes competitive ratios for all monotone benchmarks. The characterization identifies the worst-case distribution of instances and reveals intrinsic relations between competitive ratios and benchmarks in the competitive analysis. With the characterization at hand, we show optimal competitive auctions for two natural benchmarks. The most well-studied benchmark $mathcal{F}^{(2)}(cdot)$ measures the envy-free optimal revenue where at least two buyers win. Goldberg et al. [13] showed a sequence of lower bounds on the competitive ratio for each number of buyers n. They conjectured that all these bounds are tight. We show that optimal competitive auctions match these bounds. Thus, we confirm the conjecture and settle a central open problem in the design of digital goods auctions. As one more application we examine another economically meaningful benchmark, which measures the optimal revenue across all limited-supply Vickrey auctions. We identify the optimal competitive ratios to be $(fracnn-1{)}^{n-1}-1$ for each number of buyers n, that is $e-1$ as $n$ approaches infinity.

Full work available at URL: https://arxiv.org/abs/1401.0880

Recommendations

• Competitive auctions
• Competitive auctions and digital goods
• scientific article; zbMATH DE number 1875433
• scientific article; zbMATH DE number 2119761
• Averaging techniques for competitive auctions

zbMATH Keywords

competitive analysisdigital goodsmechanism designauction

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Theory of Cryptography
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower bounds in differential privacy
• Iterative Constructions and Private Data Release
• Differential privacy and the fat-shattering dimension of linear queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Title not available (Why is that?)
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• Title not available (Why is that?)
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the sample complexity for private learning and private data release
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (28)

• Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items
• Tight revenue gaps among multiunit mechanisms
• Optimal and Efficient Parametric Auctions
• Competitive auctions and digital goods
• Prior-free multi-unit auctions with ordered bidders
• Competitive auctions for markets with positive externalities
• Optimal Auction with Resale
• Prior-free auctions with ordered bidders
• Competitive auctions
• Rubinstein auctions: On competition for bargaining partners
• Tight revenue gaps among simple mechanisms
• Anonymous auctions maximizing revenue
• On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions
• The balloon popping problem revisited: lower and upper bounds
• Auction design with a revenue target
• Title not available (Why is that?)
• Envy freedom and prior-free mechanism design
• The balloon popping problem revisited: lower and upper bounds
• Optimal digital product auctions with unlimited supply and rebidding behavior
• Analyses of cardinal auctions
• Title not available (Why is that?)
• Optimality and Efficiency in Auctions Design: A Survey
• Competitive analysis of incentive compatible on-line auctions
• On the competition complexity of dynamic mechanism design
• STACS 2004
• Averaging techniques for competitive auctions
• Strictly strategy-proof auctions
• Optimal auctions with financially constrained buyers

Uses Software

• SuLQ

This page was built for publication: Optimal competitive auctions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259559)