Optimal competitive auctions

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

N. V. Gravin, Pinyan Lu, Ning Chen

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• 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
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• 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
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (9)

• Tight Revenue Gaps Among Simple Mechanisms
• Optimal and Efficient Parametric Auctions
• Optimal Auction with Resale
• Rubinstein auctions: On competition for bargaining partners
• Envy freedom and prior-free mechanism design
• Tight Revenue Gaps among Multiunit Mechanisms
• Auction Design with a Revenue Target
• 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)