An n-to-1 bidder reduction for multi-item auctions and its applications

DOI10.1137/1.9781611973730.8MaRDI QIDQ5363023zbMATH OpenOpenAlexFDO

Authors Andrew Chi-Chih Yao

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: In this paper, we introduce a novel approach for reducing the $k$-item $n$-bidder auction with additive valuation to $k$-item $1$-bidder auctions. This approach, called the emph{Best-Guess} reduction, can be applied to address several central questions in optimal revenue auction theory such as the power of randomization, and Bayesian versus dominant-strategy implementations. First, when the items have independent valuation distributions, we present a deterministic mechanism called {it Deterministic Best-Guess} that yields at least a constant fraction of the optimal revenue by any randomized mechanism. Second, if all the $nk$ valuation random variables are independent, the optimal revenue achievable in {it dominant strategy incentive compatibility} (DSIC) is shown to be at least a constant fraction of that achievable in {it Bayesian incentive compatibility} (BIC). Third, when all the $nk$ values are identically distributed according to a common one-dimensional distribution $F$, the optimal revenue is shown to be expressible in the closed form $Theta(k(r+in{t}_0^{mr}(1-F(x{)}^n)udx))$ where $r=su{p}_{xgeq0},x(1-F(x{)}^n)$ and $m=lceilk/nceil$; this revenue is achievable by a simple mechanism called emph{2nd-Price Bundling}. All our results apply to arbitrary distributions, regular or irregular.

Recommendations

• Simple and nearly optimal multi-item auctions
• Simple mechanisms for subadditive buyers via duality
• Multi-Item Nontruthful Auctions Achieve Good Revenue
• The complexity of optimal mechanism design
• Approximate revenue maximization with multiple items

Cited in

(26)

• The complexity of optimal multidimensional pricing for a unit-demand buyer
• Approximate revenue maximization with multiple items
• Risk-robust mechanism design for a prospect-theoretic buyer
• On symmetries in multi-dimensional mechanism design
• Buy-many mechanisms are not much better than item pricing
• Selling multiple correlated goods: revenue maximization and menu-size complexity
• Bounding the optimal revenue of selling multiple goods
• Optimal mechanisms for selling two items to a single buyer having uniformly distributed valuations
• On optimal mechanisms in the two-item single-buyer unit-demand setting
• Bayesian auctions with efficient queries
• Duality and optimality of auctions for uniform distributions
• A simple and approximately optimal mechanism for a buyer with complements
• A Duality-Based Unified Approach to Bayesian Mechanism Design
• Brief Announcement: Bayesian Auctions with Efficient Queries.
• On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer
• Tight revenue gaps among simple mechanisms
• Optimal mechanisms with simple menus
• Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items
• An O(\log \log m) Prophet Inequality for Subadditive Combinatorial Auctions
• Multi-Item Nontruthful Auctions Achieve Good Revenue
• Multi-agent contracts
• Buy-many mechanisms for many unit-demand buyers
• Optimal auctions through deep learning: advances in differentiable economics
• Multi-agent contracts
• An algorithmic framework for black-box reductions from Bayesian mechanism design to algorithm design
• Nonbossy mechanisms: mechanism design robust to secondary goals

This page was built for publication: An \(n\)-to-\(1\) bidder reduction for multi-item auctions and its applications

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