Near-optimal auctions on independence systems (Q6635693)

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.