Near-Optimal Auctions on Independence Systems

Abstract 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 (, ) f (ε, δ) of required samples to guarantee a certain level of precision (1-) (1 - ε) with a probability of at least (1-) (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²n⁴ ³) 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-) α · (1 - ε).