Near-optimal auctions on independence systems
It is known that the classical result by \textit{R. B. Myerson} [Math. Oper. Res. 6, 58--73 (1981; Zbl 0496.90099)] gives a characterization of an optimal auction for any given distribution of valuations of the bidders. In this paper, the authors consider the situation where the distribution is not explicitly given but can be observed in a sample of auction results from the same distribution. They prove a new bound for the case of independence systems that widely generalizes matroids and contains several important combinatorial optimization problems. More precisely, the bound of \(O\left (\frac{H^2n^4}{\epsilon ^3}\right )\) (\(n\) is the number of bidders, \(\epsilon\) the error and \(H\) the maximal valuation) falls neatly between those known for the general and the matroid case. The class of independence systems contains several well-known NP-hard problems such as knapsack. In a second result the authors show that an approximation algorithm can be used without compromising the sample complexity.
- Algorithmic Game Theory
- Efficient empirical revenue maximization in single-parameter auction environments
- scientific article; zbMATH DE number 6381703 (Why is no real title available?)
- Multi-parameter mechanism design and sequential posted pricing
- Neural Network Learning
- Optimal Auction Design
- Settling the sample complexity of single-parameter revenue maximization
- The sample complexity of auctions with side information
- The sample complexity of revenue maximization
- Understanding machine learning. From theory to algorithms
This page was built for publication: Near-optimal auctions on independence systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6635693)
