  A fundamental assumption in classical mechanism design is that buyers are
perfect optimizers. However, in practice, buyers may be limited by their
computational capabilities or a lack of information, and may not be able to
perfectly optimize their response to a mechanism. This has motivated the
introduction of approximate incentive compatibility (IC) as an appealing
solution concept for practical mechanism design. While most of the literature
has focused on the analysis of particular approximate IC mechanisms, this paper
is the first to study the design of \textit{optimal} mechanisms in the space of
approximate IC mechanisms and to explore how much revenue can be garnered by
moving from exact to approximate incentive constraints. In particular, we study
the problem of a seller facing one buyer with private values and analyze
optimal selling mechanisms under $\varepsilon$-incentive compatibility. We
establish that an optimal mechanism needs to randomize as soon as
$\varepsilon>0$ and that no mechanism can garner gains higher than order
$\varepsilon^{2/3}$. This improves upon state-of-the art results which imply
maximum gains of $\varepsilon^{1/2}$. Furthermore, we construct a mechanism
that is guaranteed to achieve order $\varepsilon^{2/3}$ additional revenues,
leading to a tight characterization of the revenue implications of approximate
IC constraints. Our study sheds light on a novel class of optimization problems
and the challenges that emerge when relaxing IC constraints. In particular, it
brings forward the need to optimize not only over allocations and payments but
also over best responses, and we develop a new framework to address this
challenge.
