Near-Optimal Auctions on Independence Systems.

A classical result by Myerson (Math. Oper. Res. 6(1), 58-73, 1981) gives a characterization of an optimal auction for any given distribution of valuations of the bidders. We consider the situation where the distribution is not explicitly given but can be observed in a sample of auction results from the same distribution. A seminal paper by Morgenstern and Roughgarden (Adv.Neural Inf. Process. Syst. 28, 2015) proposes to learn a near-optimal auction from the hypothesis class of t-level auctions. They prove a bound on the sample complexity, i.e., the function f (ε , δ) of required samples to guarantee a certain level of precision (1 - ε) with a probability of at least (1 - δ) , for the general single-parameter case and a tighter bound for the very restricted matroid case. We show a new bound for the case of independence systems, that widely generalizes matroids and contains several important combinatorial optimization problems. This bound of O ~ H 2 n 4 ε 3 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. Therefore, the allocation itself might in practice be limited to α -approximate solutions. In a second result we show that an approximation algorithm can be used without compromising the sample complexity. Also, the precision is affected only mildly, resulting in a factor of α · (1 - ε) . [ABSTRACT FROM AUTHOR]