Optimal competitive auctions
From MaRDI portal
Publication:5259559
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 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 for each number of buyers n, that is as approaches infinity.
Recommendations
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)- The balloon popping problem revisited: lower and upper bounds
- Tight revenue gaps among simple mechanisms
- Analyses of cardinal auctions
- Competitive analysis of incentive compatible on-line auctions
- On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions
- Optimal Auction with Resale
- Optimal and Efficient Parametric Auctions
- Prior-free auctions with ordered bidders
- Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items
- Strictly strategy-proof auctions
- The balloon popping problem revisited: lower and upper bounds
- Competitive auctions and digital goods
- Auction design with a revenue target
- scientific article; zbMATH DE number 1875433 (Why is no real title available?)
- On the competition complexity of dynamic mechanism design
- Anonymous auctions maximizing revenue
- STACS 2004
- Competitive auctions
- Optimal digital product auctions with unlimited supply and rebidding behavior
- Optimality and Efficiency in Auctions Design: A Survey
- Averaging techniques for competitive auctions
- Optimal auctions with financially constrained buyers
- Prior-free multi-unit auctions with ordered bidders
- scientific article; zbMATH DE number 2119761 (Why is no real title available?)
- Competitive auctions for markets with positive externalities
- Tight revenue gaps among multiunit mechanisms
- Rubinstein auctions: On competition for bargaining partners
- Envy freedom and prior-free mechanism design
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)
