  We introduce the notion of rigidity in auction design and use it to analyze
some fundamental aspects of mechanism design. We focus on single-item auctions
where the values of the bidders are drawn from some (possibly correlated)
distribution $\mathcal F$. Let $f$ be the allocation function of an optimal
mechanism for $\mathcal F$. Informally, $S$ is (linearly) rigid in $\mathcal F$
if for every mechanism $M'$ with an allocation function $f'$ where $f$ and $f'$
agree on the allocation of at most $x$-fraction of the instances of $S$, the
expected revenue of $M'$ is at most an $x$ fraction of the optimal revenue. We
use rigidity to explain the singular success of Cremer and McLean's auction.
Recall that the revenue of Cremer and McLean's auction is the optimal welfare
if the distribution obeys a certain ``full rank'' condition, but no analogous
constructions are known if this condition does not hold. Note that the
Kolmogorov complexity of the allocation function of Cremer and McLean's auction
is logarithmic, whereas we use rigidity to show that for some distributions
that do not obey the full rank condition, the Kolmogorov complexity of the
allocation function of every mechanism that provides a constant approximation
is almost linear. We further investigate rigidity assuming different notions of
individual rationality. Assuming ex-post individual rationality, if there is a
rigid set, the structure of the optimal mechanism is simple: the player with
the highest value ``usually'' wins the item and contributes most of the
revenue. In contrast, assuming interim individual rationality, there are
distributions with a rigid set $S$ where the optimal mechanism has no obvious
allocation pattern (i.e., its Kolmogorov complexity is high). Our results help
explain why we have little hope of developing good, simple and generic
approximation mechanisms in the interim individual rationality world.
