  We study revenue maximization in multi-item multi-bidder auctions under the
natural item-independence assumption - a classical problem in Multi-Dimensional
Bayesian Mechanism Design. One of the biggest challenges in this area is
developing algorithms to compute (approximately) optimal mechanisms that are
not brute-force in the size of the bidder type space, which is usually
exponential in the number of items in multi-item auctions. Unfortunately, such
algorithms were only known for basic settings of our problem when bidders have
unit-demand [CHMS10,CMS15] or additive valuations [Yao15].
  In this paper, we significantly improve the previous results and design the
first algorithm that runs in time polynomial in the number of items and the
number of bidders to compute mechanisms that are $O(1)$-approximations to the
optimal revenue when bidders have XOS valuations, resolving an open problem
raised in [CM16,CZ17]. Moreover, the computed mechanism has a simple structure:
It is either a posted price mechanism or a two-part tariff mechanism. As a
corollary of our result, we show how to compute an approximately optimal and
simple mechanism efficiently using only sample access to the bidders' value
distributions. Our algorithm builds on two innovations that allow us to search
over the space of mechanisms efficiently: (i) a new type of succinct
representation of mechanisms - the marginal reduced forms, and (ii) a novel
Lift-and-Round procedure that concavifies the problem.
