We consider the problem of maximizing revenue for a monopolist offering multiple items to multiple heterogeneous buyers. We develop a simple mechanism that obtains a constant factor approximation under the assumption that the buyers' values are additive subject to a matroid feasibility constraint and independent across items. Importantly, different buyers in our setting can have different constraints on the sets of items they desire. Our mechanism is a sequential variant of two-part tariffs. Prior to our work, simple approximation mechanisms for such multi-buyer problems were known only for the special cases of all unit-demand or all additive value buyers.

Our work expands upon and unifies long lines of work on unit-demand settings and additive settings. We employ the ex ante relaxation approach developed by Alaei [2011] for reducing a multiple-buyer mechanism design problem with an ex post supply constraint into single-buyer problems with ex ante supply constraints. Solving the single-agent problems requires us to significantly extend a decomposition technique developed in the context of additive values Li and Yao [2013] and its extension to subadditive values by [2015].