Polynomial Sample Complexity for Blackbox Reductions in Mechanism Design with Additive Bidders

Abstract

We study the sample complexity of blackbox reductions from mechanism design to algorithm design for the objective of welfare-maximization in a setting of structured buyer valuation distributions. Previous blackbox reduction procedures all require a number of samples that is exponential in the relevant parameters, due to a dependence on the exponentially-sized type space of each buyer. We ask whether restricting our attention to buyers with additive valuations over independent items can enable us to leverage this additional structure to achieve polynomial sample complexity. Our main contribution is to answer this question in the affirmative, currently under an additional smoothness assumption on the underlying buyer distributions, while we conjecture the result to hold even without this assumption.