Balseiro, Besbes and Castro

Mechanism Design under Approximate Incentive Compatibility

Mechanism Design under
Approximate Incentive Compatibility

Santiago R. Balseiro Columbia Business School Omar Besbes Columbia Business
School Francisco Castro UCLA Anderson School of Management

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 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 the gains that can be garnered depend on the local curvature of
the seller’s revenue function around the optimal posted price when the buyer
is a perfect optimizer. If the revenue function behaves locally like an
$\alpha$-power for $\alpha\in(1,\infty)$, then no mechanism can garner gains
higher than order $\varepsilon^{\alpha/(2\alpha-1)}$. This improves upon
state-of-the-art results which imply maximum gains of $\varepsilon^{1/2}$ by
providing the first parametric bounds that capture the impact of revenue
function’s curvature on revenue gains. Furthermore, we establish that an
optimal mechanism needs to randomize as soon as $\varepsilon>0$ and construct
a randomized mechanism that is guaranteed to achieve order
$\varepsilon^{\alpha/(2\alpha-1)}$ 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.

mechanism design, satisficing behavior, approximate incentive compatibility,
revenue maximization, infinite dimensional linear programs, duality

##  1 Introduction

From housing allocation to online advertising, market design is having a
profound impact on the design, implementation, and operations of markets. An
idea fundamental to good market design is the correct assessment of
participants’ incentives, usually through an exact equilibrium concept.
Indeed, most of the literature in mechanism design has assumed that agents
make decisions by perfectly optimizing their utility functions, even when
facing arbitrarily complex mechanisms. This idea has impacted how
practitioners design and operationalize their market solutions, and it has led
to a long line of research that has provided a good understanding of optimal
mechanism design with exact incentive compatibility constraints. However, in
real-world applications, markets are complex and participants are not always
able to best respond to market conditions. Lack of information or experience,
technological limitations, or even behavioral biases might prevent buyers from
accurately assessing their utility from a transaction, and thus buyers might
make only near-optimal decisions. Our focus in this paper is to explore the
consequences of these limitations, and to understand the potential value that
market designers can derive from them. In particular, the main question we
tackle is:

> What is an optimal or near-optimal selling mechanism when buyers are not
> perfect optimizers, and how does the problem structure impact the level of
> additional revenue performance that can be gained?

There has been significant interest in studying specific mechanisms and
quantifying the extent to which they are incentive compatible or not (see
Section 1.1). This line of work studies specific instances in the space of
feasible mechanisms under relaxed incentive compatibility constraints. In
addition, many studies have shown how to transform an approximately incentive-
compatible mechanism into an exactly incentive compatible one while
controlling for the loss in revenues. However, to the best of our knowledge,
the study of the optimization of mechanisms under relaxed incentive
compatibility constraints is new. As we will see, this leads to a new class of
optimization problems that is fundamentally different in nature than classical
mechanism design. Furthermore, we will derive new insights into the
relationship between the perturbation of IC constraints and the revenue
performance that can be achieved.

To make progress toward this question, we anchor our analysis around the
classical Myerson setting with a single buyer with private values. In this
case, a posted price mechanism is known to be optimal when the buyer is a
perfect optimizer. To capture that the buyer is not a perfect optimizer, we
allow the incentive compatibility (IC) constraints to be satisfied up to a
“small” $\varepsilon>0$, i.e., the buyer is satisficing and near-optimizer,
and he can select a reporting strategy that is $\varepsilon$ away from
optimal. Studying the case of small $\varepsilon$ is natural as agents, while
satisficing, might not be willing to forgo large gains from not perfectly
optimizing. We will refer to this constraint as $\varepsilon$-IC. Essentially,
we study a classical mechanism design problem in which the IC constraint is
slightly relaxed.

It is worth noting that the classical setting with IC constraints is an
infinite-dimensional linear program that admits a very simple solution through
a posted price (see, e.g., Riley and Zeckhauser 1983). The problem with
$\varepsilon$-IC constraints is also an infinite-dimensional linear program,
but, as we will see, it leads to a rich new class of problems. In light of the
question above, we are interested in quantifying the difference between the
values of the two problems as a function of $\varepsilon$, but also in
understanding the underlying structure of near-optimal mechanisms in the
$\varepsilon$-IC setting and the impact of the buyer’s distribution of private
information on performance.

##### Existing benchmarks.

A naïve comparison might lead one to expect the difference between the values
of these two linear programs to scale (at most) in a piecewise linear fashion
(as a function of $\varepsilon$) based on intuition gleaned from finite
dimensional linear programs. However, in the class of mechanism design
problems, we will see that the picture is more subtle and rich, since we are
relaxing an infinite number of constraints. On another hand, an application of
the powerful rounding argument of Nisan, which allows to transform an
$\varepsilon$-IC mechanism into an IC mechanism while bounding the revenue
loss (see Section 3.1), enables one to readily obtain an upper bound on the
maximal additional revenues that could be garnered of order
$\varepsilon^{1/2}$.

$p^{*}$$v$: value$R(v)$: revenue curve$\alpha>2$$\alpha=2$$\alpha<2$ |  |  | Revenue Gains
---|---|---
Local Revenue |  | Randomized | Deterministic
Curvature ($\alpha$) |  | mechanisms | mechanisms
$\alpha\downarrow 1$ |  | $\tilde{\Theta}(\varepsilon)$ | $\tilde{\Theta}(\varepsilon)$
… |  | … | …
$\alpha=2$ |  | $\tilde{\Theta}(\varepsilon^{2/3})$ | $\tilde{\Theta}(\varepsilon)$
… |  | … | …
$\alpha\uparrow\infty$ |  | $\tilde{\Theta}(\varepsilon^{1/2})$ | $\tilde{\Theta}(\varepsilon)$
(a)(b)

Figure 1: (a) Local curvature of the revenue function $R(v)=v(1-F(v))$ around
the optimal posted price $p^{\star}$. Here, $F(v)$ denotes the cumulative
distribution function of the buyer’s value. (b) Revenue improvement for
$\varepsilon$-optimizers as a function of $\varepsilon$. In this paper, we
provide matching upper and lower bounds showing that the optimal rate is of
order $\varepsilon^{\alpha/(2\alpha-1)}$ for randomized mechanisms where
$\alpha\in(1,\infty)$ captures the local curvature of the revenue function. We
also show that the rate is linear for deterministic mechanisms.

##### Contributions.

Our main contribution is to initiate the study of the implications of
$\varepsilon$-IC constraints from an optimization perspective. While most of
the related literature has focused on measuring deviations from IC
constraints, on studying mechanisms that are $\varepsilon$-IC, or on
reductions from $\varepsilon$-IC to IC, our focus is instead on understanding
the structure of optimal $\varepsilon$-IC mechanisms and their revenue
guarantees.

Our objective is to study the impact of the buyer’s distribution of values on
the revenue that can be garnered by relaxing the incentive compatibility
constraints. Notably, we identify that the revenue gains when $\varepsilon$ is
small are governed by the local curvature of the revenue function around the
optimal posted price when the buyer is a perfect optimizer. More formally,
denote by $F(v)$ the cumulative distribution function of the buyer’s value and
by $R(v)=v(1-F(v))$ the revenue function, which measures the seller’s expected
revenue when the posted price is $v$ and the buyer is a perfect optimizer.
Denote by $p^{\star}$ an optimal posted price. Roughly speaking, we say that
the revenue function admits local $\alpha$-power envelopes for
$\alpha\in(1,\infty)$ if

$R(p^{\star})-R(v)\asymp|v-p^{\star}|^{\alpha}\,,$

for posted prices $v$ close to the optimal, that is, the revenue loss of
choosing a suboptimal posted price decays at a rate of $\alpha$.111 Our
working definition of local envelopes in Definition 2.1 is actually slightly
stronger as it is stated in terms of the derivative of the revenue function,
but these are equivalent in many cases of interest. See Figure 1 (a) for an
illustration of different local behaviors.

We first explore upper bounds on the achievable performance. As articulated
above, we first review how Nisan’s classical rounding argument enables one to
readily obtain an impossibility result through an upper bound on the maximal
additional revenues that could be garnered, given by order $\varepsilon^{1/2}$
(Proposition 3.1). This yields a powerful, uniform guarantee that is
independent of the curvature of the revenue function. Our first main result is
a parametric upper bound on the revenue gains (that can be obtained when
relaxing the IC constraints) that depends on the local curvature of the
revenue function. In particular, we establish in Theorem 3.2 that no
(randomized) mechanism can yield revenue gains of order more than
$\varepsilon^{\alpha/(2\alpha-1)}$, which yield an improvement on classical
results for every $\alpha\in(1,\infty)$. Interestingly, in the limit when
$\alpha\uparrow\infty$, i.e., when the revenue curve is locally flat, we
recover the classical bound of $\varepsilon^{1/2}$ from Nissan. In the limit
when $\alpha\downarrow 1$, i.e., when the revenue curve has a kink, we recover
the $\varepsilon$ gains suggested by sensitivity analysis for finite
dimensional linear programming. Finally, in the prototypical case of
$\alpha=2$, i.e., when the revenue curve is smooth and locally quadratic, we
obtain a novel bound of $\varepsilon^{2/3}$ on the maximum revenue gains that
can be garnered.

We derive our upper bound through a novel duality argument that also
highlights the different nature of objects that emerge in this class of
problems, and the interplay between $\varepsilon$-IC and revenues. Our
approach involves guessing a best response for the buyer and then relaxing,
for each value, the IC constraints of all reports except the one corresponding
to the report made by the best response. Because these pairs of values and
reports induce a path in the two-dimensional Euclidean space, we dub the
resulting problem as the _path-based relaxation_. We further upper bound the
path-based relaxation by considering the Lagrangian dual problem obtained
after dualizing the remaining constraints. The most challenging part of our
analysis involves bounding the value of the latter problem. Here, our choice
of the best response ends up playing a key role.

Our second set of main results pertains to achievability. We start our search
for nearly optimal mechanisms, which would yield lower bounds on attainable
revenues, by exploring the space of deterministic mechanisms. Our study of
deterministic mechanisms is motivated by the fact that an optimal mechanism
with exact IC constraints is deterministic. In that space, we establish in
Theorem 4.1 that the gains are of order $\varepsilon$ and derive an optimal
mechanism.

We then expand our search to include randomized mechanisms. We establish in
Theorem 5.1 that there exists a mechanism that leads to gains of at least
order $\varepsilon^{\alpha/(2\alpha-1)}$. Notably, our approach is
constructive in that we exhibit a family of mechanisms that delivers such
supra-linear gains for every $\alpha\in(1,\infty)$. These are an appropriately
constructed perturbation of the optimal mechanism when $\varepsilon=0$. The
construction of this family is also instructive in that it highlights the
special nature of the problem at hand. In particular, the mechanism is
randomized and its allocations are characterized by a set of ordinary and
delayed differential equations. Such delayed differential equations appear
critical for understanding the class of $\varepsilon$-IC mechanism design
problems.

We summarize in Figure 1 (b) the results in the present paper. Notably, our
bounds provide a sharp characterization of the performance implications of
approximate incentive compatibility. The gains stemming from it are exactly of
order $\varepsilon^{\alpha/(2\alpha-1)}$, thus yielding a spectrum of gains
depending on the local curvature $\alpha\in(1,\infty)$ of the revenue
function. Furthermore, our results imply that an optimal mechanism has to
randomize. This is true even if, for example, the underlying distribution is
regular. This unveils an interesting phase transition. For $\varepsilon=0$ the
optimal allocation is deterministic—a posted-price mechanism—but as soon as
$\varepsilon$ becomes positive, the optimal mechanism requires randomization.
Our results also shed light on the geometry of the set of incentive-compatible
mechanisms. Because mechanism design problems are linear programs, by Bauer’s
maximum principle they attain their maximum at an extreme point of the
feasible set. Interestingly, in the case of exact IC constraints, extreme
points are deterministic posted-price mechanisms (Manelli and Vincent 2007). A
takeaway from our results is that as soon as $\varepsilon>0$, the set of
extreme points becomes richer as optimal mechanisms must randomize.

Our performance analysis focuses on the case of $\varepsilon$ small to derive
clean analytical insights on the limiting revenue gains when
$\varepsilon\downarrow 0$. We remark, however, that our approach is also valid
to develop upper and lower bounds for arbitrary $\varepsilon$. Our path-based
relaxation dualizes $\varepsilon$-IC constraints along the path of a best
response and, by weak duality, this approach yields upper bounds for any value
of $\varepsilon$. Moreover, by optimizing over the paths we can readily obtain
upper bounds for every instance. Similarly, our lower bound provides a
framework to construct a feasible $\varepsilon-$IC mechanism through a set of
ordinary and delayed differential equations. Both methods are general and
provide a computational framework for $\varepsilon-$IC mechanism design for
values of $\varepsilon$ that are not necessarily small.

From a methodological perspective, an important and novel takeaway emerges.
While in classical mechanism design with exact IC constraints, the problem can
be formulated as an optimization over allocations and payments, now, as one
relaxes the IC constraints to be approximately satisfied, an additional
endogenous object emerges in the optimization, through the best response of
the buyer (we discuss this in Section 2 after we introduce the problem
formally). In the same way that the allocation pins down payments for an
exactly IC mechanism, we show that the best response can be the central object
that can be used to optimize over $\varepsilon$-IC mechanisms. For example, in
our path-based relaxation, a best response fully determines an upper bound on
the achievable performance. Similarly, in constructing our proposed
mechanisms, our choice of the best response (together with some reasonable
assumptions on the mechanism) pins down both the allocation and payments.
Optimizing over best responses, and the associated methodology, might have
implications beyond the exact problem studied in the present paper.

###  1.1 Literature Review

Our paper builds on the classical mechanism design literature for revenue
maximization under exact IC constraints, e.g., Myerson (1979) and Myerson
(1981). More specifically, the setting of selling to a single buyer relates to
the work of Riley and Zeckhauser (1983). Under an exact IC constraint, Riley
and Zeckhauser (1983) establish that an optimal mechanism is simply a posted
price. In contrast, as soon as IC is relaxed to hold approximately, we
establish that any deterministic allocation mechanism is suboptimal.

There has recently been a surge of interest in measuring IC and relaxing IC in
the context of selling mechanisms. Milgrom (2011) highlights that
understanding notions of approximate IC and their implications for performance
is one of the four critical issues in the practice of market design. In the
present paper, for a class of selling problems, we study the implications of
relaxing IC constraints for both the structure of optimal mechanisms and the
associated performance, while also shedding light on the rich structure of the
associated optimization problems that emerge.

There are various studies that analyze mechanisms that are approximately IC in
various contexts. Hartline and Lucier (2010) and Hartline and Lucier (2015)
study efficient welfare black-box reductions that turn an allocation algorithm
into a Bayesian incentive-compatible mechanism with minimal welfare and
revenue losses in a single-dimensional setting. Several papers study similar
reductions in more general settings such as multi-dimensional agents’ types,
discrete or continuous types, or combinations thereof. In higher multi-
dimensional settings, Bei and Huang (2011) provide reductions that are
approximately incentive compatible for the case of discrete type space, while
Hartline et al. (2011) and Hartline et al. (2015) find reductions that are
exact IC. Until recently, the problem for continuous type space only had
$\varepsilon-$IC reductions but this gap was closed by Dughmi et al. (2021).
Finally, Cai et al. (2021) provide an efficient revenue preserving (with small
loss) transformation from $\varepsilon-$IC to exact IC and Conitzer et al.
(2020) provide a transformation that preserves revenue and incurs negligible
revenue loss.

We also refer the reader to Caroll (2013) and Dütting et al. (2021) that
motivate and study notions of $\varepsilon-$IC in the context of voting rules
and contract design, respectively.

Nazerzadeh et al. (2013) and Kanoria and Nazerzadeh (2017) consider
approximately IC mechanisms in a dynamic context with learning. Balseiro et
al. (2015) and Balseiro et al. (2019) focus on such an environment in the
context of multi-period settings with cumulative budget constraints. Gorokh et
al. (2017) also exhibits a mechanism that satisfies some form of approximate
IC when converting one-shot monetary mechanisms to dynamic mechanisms with
artificial currencies. While the studies above use related notions of
approximate IC, they differ in their focus. In these studies, the main
motivation for the introduction of approximate IC is computational and
analytical tractability since, in many settings, even computing a near-
optimal, exactly IC mechanism is not possible. To overcome this challenge,
these papers consider tractable mechanisms that are approximately IC and whose
performance is close to that of an optimal, exactly IC mechanism. By contrast,
in the present study, we ask what should be an optimal mechanism if one
optimizes over the space of approximate IC mechanisms. An interesting and
novel takeaway of our work is that relaxing the IC constraint leads to
supralinear gains.

The relaxation of IC constrains has also emerged in other general market
design settings. We refer the reader to Lubin and Parkes (2012) and Azevedo
and Budish (2018) as well as references therein for an overview of such other
applications. At a high level, these studies view approximate IC as a
desirable property of a mechanism being studied.

With the emergence of black-box mechanisms in practice, another related line
of research has focused on measuring how far a non-truhtfhul mechanism is from
incentive compatible. Examples of recent work in this area include Lahaie et
al. (2018), Balcan et al. (2019), Deng and Lahaie (2019), Feng et al. (2019),
Deng et al. (2020), and Colini-Baldeschi et al. (2020).

Finally, our work expands the set of techniques and ideas that have been used
in the literature to analyze approximate incentive-compatible mechanisms. A
central approach is the rounding argument often attributed to Noam Nisan and,
to the best of our knowledge, first used by Balcan et al. (2005) to turn any
$\varepsilon$-IC mechanism into an exactly IC mechanism while, at the same
time, limiting the revenue losses. This idea and the associated guarantees
have been extended by Daskalakis and Weinberg (2012) and Rubinstein and
Weinberg (2015) to multiple bidders settings.

##  2 Problem Formulation

We consider the classical setting developed in Myerson (1981) with a seller
(she) selling a single item to one buyer (he). The buyer’s value for the item
is drawn from a distribution $F$ with support $\mathcal{S}$. The distribution
$F$ is common knowledge. The buyer’s set of messages is denoted by $\Theta$.
The seller aims to design an indirect selling mechanism given by
$\hat{x}:\Theta\rightarrow\mathbb{R}$ and
$\hat{t}:\Theta\rightarrow\mathbb{R}$, where $\hat{x}$ denotes the allocation
probability and $\hat{t}$ the transfers. The buyer’s strategic response to the
mechanism is a function $\hat{\theta}:\mathcal{S}\rightarrow\Theta$. Given a
particular mechanism and response, the buyer’s utility is given by
$v\cdot\hat{x}(\hat{\theta}(v))-\hat{t}(\hat{\theta}(v))$. Our critical
modeling assumption is that the buyer is not a perfect optimizer. We capture
this by imposing that the incentive compatibility constraints are satisfied up
to $\varepsilon$. More precisely, the buyer aims to select a reporting
strategy that ensures that he collects non-negative utility from
participating, and the buyer is satisficing in that he aims to collect the
maximum surplus up to $\varepsilon$, i.e., for all $v\in\mathcal{S}$,
$v\cdot\hat{x}(\hat{\theta}(v))-\hat{t}(\hat{\theta}(v))\geq\sup_{\hat{\theta}^{\prime}\in\Theta}\\{v\cdot\hat{x}(\hat{\theta}^{\prime})-\hat{t}(\hat{\theta}^{\prime})\\}-\varepsilon.$
When there are multiple $\varepsilon$-optimal best responses for the buyer, we
assume that the buyer chooses the one that is the most favorable to the
principal. An implication of this assumption, which is pervasive in the
mechanism design literature, is that the seller’s problem reduces to
simultaneously choosing a mechanism together with a best response for the
buyer, which together are individually rational and approximately incentive
compatible. The seller aims to maximize the expected revenues from trade
$\mathsf{E}_{v}[\hat{t}(\hat{\theta}(v))]$ subject to the above constraints.

##### Reformulation via the revelation principle.

The key change compared to a classical mechanism design problem is that the
buyer is not a perfect optimizer. However, one may use classical arguments
(see Myerson 1979) to reduce attention to direct revelation mechanisms (see
Appendix 11 for details). In particular, without loss of optimality, one may
restrict attention to the following seller’s problem

$\displaystyle\sup_{x(\cdot),t(\cdot)}$ $\displaystyle\mathsf{E}_{v}[t(v)]$
($\mathcal{P}_{\varepsilon}$) s.t. $\displaystyle v\cdot x(v)-t(v)\geq
0,\quad\forall v\in\mathcal{S},$ (IR) $\displaystyle v\cdot x(v)-t(v)\geq
v\cdot x(v^{\prime})-t(v^{\prime})-\varepsilon,\quad\forall
v\in\mathcal{S},\quad v^{\prime}\in\mathcal{S},$ ($\mbox{IC}_{\varepsilon}$)
$\displaystyle x:\mathcal{S}\rightarrow[0,1]\quad\text{and}\quad
t:\mathcal{S}\rightarrow\mathbb{R}.$

Problem ($\mathcal{P}_{\varepsilon}$) will be our main focus of analysis. Our
goal is to shed light on the structure of an optimal or near-optimal solution
to ($\mathcal{P}_{\varepsilon}$) and provide a comprehensive characterization
of the added value of ($\mbox{IC}_{\varepsilon}$) compared to imposing exact
IC.

Note that when $\varepsilon=0$, ($\mathcal{P}_{\varepsilon}$) corresponds to
the standard mechanism design problem. In the remainder of the paper we will
use $(\mathcal{P}_{0})$ to refer to the latter problem. We denote by
$\mathcal{M}(\varepsilon)$ the set of feasible mechanisms for problem
($\mathcal{P}_{\varepsilon}$) and use $m$ to denote an element of this set.
For a mechanism $m=(x,t)\in\mathcal{M}(\varepsilon)$, we denote by $\Pi(m)$
the corresponding revenues. Note that for any $\varepsilon>0$,
$\mathcal{M}(0)\subset\mathcal{M}(\varepsilon)$.

In what follows we will be interested in quantifying the revenue implications
associated with relaxing the set of feasible mechanisms from $\mathcal{M}(0)$
to $\mathcal{M}(\varepsilon)$. Let

$\Pi^{\star}(\mathcal{M}(\varepsilon))\triangleq\sup_{m\in\mathcal{M}(\varepsilon)}\Pi(m)$

denote the optimal revenue under constraints $\mathcal{M}(\varepsilon)$. We
are interested in quantifying the difference in revenues

$\Pi^{\star}(\mathcal{M}(\varepsilon))-\Pi^{\star}(\mathcal{M}(0)),$ (1)

and how it changes as a function $\varepsilon$ when the latter is small. It is
worth noting that by comparing $\Pi^{\star}(\mathcal{M}(\varepsilon))$ to
$\Pi^{\star}(\mathcal{M}(0))$, we are essentially comparing the values of two
infinite-dimensional linear programs, where in one of these, the right-hand
side of the incentive compatibility constraint is relaxed. As noted in the
introduction, a naïve comparison, based on the intuition gleaned from finite
dimensional linear programs, may lead one to expect that the difference above
scales (at most) in a piecewise linear fashion. However, we will see that this
not the case, as we are relaxing an infinite number of constraints.

We aim to quantify the gap in Equation 1 in an instance dependent manner,
i.e., to understand the magnitude of this gap as a function of the underlying
distribution. We first introduce the following technical assumption on the
distribution of values.

The distribution $F$ admits a density, $f$, and has support in
$\mathcal{S}=[0,\overline{v}]$ with $0\leq\overline{v}<\infty$. Moreover, the
density $f$ has bounded variation. This assumption is mild and is satisfied by
a broad set of distributions commonly studied in the literature. We assume
that the lower bound of the support is zero to simplify the analysis, but our
result could be extended to distributions whose support does not include zero.
Note that bounded variation implies that $f(x)$ is bounded. We use $\bar{f}$
to denote an upper bound.

To study instance dependent bounds, we parametrize distribution families
through their local behavior around the price that maximizes their
corresponding revenue function. Formally, let $\bar{F}(v)$ denote $1-F(v)$,
and let $R(v)$ denote $v\cdot\bar{F}(v)$. We define an optimal price and
optimal revenue by

$p^{\star}\in\argmax_{v\in[0,\overline{v}]}R(v),\quad\text{and}\quad
R^{\star}=\max_{v\in[0,\overline{v}]}R(v).$ (2)

Our parametrization of distributions is then given by the following
definition.

######  Definition 2.1 (Local $\alpha$-power envelopes)

We say that the revenue function $R(v)$ admits local $\alpha$-power envelopes
if there exists a unique interior solution $p^{\star}$, and there exists
$\alpha\in(1,+\infty)$, and positive constants $\kappa_{L},\kappa_{U}$ and a
neighborhood of $p^{\star}$,
$\mathcal{N}_{\ell}=(p^{\star}-\ell,p^{\star}+\ell)\subset(0,\overline{v})$,
such that

$\kappa_{L}\alpha\cdot|v-p^{\star}|^{\alpha}\leq(p^{\star}-v)\cdot\dot{R}(v)\leq\kappa_{U}\alpha\cdot|v-p^{\star}|^{\alpha},\quad\forall
v\in\mathcal{N}_{\ell}.$

This definition characterizes the curvature of the revenue function around
$p^{\star}$. A distribution with a local $\alpha$-power envelope is such that
its associated revenue function has a power of $\alpha$ local behavior around
the unique optimal price. For example, when $\alpha=2$ then the behavior is
quadratic around $p^{\star}$. The latter case can be thought as the
prototypical one, and holds for a wide range of distributions (e.g., uniform,
exponential,…). A distribution in the limiting case when
$\alpha\uparrow\infty$ is almost flat (and approaches the isorevenue
distribution) around the optimal price; while a distribution in the limiting
case when $\alpha\downarrow 1$ has a kink around $p^{\star}$. That is, the
local $\alpha$-power envelopes notation characterizes a very broad set of
curvatures around the optimal price $p^{\star}$. We will show that the local
behavior of $R(v)$, as captured by $\alpha$, is a key driver of performance.

Finally, we note that Definition 2.1 implies that

$\kappa_{L}\cdot|v-p^{\star}|^{\alpha}\leq
R(p^{\star})-R(v)\leq\kappa_{U}\cdot|v-p^{\star}|^{\alpha}.$ (3)

Moreover if $R(p)$ is locally concave, the condition above and Definition 2.1
are equivalent (see Section 10 in the appendix for a formal statement and
proof).

##### Notation.

We next introduce some notation that will be used in the rest of the paper. In
what follows we will be interested in quantities as $\varepsilon\downarrow 0$.
Let $g$ and $h$ be two functions, we write
$g(\varepsilon)=\mathcal{O}(h(\varepsilon))$ if there exists a positive
constant $C$ and $\varepsilon_{0}>0$ such that $g(\varepsilon)\leq C\cdot
h(\varepsilon)$ for all $\varepsilon\in(0,\varepsilon_{0}]$. Additionally,
$g(\varepsilon)=\tilde{\mathcal{O}}(h(\varepsilon))$ if there exists a
positive constant $C$ and $\varepsilon_{0}>0$ such that $g(\varepsilon)\leq
C\cdot h(\varepsilon)\cdot\log(1/\varepsilon)$ for all
$\varepsilon\in(0,\varepsilon_{0}]$. We write
$g(\varepsilon)=\Omega(h(\varepsilon))$ if there exists a positive constant
$C$ and $\varepsilon_{0}>0$ such that $C\cdot h(\varepsilon)\leq
g(\varepsilon)$ for all $\varepsilon\in(0,\varepsilon_{0}]$.

###  2.1 Initial Remarks on the Impact of Relaxing IC Constraints

Before we proceed with our main analysis we elaborate on the challenges
associated with the $\varepsilon$-IC mechanism design problem. The coming
discussion will also allow to lay down the main distinctive features of
($\mathcal{P}_{\varepsilon}$) compared to $(\mathcal{P}_{0})$. In particular,
we will highlight how the arguments and reductions from classical mechanism
design no longer apply as soon as $\varepsilon$ becomes positive.

The classical mechanism design problem, $(\mathcal{P}_{0})$, is amenable to a
reformulation that greatly simplifies its analysis and that leads to a simple
posted-price solution. Fundamentally, there are three key properties that
enable this:

  1. (P1)

The allocation $x(\cdot)$ is monotone non-decreasing. This is a consequence of
$(\text{IC}_{0})$.

  2. (P2)

By $(\text{IC}_{0})$, truthful reporting is an optimal reporting strategy.
This obviates the need to keep track of the buyer’s optimal reporting
strategy.

  3. (P3)

The transfers $t(\cdot)$ can be expressed as a linear functional of the
allocation $x(\cdot)$. This is obtained by leveraging $(\text{IC}_{0})$ in
conjunction with an application of the envelope theorem.

These three properties lead to a reduction of $(\mathcal{P}_{0})$ as

$\displaystyle\max_{x(\cdot)}$
$\displaystyle\left\\{\int_{\mathcal{S}}x(v)\psi(v)f(v)dv\>:\>\text{s.t}\quad
x(\cdot)\text{ is non-decreasing}\right\\},$ (4)

where we denote the virtual value function by
$\psi:\mathcal{S}\rightarrow\mathbb{R}$ with $\psi(v)\triangleq
v-(1-F(v))/f(v)$ for all $v\in\mathcal{S}$. This reformulation was developed
and solved using ironing in Myerson (1981). A more direct approach (without
ironing) can be found in Riley and Zeckhauser (1983). It can be shown that the
optimal allocation is a posted-price mechanism $p^{\star}$ that maximizes the
revenue function

$p^{\star}\in\arg\max_{v\in\mathcal{S}}R(v).$

Let us now consider the case $\varepsilon>0$ and consider the impact on the
three properties above. First, $(\text{IC}_{0})$ implies that the allocation
is a non-decreasing function, see property (P1). However, as soon as
$\varepsilon>0$, a feasible allocation is not necessarily a non-decreasing
function. The incentive compatibility constraint $(\text{IC}_{\varepsilon})$
only implies the following “approximate” monotonicity property

$(v-v^{\prime})(x(v)-x(v^{\prime}))\geq-2\varepsilon,\quad\forall
v,v^{\prime}\in\mathcal{S}.$

Second, $(\text{IC}_{0})$ implies that it is optimal for the buyer to report
his type, see property (P2). When $\varepsilon>0$, this is no longer
necessarily true. Let $u(v)=\max_{w\in\mathcal{S}}\\{vx(w)-t(w)\\}$ be the
optimal utility of a buyer with value $v$, and
${v^{\star}}(v):\mathcal{S}\rightarrow\mathcal{S}$ be a best reporting mapping
of the buyer defined by

${v^{\star}}(v)\in\argmax_{w\in\mathcal{S}}\Big{\\{}v\cdot
x(w)-t(w)\Big{\\}}.$ (5)

While $(\text{IC}_{0})$ implies that ${v^{\star}}(v)=v$ is a best reporting
strategy, $(\text{IC}_{\varepsilon})$ only implies

$v\cdot x(v)-t(v)\geq u(v)-\varepsilon,\quad\forall v\in\mathcal{S}.$ (6)

That is, one only knows that truthful reporting leads to a utility in the
interval $[u(v)-\varepsilon,u(v)]$. Consequentially, in the $\varepsilon$-IC
setting, from an optimization perspective, the need to account for the
endogenous object ${v^{\star}}(\cdot)$ is not obviated. As a matter of fact,
we will see that this object plays a crucial role in both deriving
impossibility results but also in optimizing over mechanisms.

Finally, another important difference that emerges relates to the transfers
$t(\cdot)$, and the lack of a strong characterization readily available such
as in property (P3). In particular, when $\varepsilon>0$, according to the
envelope theorem (see e.g., Milgrom and Segal (2002)) we have

$u(v)=u(0)+\int_{0}^{v}x({v^{\star}}(s))ds,\quad\forall v\in\mathcal{S}.$ (7)

By combining eq. 6 and eq. 7 we only obtain an inequality for $t(\cdot)$ as a
function of $x(\cdot)$, $u(0)$ and ${v^{\star}}(\cdot)$, as opposed to a full
characterization of $t(\cdot)$. That is, we have

$t(v)\>\leq\>v\cdot
x(v)-u(0)-\int_{0}^{v}x({v^{\star}}(s))ds+\varepsilon,\quad\forall
v\in\mathcal{S}.$ (8)

As the above illustrates, as soon as $\epsilon>0$, the seller’s problem
becomes one of a different nature. In particular, in the $\varepsilon$-IC
case, one must solve jointly for the allocation and transfers by also tracking
a best reporting mapping. As we shall see, the latter will play a critical
role in our approach.

##  3 Upper Bound

We begin our analysis of ($\mathcal{P}_{\varepsilon}$) for general mechanisms
by developing an upper bound for eq. 1. As an initial benchmark, we review a
known upper bound of $\mathcal{O}(\varepsilon^{1/2})$ . This known upper bound
provides an initial range of what is achievable for the optimal gains on the
revenue improvement when the buyer is not a perfect optimizer. Then, we
establish our first main result: a new instance dependent upper bound of a
different order $\tilde{\mathcal{O}}(\varepsilon^{\alpha/(2\alpha-1)})$ on the
revenue improvement that is based on a novel approach and techniques.

###  3.1 An Initial Upper Bound via Nisan’s Rounding Argument

We first present an upper bound that follows directly from a classical
rounding argument, attributed to Noam Nisan (we are grateful to Anonymous for
this reference). In mechanism design, the rounding argument has been used
extensively to show that an approximate incentive-compatible mechanism can be
transformed into an exact incentive-compatible mechanism (see e.g., Balcan et
al. 2005). Here, one may use it to bound the maximal revenues one could gain
when solving under approximate, as opposed to exact, incentive compatibility.
We provide a proof in the appendix for completeness.

######  Proposition 3.1 (Upper Bound via Rounding)

$\Pi^{\star}(\mathcal{M}(\varepsilon))\>-\>\Pi^{\star}(\mathcal{M}(0))\>=\>\\\
\mathcal{O}(\varepsilon^{1/2}).$

The rounding argument provides a first step towards gauging the impact of
imperfect optimizers on the seller’s revenue. It provides an instance
independent impossibility result on the incremental revenues that can be
garnered by the seller. In the present paper, we aim at understanding the
instance dependent optimal performance, and, in turn, a natural question is
whether the bound above is tight once we specify a family of distributions. In
other words, we ask whether it is possible to improve upon this bound by
considering the characteristics of a given family of distributions.
Furthermore, we are also interested in how to achieve optimal or near-optimal
performance. We next develop a novel path-based duality approach to obtain a
new impossibility result that leads to an improved upper bound for eq. 1.

###  3.2 Upper Bound via Path-Based Duality Approach

Our first main theorem provides a new impossibility result.

######  Theorem 3.2 (Performance Upper Bound)

Suppose Section 2 holds, and that the revenue function admits local
$\alpha$-power envelopes in a neighborhood $\mathcal{N}_{\ell}$ of $p^{\star}$
and $\inf_{p\notin\mathcal{N}_{\ell}}|\dot{R}(p)|>0.$ Then

$\Pi^{\star}(\mathcal{M}(\varepsilon))\>-\>\Pi^{\star}(\mathcal{M}(0))\>=\>\tilde{\mathcal{O}}(\varepsilon^{\alpha/(2\alpha-1)}).$

This result shows that the seller can benefit by at most
$\varepsilon^{\alpha/(2\alpha-1)}$ up to polylogarithmic terms by offering a
mechanism that is $\varepsilon$-incentive compatible. (We conjecture that it
might be possible to remove the polylogarithmic terms from the upper bound.)
Theorem 3.2 presents an instance dependent impossibility result in the
presence of imperfect optimizer. Furthermore, our family of bounds (across of
$\alpha$) establishes that the limit on achievable performance is driven by
the local behavior of the revenue function around the optimal posted price.

Additionally, since for any $\alpha\in(1,+\infty)$ we have that
$1/2<\alpha/(2\alpha-1)$, our result also implies the $\varepsilon^{1/2}$
scaling (obtained through the rounding argument) for the class of
distributions that satisfies the assumptions of the theorem. We note that the
last assumption in Theorem 3.2 implies that the revenue function does not have
local maxima besides $p^{\star}$.

####  3.2.1 Main proof ideas

Our upper bound is based on an appropriate relaxation that can be analyzed
through a duality argument. For our duality approach, we will relax most IC
constraints except those that go through a carefully constructed path. This is
one of our critical observations and it is what makes the Proof of Theorem 3.2
of a different nature than previous approaches for classical mechanism design
problems. Indeed, constructing the path is analogous to choosing a best
reporting function for the $\varepsilon$-IC problem. As we will see, this is
an intricate task that requires going beyond approaches that consider local
deviations in the incentive compatibility constraints and, instead, entails
optimizing over best-response functions. Next, we explain our approach in
detail.

##### Path-based relaxation of IC constraints.

To construct the path, let us first fix $\mu$ and $\nu_{0}$ such that
$0<\mu<\nu_{0}<\overline{v}$. The values of $\mu$ and $\nu_{0}$ will
parametrize the path. Define the candidate best response function
${v^{\star}}:[\mu,\overline{v}]\rightarrow[0,\nu_{0}]$ such that
${v^{\star}}(v)$ is strictly increasing and continuous, ${v^{\star}}(\mu)=0$
and ${v^{\star}}(\overline{v})=\nu_{0}$. Later we show that this candidate is
indeed a best response function. We also assume that ${v^{\star}}(v)<v$ for
all $v$ so that the best response always under-reports. The function
$w:[0,\nu_{0}]\rightarrow[\mu,\overline{v}]$ is the inverse of
${v^{\star}}(\cdot)$. We note that ${v^{\star}}(\cdot)$ is constructed to have
all the properties that are desirable on a reporting function. Later, we will
optimize over choices of the parameters that satisfy the aforementioned
properties.

Given $\mu$ and $\nu_{0}$, we consider the following relaxed version of
($\mathcal{P}_{\varepsilon}$) in which the IR constraint is only imposed on
$[0,\mu]$ and the $\varepsilon$-IC constraint is imposed on the path given by
${v^{\star}}(\cdot)$:

$\displaystyle\max_{x(\cdot),t(\cdot)}$ $\displaystyle\mathsf{E}_{v}[t(v)]$
($\mathcal{P}_{\text{path}}$) s.t. $\displaystyle v\cdot x(v)-t(v)\geq 0,\quad
v\in[0,\mu]$ ($\text{IR}_{\mu}$) $\displaystyle v\cdot x(v)-t(v)\geq v\cdot
x({v^{\star}}(v))-t({v^{\star}}(v))-\varepsilon,\quad\forall
v\in[\mu,\overline{v}],$ ($\text{IC}_{\mu}$) $\displaystyle
x:\Theta\rightarrow[0,1]\quad\text{and}\quad t:\Theta\rightarrow\mathbb{R}.$

We let $\mathcal{M}_{\text{path}}(\varepsilon)$ denote the set of feasible
mechanisms. Clearly,
$\Pi^{\star}(\mathcal{M}(\varepsilon))\leq\Pi^{\star}(\mathcal{M}_{\text{path}}(\varepsilon))$.
The first set of constraints in ($\mathcal{P}_{\text{path}}$) come from the
individual rationality constraints in the original problem. However, we only
consider (IR) for types with low values (below $\mu$). Intuitively, individual
rationality constraints are always binding for low value buyers. Meanwhile,
incentive compatibility constraints are in general binding for high value
buyers. This leads to the second set of constraints which come from the
original approximate incentive compatibility constraints. Here we consider the
pairs $(v,{v^{\star}}(v))$ for $v\geq\mu$. That is, for any type $v\geq\mu$ we
consider a downward misreport of size $v-{v^{\star}}(v)$. The latter choice
captures an essential property of most optimal contracts in mechanism design,
namely, higher types have an incentive to report low values and so the
mechanism should prevent such deviations. We note that there are many choices
for an upper bound problem such as ($\mathcal{P}_{\text{path}}$). However, the
above problem strikes a balance in the sense that it captures key properties
of optimal mechanisms (we keep the constraints that are most likely to bind),
and it also parametrizes these properties in a simple and, as we will shortly
see, tractable way.

For each constraint ($\text{IR}_{\mu}$) and ($\text{IC}_{\mu}$), we introduce
dual variables $\lambda^{\scriptscriptstyle\text{\rm
IR}}:[0,\mu]\rightarrow\mathbb{R}_{+}$ and
$\lambda^{\scriptscriptstyle\text{\rm
IC}}:[\mu,\bar{v}]\rightarrow\mathbb{R}_{+}$, respectively. After dualizing
these constraints and optimizing over $(x,t)$ we obtain the following result.

######  Lemma 3.3 (Weak duality)

Consider the dual problem

$\displaystyle\Pi^{\star}(\mathcal{D})\triangleq\min_{\begin{subarray}{c}\lambda^{{\scriptscriptstyle\text{\rm
IC}}}:[\mu,\overline{v}]\rightarrow\mathbb{R}_{+}\end{subarray}}$
$\displaystyle\Phi_{1}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})+\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$ ($\mathcal{D}$)
s.t. $\displaystyle\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)=f(v),\quad\text{a.e on }[\nu_{0},\overline{v}],$
$\displaystyle\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)=f(v)+\dot{w}(v)\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v)),\quad\text{a.e on }[\mu,\nu_{0}],$

where

$\Phi_{1}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})=\varepsilon\int_{\mu}^{\bar{v}}\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)\text{d}v\quad\text{and}\quad\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})=\int_{0}^{\bar{v}}\Big{(}vf(v)-\dot{w}(v)(v-w(v))\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v))\mathbf{1}_{\\{v\in[0,\nu_{0}]\\}}\Big{)}^{+}\text{d}v.$

Then,

$\Pi^{\star}(\mathcal{M}_{\text{path}}(\varepsilon))\leq\Pi^{\star}(\mathcal{D}).$

The result above is obtained by first forming the Lagrangian for
($\mathcal{P}_{\text{path}}$). Since the transfer $t(\cdot)$ is a free
variable, all terms that multiply $t(v)$ must equal zero for (almost) every
realization of the values. This leads to a set of conditions the dual
variables should satisfy which, in turn, completely pin down the dual variable
of the IR constraint $\lambda^{{\scriptscriptstyle\text{\rm IR}}}$ and give a
functional equation that determines the dual variable
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}$. Therefore, in the dual problem
we can eliminate $\lambda^{{\scriptscriptstyle\text{\rm IR}}}$ and state the
problem in terms of $\lambda^{{\scriptscriptstyle\text{\rm IC}}}$ directly.
Our dual problem is an infinite-dimensional mathematical program with
constraints given by functional equations.

The new upper bound objective has two terms. The first,
$\Phi_{1}(\lambda^{\scriptscriptstyle\text{\rm IC}})$, comes from the
approximate incentive constraint ($\text{IC}_{\mu}$) while the second term,
$\Phi_{2}(\lambda^{\scriptscriptstyle\text{\rm IC}})$, comes from optimizing
$x(v)\in[0,1]$. Due to the functional equation that defines
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}$, problem ($\mathcal{D}$) does
not have a straightforward solution. Moreover, its solution depends on our
choice of $w(\cdot)$ which we have not explicitly defined yet. In order to
circumvent this, we provide further bounds for the dual problem. In what
follows, we develop structural properties for ($\mathcal{D}$). These
properties will provide guidelines for how to choose $w(\cdot)$ and will lead
us to develop a tight bound for $\Pi^{\star}(\mathcal{D})$.

##### Structural properties.

We provide some definitions and a lemma that simplifies
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}(\cdot)$. We define a sequence of
thresholds $\\{\nu_{k}\\}$ iteratively by

$\nu_{k}=w(\nu_{k+1}),\quad k\geq 0,\quad\nu_{-1}=\overline{v}.$

We let $K$ be the first index such that $\nu_{K}\leq\mu$ and
$\nu_{K-1}\geq\mu$. Since $w(\cdot)$ is strictly increasing, this sequence is
well defined. Also, because $w(x)\geq x$ we have that $\nu_{k}\geq\nu_{k+1}$.
We will refer to $K$ as the number of steps while every interval of the form
$[\nu_{k},\nu_{k-1}]$ will be referred to as a step. Intuitively, $K$ gives
the number of times we need to iterate $w(\cdot)$ to reach the origin starting
from $\nu_{0}$. Geometrically, this sequence is constructed by repeatedly
moving leftward and downward until we touch the best response and the
$45^{\circ}$ line, respectively. See Figure 2 for a graphical representation
of $\\{\nu_{k}\\}$.

$w(v)$$v$$\nu_{0}$$\overline{v}$$45^{\circ}$$\mu$$\nu_{1}$$\nu_{2}$$\nu_{3}$$\nu_{K-1}$$\nu_{K}$$v$$0$$p^{\star}$$p^{\star}_{U}$$p^{\star}_{L}$$\Delta_{U}(v)$$-\dot{R}(v)$$\Delta(v)$$\Delta_{L}(v)$(a)(b)

Figure 2: (a) Illustration of $w$—the inverse of the best-response mapping
${v^{\star}}(\cdot)$—and the sequence $\\{\nu_{k}\\}$. In our relaxation
($\mathcal{P}_{\text{path}}$), we drop all IC constraints except for the pairs
$(v,{v^{\star}}(v))_{v\in[\mu,\overline{v}]}$ or, equivalently,
$(w(v),v)_{v\in[0,\nu_{0}]}$. (b) Illustration for the bound on
$\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$—the integral of
$\Delta(v)$. For $v\geq p^{\star}_{L}$, we bound the integral using Lemma 3.6,
and for $v$ in $[p^{\star}_{U},p^{\star}_{L}]$ we bound it with the area under
$\Delta_{U}(v)$.

The purpose of defining the thresholds $\\{\nu_{k}\\}$ is that they allow to
look at the functional equation that defines
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}$ in ($\mathcal{D}$) from a
different perspective. In particular, we can obtain a quasi-closed form
solution for $\lambda^{{\scriptscriptstyle\text{\rm IC}}}$ that depends on
these thresholds by iteratively solving for
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}$ in each step.

######  Lemma 3.4 (Solution to Functional Equation)

A solution $\lambda^{{\scriptscriptstyle\text{\rm IC}}}(\cdot)$ to Problem
($\mathcal{D}$) is given by, for any $k\in\\{0,\dots,K\\}$ and for any
$v\geq\mu$,

$\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)=\frac{d}{dv}\sum_{j=0}^{k}F(w^{j}(v)),\quad\text{a.e on
}[\nu_{k},\nu_{k-1}].$

where $w^{j}(v)$ is the $j$th composition of $w$ and $w^{0}(v)=v$.

Armed with Lemma 3.4 we can derive upper bounds for
$\Phi_{1}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$ and
$\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$ that depend solely on
properties of $w(\cdot)$.

######  Lemma 3.5 (Bound on Number of Steps)

There exists a constant $C>0$ such that

$\Phi_{1}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})\leq
C\cdot\varepsilon\cdot K.$

Lemma 3.5 asserts that $\Phi_{1}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$
is bounded above by $\varepsilon\cdot K$ where $K$ is the number of steps. We
prove the result by using our formula for
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}$ given in Lemma 3.4, which allows
us to easily integrate the dual variable in each step, and then telescoping
the resulting sums.

######  Lemma 3.6 (Dual Virtual Value Bound)

Define the integrand of $\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})$ by

$\Delta(v)\triangleq
vf(v)-\dot{w}(v)(w(v)-v)\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v))\mathbf{1}_{\\{v\in[0,\nu_{0}]\\}}.$

Suppose that $\Delta(v)$ is non-negative in $[x,\nu_{0}]$ for some
$x\in[0,\nu_{0})$ then

$\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})=\int_{x}^{\overline{v}}\Delta(v)dv\leq R(x)+2\cdot(w(x)-x).$

Lemma 3.6 is reminiscent of the analysis in classical mechanism design where
it is shown that the integral of the virtual value times the density in an
interval $[x,\overline{v}]$ equals the revenue function
$R(x)=x\cdot\bar{F}(x)$. However, in our dual problem, we do not have the
standard virtual value $\psi(v)$ in the objective but a modified “dual virtual
value” given by $\Delta(v)$, whose integral can be bounded in terms of the
revenue function and an additional correction term proportional to $w(x)-x$.

##### Designing a best-response mapping.

We leverage the structural properties developed in Lemma 3.5 and Lemma 3.6 to
build a candidate $w(\cdot)$ that is both easy to manipulate—it allows for a
closed-form approximation for $\lambda^{{\scriptscriptstyle\text{\rm
IC}}}$—and that yields a tight upper bound. The previous lemmas provide two
guidelines for choosing $w(\cdot)$. First, to apply Lemma 3.6 we need to
design the inverse reporting $w(\cdot)$ such that $\Delta(v)$ crosses zero
only once and, at the crossing point, its distance to the $45^{\circ}$ line as
measured by $w(x)-x$ is of order $\varepsilon^{\alpha/(2\alpha-1)}$. This
implies that, as $\varepsilon$ goes to zero, the inverse reporting function
must get closer to the $45^{\circ}$ line. Second, from Lemma 3.5, $w(\cdot)$
must be such that the number of steps scales, at most, with order
$\varepsilon^{(1-\alpha)/(2\alpha-1)}$ (which goes to infinity as
$\varepsilon\downarrow 0$) to yield a revenue improvement of
$\varepsilon^{\alpha/(2\alpha-1)}$. Therefore, because the number of steps
increases as the inverse reporting function gets closer to the $45^{\circ}$
line, $w(\cdot)$ should not approach the $45^{\circ}$ line too fast. The two
lemmas present a trade off: we would like to set $w(x)-x$ small but not too
small otherwise $K$ may be too large.

A first, natural approach would be to choose $w(x)=x+\delta$ with $\delta>0$,
i.e., the buyer is under-reporting by an amount of $\delta$. This choice would
converge to the truthful reporting function as $\delta$ decreases. Because the
number of steps is proportional to $1/\delta$, assuming that we can use the
lemmas above, it is possible to show that

$\Phi_{1}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})+\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})\leq\frac{C\cdot\varepsilon}{\delta}+\Pi^{\star}(\mathcal{M}(0))+2\cdot\delta,$

where we have used that, for any $x$, $R(x)\leq\Pi^{\star}(\mathcal{M}(0))$.
With this choice of $w$ it is optimal to set $\delta\approx\epsilon^{1/2}$,
which yields the upper bound $\mathcal{O}(\varepsilon^{1/2})$ . (Choosing a
smaller value of $\delta$ would necessarily lead to a too-large number of
steps.) This simple choice of $w(\cdot)$ is, unfortunately, not tight but
provides an alternative proof to Proposition 3.1 using our duality based
approach. The strength of our approach is that it provides the flexibility to
design the best-response function and choose a $w(\cdot)$ that leads to an
improved bound. To do so, we need $w(\cdot)$ to be closer to the $45^{\circ}$
line while, at the same time, preventing the number of steps from growing too
fast. The previous analysis shows this is impossible to achieve with a linear
$w(\cdot)$. We address this challenge by making $w(\cdot)$ piecewise linear
with a kink at $p^{\star}$. By carefully adjusting the slope of $w(\cdot)$ we
can guarantee that the number of steps does not grow too fast while
approaching the $45^{\circ}$ line at the right rate.

Our choice of $w(\cdot)$ is given by

$w(v)=\begin{dcases*}m\cdot(v-p^{\star})+p^{\star}+\varepsilon^{1-\beta}&\mbox{if
} $v\geq p^{\star};$\\\
(2-m)\cdot(v-p^{\star})+p^{\star}+\varepsilon^{1-\beta}&\mbox{if } $v\leq
p^{\star},$\end{dcases*}\quad
m=\frac{\overline{v}-(p^{\star}+\varepsilon^{1-\beta})}{\nu_{0}-p^{\star}},\quad\nu_{0}=\overline{v}-\varepsilon^{\beta},$
(9)

for $\beta\in(0,1/2)$. The closest point of $w(\cdot)$ to the $45^{\circ}$
line is at $p^{\star}$ where the distance is $\varepsilon^{1-\beta}$. The
slopes of $w(\cdot)$ are $m>1$ and $2-m<1$ to the right and left of
$p^{\star}$, respectively. This choice of $w(\cdot)$ trades off tractability
and tightness of our bound. Indeed, because $w(\cdot)$ is a piecewise linear
function we can obtain a simple approximation for
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}$ and, ultimately, analyze
$\Delta(v)$ in a tractable way. In order to obtain a tight bound, we
constructed $w(\cdot)$ such that as $\varepsilon\downarrow 0$, $w(\cdot)$
approaches the $45^{\circ}$ line in two ways: the slope converges to one and
the distance converges to zero. By doing so, as we explain next, we can
guarantee that $w(\cdot)$ balances the number of steps $K$ and the difference
$w(x)-x$ in Lemma 3.5 and Lemma 3.6.

For $w(\cdot)$ defined above, we leverage Lemma 3.5 and Lemma 3.6 to obtain
closed form bounds in terms of $\varepsilon$ for the dual problem. We begin by
bounding the number of steps.

######  Proposition 3.7 (Number of Steps)

Under $w(\cdot)$ given by eq. 9 the number of steps, $K$, satisfies
$K=\mathcal{O}\left(\log(1/\varepsilon)/\varepsilon^{\beta}\right).$

The intuition behind the proposition is simple. For ease of exposition,
consider the number of steps above $p^{\star}$. Since $w(\cdot)$ is linear
with slope $m$, it must be that
$(w(\nu_{k})-w(\nu_{k+1}))/(\nu_{k}-\nu_{k+1})=m$. But by the definition of
$\nu_{k}$ this is equivalent to
$(w(\nu_{k+1})-\nu_{k+1})=(w(\nu_{k})-\nu_{k})/m$. That is, the distance
between $w(\cdot)$ and the $45^{\circ}$ degree line decreases by a factor of
$1/m$ in every step. In general, we have that
$(w(\nu_{k})-\nu_{k})=(\overline{v}-\nu_{0})/m^{k}$. Because
$w(p^{\star})-p^{\star}=\varepsilon^{1-\beta}$, the number of steps above
$p^{\star}$ is the value of $K$ such that
$(w(\nu_{K})-\nu_{K})\approx\varepsilon^{1-\beta}$ and, therefore,

$K\approx\frac{\log((\overline{v}-\nu_{0})/\varepsilon^{1-\beta})}{\log(m)}=\mathcal{O}\left(\log(1/\varepsilon)/\varepsilon^{\beta}\right),$

where the last equality comes from a Taylor series around $\varepsilon=0$ and
from $m-1\approx\varepsilon^{\beta}$. By combining this result and Lemma 3.5,
we deduce that $\Phi_{1}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$ is
upper bounded by a term proportional to
$\log(1/\varepsilon)\cdot\varepsilon^{1-\beta}$.

Next, we use Lemma 3.6 to bound
$\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$. The key idea of our
argument is to show that, given our choice of $w(\cdot)$, there exists a
vanishing neighborhood $(p^{\star}_{U},p^{\star}_{L})$ of size
$\varepsilon^{\beta/(\alpha-1)}$ around $p^{\star}$ such the integrand in
$\Delta(v)$ is negative below and positive above the neighborhood. Below the
neighborhood, the integral is zero because we take the positive part of
$\Delta(v)$. Inside the neighborhood, the integral of $\Delta(v)$ is at most
$\mathcal{O}(\varepsilon^{\beta+\beta/(\alpha-1)})$ because both the integrand
and the size of neighborhood are small. Above the neighborhood, we can use
Lemma 3.6 to obtain an upper bound for
$\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$ which, together with
the fact that $w(v)-v\approx\varepsilon^{1-\beta}$ for $v\approx p^{\star}$,
obtains an upper bound of $\mathcal{O}(\varepsilon^{\gamma})$, with
$\gamma=\min\\{1-\beta,\beta+\beta/(\alpha-1)\\}$. We illustrate this in
Figure 2 (a) and provide a more detailed explanation next.

By developing an approximation for $\lambda^{{\scriptscriptstyle\text{\rm
IC}}}$, we can establish that

$\Delta_{L}(v)\triangleq
vf(v)-\bar{F}(v)-K_{1}\cdot\varepsilon^{\beta}\leq\Delta(v)\leq
vf(v)-\bar{F}(v)+K_{2}\cdot\varepsilon^{\beta}\triangleq\Delta_{U}(v),$

almost everywhere, that is, $\Delta(v)$ converges uniformly (almost
everywhere) to the negative of the derivative of the revenue function
$-R^{\prime}(v)=vf(v)-\bar{F}(v)$. Note that we cannot simply use
$\Delta_{U}(v)$ to bound $\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})$ because that would lead to a bound of
$\mathcal{O}(\varepsilon^{\beta})$. Instead, we can use $\Delta_{L}(v)$ and
$\Delta_{U}(v)$ to approximate where $\Delta(v)$ crosses zero and then apply
Lemma 3.6.

Using the lower bound above and the local $\alpha$-power envelopes of the
revenue function given in Definition 2.1, we can determine the right endpoint
of our neighborhood to be $p^{\star}_{L}\approx
p^{\star}+\varepsilon^{\beta/(\alpha-1)}$ above which $\Delta_{L}(v)$ is non-
negative and, therefore, $\Delta(v)$ is non-negative above $p^{\star}_{L}$. By
Lemma 3.6, we have

$\int_{p^{\star}_{L}}^{\overline{v}}\Delta(v)dv\leq
R(p^{\star}_{L})+2(w(p^{\star}_{L})-p^{\star}_{L}).$ (10)

The left endpoint of the neighborhood is similarly determined to be
$p^{\star}_{U}\approx p^{\star}-\varepsilon^{\beta/(\alpha-1)}$ below which
$\Delta(v)$ can be guaranteed to be non-positive. Now, within the neighborhood
we cannot control the sign of $\Delta(v)$; however, we can make use of
$\Delta_{U}(v)$ as follows:

$\int_{p^{\star}}^{p^{\star}_{L}}\Delta(v)^{+}dv\leq\int_{p^{\star}}^{p^{\star}_{L}}\Delta_{U}(v)dv=R(p^{\star})-R(p^{\star}_{L})+\mathcal{O}(\varepsilon^{\beta+\beta/(\alpha-1)}),$
(11)

by integrating the derivative of the revenue function which is negative above
$p^{\star}$ and using that $[p^{\star},p^{\star}_{L}]$ has size
$\varepsilon^{\beta/(\alpha-1)}$. In $[p^{\star}_{U},p^{\star}]$,
$\Delta_{U}(v)^{+}$ is bounded above by $K_{2}\varepsilon^{\beta}$ because the
derivative of the revenue function is positive in this interval. Hence, in
this interval, the integral of $\Delta(v)^{+}$ is at most of size
$\mathcal{O}(\varepsilon^{\beta+\beta/(\alpha-1)})$. Combining this with (10)
and (11):

$\int_{0}^{\overline{v}}\Delta(v)^{+}dv\leq
R(p^{\star})+2(w(p^{\star}_{L})-p^{\star}_{L})+\mathcal{O}(\varepsilon^{\beta+\beta/(\alpha-1)})=\Pi^{\star}(\mathcal{M}(0))+\mathcal{O}(\varepsilon^{\beta+\beta/(\alpha-1)})+\varepsilon^{1-\beta},$

where we have used the definition of $w(\cdot)$ and that
$m-1\approx\varepsilon^{\beta}$. We obtain Theorem 3.2 by combining the
previous upper bound with Proposition 3.7, which gives a bound for the dual
problem of order $\tilde{\mathcal{O}}(\varepsilon^{\gamma})$ with
$\gamma=\min\\{1-\beta,\beta+\beta/(\alpha-1)\\}$. The latter is minimized by
taking $\beta=(\alpha-1)/(2\alpha-1)$ which, in turn, yields
$\gamma=\alpha/(2\alpha-1)$.

##  4 Performance of deterministic mechanisms

In the previous section, we developed an upper bound on the revenue gains for
the seller. We now begin our analysis of the achievable revenue gains by
looking at the class of deterministic mechanisms, i.e., the class

$\displaystyle\mathcal{M}_{\texttt{d}}(\varepsilon)=\left\\{m\in\mathcal{M}(\varepsilon):x(\cdot):\mathcal{S}\rightarrow\\{0,1\\}\right\\}.$

By analyzing this class of mechanism, we will develop a lower bound for
Equation 1 which, together with the upper bound, will define the feasible
spectrum of achievable revenue performances. Deterministic mechanisms are also
appealing in practice because the buyer can always expect the same outcome
from the same report. It is important to note that when $\varepsilon=0$, an
optimal mechanism is deterministic and hence included in
$\mathcal{M}_{\texttt{d}}(0)$. The next result characterizes the best
performance of deterministic mechanisms.

######  Theorem 4.1 (Deterministic mechanisms)

Suppose Section 2 holds. An optimal deterministic mechanism,
$m_{\textup{{d}}}=(x_{\textup{{d}}},t_{\textup{{d}}})$, is given by the
hard/soft floor mechanism:

$\displaystyle x_{\textup{{d}}}(v)$ $\displaystyle=$
$\displaystyle\mathbf{1}\\{v\in[p,\overline{v}]\\},$ $\displaystyle
t_{\textup{{d}}}(v)$ $\displaystyle=$ $\displaystyle
v\>\mathbf{1}\\{v\in[p,s]\\}+s\>\mathbf{1}\\{v\in[s,\overline{v}]\\},$

where the hard floor $p$ and soft floor $s$ satisfy $s=p+\epsilon$ and are
chosen to maximize revenue. Furthermore, the optimal performance satisfies

$\Pi^{\star}(\mathcal{M}_{\texttt{d}}(\varepsilon))\>-\>\Pi^{\star}(\mathcal{M}(0))\>=\>\Theta(\varepsilon).$

The theorem establishes that over the entire class of $\varepsilon$-IC
deterministic mechanisms, the seller cannot exploit the relaxation of the IC
constraints to yield more than linear gains in $\varepsilon$. Furthermore,
this bound is shown to be tight for deterministic mechanisms as one can
exhibit a mechanism that yields such gains in performance. That is, there
exist mechanisms that yield a linear improvement when relaxing the IC
constraints. This sets a lower bound on the performance that can be achieved
in the approximate-IC setting. Any optimal approximate-IC mechanism should
deliver at least linear gains compared to the optimal performance with IC
constraints. Furthermore, we know that it is impossible to break the linear
barrier with deterministic mechanisms. This means that the spectrum of
achievable performances ranges in general from $\varepsilon$ to
$\varepsilon^{1/2}$, but from Theorem 3.2 this spectrum can be tightened: it
becomes $\varepsilon$ to $\varepsilon^{\alpha/(2\alpha-1)}$ when we account
for the characteristics of a distribution. The next natural questions that
emerge are whether this linear guarantee can be surpassed, and if so, how much
more performance gain can be achieved and what mechanisms guarantee such
improved performance, i.e., is the $\varepsilon^{\alpha/(2\alpha-1)}$
performance achievable? In the next section, we will expand to broader
families of randomized mechanisms and provide a positive answer to these
questions.

##### Discussion and proof ideas.

The proof is organized around two main steps. We first establish that an
optimal deterministic mechanism must take the form of a hard/soft floor
mechanism, i.e., a mechanism characterized by a pair $(p,s)$ with $p\leq
s\leq\overline{v}$ such that the allocation and payments are as in the
statement of the theorem. In this family of mechanisms, if the buyer’s bid is
between the hard and soft floor then he pays his own bid and is allocated the
item. If the buyer’s bid is above the soft floor then he pays the soft floor
and is allocated the item. Otherwise the item is not allocated and the buyer
does not incur any payment. Incidentally, this class of mechanisms that
naturally emerges in the $\varepsilon$-IC setting has been used by some online
advertising platforms in the past to extract revenue from buyers with high
values (MoPub 2013, Zeithammer 2019).

In the second step of the proof, we show that there exists
$r\in[0,\overline{v}]$ such that the optimal hard/soft floor mechanism is
characterized by $p=r$ and $s=r+\varepsilon$. Note that this is an alternative
way to show that when $\varepsilon=0$ the optimal deterministic mechanism must
be the optimal posted price $p^{\star}$. Importantly, from this
characterization one can readily obtain the upper bound in the theorem.
Indeed, using integration by parts, we obtain that the revenue of
$m_{\textup{{d}}}$ with hard/soft floors as above satisfies

$\Pi(m_{\textup{{d}}})=r\cdot\overline{F}(r)+\int_{r}^{r+\varepsilon}\overline{F}(v)dv\>\leq\>R(r)+\varepsilon\>\leq\>\Pi^{\star}(\mathcal{M}(0))+\varepsilon,$

where the first inequality follows because $\overline{F}(v)\leq 1$ and the
second by optimizing over $r$. The lower bound is derived in a similar fashion
except that we replace $r$ with $p^{\star}$ and bound the integral above from
below by $\overline{F}(p^{\star}+\varepsilon)$, which is positive for small
enough $\epsilon>0$ because the optimal posted price is interior.

Interestingly, for hard/soft floor mechanisms, truthful reporting is not a
best reporting strategy. A best reporting strategy is given by

$v_{\textup{{d}}}^{\star}(v)=\begin{dcases*}0&\mbox{if } $v\in[0,r);$\\\
r&\mbox{if } $v\in[r,\overline{v}].$\end{dcases*}$ (12)

See Figure 4 (b) for an illustration. For $v\in[r,\overline{v}]$ the best
reporting strategy for the buyer is always to report a lower type, namely,
$v_{\textup{{d}}}^{\star}(v)=r$ and gain a utility of $v-r$. Nevertheless,
since the buyer is $\varepsilon$-optimizer he will be willing to bid $v$ and
take a loss of at most $\varepsilon$. The mechanism exploits this fact to
obtain an extra revenue of
$\int_{r}^{r+\varepsilon}\overline{F}(v)dv=\mathcal{O}(\varepsilon)$ compared
to the optimal posted-price mechanism.

The main departure point of ($\mathcal{P}_{\varepsilon}$) from
$(\mathcal{P}_{0})$ is that in the former the reporting function is not
necessarily determined by the incentive constraints and, therefore, one can
perform the optimization in ($\mathcal{P}_{\varepsilon}$) by searching over
the space of reporting functions. In the space of deterministic mechanisms, if
we fix the allocation to $x_{\textup{{d}}}(\cdot)$ and choose as a reporting
function $v_{\textup{{d}}}^{\star}(\cdot)$ as described above, then from
($\mbox{IC}_{\varepsilon}$) and (IR) it is possible to infer that the transfer
$t_{\textup{{d}}}(\cdot)$ must be zero below $r$ and bounded above by
$\min\\{t_{\textup{{d}}}(r)+\varepsilon,v\\}$ with $t_{\textup{{d}}}(r)\leq
r$. Therefore, if we optimize over the transfer, we will end up with
$t_{\textup{{d}}}(\cdot)$ as in the statement of Theorem 4.1. In other words,
in mechanism design with approximate incentive compatibility we have two
degrees of freedom when designing mechanisms: allocations and reporting
functions. In the following section, we will exploit this observation to
analyze the richer class of randomized mechanisms.

##  5 Near Optimal Mechanisms

In Section 3, we saw that the relaxation to $\varepsilon$-IC mechanisms can
lead to at most $\tilde{\mathcal{O}}(\varepsilon^{\alpha/(2\alpha-1)})$
revenue gains for $\alpha\in(1,\infty)$ compared to $(\mathcal{P}_{0})$. In
this section, we establish that our upper bound is tight by developing a lower
bound for the growth rate of
$\Pi^{\star}(\mathcal{M}(\varepsilon))\>-\>\Pi^{\star}(\mathcal{M}(0))$ as a
function of $\varepsilon$. We also present some of the main proof ideas as
they highlight new techniques and arguments that are critical for the
understanding of $\varepsilon$-IC mechanism design problems. We present the
main result of this section next.

######  Theorem 5.1 (Performance Lower Bound)

Suppose Section 2 holds, and that the revenue function admits local
$\alpha$-power envelopes in a neighborhood $\mathcal{N}_{\ell}$ of
$p^{\star}$. Then

$\Pi^{\star}(\mathcal{M}(\varepsilon))\>-\>\Pi^{\star}(\mathcal{M}(0))\>=\>\Omega(\varepsilon^{\alpha/(2\alpha-1)}).$

This result has multiple implications. First, it shows that the seller can
benefit by at least $\Omega(\varepsilon^{\alpha/(2\alpha-1)})$ by offering a
mechanism that is $\varepsilon$-IC as opposed to IC. That is, when we search
in the entire class of $\varepsilon$-IC mechanisms,
$\mathcal{M}(\varepsilon)$, quite notably, it is indeed possible to achieve
supralinear gains compared to when we restrict attention to $\mathcal{M}(0)$.
In conjunction with Theorem 5.1, we obtain that there exist constants
$\underline{C},\bar{C}>0$ such that for all $\varepsilon$ small enough

$\underline{C}\varepsilon^{\alpha/(2\alpha-1)}\>\leq\>\Pi^{\star}(\mathcal{M}(\varepsilon))\>-\>\Pi^{\star}(\mathcal{M}(0))\>\leq\>\bar{C}\varepsilon^{\alpha/(2\alpha-1)}\log(1/\varepsilon),\quad\alpha\in(1,\infty).$

In other words, we have established that it is possible to achieve supralinear
growth and characterized the types of supralinear growths that are possible
ranging from linear to square root performance. Interestingly, in contrast to
classical linear programming, a linear perturbation to the infinite-
dimensional linear program ($\mathcal{P}_{\varepsilon}$) leads to a nonlinear
gain in the objective. In conjunction with Theorem 4.1, this result also
establishes the crucial role that randomization takes in the class of
$\varepsilon$-IC problems: An optimal mechanism has to randomize as soon as
$\varepsilon>0$.  This implies that the extreme points in
($\mathcal{P}_{\varepsilon}$) and $(\mathcal{P}_{0})$ are of a very different
nature. In $(\mathcal{P}_{0})$ the extreme points are posted-price mechanisms;
however, Theorem 5.1 establishes that perturbing the IC constraints in a
mechanism design problem fundamentally changes the feasible region and the set
of extreme points is richer. In Figure 3, we depict a near optimal
$\varepsilon$-IC mechanism that exhibits randomization. This highlights the
subtle and deep impact of relaxing IC constraints on the nature of the
optimization problem, and the significant impact it has on the performance
that can be achieved (see Martin et al. 2016 and Basu et al. 2017 for other
examples of properties that are true in finite dimension but fail in infinite-
dimensional optimization problems).

$v$0$x(v)$$1$$v$0$t(v)$$0.5$$p^{\star}$$p^{\star}$near-optimal
($m_{\textup{{pd}}}$)deterministic ($m_{\textup{{d}}}$)

Figure 3: Allocations and transfers of the lower bound mechanism and the
optimal deterministic mechanism when $F$ is uniform in $[0,1]$, i.e.,
$\alpha=2$, and $\varepsilon=0.001$. Because $\varepsilon$ is small, the
optimal posted-price mechanism when $\varepsilon=0$ is almost
indistinguishable from $m_{\textup{{d}}}$.

The Proof of Theorem 5.1 is constructive in that we judiciously construct a
feasible mechanism that yields said performance. The proof also sheds light on
what are the key forces at play when optimizing over
$\mathcal{M}(\varepsilon)$, and showcases important departures from the
classical mechanism design approach. We next detail the proof and its main
building blocks.

###  5.1 Proof of Theorem 5.1

The proof has three main components. First we propose a family of mechanisms
through an endogenous characterization. This characterization critically
depends on a carefully designed parametric family of best reporting mappings
which indirectly induce the mechanisms. In particular, we establish that for
our proposed family, the allocation is fully characterized by a system of
ordinary and delayed differential equations. We then solve this system and
establish that the induced mechanisms are feasible for
($\mathcal{P}_{\varepsilon}$). Finally, we characterize the performance of
these mechanisms and, by optimizing over their defining parameters, we obtain
the $\Omega(\varepsilon^{\alpha/(2\alpha-1)})$ revenue gains.

####  5.1.1 Step 1: A Proposed Family of Mechanisms

Our main challenge is to exhibit a feasible mechanism that is simple enough so
that we can analyze its performance, but rich enough so that it can garner
additional $\varepsilon^{\alpha/(2\alpha-1)}$ revenue gains. We accomplish
this in two steps. First, we propose a suitable family of best reporting
functions ${v^{\star}}(\cdot|\mu,\delta)$ parametrized by $(\mu,\delta)$ (see
eq. 13). Second, we establish a consistency property of
${v^{\star}}(\cdot|\mu,\delta)$: it coincides with the best reporting function
of a family of mechanisms that we coin perturbed delayed mechanisms (see
Proposition 5.2).

##### Best reporting function.

In Section 2, we saw that standard reductions no longer apply when
$\varepsilon>0$. In particular, after selecting a mechanism
$m\in\mathcal{M}(\varepsilon)$ the seller must also account for the best
reporting mappings ${v^{\star}}(\cdot)$ (c.f., eq. 5). Consequently, the
optimization must be indirectly performed over the triplet
$(x,t,{v^{\star}})$. One possible approach to come up with a feasible solution
for ($\mathcal{P}_{\varepsilon}$) is to define a pair $(x,t)$ that is both IR
and $\varepsilon$-IC. However, such an approach is challenging given the lack
of control on ${v^{\star}}(\cdot)$. To bypass this issue, the approach we take
is to define ${v^{\star}}(\cdot)$ as a natural perturbation of
$v_{\textup{{d}}}^{\star}(\cdot)$, defined in Equation 12 and depicted in
Figure 4 (b). Then we use the fact that ${v^{\star}}(v)$ must maximize $v\cdot
x(w)-t(w)$ for some $m=(x,t)\in\mathcal{M}(\varepsilon)$ to reverse engineer
the mechanism $m$ that is consistent with ${v^{\star}}(\cdot)$. The
perturbation of the reporting function will lead to randomization in the
mechanisms that induce it. We define the best reporting mappings
${v^{\star}}(\cdot|\mu,\delta)$—a perturbation of
$v_{\textup{{d}}}^{\star}(\cdot)$—parametrized by some positive constants
$(\mu,\delta)$ as follows

${v^{\star}}(v|\mu,\delta)\triangleq\begin{dcases*}0&\mbox{if }
$v\in[0,p^{\star}-\delta);$\\\ v-\mu&\mbox{if }
$v\in[p^{\star}-\delta,p^{\star}+\delta+\mu];$\\\ p^{\star}+\delta&\mbox{if }
$v\in[p^{\star}+\delta+\mu,\overline{v}].$\end{dcases*}$ (13)

We assume that $\delta<p^{\star}$ and $p^{\star}+\delta+\mu<\overline{v}$,
which is possible because the optimal posted price $p^{\star}$ is assumed to
be interior.

$v_{\textup{{d}}}^{\star}(v)$$v$$p^{\star}$$p^{\star}$${v^{\star}}(v|\mu,\delta)$$v$$p^{\star}-\delta$$p^{\star}-\delta-\mu$$p^{\star}+\delta+\mu$$p^{\star}+\delta$$p^{\star}$$p^{\star}$(b)(a)

Figure 4: Illustration of (a) the parametrized best reporting function and (b)
the best reporting function for a hard/soft floor mechanism with $p=p^{\star}$
and $s=p^{\star}+\varepsilon$.

For a graphical illustration of ${v^{\star}}(v|\mu,\delta)$ see Figure 4 (a).
In what follows, when clear from context, we drop the dependence on
$(\mu,\delta)$ and use ${v^{\star}}(v)$ to denote ${v^{\star}}(v|\mu,\delta)$.
The definition of ${v^{\star}}(\cdot)$ implies that under the associated
mechanism the best reporting function always misreports the value in a
downward fashion, ${v^{\star}}(v)\leq v$. It equals 0 for small enough
valuations (below $p^{\star}-\delta$), $v-\mu$ for intermediate valuations (in
$[p^{\star}-\delta,p^{\star}+\delta+\mu]$) and $p^{\star}+\delta$ for large
valuations (above $p^{\star}+\delta$).

Note that ${v^{\star}}(\cdot)$ generalizes the best reporting functions of the
hard/soft floor mechanism $(p^{\star},p^{\star}+\varepsilon)$. Indeed, for
$\delta=0$ both functions coincide, except in $[p^{\star},p^{\star}+\mu]$
where ${v^{\star}}(\cdot)$ is linear. However, as $\mu$ becomes smaller the
functions become indistinguishable, i.e., $\lim_{\mu\downarrow
0}{v^{\star}}(v|\mu,0)=v_{\textup{{d}}}^{\star}(v)$.

##### Perturbed delayed mechanisms.

We first establish that it is possible to characterize the allocation and
payments associated to ${v^{\star}}(\cdot)$ through a set of ordinary and
delayed differential equations. Before stating the result, we let $w(\cdot)$
denote the generalized inverse of ${v^{\star}}(\cdot)$, which is given by

$w(v)\triangleq\begin{dcases*}p^{\star}-\delta&\mbox{if }
$v\in[0,p^{\star}-\delta-\mu];$\\\ v+\mu&\mbox{if }
$v\in[p^{\star}-\delta-\mu,p^{\star}+\delta].$\end{dcases*}$

######  Proposition 5.2 (Perturbed delayed mechanisms)

Let $x_{\textup{{pd}}}:[0,p^{\star}+\delta]\rightarrow\mathbb{R}$ be a
solution of the system

$\displaystyle\dot{x}_{\textup{{pd}}}(v)$
$\displaystyle=\frac{x_{\textup{{pd}}}(v)}{w(v)-v},\>\>\forall
v\in[0,p^{\star}-\delta],\qquad
x_{\textup{{pd}}}(0)=\frac{\varepsilon}{p^{\star}-\delta},$ (ODE)
$\displaystyle\dot{x}_{\textup{{pd}}}(v)$
$\displaystyle=\frac{x_{\textup{{pd}}}(v)-x_{\textup{{pd}}}({v^{\star}}(v))}{w(v)-v},\>\>\forall
v\in[p^{\star}-\delta,p^{\star}+\delta].$ (DDE)

Moreover, let $x_{\textup{{pd}}}(v)=1$ for all
$v\in(p^{\star}+\delta,\overline{v}]$ and let
$t_{\textup{{pd}}}:[0,\overline{v}]\rightarrow\mathbb{R}$ be given by

$t_{\textup{{pd}}}(v)=\begin{dcases*}v\cdot x_{\textup{{pd}}}(v)&\mbox{if }
$v<p^{\star}-\delta;$\\\ v\cdot
x_{\textup{{pd}}}(v)-\int_{0}^{v}x_{\textup{{pd}}}({v^{\star}}(s))ds+\varepsilon&\mbox{if
} $v\geq p^{\star}-\delta.$\end{dcases*}$

If $\lim_{v\uparrow p^{\star}+\delta}x_{\textup{{pd}}}(v)=1$, then
${v^{\star}}(\cdot)$, defined in (13), is a best reporting function for
$m_{\textup{{pd}}}=(x_{\textup{{pd}}},t_{\textup{{pd}}})$.

This result provides a partial characterization of the family of mechanisms
that lead to ${v^{\star}}(\cdot)$. The allocation, and as a consequence the
transfers, are determined by a set of ordinary (ODE) and delayed differential
equations (DDE). That is, Proposition 5.2 equips us with a precise methodology
to generate mechanisms. (In the next section we will show that there is a
range of values $(\mu,\delta)$ for which $m_{\textup{{pd}}}$ is indeed an
$\varepsilon$-IC mechanism.) Given that $x_{\textup{{pd}}}$ must be found by
solving a delayed differential equation and that it depends on
${v^{\star}}(\cdot)$ (a perturbation of $v_{\textup{{d}}}^{\star}(\cdot)$), we
name the family of mechanisms in Proposition 5.2 the perturbed delayed
mechanisms.

Another important implication of Proposition 5.2 is that it showcases the
relationship between the allocations and transfers as a function of the best
reporting function they induce via (ODE)-(DDE). This highlights that the class
of $\varepsilon$-IC mechanisms is of a different nature compared to the class
of IC mechanism.

To obtain Proposition 5.2 we establish necessary conditions for the
allocations and transfers that induce the postulated best reporting mapping.
Under differentiability conditions, this leads to the set of ordinary and
delayed differential equations for the allocation. Next we provide a heuristic
derivation of the differential equations for $x_{\textup{{pd}}}$ and
transfers. A formal proof of the proposition can be found in the appendix.

Any mechanism $m=(x,t)$ that is compatible with ${v^{\star}}(\cdot)$ must
satisfy condition (5), i.e., the best response function should maximize the
buyer’s utility. If we further assume that the allocations and transfers are
differentiable, and impose that the first order conditions are satisfied at
every ${v^{\star}}(v)$, we deduce that
$v\cdot\dot{x}({v^{\star}}(v))=\dot{t}({v^{\star}}(v))$ for all
$v\in[0,\overline{v}]$. Recalling that $w(\cdot)$ is the generalized inverse
of ${v^{\star}}(\cdot)$, we then have

$w(v)\cdot\dot{x}(v)=\dot{t}(v),\quad\forall v\in[0,p^{\star}+\delta].$ (14)

Note that because ${v^{\star}}(v)=0$ for $v\leq p^{\star}-\delta$ this
equation is valid only for $v\in[p^{\star}-\delta+\mu,p^{\star}+\delta]$. By
extending the equation for $v\leq p^{\star}-\delta+\mu$, we are simply
imposing more structure on $(x,t)$. The equation above characterizes the
transfers (up to a constant) in $[0,p^{\star}+\delta]$ as a function of
$w(\cdot)$ (or, equivalently, as a function of ${v^{\star}}(\cdot)$) and
$x(\cdot)$. We would like, however, to obtain a characterization of both
transfers and allocations as a function of solely ${v^{\star}}(\cdot)$. Using
the structure of the optimal deterministic mechanism and the upper bound
derived in Section 3.2 as motivation, we impose two additional conditions that
will enable us to accomplish this goal. First, we assume that (IR) binds for
all low types $v\in[0,p^{\star}-\delta]$, that is, $v\cdot x(v)-t(v)=0$. By
differentiating, we obtain $x(v)+v\cdot\dot{x}(v)=\dot{t}(v)$ for all
$v\in[0,p^{\star}-\delta]$. Combining this with Eq. (14) yields

$x(v)+(v-w(v))\cdot\dot{x}(v)=0,\quad\forall v\in[0,p^{\star}-\delta].$ (15)

Second, we assume that ($\mbox{IC}_{\varepsilon}$) binds for high types
$v\in[p^{\star}-\delta,\overline{v}]$. When ($\mbox{IC}_{\varepsilon}$) holds,
condition (8) holds with equality and we obtain

$v\cdot
x(v)-t(v)=u(0)+\int_{0}^{v}x({v^{\star}}(s))ds-\varepsilon,\quad\forall
v\in[p^{\star}-\delta,\overline{v}].$

Differentiating both sides above obtains
$x(v)+v\dot{x}(v)-\dot{t}(v)=x({v^{\star}}(v))$ for all
$v\in[p^{\star}-\delta,\overline{v}]$, which in conjuction with eq. 14 implies

$x(v)+(v-w(v))\dot{x}(v)=x({v^{\star}}(v)),\quad\forall
v\in[p^{\star}-\delta,p^{\star}+\delta].$ (16)

In summary, eq. 15 and eq. 16 together provide a characterization (up to a
constant) for the allocation as a function of our choice of best reporting
function ${v^{\star}}(\cdot)$. Note that the solution to these equations only
yields the allocation in $[0,p^{\star}+\delta]$. For higher values we always
allocate. Since we are assuming that (IR) and ($\mbox{IC}_{\varepsilon}$) bind
in $[0,p^{\star}-\delta]$ and $[p^{\star}-\delta,\overline{v}]$, respectively,
we also obtain the transfers for all values. Finally, observe that combining
(IR) and ($\mbox{IC}_{\varepsilon}$) at $p^{\star}-\delta$ implies that
$x(0)=\varepsilon/(p^{\star}-\delta)$. This leads to the systems of ordinary
and delayed differential equations in Proposition 5.2.

####  5.1.2 Step 2: Feasibility of proposed mechanisms

In this section, we establish that the perturbed delayed mechanism from
Proposition 5.2 is feasible, that is,
$m_{\textup{{pd}}}\in\mathcal{M}(\varepsilon)$. To do so, we take two steps.
We first argue that the system (ODE)-(DDE) admits a unique solution and that
the solution is monotone. Then, we establish that for a range of parameters
$(\mu,\delta)$ the mechanism is feasible.

######  Proposition 5.3 (Well-posedness)

The perturbed delayed mechanism $m_{\textup{{pd}}}$ from Proposition 5.2 is
well defined, that is, the system (ODE)-(DDE) has a unique solution. In
addition, $x_{\textup{{pd}}}$ is strictly positive, monotone non-decreasing in
$[0,p^{\star}+\delta]$, and admits a closed-form representation.

We establish the proposition by analyzing the system of differential
equations. Note that (ODE) can be solved by simple integration. However, (DDE)
is a delayed differential equation for which standard methods of ordinary
differential equations do not apply. Performing a change of variables and
using the method of steps (see, e.g., Driver 2012), we can derive a closed-
form solution for the allocation. We provide the closed-form solution in the
proof.

Figure 3 provides an example when $F$ is a uniform distribution. There are
several interesting observations. First, note that $x_{\textup{{pd}}}(\cdot)$
is a non-decreasing and randomized allocation. Second, both allocations and
transfers represent a perturbation of the optimal hard/soft floor mechanism
$m_{\textup{{pd}}}=(0.5\cdot(1-\varepsilon),0.5\cdot(1+\varepsilon))$. Indeed,
one can establish that as $\varepsilon\downarrow 0$, $m_{\textup{{pd}}}$
becomes $m_{\textup{{d}}}$. Now that we have proved that $m_{\textup{{pd}}}$
can be explicitly determined, we can leverage Proposition 5.2 to show that
$m_{\textup{{pd}}}$ is an $\varepsilon$-IC mechanism.

######  Proposition 5.4 (Feasibility)

Fix $\varepsilon>0$ and $\mu>\varepsilon\cdot e$ then there exists
$\delta(\mu,\varepsilon)>0$ in
$\left[\frac{\mu^{2}}{4\varepsilon}-\mu,\frac{\mu^{2}}{4\varepsilon}\right]$
such that $\lim_{v\uparrow p^{\star}+\delta}x_{\textup{{pd}}}(v)=1$. For $\mu$
small such that
$(p^{\star}-\delta,p^{\star}+\delta+\mu)\subset[0,\overline{v}]$ the perturbed
delayed mechanism is feasible, i.e.,
$m_{\textup{{pd}}}\in\mathcal{M}(\varepsilon)$.

Note that Proposition 5.2 provides a sufficient condition for
${v^{\star}}(\cdot)$ to be a best reporting function for $m_{\textup{{pd}}}$.
Under this condition one can readily verify that
$m_{\textup{{pd}}}\in\mathcal{M}(\varepsilon)$. To see why
($\mbox{IC}_{\varepsilon}$) holds, note that because ${v^{\star}}(\cdot)$ is a
best reporting function we have that $\max_{w}\\{v\cdot
x_{\textup{{pd}}}(w)-t_{\textup{{pd}}}(w)\\}=v\cdot
x_{\textup{{pd}}}({v^{\star}}(v))-t_{\textup{{pd}}}({v^{\star}}(v))$. This,
together with the envelope theorem (see (7)), implies that
($\mbox{IC}_{\varepsilon}$) can be cast as

$v\cdot
x_{\textup{{pd}}}(v)-t_{\textup{{pd}}}(v)\geq\int_{0}^{v}x_{\textup{{pd}}}({v^{\star}}(s))ds-\epsilon,\quad\forall
v\in[0,\overline{v}].$

If $v\leq p^{\star}-\delta$, then the left hand-side above is 0; while the
right hand-side is $vx_{\textup{{pd}}}(0)-\varepsilon$ which, by the boundary
condition of $x_{\textup{{pd}}}(\cdot)$, is non-negative. If $v\geq
p^{\star}-\delta$ then the inequality above is binding. That is,
$m_{\textup{{pd}}}$ verifies ($\mbox{IC}_{\varepsilon}$). The (IR) constraint
can be verified in a similar fashion. We note that the condition
$(p^{\star}-\delta,p^{\star}+\delta+\mu)\subset[0,\overline{v}]$ is needed to
ensure that ${v^{\star}}(\cdot)$ is properly defined in $[0,\overline{v}]$
and, from the characterization of $\delta(\mu,\varepsilon)$, it is satisfied
when $\mu$ is small. In Section 5.1.3, we show how to properly choose $\mu$.

Therefore, the crucial step to establish Proposition 5.4 is to show that the
sufficient condition in Proposition 5.2 can be met. To do so, we show it is
always possible to find $(\mu,\delta)$ such that
$x_{\textup{{pd}}}((p^{\star}+\delta)^{-})=1$. Using that
$x_{\textup{{pd}}}(\cdot)$ is non-decreasing and that it belongs to $[0,1]$,
yields the desired conclusion. We note that establishing that
$x_{\textup{{pd}}}((p^{\star}+\delta)^{-})=1$ requires to carefully choose
$(\mu,\delta)$ so the solution to (ODE)-(DDE) hits 1 at $p^{\star}+\delta$.
The proof involves an elegant application of renewal theory—we provide more
details in the appendix.

####  5.1.3 Step 3: Performance characterization

From Proposition 5.4, we have derived a feasible mechanism. Next, we analyze
its performance. The following result derives an explicit form for the
performance of a perturbed delayed mechanism.

######  Proposition 5.5 (Performance Analysis)

Fix $\mu,\delta>0$ and $\varepsilon>0$ such that the mechanism
$m_{\textup{{pd}}}$ is feasible. Then the revenues garnered under
$m_{\textup{{pd}}}$ are given by

$\displaystyle\Pi(m_{\textup{{pd}}})=\int_{0}^{p^{\star}+\delta}x_{\textup{{pd}}}(v)\psi(v|w(\cdot))f(v)dv+R(p^{\star}+\delta)+\int_{p^{\star}+\delta}^{p^{\star}+\delta+\mu}\overline{F}(v)dv$

where

$\psi(v|w(\cdot))=v-\frac{\overline{F}(v+\mu)}{f(v)}\cdot\dot{w}(v),\quad\forall
v\in[0,p^{\star}+\delta].$

The result above provides an expression for the revenues that highlights the
different forces at play. A particular term is notable in the objective above,
the first integral. This integral resembles the classical objective
reformulation for the (IC0) problem (see Section 2, eq. 4). Naïvely, one may
be tempted to try to optimize point-wise (as in a classical argument), but
such an approach fails here as $x_{\textup{{pd}}}(v)$ depends on the entire
profile of the best reporting strategy ${v^{\star}}(\cdot)$ and its inverse.
The latter, $w(\cdot)$, comes into play in the term $\psi(v|w(\cdot))$ that,
due to its resemblance to the standard virtual value, we coin “delayed virtual
value.” This further highlights the difference between the class of
$\varepsilon$-IC problems and the standard IC ones. Even when values are
regular, the presence of $\varepsilon$-IC demands a global optimization
approach, while in the IC setting local optimization is enough to characterize
an optimal mechanism.

Next, we analyze and lower bound each term in $\Pi(m_{\textup{{pd}}})$.
Consider the second and third terms in $\Pi(m_{\textup{{pd}}})$. Because
distributions are monotone, we have

$\displaystyle
R(p^{\star}+\delta)+\int_{p^{\star}+\delta}^{p^{\star}+\delta+\mu}\overline{F}(v)dv$
$\displaystyle\geq
R(p^{\star}+\delta)+\overline{F}(p^{\star}+\delta+\mu)\cdot\mu$
$\displaystyle\geq
R^{\star}-\kappa_{U}\delta^{\alpha}+\bar{F}(p^{\star}+\delta+\mu)\mu:=(A),$

where the last inequality follows from a Taylor expansion of the revenue
function and from Definition 2.1, which implies that the derivative of
$R(\cdot)$ is bounded below by $-\kappa_{U}\alpha(v-p^{\star})^{\alpha-1}$ for
$v\geq p^{\star}$. Using (A) and the bounds for $\delta$ in Proposition 5.4 we
choose $\mu$ that enables us to achieve the right scaling. If we choose
$\mu=\mu(\varepsilon)=K\cdot\varepsilon^{\alpha/(2\alpha-1)}$ for some
positive constant $K>0$, we have that
$\delta(\mu(\varepsilon),\varepsilon)\leq\mu(\varepsilon)^{2}/(4\varepsilon)\leq
K^{2}\varepsilon^{1/(2\alpha-1)/4}$. This delivers,

$(A)\geq\Pi^{\star}(\mathcal{M}(0))+\left(\bar{F}(p^{\star}+\delta+\mu)\cdot
K-\kappa_{U}\left(\frac{K^{2}}{4}\right)^{\alpha}\right)\cdot\varepsilon^{\alpha/(2\alpha-1)},$

In the equation above $K$ needs to be taken small enough so that
$\bar{F}(p^{\star}+\delta+\mu)>\kappa_{U}\left(\frac{1}{4}\right)^{\alpha}K^{2\alpha-1}>0$
(which is possible because $\alpha>1/2$,
$\delta(\varepsilon)+\mu(\varepsilon)\downarrow 0$ and
$\overline{F}(p^{\star})>0$ ).

This argument shows that the last two terms in Proposition 5.5 already deliver
the desired $\varepsilon^{\alpha/(2\alpha-1)}$ rate. We highlight that this
choice of $\mu(\varepsilon)$ as in Proposition 5.4 is optimal. That is,
$\Omega(\varepsilon^{\alpha/(2\alpha-1)})$ is the best guarantee that can be
achieved in the class of perturbed delayed mechanisms. We still need to show,
however, that the first term in Proposition 5.5 does not negatively affect the
order of magnitude of the performance gains. We provide a complete, and more
formal analysis of $\Pi(m_{\textup{{pd}}})$ in the proof of Theorem 5.1.

We note that for the family of perturbed delayed mechanisms—which generalizes
optimal deterministic ones—allocations not only exhibit randomization, but
they also randomize even the smallest type, $x_{\textup{{pd}}}(0)>0$. A sharp
departure from the standard IC mechanism design literature.

##### Discussion.

Interestingly, the second and third terms of $\Pi(m_{\textup{{pd}}})$ which,
as we have seen, provide the $\varepsilon^{\alpha/(2\alpha-1)}$ gains in
revenue, coincide with the expected revenue of a hard/soft floor mechanism
with hard floor $p^{\star}+\delta$ and soft floor $p^{\star}+\delta+\mu$.
Because the revenue function $R(\cdot)$ is smooth around its interior
optimizer $p^{\star}$, shifting the hard floor by an amount $\delta$ from the
optimal price $p^{\star}$ leads to a loss of order
$-\delta^{\alpha}\approx-\varepsilon^{\alpha/(2\alpha-1)}$ (see Equation 3).
The seller’s gains are introduced by offering a region of size $\mu$ in which
the hard/soft floor mechanism charges the bid. Note that in the deterministic
case, this region can have length at most $\varepsilon$, because otherwise
($\mbox{IC}_{\varepsilon}$) would be violated. Interestingly, randomization
allows one to offer a region of larger size
$\mu\approx\varepsilon^{\alpha/(2\alpha-1)}$. By carefully choosing the
parameters, we can guarantee that the benefits of the region in which bids are
paid outweigh the loss of picking a suboptimal hard floor. These terms
combined lead to the $\varepsilon^{\alpha/(2\alpha-1)}$ revenue gains.

##  6 Conclusion

In the present paper, we have initiated the study of the optimization of
mechanisms under $\varepsilon$-IC constraints. We have highlighted the rich
structure underlying this class of optimization problems and characterized the
gains in performance that are achievable. These are, to the best of our
knowledge, the first results of this nature in the literature.

This paper opens up various avenues for future research. First, characterizing
the structure of an optimal mechanism in this setting is an open question.
While the results in the paper establish the need for randomization and
construct mechanisms with supralinear gains, various arguments developed are
fairly general, yield bounds for arbitrary value of $\varepsilon$, and may
prove useful in characterizing an optimal mechanism in the future. Another
important avenue of research pertains to studying settings with an arbitrary
number of buyers and analyzing how the gains grow as a function of this
number.

Another possible implication of our analysis is that the classical rounding
argument discussed in Section 3.1 might not be tight for all mechanisms. This
argument is used extensively in the literature on black-box reductions for
mechanism design as it provides an approach to construct a exactly IC
mechanism from an $\varepsilon$-IC mechanisms while losing an optimal revenue
of $\varepsilon^{1/2}$. Because the revenue gains of our near-optimal
$\varepsilon$-IC mechanism are $\varepsilon^{\alpha/(2\alpha-1)}$, this
suggests that the rounding argument might introduce revenue losses that are
higher than necessary for some mechanisms and some distributions. We hope that
the ideas developed in this paper also open the door to developing new
techniques to construct exactly IC mechanisms from $\varepsilon$-IC ones.

While we have focused on a static setting, the present analysis also opens
possibilities for the design and optimization of dynamic mechanisms under
(dynamic) $\varepsilon$-IC constraints. In such settings, an IC mechanism may
often be intractable, however, under $\varepsilon$-IC constraints, many
potentially “simple” mechanisms become feasible. The present analysis may
suggest local perturbations to mechanisms to improve performance while
maintaining $\varepsilon$-IC. Additionally, the present paper suggests a
refined metric to assess near-optimality of mechanisms when relaxing to
$\varepsilon$-IC constraints. The performance of an $\varepsilon$-IC mechanism
should not be judged just by whether it approaches the performance of an
optimal IC mechanism (first order optimality), but also by the order of
magnitude of the gap between the performance of the $\varepsilon$-IC mechanism
and an optimal IC mechanism (second order optimality).

Online Appendix: Mechanism Design under Approximate Incentive Compatibility

##  7 Proofs for Section 3

###### Proof 7.1

Proof of Proposition 3.1The following argument follows from a classic rounding
argument attributed to Nisan. Let $m=(x,t)$ be an $\varepsilon$-IC mechanism.
Define an alternative mechanism $\tilde{m}$ as follows. For $\delta\in(0,1)$,
we let

$v^{\star}_{\delta}(v)\in\argmax_{w\in\mathcal{S}}\Big{\\{}v\cdot
x(w)-(1-\delta)t(w)\Big{\\}}.$

Then we define the mechanism
$\tilde{m}\triangleq(\tilde{x},\tilde{t})=(x(v^{\star}_{\delta}(\cdot)),(1-\delta)t(v^{\star}_{\delta}(\cdot)))$.
Therefore, $\tilde{m}$ is a $0$-IC mechanism and for
$v^{\prime}=v^{\star}_{\delta}(v)$ we have that

$\displaystyle v\cdot x(v)-t(v)$ $\displaystyle\geq v\cdot
x(v^{\prime})-t(v^{\prime})-\varepsilon,$ $\displaystyle v\cdot
x(v^{\prime})-(1-\delta)t(v^{\prime})$ $\displaystyle\geq v\cdot
x(v)-(1-\delta)t(v),$

where the first inequality holds because $(x,t)$ is $\varepsilon$-IC, and the
second comes from the definition of $v^{\star}_{\delta}(v)$. Combining the
inequalities above we obtain

$t(v^{\prime})\geq t(v)-\frac{\varepsilon}{\delta}.$

Now since $\tilde{m}$ is $0$-IC, we have

$\Pi^{\star}(\mathcal{M}(0))\geq\Pi(\tilde{m})=\mathsf{E}_{v}[\tilde{t}(v)]=(1-\delta)\mathsf{E}_{v}[t(v^{\star}_{\delta}(v))]\geq(1-\delta)\left(\mathsf{E}_{v}[t(v)]-\frac{\varepsilon}{\delta}\right).$

The latter can be rearranged to yield the following

$\Pi(m)-\Pi^{\star}(\mathcal{M}(0))\leq\frac{\delta}{1-\delta}\Pi^{\star}(\mathcal{M}(0))+\frac{\varepsilon}{\delta}\leq
2\delta\Pi^{\star}(\mathcal{M}(0))+\frac{\varepsilon}{\delta},$

where in the last inequality we considered $\delta\leq 1/2$. Choosing
$\delta=\sqrt{\varepsilon}$ delivers the result.

###### Proof 7.2

Proof of Lemma 3.3

Given the definitions preceding the lemma, the Lagrangian is:

$\displaystyle L$
$\displaystyle=\int_{0}^{\overline{v}}t(v)f(v)dv+\int_{0}^{\mu}\lambda^{{\scriptscriptstyle\text{\rm
IR}}}(v)(vx(v)-t(v))dv+\int_{\mu}^{\overline{v}}\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)\Big{(}vx(v)-t(v)-vx({v^{\star}}(v))+t({v^{\star}}(v))+\varepsilon\Big{)}dv$
$\displaystyle=\varepsilon\int_{\mu}^{\overline{v}}\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)dv+\int_{0}^{\overline{v}}t(v)\Big{(}f(v)-\lambda^{{\scriptscriptstyle\text{\rm
IR}}}(v)\mathbf{1}_{\\{v\in[0,\mu]\\}}-\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)\mathbf{1}_{\\{v\in[\mu,\overline{v}]\\}}+\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v))\dot{w}(v)\mathbf{1}_{\\{v\in(0,\nu_{0})\\}}\Big{)}dv$
$\displaystyle+\int_{0}^{\overline{v}}x(v)\Big{(}\lambda^{{\scriptscriptstyle\text{\rm
IR}}}(v)v\mathbf{1}_{\\{v\in[0,\mu]\\}}+\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)v\mathbf{1}_{\\{v\in[\mu,\overline{v}]\\}}-\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v))w(v)\dot{w}(v)\mathbf{1}_{\\{v\in(0,\nu_{0})\\}}\Big{)}dv,$

where we have used the change of variables $u={v^{\star}}(v)$, the fact that
$w$ is the inverse of ${v^{\star}}$, that ${v^{\star}}$ is continuous and
increasing (hence almost everywhere differentiable). Since $t(v)$ is a free
variable, we must have that

$f(v)-\lambda^{{\scriptscriptstyle\text{\rm
IR}}}(v)\mathbf{1}_{\\{v\in[0,\mu]\\}}-\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)\mathbf{1}_{\\{v\in[\mu,\overline{v}]\\}}+\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v))\dot{w}(v)\mathbf{1}_{\\{v\in(0,\nu_{0})\\}}=0,\quad\text{a.e on
}[0,\overline{v}].$

From this, we can deduce the following

$\displaystyle\lambda^{{\scriptscriptstyle\text{\rm IC}}}(v)$
$\displaystyle=f(v),\quad\text{a.e on }[\nu_{0},\overline{v}]$
$\displaystyle\lambda^{{\scriptscriptstyle\text{\rm IC}}}(v)$
$\displaystyle=f(v)+\dot{w}(v)\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v)),\quad\text{a.e on }[\mu,\nu_{0}]$
$\displaystyle\lambda^{{\scriptscriptstyle\text{\rm IR}}}(v)$
$\displaystyle=f(v)+\dot{w}(v)\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v)),\quad\text{a.e on }[0,\mu]$

Note that since $w$ is increasing then it is differentiable with positive
derivative almost everywhere. As a consequence,
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}$ and
$\lambda^{{\scriptscriptstyle\text{\rm IR}}}$ are non-negative and are well
defined almost everywhere in their domains.

Going back to the Lagrangian, we find that

$L=\varepsilon\int_{\mu}^{\overline{v}}\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(v)dv+\int_{0}^{\overline{v}}\left(vf(v)-\dot{w}(v)(w(v)-v)\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v))\mathbf{1}_{\\{v\in[0,\nu_{0}]\\}}\right)^{+}dv.$

Since we have relaxed the constraints outside the path $(v,{v^{\star}}(v))$,
only considered the IR constraints for $v\leq\mu$, and the dual variables are
non-negative, the above provides an upper bound for the primal problem. This
concludes the proof.

###### Proof 7.3

Proof of Lemma 3.4 It is easy to see that this is true for $k=0$. Consider
$v\in[\nu_{k},\nu_{k-1}]$ for some arbitrary $k\geq 1$, in this case,
$w(v)\in[\nu_{k-1},\nu_{k-2}]$. Hence, by induction, we have (a.e)

$\displaystyle\lambda(v)$ $\displaystyle=f(v)+\lambda(w(v))\dot{w}(v)$
$\displaystyle=f(v)+\frac{d}{dx}\sum_{j=0}^{k-1}F(w^{j}(x))\Big{|}_{x=w(v)}$
$\displaystyle=f(v)+\sum_{j=0}^{k-1}f(w^{j}(w(v)))\dot{(w^{j})}(w(v))\dot{w}(v)$
$\displaystyle=f(v)+\frac{d}{dv}\sum_{j=0}^{k-1}F(w^{j+1}(v))$
$\displaystyle=\frac{d}{dv}\sum_{j=0}^{k}F(w^{j}(v)).$

###### Proof 7.4

Proof of Lemma 3.5

$\displaystyle\int_{\mu}^{\overline{v}}\lambda(v)dv$
$\displaystyle=\int_{\mu}^{\nu_{0}}\lambda(v)dv+\int_{\nu_{0}}^{\overline{v}}\lambda(v)dv$
$\displaystyle=\int_{\mu}^{\nu_{0}}\lambda(v)dv+\int_{\nu_{0}}^{\overline{v}}f(v)dv$
$\displaystyle=\sum_{k=1}^{K-1}\int_{\nu_{k}}^{\nu_{k-1}}\lambda(v)dv+\int_{\mu}^{\nu_{K-1}}\lambda(v)dv+\int_{\nu_{0}}^{\overline{v}}f(v)dv$
$\displaystyle=\sum_{k=1}^{K-1}\int_{\nu_{k}}^{\nu_{k-1}}\left(\frac{d}{dv}\sum_{j=0}^{k}F(w^{j}(v))\right)dv+\int_{\mu}^{\nu_{K-1}}\left(\frac{d}{dv}\sum_{j=0}^{K}F(w^{j}(v))\right)dv+\int_{\nu_{0}}^{\overline{v}}f(v)dv$
$\displaystyle=\sum_{k=1}^{K-1}\left(\sum_{j=0}^{k}F(w^{j}(v))\right)\Big{|}_{\nu_{k}}^{\nu_{k-1}}+\left(\sum_{j=0}^{K}F(w^{j}(v))\right)\Big{|}_{\mu}^{\nu_{K-1}}+\int_{\nu_{0}}^{\overline{v}}f(v)dv$
$\displaystyle=\sum_{k=1}^{K-1}\left(\sum_{j=0}^{k}F(w^{j}(\nu_{k-1}))-F(w^{j}(\nu_{k}))\right)+\left(\sum_{j=0}^{K}F(w^{j}(\nu_{K-1}))-F(w^{j}(\mu))\right)+\int_{\nu_{0}}^{\overline{v}}f(v)dv$
$\displaystyle=\sum_{k=1}^{K-1}\left(\sum_{j=0}^{k}(F(\nu_{k-j-1})-F(\nu_{k-j}))\right)+\left(\sum_{j=0}^{K}(F(\nu_{K-1-j})-F(w^{j}(\mu)))\right)+\int_{\nu_{0}}^{\overline{v}}f(v)dv$
$\displaystyle\leq\sum_{k=1}^{K-1}(1-F(\nu_{k}))+\left(\sum_{j=0}^{K}(F(\nu_{K-1-j})-F(\nu_{K-j}))\right)+\int_{\nu_{0}}^{\overline{v}}f(v)dv$
$\displaystyle=\sum_{k=1}^{K-1}(1-F(\nu_{k}))+(1-F(\nu_{K}))+\int_{\nu_{0}}^{\overline{v}}f(v)dv$
$\displaystyle\leq K+1,$

where in the above we used the property that $w^{j}(\nu_{k})=\nu_{k-j}$ and
Lemma 3.4. In the first inequality, we used that $w^{j}(\mu)\geq\nu_{K-j}$
which is true because $\mu\geq\nu_{K}$. In the last inequality, we used that
$\int_{\nu_{0}}^{\overline{v}}f(v)dv\leq 1$. This concludes the proof.

###### Proof 7.5

Proof of Lemma 3.6 We separate the computation of the integral
$\int_{x}^{\overline{v}}\Delta(v)dv$ into three pieces. We do the computation
for each piece for an arbitrary interval, $[a,b]$, first. We then combine all
the pieces and intervals.

We will make the following definitions. Since $\lambda(v)$ is defined
differently in different interval of the form $[\nu_{k},\nu_{k-1}]$ (see Lemma
3.4), we will consider first $[a,b]\subset[\nu_{k},\nu_{k-1}]$ for some $k\geq
1$. We also define

$H_{k}(v)\triangleq\sum_{j=0}^{k}F(w^{j}(v)),\quad\text{for
}v\in[\nu_{k},\nu_{k-1}].$

Note that from Lemma 3.4 for $v\in[\nu_{k},\nu_{k-1}]$, we have that
$\lambda(v)=\dot{H}_{k}(v)$ a.e.

First piece.

$A_{1}=\int_{a}^{b}vf(v)dv=vF(v)\Big{|}_{a}^{b}-\int_{a}^{b}F(v)dv.$

Second piece.

$\displaystyle A_{2}$
$\displaystyle=\int_{a}^{b}w(v)\dot{w}(v)\lambda(w(v))dv$
$\displaystyle=\int_{w(a)}^{w(b)}v\lambda(v)dv$
$\displaystyle=\int_{w(a)}^{w(b)}v\dot{H}_{k-1}(v)dv$
$\displaystyle=vH_{k-1}(v)\Big{|}_{w(a)}^{w(b)}-\int_{w(a)}^{w(b)}H_{k-1}(v)dv$
$\displaystyle=w(b)H_{k-1}(w(b))-w(a)H_{k-1}(w(a))-\int_{w(a)}^{w(b)}H_{k-1}(v)dv,$

where in the second equality we used the change of variables $u=w(v)$. In the
third equality, we used that because $[a,b]\subset[\nu_{k},\nu_{k-1}]$ we must
have $[w(a),w(b)]\subset[\nu_{k-1},\nu_{k-2}]$ and, therefore,
$\lambda(v)=\dot{H}_{k-1}(v)$ a.e.

Third piece.

$\displaystyle A_{3}$ $\displaystyle=\int_{a}^{b}v\dot{w}(v)\lambda(w(v))dv$
$\displaystyle=\int_{a}^{b}v\dot{w}(v)\dot{H}_{k-1}(w(v))dv$
$\displaystyle=vH_{k-1}(w(v))\Big{|}_{a}^{b}-\int_{a}^{b}H_{k-1}(w(v))dv$
$\displaystyle=bH_{k-1}(w(b))-aH_{k-1}(w(a))-\int_{a}^{b}H_{k-1}(w(v))dv$

Using the expressions above we can compute the integrals in $[x,\nu_{0}]$. We
will need the following properties

$H_{k}(\nu_{k-1})=\sum_{j=0}^{k}F(w^{j}(\nu_{k-1}))=\sum_{j=0}^{k}F(\nu_{k-1-j})=\sum_{j=0}^{k}F(\nu_{j-1}),$
(17)

and

$H_{k}(\nu_{k})=\sum_{j=0}^{k}F(w^{j}(\nu_{k}))=\sum_{j=0}^{k}F(\nu_{k-j})=\sum_{j=0}^{k+1}F(\nu_{j-1})-1,$
(18)

and

$H_{k}(w(v))=\sum_{j=0}^{k}F(w^{j}(w(v)))=\sum_{j=0}^{k}F(w^{j+1}(v))=\sum_{j=1}^{k+1}F(w^{j}(v))=H_{k+1}(v)-F(v)$
(19)

Next we exploit the properties above to compute the three integrals in
$[x,\nu_{0}]$. Let $k$ be such that $\nu_{k}\leq x\leq\nu_{k-1}$. For the
second piece we have

$\displaystyle\int_{x}^{\nu_{0}}w(v)\dot{w}(v)\lambda(w(v))dv$
$\displaystyle=\sum_{j=1}^{k-1}\int_{\nu_{j}}^{\nu_{j-1}}w(v)\dot{w}(v)\lambda(w(v))dv+\int_{x}^{\nu_{k-1}}w(v)\dot{w}(v)\lambda(w(v))dv$
$\displaystyle=\sum_{j=1}^{k-1}w(\nu_{j-1})H_{j-1}(w(\nu_{j-1}))-w(\nu_{j})H_{j-1}(w(\nu_{j}))-\int_{w(\nu_{j})}^{w(\nu_{j-1})}H_{j-1}(v)dv$
$\displaystyle+w(\nu_{k-1})H_{k-1}(w(\nu_{k-1}))-w(x)H_{k-1}(w(x))-\int_{w(x)}^{w(\nu_{k-1})}H_{k-1}(v)dv$
$\displaystyle=\sum_{j=1}^{k-1}\nu_{j-2}H_{j-1}(\nu_{j-2})-\nu_{j-1}H_{j-1}(\nu_{j-1})-\int_{\nu_{j-1}}^{\nu_{j-2}}H_{j-1}(v)dv$
$\displaystyle+\nu_{k-2}H_{k-1}(\nu_{k-2})-w(x)H_{k-1}(w(x))-\int_{w(x)}^{\nu_{k-2}}H_{k-1}(v)dv$

For the third piece we have

$\displaystyle\int_{x}^{\nu_{0}}v\dot{w}(v)\lambda(w(v))dv$
$\displaystyle=\sum_{j=1}^{k-1}\int_{\nu_{j}}^{\nu_{j-1}}v\dot{w}(v)\lambda(w(v))dv+\int_{x}^{\nu_{k-1}}v\dot{w}(v)\lambda(w(v))dv$
$\displaystyle=\sum_{j=1}^{k-1}\nu_{j-1}H_{j-1}(\nu_{j-2})-\nu_{j}H_{j-1}(\nu_{j-1})-\int_{\nu_{j}}^{\nu_{j-1}}H_{j-1}(w(v))dv$
$\displaystyle+\nu_{k-1}H_{k-1}(\nu_{k-2})-xH_{k-1}(w(x))-\int_{x}^{\nu_{k-1}}H_{k-1}(w(v))dv$

Combining the second and third pieces and using properties (17), (18) and (19)
yields

$\displaystyle\int_{x}^{\nu_{0}}(w(v)-v)\dot{w}(v)\lambda(w(v))dv$
$\displaystyle=\sum_{j=1}^{k-1}\left(\nu_{j-2}-\nu_{j-1}\right)H_{j-1}(\nu_{j-2})-\left(\nu_{j-1}-\nu_{j}\right)H_{j-1}(\nu_{j-1})$
$\displaystyle-\left(\int_{\nu_{j-1}}^{\nu_{j-2}}H_{j-1}(v)dv-\int_{\nu_{j}}^{\nu_{j-1}}H_{j-1}(w(v))dv\right)$
$\displaystyle+(\nu_{k-2}-\nu_{k-1})H_{k-1}(\nu_{k-2})-(w(x)-x)H_{k-1}(w(x))$
$\displaystyle-\left(\int_{w(x)}^{\nu_{k-2}}H_{k-1}(v)dv-\int_{x}^{\nu_{k-1}}H_{k-1}(w(v))dv\right)$
$\displaystyle=\sum_{j=1}^{k-1}\left(\nu_{j-2}-\nu_{j-1}\right)\sum_{i=0}^{j-1}F(\nu_{i-1})-\left(\nu_{j-1}-\nu_{j}\right)\left(\sum_{i=0}^{j}F(\nu_{i-1})-1\right)$
$\displaystyle-\left(\int_{\nu_{j-1}}^{\nu_{j-2}}H_{j-1}(v)dv-\int_{\nu_{j}}^{\nu_{j-1}}\left(H_{j}(v)-F(v)\right)dv\right)$
$\displaystyle+(\nu_{k-2}-\nu_{k-1})H_{k-1}(\nu_{k-2})-(w(x)-x)H_{k-1}(w(x))$
$\displaystyle-\left(\int_{w(x)}^{\nu_{k-2}}H_{k-1}(v)dv-\int_{x}^{\nu_{k-1}}\left(H_{k}(v)-F(v)\right)dv\right).$

Note that

$\displaystyle\sum_{j=1}^{k-1}\left(\nu_{j-2}-\nu_{j-1}\right)\sum_{i=0}^{j-1}F(\nu_{i-1})-\left(\nu_{j-1}-\nu_{j}\right)\left(\sum_{i=0}^{j}F(\nu_{i-1})-1\right)$
$\displaystyle=-(\nu_{k-1}-\nu_{0})+\left(\overline{v}-\nu_{0}\right)$
$\displaystyle-\left(\nu_{k-2}-\nu_{k-1}\right)\sum_{i=0}^{k-1}F(\nu_{i-1})$
$\displaystyle=(\overline{v}-\nu_{k-1})-\left(\nu_{k-2}-\nu_{k-1}\right)H_{k-1}(\nu_{k-2}).$

We also have that

$\displaystyle\sum_{j=1}^{k-1}\left(\int_{\nu_{j-1}}^{\nu_{j-2}}H_{j-1}(v)dv-\int_{\nu_{j}}^{\nu_{j-1}}\left(H_{j}(v)-F(v)\right)dv\right)$
$\displaystyle=\int_{\nu_{0}}^{\overline{v}}H_{0}(v)dv-\int_{\nu_{k-1}}^{\nu_{k-2}}H_{k-1}(v)dv+\int_{\nu_{k-1}}^{\nu_{0}}F(v)dv$
$\displaystyle=\int_{\nu_{k-1}}^{\overline{v}}F(v)dv-\int_{\nu_{k-1}}^{\nu_{k-2}}H_{k-1}(v)dv.$

In turn, we have that

$\displaystyle\int_{x}^{\nu_{0}}(w(v)-v)\dot{w}(v)\lambda(w(v))dv$
$\displaystyle=(\overline{v}-\nu_{k-1})-\left(\nu_{k-2}-\nu_{k-1}\right)H_{k-1}(\nu_{k-2})-\int_{\nu_{k-1}}^{\overline{v}}F(v)dv+\int_{\nu_{k-1}}^{\nu_{k-2}}H_{k-1}(v)dv$
$\displaystyle+(\nu_{k-2}-\nu_{k-1})H_{k-1}(\nu_{k-2})-(w(x)-x)H_{k-1}(w(x))$
$\displaystyle-\left(\int_{w(x)}^{\nu_{k-2}}H_{k-1}(v)dv-\int_{x}^{\nu_{k-1}}\left(H_{k}(v)-F(v)\right)dv\right)$
$\displaystyle=(\overline{v}-\nu_{k-1})-\int_{x}^{\overline{v}}F(v)dv+\int_{x}^{w(x)}H_{k-1}(v)dv-(w(x)-x)H_{k-1}(w(x))$
$\displaystyle+\int_{x}^{\nu_{k-1}}H_{k}(v)dv.$

Therefore,

$\displaystyle\int_{x}^{\nu_{0}}\Delta(v)dv+\int_{\nu_{0}}^{\overline{v}}vf(v)dv$
$\displaystyle=\nu_{k-1}-xF(x)-\int_{x}^{w(x)}H_{k-1}(v)dv+(w(x)-x)H_{k-1}(w(x))-\int_{x}^{\nu_{k-1}}H_{k}(v)dv$
$\displaystyle=(\nu_{k-1}-x)+x\bar{F}(x)-\int_{x}^{w(x)}H_{k-1}(v)dv+(w(x)-x)H_{k-1}(w(x))$
$\displaystyle-\int_{x}^{\nu_{k-1}}H_{k}(v)dv.$

Now, we have that $H_{k-1}(w(x))=H_{k}(x)-F(x)=H_{k-1}(x)+F(w^{k}(x))-F(x)$.
Therefore,

$\displaystyle(w(x)-x)H_{k-1}(w(x))$
$\displaystyle=(w(x)-x)H_{k-1}(x)+(w(x)-x)(F(w^{k}(x))-F(x))$
$\displaystyle\leq\int_{x}^{w(x)}H_{k-1}(v)dv+(w(x)-x)(F(w^{k}(x))-F(x)),$

where the inequality follows from $H_{k-1}(v)$ being non-decreasing
(composition of non-decreasing functions). So finally, we deduce

$\displaystyle\int_{x}^{\nu_{0}}\Delta(v)dv+\int_{\nu_{0}}^{\overline{v}}vf(v)dv$
$\displaystyle\leq(\nu_{k-1}-x)+x\bar{F}(x)+(w(x)-x)(F(w^{k}(x))-F(x))$
$\displaystyle\leq(w(x)-x)+x\bar{F}(x)+(w(x)-x)$
$\displaystyle=x\bar{F}(x)+2(w(x)-x),$

where in the second inequality we used that $\nu_{k-1}\leq w(x)$ and that
$(F(w^{k}(x))-F(x))\leq 1$.

###### Proof 7.6

Proof of Proposition 3.7 First, let us consider counting the number of steps
in $[p^{\star},\nu_{0}]$. For $k$ such that $\nu_{k}\geq p^{\star}$ we have

$\nu_{k}=\frac{1}{m^{k}}\left\\{\nu_{0}+p^{\star}(m^{k}-1)-\varepsilon^{1-\beta}\frac{m^{k}-1}{m-1}\right\\}.$

The number of steps in $v\geq p^{\star}$ equals $k$ where $k$ is the largest
$k$ such that $\nu_{k}\geq p^{\star}$. We solve for $k$ such that

$\frac{1}{m^{k}}\left\\{\nu_{0}+p^{\star}(m^{k}-1)-\varepsilon^{1-\beta}\frac{m^{k}-1}{m-1}\right\\}\leq
p^{\star}+\varepsilon^{1-\beta}\leq\frac{1}{m^{k-1}}\left\\{\nu_{0}+p^{\star}(m^{k-1}-1)-\varepsilon^{1-\beta}\frac{m^{k-1}-1}{m-1}\right\\}.$

This is equivalent to

$\left\\{\frac{(\nu_{0}-p^{\star})(m-1)}{\varepsilon^{1-\beta}}+1\right\\}\frac{1}{m}\leq
m^{k}\leq\frac{(\nu_{0}-p^{\star})(m-1)}{\varepsilon^{1-\beta}}+1.$

Note that

$\displaystyle\frac{(\nu_{0}-p^{\star})(m-1)}{\varepsilon^{1-\beta}}$
$\displaystyle=\frac{(\nu_{0}-p^{\star})}{\varepsilon^{1-\beta}}\left(\frac{\overline{v}-p^{\star}-\varepsilon^{1-\beta}}{\nu_{0}-p^{\star}}-1\right)$
$\displaystyle=\frac{(\nu_{0}-p^{\star})}{\varepsilon^{1-\beta}}\left(\frac{\overline{v}-p^{\star}-\varepsilon^{1-\beta}}{\nu_{0}-p^{\star}}-\frac{\nu_{0}-p^{\star}}{\nu_{0}-p^{\star}}\right)$
$\displaystyle=\frac{(\nu_{0}-p^{\star})}{\varepsilon^{1-\beta}}\left(\frac{\overline{v}-p^{\star}-\varepsilon^{1-\beta}-\nu_{0}+p^{\star}}{\nu_{0}-p^{\star}}\right)$
$\displaystyle=\frac{1}{\varepsilon^{1-\beta}}\left(\overline{v}-\varepsilon^{1-\beta}-\nu_{0}\right)$
$\displaystyle=\frac{1}{\varepsilon^{1-\beta}}\left(\overline{v}-\nu_{0}\right)-1$
$\displaystyle=\varepsilon^{\beta-({1-\beta})}-1.$

In turn, we have

$\frac{\varepsilon^{2\beta-1}}{m}\leq m^{k}\leq\varepsilon^{2\beta-1},$ (20)

and, thus,

$\frac{\log\left(\frac{\varepsilon^{2\beta-1}}{m}\right)}{\log(m)}\leq
k\leq\frac{\log\left(\varepsilon^{2\beta-1}\right)}{\log(m)},$

Note that,

$\log(m)=\log\left(m-1+1\right)=\log\left(\frac{\overline{v}-\varepsilon^{1-\beta}-\nu_{0}}{\nu_{0}-p^{\star}}+1\right)=\log\left(\frac{\varepsilon^{\beta}-\varepsilon^{1-\beta}}{\overline{v}-\varepsilon^{\beta}-p^{\star}}+1\right)=\mathcal{O}(\varepsilon^{\beta}),$

where in the last equality we used that $\beta<1/2$. This shows that the
number of steps above $p^{\star}$ is of order
$\Theta\left(\log(\varepsilon^{2\beta-1})/\varepsilon^{\beta}\right)$.

Next, we bound the number of steps below $p^{\star}$. Let $k^{\star}$ be the
largest $k$ such that $\nu_{k}\geq p^{\star}$. We can obtain the number of
steps $j+1$ below $p^{\star}$ by finding the largest $j$ such that
$\nu_{k^{\star}+j}\geq\mu$. First note that

$\nu_{k^{\star}+j}=\frac{1}{(2-m)^{j}}\left\\{\nu_{k^{\star}}+p^{\star}((2-m)^{j}-1)-\varepsilon^{1-\beta}\frac{(2-m)^{j}-1}{2-m-1}\right\\}.$

We use the above to solve for the largest $j$ such that
$\nu_{k^{\star}+j}\geq\mu$. Recall that

$w(0)=\mu=-p^{\star}(2-m)+p^{\star}+\varepsilon^{1-\beta}=p^{\star}(m-1)+\varepsilon^{1-\beta}$

We have

$\frac{1}{(2-m)^{j}}\left\\{\nu_{k^{\star}}+p^{\star}((2-m)^{j}-1)-\varepsilon^{1-\beta}\frac{(2-m)^{j}-1}{2-m-1}\right\\}\geq
p^{\star}(m-1)+\varepsilon^{1-\beta}$

which is equivalent to

$\varepsilon^{1-\beta}-p^{\star}(1-m)+\nu_{k^{\star}}(1-m)\leq(2-m)^{j+1}\left(p^{\star}(m-1)+\varepsilon^{1-\beta}\right),$

hence we have

$\log\left(1-\frac{\nu_{k^{\star}}(m-1)}{p^{\star}(m-1)+\varepsilon^{1-\beta}}\right)\leq(j+1)\log(2-m)$

or equivalently

$(j+1)\leq\frac{\log\left(1-\frac{\nu_{k^{\star}}(m-1)}{p^{\star}(m-1)+\varepsilon^{1-\beta}}\right)}{\log(2-m)}$

We note that $\log(2-m)<0$ and

$\log(2-m)=\log(1-(m-1))=\log\left(1-\frac{\varepsilon^{\beta}-\varepsilon^{1-\beta}}{\overline{v}-\varepsilon^{\beta}-p^{\star}}\right)=\mathcal{O}(-\varepsilon^{\beta}).$

Also note that by the definition of $\nu_{k^{\star}}$ we have

$\frac{\nu_{k^{\star}}-p^{\star}-\varepsilon^{1-\beta}}{m}+p^{\star}\leq
p^{\star}+\varepsilon^{1-\beta}\Leftrightarrow\nu_{k^{\star}}\leq
p^{\star}+(m+1)\varepsilon^{1-\beta}.$

So

$1-\frac{\nu_{k^{\star}}(m-1)}{p^{\star}(m-1)+\varepsilon^{1-\beta}}\geq
1-\frac{(p^{\star}+(m+1)\varepsilon^{1-\beta})(m-1)}{p^{\star}(m-1)+\varepsilon^{1-\beta}}=\frac{(2-m^{2})\varepsilon^{1-\beta}}{p^{\star}(m-1)+\varepsilon^{1-\beta}}=\mathcal{O}(\varepsilon^{1-2\beta}).$

Putting all together we deduce that

$(j+1)=\mathcal{O}\left(\frac{\log(\varepsilon^{2\beta-1})}{\varepsilon^{\beta}}\right).$

In conclusion, the total number of steps is
$\mathcal{O}\left(\frac{\log(\varepsilon^{2\beta-1})}{\varepsilon^{\beta}}\right)$.
This concludes the proof.

###### Proof 7.7

Proof of Theorem 3.2 We show that

$\Pi^{\star}(\mathcal{D})\leq\Pi^{\star}(\mathcal{M}(0))+\tilde{\mathcal{O}}(\varepsilon^{\alpha/(2\alpha-1)}).$

By combining Lemma 3.5 and Proposition 3.7, we can deduce that
$\Pi^{\star}(\mathcal{D})-\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})=\tilde{\mathcal{O}}(\varepsilon^{1-\beta})$. It remains to provide an
upper bound for $\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$.

We separate the proof into two cases: $v\geq p^{\star}$ and $v\leq p^{\star}$.
In both cases we provide bounds for $\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v))$ which we then use to further bound
$\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$. For $v\geq
p^{\star}$, we will provide an upper and a lower bound for
$\lambda^{{\scriptscriptstyle\text{\rm IC}}}(w(v))$. For $v<p^{\star}$, we
will provide an upper bound for $\lambda^{{\scriptscriptstyle\text{\rm
IC}}}(w(v))$. These bounds will be tight and will enable us to use Lemma 3.6
to bound $\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm IC}}})$.

Case 1: We consider the case $v\geq p^{\star}$. For ease of exposition, we use
$\gamma$ to denote $1-\beta$. First, we characterize the difference
$\nu_{k-1}-\nu_{k}$ for $\nu_{k}\geq p^{\star}$.

$\displaystyle\nu_{k-1}-\nu_{k}$
$\displaystyle=\frac{1}{m^{k-1}}\left\\{\nu_{0}+p^{\star}(m^{k-1}-1)-\varepsilon^{\gamma}\frac{m^{k-1}-1}{m-1}\right\\}-\frac{1}{m^{k}}\left\\{\nu_{0}+p^{\star}(m^{k}-1)-\varepsilon^{\gamma}\frac{m^{k}-1}{m-1}\right\\}$
$\displaystyle=\frac{1}{m^{k}}\left\\{m\nu_{0}+p^{\star}(m^{k}-m)-\varepsilon^{\gamma}\frac{m^{k}-m}{m-1}-\nu_{0}-p^{\star}(m^{k}-1)+\varepsilon^{\gamma}\frac{m^{k}-1}{m-1}\right\\}$
$\displaystyle=\frac{1}{m^{k}}\left\\{(m-1)\nu_{0}-p^{\star}(m-1)+\varepsilon^{\gamma}\right\\}$
$\displaystyle=\frac{1}{m^{k}}\left\\{(m-1)(\nu_{0}-p^{\star})+\varepsilon^{\gamma}\right\\}$
$\displaystyle=\frac{1}{m^{k}}\left\\{\varepsilon^{\beta}-\varepsilon^{\gamma}+\varepsilon^{\gamma}\right\\}$
$\displaystyle=\frac{\varepsilon^{\beta}}{m^{k}}.$

Note that from Lemma 3.4 for $k\geq 1$, we have

$\lambda(w(v))=\sum_{i=1}^{k}m^{i-1}f(w^{i}(v)),\quad a.e\text{ in
}[\nu_{k},\nu_{k-1}]\cap[p^{\star},\overline{v}].$

First, note that the following holds for
$v\in[\nu_{k},\nu_{k-1}]\cap[p^{\star},\overline{v}]$

$\sum_{i=1}^{k}m^{i-1}f(w^{i}(v))=m^{k-1}\sum_{i=0}^{k-1}m^{-i}f(w^{k-i}(v)).$

In order to bound the expression above, we make use of the mean value theorem
for integrals. We have that since $v\in[\nu_{k},\nu_{k-1}]$ then
$w^{k-i}(v)\in[\nu_{i},\nu_{i-1}]$ and there exists
$\xi\in[\nu_{i},\nu_{i-1}]$ such that

$\displaystyle\int_{\nu_{i}}^{\nu_{i-1}}f(v)dv$
$\displaystyle=f(\xi)(\nu_{i-1}-\nu_{i})$
$\displaystyle=(f(\xi)-f(w^{k-i}(v)))(\nu_{i-1}-\nu_{i})+f(w^{k-i}(v))(\nu_{i-1}-\nu_{i})$
$\displaystyle=\underbrace{(f(\xi)-f(w^{k-i}(v)))}_{\chi_{i}(v)}\frac{\varepsilon^{\beta}}{m^{i}}+f(w^{k-i}(v))\frac{\varepsilon^{\beta}}{m^{i}}.$

Then

$m^{k-1}\sum_{i=0}^{k-1}\int_{\nu_{i}}^{\nu_{i-1}}f(v)dv=m^{k-1}\sum_{i=0}^{k-1}\chi_{i}(v)\frac{\varepsilon^{\beta}}{m^{i}}+m^{k-1}\sum_{i=0}^{k-1}f(w^{k-i}(v))\frac{\varepsilon^{\beta}}{m^{i}}$

Equivalently,

$\frac{m^{k-1}}{\varepsilon^{\beta}}\bar{F}(\nu_{k-1})=m^{k-1}\sum_{i=0}^{k-1}\frac{\chi_{i}(v)}{m^{i}}+\lambda(w(v)).$

Note that

$\left|\sum_{i=0}^{k-1}\frac{\chi_{i}(v)}{m^{i}}\right|\leq\sum_{i=0}^{k-1}\frac{|\chi_{i}(v)|}{m^{i}}\leq\sum_{i=0}^{k-1}\frac{|\chi_{i}(v)|}{m^{i}}\leq\sum_{i=0}^{k-1}|\chi_{i}(v)|\leq
V_{0}^{\overline{v}}(f),$

where we have used that $m>1$ and that $V_{0}^{\overline{v}}(f)$ denotes the
total variation222The total variation of a function $f$ over
$[0,\overline{v}]$ is given by
$V_{0}^{\overline{v}}(f)=\sup_{P\in\mathcal{P}}\sum_{i=0}^{n_{P}-1}|f(x_{i+1})-f(x_{i})|,$
where $\mathcal{P}$ is the set of partitions in $[0,\overline{v}]$ and $n_{P}$
is the number of intervals in partition $P$. $f(\cdot)$ which we assume to be
bounded (see Section 2), and that $\xi\in[\nu_{i},\nu_{i-1}]$ and
$w^{k-i}(v)\in[\nu_{i},\nu_{i-1}]$. Hence, for
$v\in[\nu_{k},\nu_{k-1}]\cap[p^{\star},\overline{v}]$ (a.e)

$\frac{m^{k-1}}{\varepsilon^{\beta}}\bar{F}(\nu_{k-1})-m^{k-1}V_{0}^{\overline{v}}(f)\leq\lambda(w(v))\leq\frac{m^{k-1}}{\varepsilon^{\beta}}\bar{F}(\nu_{k-1})+m^{k-1}V_{0}^{\overline{v}}(f).$

Note that $\bar{F}(\nu_{k-1})\leq\bar{F}(v)$. Also,

$\bar{F}(\nu_{k-1})=\bar{F}(v)-\int_{v}^{\nu_{k-1}}f(x)dx\geq\bar{F}(v)-\bar{f}(\nu_{k-1}-v)\geq\bar{F}(v)-\bar{f}\cdot(w(v)-v).$

Additionally, we note that $(w(v)-v)$ in increasing for $v\geq p^{\star}$
hence $(w(v)-v)\leq\nu_{k-2}-\nu_{k-1}=\varepsilon^{\beta}/m^{k-1}$. Then, for
$v\in[\nu_{k},\nu_{k-1}]\cap[p^{\star},\overline{v}]$ (a.e)

$\frac{m^{k-1}}{\varepsilon^{\beta}}\bar{F}(v)-\bar{f}-m^{k-1}V_{0}^{\overline{v}}(f)\leq\lambda(w(v))\leq\frac{m^{k-1}}{\varepsilon^{\beta}}\bar{F}(v)+m^{k-1}V_{0}^{\overline{v}}(f).$

We thus have that the following holds almost everywhere for
$v\in[p^{\star},\nu_{0}]$

$\displaystyle\Delta(v)$ $\displaystyle=vf(v)-\dot{w}(v)(w(v)-v)\lambda(w(v))$
$\displaystyle\geq vf(v)-m\frac{\varepsilon^{\beta}}{m^{k-1}}\lambda(w(v))$
$\displaystyle\geq
vf(v)-m\frac{\varepsilon^{\beta}}{m^{k-1}}\left(\frac{m^{k-1}}{\varepsilon^{\beta}}\bar{F}(v)+m^{k-1}V_{0}^{\overline{v}}(f)\right)$
$\displaystyle=vf(v)-m\bar{F}(v)-m\varepsilon^{\beta}V_{0}^{\overline{v}}(f)$
$\displaystyle=vf(v)-\bar{F}(v)-(m-1)\bar{F}(v)-m\varepsilon^{\beta}V_{0}^{\overline{v}}(f)$
$\displaystyle=vf(v)-\bar{F}(v)-\frac{\varepsilon^{\beta}-\varepsilon^{\gamma}}{\nu_{0}-p^{\star}}-m\varepsilon^{\beta}V_{0}^{\overline{v}}(f)$
$\displaystyle\geq vf(v)-\bar{F}(v)-C_{L}\varepsilon^{\beta},$

where $C_{L}$ is a positive constant. In the last inequality we have used
$\varepsilon>0$ small. We also have

$\displaystyle\Delta(v)$ $\displaystyle=vf(v)-\dot{w}(v)(w(v)-v)\lambda(w(v))$
$\displaystyle\leq vf(v)-\dot{w}(v)(w(\nu_{k})-\nu_{k})\lambda(w(v))$
$\displaystyle\leq vf(v)-m\frac{\varepsilon^{\beta}}{m^{k}}\lambda(w(v))$
$\displaystyle\leq
vf(v)-\frac{\varepsilon^{\beta}}{m^{k-1}}\left(\frac{m^{k-1}}{\varepsilon^{\beta}}\bar{F}(v)-\bar{f}-m^{k-1}V_{0}^{\overline{v}}(f)\right)$
$\displaystyle\leq
vf(v)-\bar{F}(v)+\varepsilon^{\beta}\left\\{\bar{f}+V_{0}^{\overline{v}}(f)\right\\}$
$\displaystyle=vf(v)-\bar{F}(v)+C_{U}\varepsilon^{\beta},$

where $C_{U}$ is a positive constant. We have thus shown that

$\Delta_{L}(v)\triangleq
vf(v)-\bar{F}(v)-C_{L}\varepsilon^{\beta}\leq\Delta(v)\leq
vf(v)-\bar{F}(v)+C_{U}\varepsilon^{\beta}\triangleq\Delta_{U}(v),\quad
v\in[p^{\star},\nu_{0}]\>\>\text{ a.e}.$

Note that $\Delta_{L}(v)=-\dot{R}(v)-C_{L}\varepsilon^{\beta}$ and, hence,
$\Delta_{L}(v)\geq 0$ if and only if $\dot{R}(v)\leq-
C_{L}\varepsilon^{\beta}$. By Definition 2.1, the latter is true for all $v$
such that $-\kappa_{L}\alpha(v-p^{\star})^{\alpha-1}\leq-
C_{L}\varepsilon^{\beta}$ or, equivalently, for all
$v\in(p^{\star},p^{\star}+\ell)$ such that $v\geq
p^{\star}+(C_{L}/(\kappa_{L}\alpha))^{1/(\alpha-1)}\varepsilon^{\beta/(\alpha-1)}$.
We define

$p^{\star}_{L}=p^{\star}+\underbrace{(C_{L}/(\kappa_{L}\alpha))^{1/(\alpha-1)}}_{C_{L}^{\prime}(\alpha)}\varepsilon^{\beta/(\alpha-1)},$

and we consider $\varepsilon>0$ small enough such that
$p^{\star}_{L}\in(p^{\star},p^{\star}+\ell)$. Hence, for
$v\in[p^{\star}_{L},p^{\star}+\ell)$ we have that $\Delta_{L}(v)\geq 0$. Now,
for $v\geq p^{\star}+\ell$ we use the last assumption in the statement of the
theorem. From the assumption, we can see that it is always possible to
consider $\varepsilon>0$ small enough such that $\sup_{v\geq
p^{\star}+\ell}\dot{R}(v)\leq-C_{L}\varepsilon^{\beta}$ (because the sup is
strictly negative). Therefore, for any $v\geq p^{\star}+\ell$ we have that
$\Delta_{L}(v)\geq 0$. In conclusion, we can always consider $\varepsilon>0$
small enough such that for $v\geq p^{\star}_{L}$ we have that
$\Delta_{L}(v)\geq 0$. Hence, considering $\varepsilon>0$ small enough such
that $p^{\star}_{L}<\nu_{0}$, Lemma 3.6 with $x=p^{\star}_{L}$ implies

$\displaystyle\int_{p^{\star}_{L}}^{\overline{v}}\Delta(v)^{+}dv$
$\displaystyle=\int_{p^{\star}_{L}}^{\overline{v}}\Delta(v)dv$
$\displaystyle\leq
p^{\star}_{L}\bar{F}(p^{\star}_{L})+2(w(p^{\star}_{L})-p^{\star}_{L})$
$\displaystyle=R(p^{\star}_{L})+2(w(p^{\star}_{L})-p^{\star}_{L})$
$\displaystyle=R(p^{\star}_{L})+(m-1)C_{L}^{\prime}(\alpha)\varepsilon^{\frac{\beta}{\alpha-1}}+\varepsilon^{\gamma}$
$\displaystyle=R(p^{\star}_{L})+\mathcal{O}\left(\varepsilon^{\beta+\frac{\beta}{\alpha-1}}\right)+\varepsilon^{\gamma},$

where we have used that $m-1=\mathcal{O}(\varepsilon^{\beta})$. We also have,
$\Delta_{U}(v)\geq 0$ for $v\geq p^{\star}$ and

$\displaystyle\int_{p^{\star}}^{p^{\star}_{L}}\Delta(v)^{+}dv$
$\displaystyle\leq\int_{p^{\star}}^{p^{\star}_{L}}\Delta_{U}(v)dv=R(p^{\star})-R(p^{\star}_{L})+C_{U}\varepsilon^{\beta}C_{L}^{\prime}(\alpha)\varepsilon^{\frac{\beta}{\alpha-1}}.$

Then,

$\int_{p^{\star}}^{\overline{v}}\Delta(v)^{+}dv\leq
R(p^{\star})+\mathcal{O}\left(\varepsilon^{\beta+\frac{\beta}{\alpha-1}}\right)+\varepsilon^{\gamma}.$

Now, we still need to bound $\Phi_{2}(\lambda^{{\scriptscriptstyle\text{\rm
IC}}})$ for $v\leq p^{\star}$. Before we do that we can check that we are
getting the right order. From the bound for the number of steps, we have a
term of order
$\varepsilon\cdot\log(\varepsilon^{\beta-\gamma})/\varepsilon^{\beta}$. So if
we take $\beta=(\alpha-1)/(2\alpha-1)$. We will have that

$\gamma=1-\beta=\frac{\alpha}{2\alpha-1}\quad\text{and}\quad\beta+\frac{\beta}{\alpha-1}=\frac{\alpha}{2\alpha-1}.$

Note that $\gamma>\beta$ if and only if $\beta<1/2$ which is true if
$\alpha<\infty$. In sum, this gives the upper bound of order
$\frac{\alpha}{2\alpha-1}$. As desired.

Case 2: We consider the case $v\leq p^{\star}$. We will provide an upper bound
for $\Delta(v)$ for $v\leq p^{\star}$. Then we will show that the upper is
negative except close to $p^{\star}$. The area below the upper bound in such
region will be of the desired order. We have the following

$\displaystyle\Delta(v)$ $\displaystyle=vf(v)-\dot{w}(v)(w(v)-v)\lambda(w(v))$
$\displaystyle=vf(v)-(2-m)(w(v)-v)\lambda(w(v)).$

We now provide bounds for the terms $(w(v)-v)$ and $\lambda(w(v))$. Let
$k^{\star}$ be the largest $k$ such that $\nu_{k}\geq p^{\star}$. We consider
$v\in[\nu_{k^{\star}+j},\nu_{k^{\star}+j-1}]\cap[0,p^{\star}]$ for $j\geq 1$.
We let $\bar{j}$ to be the largest $j$ such that $\nu_{k^{\star}+j}\geq 0$ and
define $\nu_{k^{\star}+\bar{j}+1}=0$. For $j\in\\{1,\dots,\bar{j}\\}$, we have

$\displaystyle\nu_{k^{\star}+j-1}-\nu_{k^{\star}+j}$
$\displaystyle=\frac{1}{(2-m)^{j-1}}\left\\{\nu_{k^{\star}}+p^{\star}((2-m)^{j-1}-1)-\varepsilon^{\gamma}\frac{(2-m)^{j-1}-1}{2-m-1}\right\\}$
$\displaystyle-\frac{1}{(2-m)^{j}}\left\\{\nu_{k^{\star}}+p^{\star}((2-m)^{j}-1)-\varepsilon^{\gamma}\frac{(2-m)^{j}-1}{2-m-1}\right\\}$
$\displaystyle=\frac{1}{(2-m)^{j}}\left\\{(1-m)\nu_{k^{\star}}+p^{\star}(m-1)+\varepsilon^{\gamma}\right\\}$
$\displaystyle=\frac{1}{(2-m)^{j}}\left\\{(p^{\star}-\nu_{k^{\star}})(m-1)+\varepsilon^{\gamma}\right\\}.$
(21)

Additionally, since $\nu_{k^{\star}+j}\geq 0$ we have that

$(2-m)^{j-1}((m-1)p^{\star}+\varepsilon^{\gamma})\geq(p^{\star}-\nu_{k^{\star}})(m-1)+\varepsilon^{\gamma},$

note that $\nu_{k^{\star}}-p^{\star}\leq
w(p^{\star})-p^{\star}=\varepsilon^{\gamma}$. Hence, $\nu_{k^{\star}+j}\geq 0$
implies that

$\frac{1}{(2-m)^{j-1}}\leq\frac{1}{(2-m)}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1\right),\quad
j\in\\{1,\dots,\bar{j}\\}.$ (22)

We use the above to provide lower bounds for both $(w(v)-v)$ and
$\lambda(w(v))$. We start with $w(v)-v$. Note that for $v\leq p^{\star}$,
$w(v)-v$ is decreasing. Hence for
$v\in[\nu_{k^{\star}+j},\nu_{k^{\star}+j-1}]\cap[0,p^{\star}]$ with
$j\in\\{1,\dots,\bar{j}+1\\}$ we have

$w(v)-v\geq(2-m)\frac{\varepsilon^{\gamma}}{(2-m)^{j-1}}.$

Indeed, for $j=1$ we have

$w(v)-v\geq
w(p^{\star})-p^{\star}=\varepsilon^{\gamma}\geq(2-m)\varepsilon^{\gamma},$

where we have used that $(2-m)<1$. For $j>1$ we have

$\displaystyle w(v)-v$ $\displaystyle\geq
w(\nu_{k^{\star}+j-1})-\nu_{k^{\star}+j-1}$
$\displaystyle=\nu_{k^{\star}+j-2}-\nu_{k^{\star}+j-1}$
$\displaystyle=\frac{1}{(2-m)^{j-1}}\left\\{(p^{\star}-\nu_{k^{\star}})(m-1)+\varepsilon^{\gamma}\right\\}$
$\displaystyle\geq(2-m)\frac{\varepsilon^{\gamma}}{(2-m)^{j-1}}.$

Using the above, so far we have that for
$v\in[\nu_{k^{\star}+j},\nu_{k^{\star}+j-1}]\cap[0,p^{\star}]$ for
$j\in\\{1,\dots,\bar{j}+1\\}$

$\displaystyle\Delta(v)$ $\displaystyle\leq
vf(v)-(2-m)^{2}\frac{\varepsilon^{\gamma}}{(2-m)^{j-1}}\lambda(w(v)).$

Next, we provide a lower bound for $\lambda(w(v))$. From Lemma 3.4 and since
$(w(v))\geq\mu$ we have for
$v\in[\nu_{k^{\star}+j},\nu_{k^{\star}+j-1}]\cap[0,p^{\star}]$ with
$j\in\\{1,\dots,\bar{j}+1\\}$ that (almost everywhere)

$\displaystyle\lambda(w(v))$
$\displaystyle\geq\sum_{i=0}^{j-1}f(w^{i+1}(v))(2-m)^{i}+(2-m)^{j-1}\sum_{i=j}^{k^{\star}+j-1}f(w^{i+1}(v))m^{i-j+1}$
$\displaystyle=(2-m)^{j-1}\underbrace{\sum_{i=0}^{j-1}f(w^{j-i}(v))(2-m)^{-i}}_{(A)}+(2-m)^{j-1}m^{k^{\star}}\underbrace{\sum_{i=0}^{k^{\star}-1}f(w^{k^{\star}-i+j}(v))m^{-i}}_{(B)}.$

Next, we bound each sum above. For $(A)$ we have that since
$v\in[\nu_{k^{\star}+j},\nu_{k^{\star}+j-1}]$ then
$w^{j-i}(v)\in[\nu_{k^{\star}+i},\nu_{k^{\star}+i-1}]$. So we can always find
$\xi\in[\nu_{k^{\star}+i},\nu_{k^{\star}+i-1}]$ such that

$\displaystyle\int_{\nu_{k^{\star}+i}}^{\nu_{k^{\star}+i-1}}f(v)dv$
$\displaystyle=\underbrace{(f(\xi)-f(w^{j-i}(v)))}_{\triangleq\chi_{j,i}(v)}\cdot(\nu_{k^{\star}+i-1}-\nu_{k^{\star}+i})+f(w^{j-i}(v))\cdot(\nu_{k^{\star}+i-1}-\nu_{k^{\star}+i})$
$\displaystyle\leq|\chi_{j,i}(v)|\cdot(\nu_{k^{\star}+i-1}-\nu_{k^{\star}+i})+f(w^{j-i}(v))\cdot(\nu_{k^{\star}+i-1}-\nu_{k^{\star}+i})$
$\displaystyle\leq|\chi_{j,i}(v)|\cdot