Improving Competition Complexity Bounds in Multi-Item Auctions

In the field of mechanism design, a central focus of research is designing auctions to maximize the revenue generated. In the relevant multi-item auction setting, it is well known that the optimal mechanism is prohibitively complex: namely, it is randomized, computationally difficult, and presents the buyer with an uncountably infinite number of menu choices. Thus, much work in recent years has focused on the revenue of simple mechanisms, which are widely used in practice and are approximately optimal in fairly general cases. In this setting, a seller wants to sell m items to n bidders, each of which has a valuation for each item drawn independently from some known distribution. When this distribution satisfies the Monotone Hazard Rate (MHR) condition, the buyers have additive valuations, and are drawn from the same population, it is possible to run a simple second price auction with reserves that achieves a (1-\epsilon) fraction of the optimal revenue, given that there are sufficiently many bidders n. In this paper, we begin by laying out the details of the setting that we are working in. Then, we use numerical simulations to observe the fraction of optimal revenue that the simple reserve- price mechanism can extract, under various choices of n and underlying distribution F. In simulating the very large values of n, we also use various probabilistic convergence results to improve the efficiency of calculation. By studying how the reserve-price mechanism performs as a function of n in our simulations, we make various observations on the relationships between n, F, and the fraction of optimal revenue that the simple mechanism achieves. Finally, we conjecture that we require only n > 300^(1/\epsilon) bidders as opposed to the existing bound of n > (12/\epsilon)^(12/\epsilon).