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(ε , δ ) 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 Õ( 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 - ε ) .