  We study the efficiency of simple auctions in the presence of complements.
[DMSW15] introduced the single-bid auction, and showed that it has a price of
anarchy (PoA) of $O(\log m)$ for complement-free (i.e., subadditive)
valuations. Prior to our work, no non-trivial upper bound on the PoA of single
bid auctions was known for valuations exhibiting complements. We introduce a
hierarchy over valuations, where levels of the hierarchy correspond to the
degree of complementarity, and the PoA of the single bid auction degrades
gracefully with the level of the hierarchy. This hierarchy is a refinement of
the Maximum over Positive Hypergraphs (MPH) hierarchy [FFIILS15], where the
degree of complementarity $d$ is captured by the maximum number of neighbors of
a node in the positive hypergraph representation. We show that the price of
anarchy of the single bid auction for valuations of level $d$ of the hierarchy
is $O(d^2 \log(m/d))$, where $m$ is the number of items. We also establish an
improved upper bound of $O(d \log m)$ for a subclass where every hyperedge in
the positive hypergraph representation is of size at most 2 (but the degree is
still $d$). Finally, we show that randomizing between the single bid auction
and the grand bundle auction has a price of anarchy of at most $O(\sqrt{m})$
for general valuations. All of our results are derived via the smoothness
framework, thus extend to coarse-correlated equilibria and to Bayes Nash
equilibria.
