  We introduce two new "degree of complementarity" measures, which we refer to,
respectively, as supermodular width and superadditive width. Both are
formulated based on natural witnesses of complementarity. We show that both
measures are robust by proving that they, respectively, characterize the gap of
monotone set functions from being submodular and subadditive. Thus, they define
two new hierarchies over monotone set functions, which we will refer to as
Supermodular Width (SMW) hierarchy and Superadditive Width (SAW) hierarchy,
with level 0 of the hierarchies resting exactly on submodular and subadditive
functions, respectively.
  We present a comprehensive comparative analysis of the SMW hierarchy and the
Supermodular Degree (SD) hierarchy, defined by Feige and Izsak. We prove that
the SMW hierarchy is strictly more expressive than the SD hierarchy. We show
that previous results regarding approximation guarantees for welfare and
constrained maximization as well as regarding the Price of Anarchy (PoA) of
simple auctions can be extended without any loss from the SD hierarchy to the
SMW hierarchy. We also establish almost matching information-theoretical lower
bounds. The combination of these approximation and hardness results illustrate
that the SMW hierarchy provides an accurate characterization of "near
submodularity" needed for maximization approximation. While SD and SMW
hierarchies support nontrivial bounds on the PoA of simple auctions, we show
that our SAW hierarchy seems to capture more intrinsic properties needed to
realize the efficiency of simple auctions. So far, the SAW hierarchy provides
the best dependency for the PoA of Single-bid Auction, and is nearly as
competitive as the Maximum over Positive Hypergraphs (MPH) hierarchy for
Simultaneous Item First Price Auction (SIA). We provide almost tight lower
bounds for the PoA of both auctions with respect to the SAW hierarchy.
