  Internet ad auctions have evolved from a few lines of text to richer
informational layouts that include images, sitelinks, videos, etc. Ads in these
new formats occupy varying amounts of space, and an advertiser can provide
multiple formats, only one of which can be shown. The seller is now faced with
a multi-parameter mechanism design problem. Computing an efficient allocation
is computationally intractable, and therefore the standard
Vickrey-Clarke-Groves (VCG) auction, while truthful and welfare-optimal, is
impractical.
  In this paper, we tackle a fundamental problem in the design of modern ad
auctions. We adopt a ``Myersonian'' approach and study allocation rules that
are monotone both in the bid and set of rich ads. We show that such rules can
be paired with a payment function to give a truthful auction. Our main
technical challenge is designing a monotone rule that yields a good
approximation to the optimal welfare. Monotonicity doesn't hold for standard
algorithms, e.g. the incremental bang-per-buck order, that give good
approximations to ``knapsack-like'' problems such as ours. In fact, we show
that no deterministic monotone rule can approximate the optimal welfare within
a factor better than $2$ (while there is a non-monotone FPTAS). Our main result
is a new, simple, greedy and monotone allocation rule that guarantees a $3$
approximation.
  In ad auctions in practice, monotone allocation rules are often paired with
the so-called Generalized Second Price (GSP) payment rule, which charges the
minimum threshold price below which the allocation changes. We prove that, even
though our monotone allocation rule paired with GSP is not truthful, its Price
of Anarchy (PoA) is bounded. Under standard no overbidding assumption, we prove
a pure PoA bound of $6$ and a Bayes-Nash PoA bound of $\frac{6}{(1 -
\frac{1}{e})}$. Finally, we experimentally test our algorithms on real-world
data.
