Optimal competitive auctions

DOI10.1145/2591796.2591855MaRDI QIDQ5259559zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(28)

• Optimal auctions with financially constrained buyers
• 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
• Competitive auctions
• Optimal Auction with Resale
• Prior-free auctions with ordered bidders
• 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
• Envy freedom and prior-free mechanism design
• scientific article; zbMATH DE number 2119761 (Why is no real title available?)
• The balloon popping problem revisited: lower and upper bounds
• Optimal digital product auctions with unlimited supply and rebidding behavior
• Analyses of cardinal auctions
• scientific article; zbMATH DE number 1875433 (Why is no real title available?)
• 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

Describes a project that uses

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)