# A survey on set-theoretical solutions to the pentagon equation

Marzia MAZZOTTA<EMAIL_ADDRESS>Dipartimento di Matematica e
Fisica “Ennio De Giorgi”, Università del Salento,
Via Provinciale Lecce-Arnesano, 73100 Lecce (Italy)

###### Abstract

This survey aims to collect the main results of the theory of the set-
theoretical solutions to the pentagon equation obtained up to now in the
literature. In particular, we present some classes of these solutions and
raise some questions.

###### keywords:

pentagon equation , set-theoretical solution

###### MSC:

[2020] 16T25, 81R50

## Introduction

The _pentagon equation_ classically originates from the field of Mathematical
Physics. It appears in various forms in different contexts, such as in the
representation theory of quantum groups as the Biedenharn–Elliott identity for
$6j$-symbols [4], in quantum conformal field theory as the identity for the
fusion matrices [28], in quasi-Hopf algebras as the consistency equation for
the association [12]. Still, it appears in other areas of mathematics, also
with different terminologies (see, for instance, [1, 2, 17, 15, 18, 25, 31]).
Supposed anyone wants to deepen contexts in which the pentagon equation
appears, we refer to the papers on polygon equations [11, 27] with the
references therein.
Given a vector space $V$ over a field $F$, a linear map $S:V\otimes V\to
V\otimes V$ is said to be a _solution of the pentagon equation_ if it holds

$\displaystyle S_{12}S_{13}S_{23}=S_{23}S_{12},$

where $S_{12}=S\otimes\operatorname{id}_{V}$,
$S_{23}=\operatorname{id}_{V}\otimes\,S$,
$S_{13}=(\operatorname{id}_{V}\otimes\,\Sigma)\,S_{12}\;(\operatorname{id}_{V}\otimes\,\Sigma)$,
with $\Sigma$ the flip operator on $V\otimes V$, i.e., $\Sigma(u\otimes
v)=v\otimes u$, for all $u,v\in V$. Maillet [21] showed that solutions of the
pentagon equation lead to solutions of the tetrahedron equation [34], a
multidimensional generalization of the well-known quantum Yang-Baxter equation
[3, 32]. Indeed, as one can note, the pentagon equation is the quantum Yang-
Baxter equation with the middle term missing on the right-hand side.
Furthermore, Militaru showed that bijective solutions on finite vector spaces
are in one-to-one correspondence with finite Hopf algebras, so the
classification of the latter is reduced to the classification of solutions
(see [26, Theorem 3.2]).

In 1998, Kashaev and Sergeev [16] began the study of the pentagon equation
into set-theoretical terms to find vector solutions. Into the specific, if $X$
is a finite set and $s:X\times X\to X\times X$ is a map satisfying the
relation

$s_{23}s_{13}s_{12}=s_{12}s_{23},$

where $s_{12}=s\times\operatorname{id}_{X}$,
$s_{23}=\operatorname{id}_{X}\times s$,
$s_{13}=(\operatorname{id}_{X}\times\tau)\,s_{12}\,(\operatorname{id}_{X}\times\tau)$,
with $\tau(x,y)=(y,x)$, for all $x,y\in X$, one can associate a solution
$S:F^{X\times X}\to F^{X\times X}$ on the function space $F^{X}$ defined as
$S(f)(x,y)=f(s(x,y)),$ for all $x,y\in X$. The map $s$ above is said to be a
_set-theoretical solution of the pentagon equation_ , or briefly a _PE
solution_ , on $X$. Yet, the first instances of PE solutions can be also
extrapolated from the papers by Zakrzewski [33] and Baaj and Skandalis [2],
where the authors dealt with specific solutions on differential manifolds and
measured spaces, respectively. A purely algebraic transcription of these
solutions can be found in [5]. In this last paper, the authors provide the
first systematic approach for investigating PE solutions. Writing a PE
solution $s:X\times X\to X\times X$ as $s(x,y)=(x\cdot y,\theta_{x}(y))$,
where $\theta_{x}:X\to X$ is a map, for every $x\in X$, one has that

  * -

$(X,\cdot)$ is a semigroup,

  * -

$\theta_{x}(y)\cdot\theta_{x\cdot y}(z)=\theta_{x}(y\cdot z)$,

  * -

$\theta_{\theta_{x}(y)}\theta_{x\cdot y}=\theta_{y}$,

for all $x,y,z\in X$. Therefore, the natural first step is to look for PE
solutions in a group. In this regard, a complete classification of these maps
was provided in [5, Theorem 13] in terms of normal subgroups of the group.
Subsequently, the authors in [24] have started the study of PE solutions in
Clifford semigroups with an attempt to describe them, since they are the
closest semigroups to groups (see [7] and the monographs [29, 20] for more
details). However, the study has not been completed because there are many
families of solutions in this class of semigroups. Given a Clifford semigroup
$X$, they describe the _$\operatorname{E}(X)$ -invariant PE solutions_,
namely, those solutions for which $\theta_{a}$ remains invariant in the set
$\operatorname{E}(X)$ of all idempotents of $X$, for every $a\in X$. Moreover,
they construct a family of _$\operatorname{E}(X)$ -fixed PE solutions_, i.e.,
those solutions for which $\theta_{a}$ fixes every element in
$\operatorname{E}(X)$, for every $a\in X$. Future developments in this regard
can be found in this paper.

Describing PE solutions on arbitrary semigroups seems very challenging since
there are many even in the case of small-order semigroups. For example, for
semigroups of order $3$ there are already 202 non-isomorphic solutions (see
[23, Appendix B]). A strategy is finding and studying specific classes of PE
solutions. In this respect, Colazzo, Jespers, and Kubat [10] described all the
_involutive_ PE solutions, namely, solutions satisfying the property
$s^{2}=\operatorname{id}_{X\times X}$. Recently, the author in [22] started
the investigation of _idempotent_ PE solutions, i.e., solutions such that
$s^{2}=s$. A classification of these solutions is obtained in the case of
monoids having central idempotents. Additionally, in [6], one can find a
description of PE solutions that are also set-theoretical solutions of the
Yang-Baxter equation, the so-called _P-QYBE solutions_. Easy examples are the
maps $s$ of the form $s(x,y)=(f(x),g(y))$, with $f,g:X\to X$ idempotent maps
such that $fg=gf$, that belongs to the class of Lyubashenko’s solutions (for
more details, see [13]).

Another line of research consists of looking for methods to obtain new
solutions starting from known ones. In [6], some can be found, such as the
technique of the _matched product_ of two solutions $s$ and $t$ on two
semigroups $S$ and $T$, respectively, that is a new solution on the semigroup
$S\bowtie T$ (see [6, Definition 1]), namely a semigroup including the
_classical Zappa product_ of $S$ and $T$ (see [19, Definition 1.1]).

In this survey, we give an overview of PE solutions and collect the most
important results on this little-explored area. Some open questions will be
raised during the work that may inspire the reader. Specifically, the survey
is organized as follows: in the first section, we give some preliminaries and
examples by recalling the description of all PE solutions defined in groups;
in the second one, we present some problems related to PE solutions in the
class of Clifford semigroups; the third section devotes to the description of
all involutive PE solutions: the fourth one contains the characterization of
idempotent PE solutions in monoids having central idempotents and some issues
concerning this class of solutions. Finally, in the last paragraph, we give
some hints on other classes of PE solutions that one could study, namely the
commutative and cocommutative ones.

##  1 Definitions and examples

This section aims to give some basics on PE solutions. In particular, we
recall some examples and constructions.

Let $X$ be a non-empty set. The map $s:X\times X\to X\times X$ given by
$s(x,y)=(x\cdot y,\theta_{x}(y))$, where $\theta_{x}:X\to X$ is a map, for
every $x\in X$, is a _PE solution_ if, and only if, $(X,\cdot)$ is a semigroup
and they hold

$\displaystyle\theta_{x}(y)\cdot\theta_{x\cdot y}(z)$
$\displaystyle=\theta_{x}(y\cdot z),$ (P1)
$\displaystyle\theta_{\theta_{x}(y)}\theta_{x\cdot y}$
$\displaystyle=\theta_{y},$ (P2)

for all $x,y,z\in X$. Moreover, $s$ is said to be _involutive_ if
$s^{2}=\operatorname{id}_{X\times X}$; _idempotent_ if $s^{2}=s$; _non-
degenerate_ if $\theta_{x}$ is bijective, for every $x\in X$.

######  Definition 1.1.

Let $X$ and $Y$ be two semigroups and consider $s(x,y)=(xy,\theta_{x}(y))$ and
$t(u,v)=(uv,\eta_{u}(v))$ two PE solutions on $X$ and $Y$, respectively. Then,
$s$ and $t$ are _isomorphic_ if there exists an isomorphism $\psi:X\to Y$ such
that $\psi\theta_{x}(y)=\eta_{\psi\left(x\right)}\psi(y)$, for all $x,y\in X$,
or, equivalently, $(\psi\times\psi)s=t(\psi\times\psi)$.

From now on, we will use juxtaposition for the product in any semigroup. In
the next, we give some examples of solutions.

######  Examples 1.

  1. 1.

Let $X$ be a set and $f,g:X\to X$ maps such that $f^{2}=f$, $g^{2}=g$, and
$fg=gf$. Then, the map
$s(x,y)=\left(f\left(x\right),\,g\left(y\right)\right)$, for all $x,y\in X$,
is an idempotent PE solution on $X$ (cf. [25]). Note that this map also
belongs to the class of P-QYBE solutions since it also satisfies the quantum
Yang-Baxter equation (cf. [6, Examples 8]).

  2. 2.

If $S$ is a semigroup and $\gamma\in\operatorname{End}(S)$ such that
$\gamma^{2}=\gamma$, the map $s(x,y)=\left(xy,\gamma\left(y\right)\right),$
for all $x,y\in S$, is a PE solution on $S$ (see [5, Examples 2-2.]). Note
that $s$ is non-degenerate if, and only if, $\gamma=\operatorname{id}_{S}$.

  3. 3.

Let $S=\\{0,a,b\\}$ be the null semigroup, i.e., $xy=0$, for all $x,y\in S$.
Consider the maps $\theta_{0}=\operatorname{id}_{S}$ and
$\theta_{a}=\theta_{b}$ such that $\theta_{a}(0)=0$, $\theta_{a}(a)=b$, and
$\theta_{a}(b)=a$. Then, the map $s(x,y)=(0,\theta_{x}(y))$ is an idempotent
and non-degenerate PE solution on $S$ (see [23, Appendix B]).

  4. 4.

Let $G$ be a group of finite exponent, $E=\\{1,\dots,n\\}$, and
$\sigma\in\operatorname{Sym}(n)$ such that $\sigma^{\sigma(i)+1}=\sigma^{i}$,
for any $i\in E$. Put $S=G\times E$, the map $s:S\times S\to S\times S$
defined by

$\displaystyle
s((i,a),(j,b))=\left(\left(i,ab\right),\left(\sigma^{i}(j),b\right)\right)$

is a bijective PE solution on $S$ (see [10, Example 1.3]). Additionally, $s$
is involutive if, and only if $G$ has exponent $2$ and $\sigma$ has order $2$.

Other examples of PE solutions can be obtained from the pioneering works [33,
2], where the authors deal with the PE solutions in non-algebraic contexts, by
calling such maps _pentagonal transformations_. We present such solutions by
transcribing them in purely algebraic terms.

######  Examples 2.

Let $G$ be a group that admits an exact factorization through two subgroups
$H,K$ and $p_{1}:G\to H$, $p_{2}:G\to K$ the projection maps such that every
$x\in G$ can be written as $x=p_{1}(x)\,p_{2}(x)$. Then, the maps $s,r:G\times
G\to G\times G$ given by

$\displaystyle
s\left(x,y\right)=\left(p_{2}\left(yp_{1}\left(x\right)^{-1}\right)x,\;yp_{1}\left(x\right)^{-1}\right)\quad\&\quad
r\left(x,y\right)=\left(xp_{1}\left(p_{2}\left(x\right)^{-1}y\right),\,p_{2}\left(x\right)^{-1}y\right)$

are bijective PE solutions on $G$. In particular, $G$ endowed with the
operation defined by the first component of the map $r$ (or $s$) is a left
group, i.e., the direct product of a left zero semigroup and a group.

The maps in 2 are such that $r=\tau s\tau$, with $\tau$ the flip map. In
general, one has that if $s$ is a bijective PE solution on a set $X$, the map
$s^{op}=\tau s^{-1}\tau$ also is a PE solution, called the _opposite PE
solution_ of $s$ (in analogy to the opposite operators defined on Hilbert
spaces [2]).

In [16, Proposition 1], one can find the first systematic way for constructing
PE solutions which we recall below.

######  Proposition 1.2.

Let $G$ be a group, $X$ a subsemigroup of $G$, and $\lambda,\mu:X\to G$ maps
such that, for all $x,y\in X$,

  1. 1.

$x\ast y:=\mu(x)^{-1}\mu(xy)\in X$,

  2. 2.

$\mu(x\ast y)=\lambda(x)\mu(y)$.

Then, the map $s:X\times X\to X\times X$ given by $s(x,y)=(xy,x\ast y)$ is a
PE solution on $X$.

The following theorem illustrates how to find all the PE solutions in the case
of a group.

######  Theorem 1.3.

[5, Theorem 15] Let $G$ be a group, $K$ a normal subgroup of $G$, and $R$ a
system of representatives of $G/K$. If $\mu:G\to R$ is a map such that
$\mu(x)\in Kx$, for any $x\in G$, then the map
$s(x,y)=\left(xy,\mu\left(x\right)^{-1}\mu\left(xy\right)\right),$ for all
$x,y\in G$, is a PE solution.
Vice versa, if $s(x,y)=(xy,\theta_{x}(y))$ is a PE solution on $G$, then
$K=\\{x\in G\,\mid\,\theta_{1}(x)=1\\}$ is a normal subgroup of $G$,
$\operatorname{Im}\theta_{1}$ is a system of representatives of $G/K$,
$\theta_{1}(x)\in Kx$, and
$\theta_{x}(y)=\theta_{1}\left(x\right)^{-1}\theta_{1}\left(xy\right),$ for
all $x,y\in G$.

It immediately follows from 1.3 that the only bijective PE solution on a group
$G$ is given by the map $s_{G}(x,y)=(xy,y)$ that is known in literature as
_Kac-Takesaki solution_ , concerning the associated linear operator defined on
the Hilbert space of square-integrable functions [30].

An easy example of PE solutions on the symmetric group is the following.

######  Example 3.

Let $n\geq 3$, $\operatorname{Sym}_{n}$ the symmetric group of order $n$,
$\operatorname{A}_{n}$ the alternating group of degree $n$, and
$R=\\{\operatorname{id}_{\operatorname{Sym}_{n}},\pi\\}$ a system of
representatives of $\operatorname{Sym}_{n}/\operatorname{A}_{n}$, where $\pi$
is a transposition of $\operatorname{Sym}_{n}$. Besides, consider the map
$\mu:\operatorname{Sym}_{n}\to R$ given by

$\mu(\alpha)=\begin{cases}\pi\qquad&\text{if}\;\operatorname{sgn}(\alpha)=-1\\\
\operatorname{id}_{\operatorname{Sym}_{n}}\quad&\text{if}\;\operatorname{sgn}(\alpha)=1\end{cases},$

for every $\alpha\in\operatorname{Sym}_{n}$. Then, the map
$s(\alpha,\beta)=\left(\alpha\beta,\mu\left(\alpha\right)^{-1}\mu\left(\alpha\beta\right)\right)$,
for all $\alpha,\beta\in\operatorname{Sym}_{n}$, is a PE solution on
$\operatorname{Sym}_{n}$.

In the next section, we will show how to extend the theorem above to a
specific class of solutions defined in Clifford semigroups. Regarding the PE
solutions defined on monoids, some properties of the maps $\theta_{x}$ are
given in [22]. However, we are still far from a classification.

######  Problem 1.

Study or find some constructions of PE solutions defined on monoids.

To conclude this preliminary section, we mention the technique of _matched
product_ of PE solutions introduced in [6], which is a method to obtain a new
PE solution on the Cartesian Product of two semigroups starting from two given
ones. To recall it, we first give the following definition.

######  Definition 1.4.

Let $S$ and $T$ be semigroups, $\alpha:T\to S^{S}$ and $\beta:S\to T^{T}$
maps, and set $\alpha_{u}:=\alpha\left(u\right)$, for every $u\in T$, and
$\beta_{a}:=\beta\left(a\right)$, for every $a\in S$. Moreover, let
$s(a,b)=(ab,\theta_{a}(b))$ and $t(u,v)=(uv,\theta_{u}(v))$ PE solutions on
$S$ and $T$, respectively. If the following conditions are satisfied

$\displaystyle\alpha_{u}\left(a\alpha_{v}\left(b\right)\right)=\alpha_{u}\left(a\right)\alpha_{\beta_{a}\left(u\right)v}\left(b\right)$
$\displaystyle\quad\&\quad\beta_{a}\left(\beta_{b}\left(u\right)v\right)=\beta_{b\alpha_{v}\left(a\right)}\left(u\right)\beta_{a}\left(v\right).$
$\displaystyle\theta_{a}{\alpha_{u}{}}$
$\displaystyle=\theta_{\alpha_{v}{\left(a\right)}}{\alpha_{\beta_{a}{\left(v\right)u}}{}}$
$\displaystyle\theta_{a\alpha_{u}{\left(b\right)}}{}$
$\displaystyle=\alpha_{\theta_{\beta_{b}{\left(u\right)}}{\left(v\right)}}{\theta_{a\alpha_{u}{\left(b\right)}}{}}$
$\displaystyle\theta_{\beta_{b\alpha_{v}{\left(c\right)}}{\left(u\right)}}{\beta_{c}{\left(v\right)}}$
$\displaystyle=\beta_{\theta_{a\alpha_{u}{\left(b\right)}}{\alpha_{\beta_{b}{\left(u\right)v}}{\left(c\right)}}}{\theta_{\beta_{b}{\left(u\right)}}{\left(v\right)}},$

for all $a,b,c\in S$ and $u,v\in T$, then we call
$\left(s,t,\alpha,\beta\right)$ a _matched quadruple_.

It is a routine computation to verify that $S\times T$ is a semigroup endowed
with the operation defined by
$\left(a,u\right)\left(b,v\right)=\left(a\alpha_{u}{\left(b\right)},\beta_{b}{\left(u\right)}v\right)$,
for all $(a,u),(b,v)\in S\times T$, called _matched product of $S$ and $T$_
and denoted by $S\bowtie T$. As a class of examples, one can easily find the
classical Zappa product [19].

######  Theorem 1.5.

Let $S$, $T$ be semigroups and $\left(s,t,\alpha,\beta\right)$ a matched
quadruple. Then, the map $s\bowtie t:(S\times T)\times(S\times T)\to(S\times
T)\times(S\times T)$ defined by

$\displaystyle s\bowtie
t\left((a,u),(b,v)\right)=\left(\left(a\alpha_{u}{\left(b\right)},\beta_{b}{\left(u\right)}v\right),\,\left(\theta_{a}{\alpha_{u}{\left(b\right)}},\theta_{\beta_{b}{\left(u\right)}}{\left(v\right)}\right)\right),$

for all $\left(a,u\right),\left(b,v\right)\in S\times T$, is a PE solution on
$S\bowtie T$, called _matched product of $s$ and $t$_.

######  Example 4.

Let $S=\\{1_{S},x,y\\}$ be the commutative idempotent monoid such that $xy=y$
and $T=\\{1_{T},z\\}$ the idempotent monoid. Consider the maps $\alpha:T\to
S^{S}$ given by $\alpha_{1_{T}}=\operatorname{id}_{S}$ and
$\alpha_{z}=\gamma$, where $\gamma\in\operatorname{End}(S)$,
$\gamma^{2}=\gamma$, and $\beta:S\to T^{T}$ defined by
$\beta_{1_{S}}=\operatorname{id}_{T}$ and $\beta_{x}(u)=\beta_{y}(u)=1_{T}$,
for every $u\in T$. Moreover, let $s(a,b)=(ab,\gamma(b))$ and $t(u,v)=(uv,v)$
be the PE solutions on $S$ and $T$, respectively. Then, $(s,t,\alpha,\beta)$
is a matched quadruple and the map

$s\bowtie
t\,((a,u),(b,v))=\begin{cases}((a,v),(1_{S},v))\qquad&\text{if}\;b=1_{S},\,u=1_{T}\\\
((a,uv),(1_{S},v))\qquad&\text{if}\;b=1_{S},\,u\neq 1_{T}\\\
((ab,v,(\gamma(b),v))\qquad&\text{if}\;b\neq 1_{S},\,u=1_{T}\\\
((a\gamma(b),v),(\gamma(b),v))\qquad&\text{if}\;b\neq 1_{S},\,u\neq
1_{T}\end{cases}$

is a PE solution on $S\bowtie T$.

##  2 PE solutions on Clifford semigroups

In this section, we focus on PE solutions defined in a Clifford semigroup and
satisfying special properties on the set of all idempotents discussed in [24].
Moreover, we propose some topics to be developed.

Initially, we recall some basics of Clifford semigroups useful for our
purposes. For a more detailed treatment of this class of semigroups, we refer
the reader to the paper by Clifford [7] and the monographs by Petrich [29] and
Lawson [20]. A semigroup $X$ is _inverse_ if for each $x\in X$ there exists a
unique $x^{-1}\in X$ such that

$x=xx^{-1}x$ & $x^{-1}=x^{-1}xx^{-1}$.

Every group is an inverse semigroup. They hold $(xy)^{-1}=y^{-1}x^{-1}$ and
$(x^{-1})^{-1}=x$, for all $x,y\in X$. Additionally, $X$ is _Clifford_ if the
idempotents $xx^{-1}$ and $x^{-1}x$ are equal, for any $x\in X$, or,
equivalently, the idempotents are central in the sense that commute with every
element in $X$. Furthermore, any Clifford semigroup is _union of groups._ Into
the specific, denoted by $\operatorname{E}(X)$ the set of all idempotents of
$X$, there exist a family $\\{G_{e}\\}_{e\in\operatorname{E}(X)}$ of disjoint
groups, a family of group homomorphisms $\varphi_{f,e}:G_{f}\to G_{e}$, for
all $e,f\in\operatorname{E}(X)$ with $e\leq f$, i.e., $ef=fe=e$, satisfying
the properties

  1. 1.

$\varphi_{f,e}(y)=ey$, for any $y\in G_{f}$,

  2. 2.

$\varphi_{g,e}=\varphi_{f,e}\varphi_{g,f}$, for all $e\leq f\leq g$,

such that the product in $X$ can be expressed as
$xy=\varphi_{e,ef}\left(x\right)\varphi_{f,ef}\left(y\right)$, for all $x\in
G_{e}$ and $y\in G_{f}$.

Let us observe that every Clifford semigroup $X$ gives rise to the following
PE solutions

$\displaystyle\mathcal{I}(x,y)=(xy,y),\qquad\mathcal{F}(x,y)=\left(xy,yy^{-1}\right),\qquad\mathcal{E}(x,y)=(xy,e),$

for all $x,y\in X$, where $e\in\operatorname{E}(X)$. These examples suggest
studying the PE solution classes defined as follows.

######  Definition 2.1.

A PE solution $s(x,y)=(xy,\theta_{x}(y))$ on a semigroup $X$ is said to be:

  1. 1.

_$\operatorname{E}\left(X\right)$ -invariant_ if
$\theta_{x}(e)=\theta_{x}(f)$, for all $x\in X$ and
$e,f\in\operatorname{E}(X)$;

  2. 2.

_$\operatorname{E}(X)$ -fixed_ if $\theta_{x}(e)=e$, for all $x\in X$ and
$e\in\operatorname{E}(X)$.

In particular, $\mathcal{E}$ is $\operatorname{E}\left(X\right)$-invariant,
while $\mathcal{I}$ and $\mathcal{F}$ are
$\operatorname{E}\left(X\right)$-fixed in any Clifford semigroup $X$.

######  Example 5.

Let $M=\\{1,\,x,\,y\\}$ be commutative Clifford monoid such that $x^{2}=x$,
$y^{2}=x$, and $xy=y$, and $\gamma\in\operatorname{End}(M)$ given by
$\gamma(1)=\gamma(x)=x$ and $\gamma(y)=y$. Then, the map
$s(x,y)=(xy,\gamma(y))$ is an $\operatorname{E}(M)$-invariant PE solution on
$M$.

Next, following [24, Theorem 15], we show how to construct all the
$\operatorname{E}(X)$-invariant PE solutions on a Clifford $X$, by extending
the description in 1.3. First, recall that a congruence $\tau$ on
$\operatorname{E}(X)$ is said to be _normal_ if

$\displaystyle\forall\ e,f\in\operatorname{E}(X)\quad e\ \tau\ f\
\Longrightarrow\ \forall\ a\in X\quad a^{-1}ea\ \tau\ a^{-1}fa.$

If $K$ is a normal subsemigroup of $X$, the pair $(K,\tau)$ is named a
_congruence pair_ of $X$ if

$\displaystyle\forall\ a\in X,\ e\in\operatorname{E}(X)\quad ae\in K\ \
\text{and}\ \ (e,a^{-1}a)\in\tau\ \Longrightarrow\ a\in K.$

Besides, recall that the restriction of a congruence $\rho$ in $X$ to
$\operatorname{E}(X)$ is also a congruence on $\operatorname{E}(X)$, called
the _trace_ of $\rho$ and usually written as $\operatorname{tr}\rho$. Denoted
by $\operatorname{Ker}\rho$ the union of all the idempotent $\rho$-classes,
the properties of $\rho$ can be described entirely in terms of
$\operatorname{Ker}\rho$ and $\operatorname{tr}\rho$, as we show next (for
more details, see [14, Section 5.3]).

######  Theorem 2.2 (cf. Theorem 5.3.3 in [14]).

Let $X$ be an inverse semigroup. If $\rho$ is a congruence on $X$, then
$(\operatorname{Ker}\rho,\operatorname{tr}\rho)$ is a congruence pair.
Conversely, if $(K,\tau)$ is a congruence pair, then

$\displaystyle\rho_{(K,\tau)}=\\{(a,b)\in X\times
X\,\mid\,\left(a^{-1}a,b^{-1}b\right)\in\tau,\,ab^{-1}\in K\\}$

is a congruence on $X$. Moreover, $\operatorname{Ker}\rho_{(K,\tau)}=K$,
$\operatorname{tr}\rho_{(K,\tau)}=\tau$, and
$\rho_{(\operatorname{Ker}\rho,\operatorname{tr}\rho)}=\rho$.

######  Theorem 2.3.

Let $X$ be a Clifford semigroup, $\rho$ a congruence on $X$ such that $X/\rho$
is a group and $\mathcal{R}$ a system of representatives of $X/\rho$. If
$\mu:X\to\mathcal{R}$ is a map such that

$\mu\left(xy\right)=\mu\left(x\right)\mu\left(x\right)^{-1}\mu\left(xy\right)$

and $\left(\mu(x),x\right)\in\rho$, for all $x,y\in X$, then the map
$s(x,y)=\left(xy,\mu\left(x\right)^{-1}\mu\left(xy\right)\right)$, for all
$x,y\in X$, is an $\operatorname{E}(X)$-invariant PE solution on $X$.
Conversely, let $s(x,y)=(xy,\theta_{x}(y))$ be an
$\operatorname{E}\left(X\right)$-invariant PE solution on $X$. Then, there
exists a congruence pair $\left(K,\tau\right)$, with $K=\\{x\in
X\,\mid\,\theta_{e}(x)\in\operatorname{E}(X),\,\text{for any}\
e\in\operatorname{E}(X)\\}$ and
$\tau=\operatorname{E}(X)\times\operatorname{E}(X)$, such that

$\displaystyle\rho_{(K,\tau)}=\\{(x,y)\in X\times
X\,\mid\,\left(x^{-1}x,y^{-1}y\right)\in\tau,\,xy^{-1}\in K\\}$

is a congruence on $X$ and $\theta_{e}\left(X\right)$ is a system of
representatives of the group $X/\rho_{\left(K,\tau\right)}$ and
$\left(\theta_{e}\left(x\right),x\right)\in\rho_{\left(K,\tau\right)}$, for
all $e\in\operatorname{E}(S)$ and $x\in X$. Moreover, the map $\theta_{e}$
satisfies

$\theta_{e}\left(xy\right)=\theta_{e}\left(x\right)\theta_{e}\left(x\right)^{-1}\theta_{e}\left(xy\right),$

and $\theta_{x}(y)=\theta_{e}(x)^{-1}\theta_{e}(xy)$, for all $x,y\in X$ and
$e\in\operatorname{E}\left(X\right)$.

######  Proposition 2.4.

Let $X$ be a Clifford semigroup and $s(x,y)=(xy,\theta_{x}(y))$ and
$t(u,v)=(uv,\theta_{u}(v))$ two $\operatorname{E}(X)$-invariant PE solutions
on $X$. Then, $s$ and $t$ are isomorphic if, and only if, there exists an
isomorphism $\psi$ of $X$ such that $\psi\theta_{e}=\eta_{e}\psi$, for every
$e\in\operatorname{E}(X)$.

In other words, $\psi$ sends the system of representatives $\theta_{e}(X)$
into the other one $\eta_{e}\left(\psi(X)\right)$.

As regards the class of $\operatorname{E}(X)$-fixed PE solutions, a
construction has been provided. Indeed, considering that every Clifford
semigroup can be seen as a union of groups $G_{e}$, it is natural to
contemplate whether it is possible to construct a global PE solution from PE
solutions obtained in each of its groups.

######  Proposition 2.5.

Let $X$ be a Clifford semigroup and assume that, for every
$e\in\operatorname{E}(X)$,
$s^{[e]}(x,by)=\left(xy,\,\theta^{[e]}_{x}\left(y\right)\right)$ is a PE
solution on $G_{e}$. Moreover, for all $e,f\in\operatorname{E}(X)$, let
$\epsilon_{e,f}:G_{e}\to G_{f}$ be maps such that
$\epsilon_{e,f}=\varphi_{e,f}$ if $e\geq f$. If the following conditions are
satisfied

$\displaystyle\theta^{[h]}_{\epsilon_{ef,h}(xy)}=\theta^{[h]}_{\epsilon_{e,h}(x)\epsilon_{f,h}(y)}\quad\&\quad\epsilon_{f,h}\theta^{[f]}_{\epsilon_{e,f}(x)}(y)=\theta^{[h]}_{\epsilon_{e,h}(x)}\epsilon_{f,h}(y),$

for all $e,f,h\in\operatorname{E}(X)$ and $x\in G_{e},y\in G_{f}$, set
$\theta_{x}(y):=\theta^{[f]}_{\epsilon_{e,f}(x)}(y),$ for all $x\in G_{e},y\in
G_{f}$, then the map $s(x,y)=(xy,\theta_{x}(y))$ is an
$\operatorname{E}(X)$-fixed PE solution on $X$.

######  Example 6.

Let $X$ be a Clifford semigroup and
$s^{[e]}\left(a,b\right)=\left(ab,\gamma^{[e]}\left(b\right)\right)$ a PE
solution on the group $G_{e}$, with $\gamma^{[e]}$ an idempotent endomorphism
of $G_{e}$, for every $e\in\operatorname{E}(X)$. Then, by choosing maps
$\epsilon_{e,f}:G_{e}\to G_{f}$, for all $e,f\in\operatorname{E}(X)$ such that
$\varphi_{e,f}\gamma^{[e]}=\gamma^{[f]}\varphi_{e,f}$ if $e\geq f$ and
$\epsilon_{e,f}\left(x\right):=f$ otherwise, one has that the map
$s(a,b)=\left(ab,\gamma^{[f]}(b)\right)$, for all $a\in G_{e}$ and $b\in
G_{f}$, is a PE solution on $X$.

Denoted by $K_{e}$ the kernel of each PE solution $s^{[e]}$ on $G_{e}$, i.e.,
the normal subgroup $K_{e}=\\{a\in G_{e}\,\mid\,\theta^{[e]}_{e}(a)=e\\}$ of
$G_{e}$ that we know that exists from 1.3, we have the following result.

######  Proposition 2.6.

Let $X$ be a Clifford semigroup, $\epsilon_{e,f}(e)=f$, for all
$e,f\in\operatorname{E}(X)$ with $e\leq f$, and $s$ be an
$\operatorname{E}(X)$-fixed solution on $X$ constructed as in 2.5. Then,
$K=\\{a\in X\,\mid\,\forall\,e\in\operatorname{E}(X),\,e\leq a,\
\theta_{e}(a)=aa^{-1}\\}=\displaystyle\bigcup_{e\in\operatorname{E}(X)}\,K_{e}$.

However, in [24], it is argued that this cannot be a description. In light of
the previous discussion, the following question arises.

######  Problem 2.

Find all the $\operatorname{E}(X)$-fixed PE solutions on a Clifford semigroup
$X$.

To conclude, we observe that not every PE solution on a Clifford $X$ lies in
the class of $\operatorname{E}(X)$-invariant or $\operatorname{E}(X)$-fixed PE
solutions (see [24, Example 4]). Thus, the next problem arises.

######  Problem 3.

Find and study other classes of PE solutions on a Clifford semigroup $X$.

##  3 Description of the involutive PE solutions

In this section, we recall the description of the involutive PE solutions
obtained by Colazzo, Jespers, and Kubat in [10].

Initially, let $s(x,y)=(xy,\theta_{x}(y))$ be an involutive PE solution on a
semigroup $X$. Then, beyond (P1) and (P2), the following additional equalities

$\displaystyle xy\theta_{x}(y)=x\qquad\&\qquad\theta_{xy}\theta_{x}(y)=y$

hold, for all $x,y\in X$. We give some immediate considerations.

######  Remarks 1.

  1. 1.

If $G$ is a group, then the only bijective PE solution $s_{G}(x,y)=(xy,y)$ on
$G$ is involutive if, and only if, $G$ is an elementary abelian $2-$group.

  2. 2.

If $L$ is a left zero semigroup and $s_{L}$ is an involutive PE solution on
$L$, one has that the map $s=s_{L}\times s_{G}$ is an involutive PE solution
on the left group $X=L\times G$. In addition, [10, Theorem 3.2] shows that the
converse is true, namely, all the involutive PE solutions are of this type. It
is mainly a consequence of [8, Theorem I.1.27].

Therefore, from the considerations above, the problem of describing all the
involutive PE solutions reduces to finding them on a left zero semigroup. It
will turn out that all such solutions are uniquely determined by two
elementary abelian $2-$groups. Thus, in the next, we list some results and
useful notions to give the main theorem.

First, following [10, Section 4], given an involutive PE solution
$s(x,y)=(xy,\theta_{x}(y))$ on a semigroup $X$, one can consider the following
congruence relation

$\displaystyle\forall x,y\in X\qquad x\sim y\iff\theta_{x}=\theta_{y}.$

So, set $\overline{X}:=X/\sim$ and denoted by $\overline{x}$ the $\sim$-class
of $x\in X$, one has that $\overline{X}$ is a left zero semigroup and the map
$\operatorname{Ret}(s)=\left(\overline{xy},\overline{\theta}_{\overline{x}}\left(\overline{y}\right)\right)$
is an involutive PE solution on $\overline{X}$, called the _retract_ of $s$.
Moreover, the PE solution $s$ is called _irretractable_ if
$s=\operatorname{Ret}(s)$. One can show that $\operatorname{Ret}(s)$ is
irretractable.
The following is a complete description of irretractable involutive PE
solutions.

######  Proposition 3.1.

Let $(A,+)$ be an elementary abelian $2$-group. Then, the map
$t_{A}(x,y)=(x,x+y)$ is an irretractable involutive PE solution on $A$.
Conversely, if $s$ is an irretractable involutive PE solution on a semigroup
$X$, then there exists a structure $(X,+)$ of elementary abelian $2$-group on
$X$ such that $s(x,y)=(x,x+y)$, for all $x,y\in X$.

The following problem might be interesting to deal with.

######  Problem 4.

Study a possible retract relation for not necessarily involutive bijective PE
solutions.

######  Lemma 3.2.

[10, Proposition 5.1 - 5.3] Let $(A,+)$ be an elementary abelian $2$-group ,
$t_{A}$ the irretractable involutive PE solution on $A$, $X$ a non-empty set,
and $\sigma:A\to\operatorname{Sym}(X)$ a map. Put $S=X\times A$, the map
$\operatorname{Ext}^{\sigma}_{X}(t_{A}):S\times S\to S\times S$ given by

$\operatorname{Ext}^{\sigma}_{X}(t_{A})((x,a),(y,b))=\left(\left(x,a\right),(\sigma_{a+b}\sigma^{-1}_{b}\left(y\right),a+b\right),$

for all $(x,a),(y,b)\in S$, is an involutive PE solution on $S$, called the
_extension of $t_{A}$ by $X$ and $\sigma$_. In addition, every involutive PE
solution on a left zero semigroup can be so constructed.

######  Theorem 3.3.

[10, Theorem 5.5 - 5.6] Let $s(x,y)=(xy,\theta_{x}(y))$ be an involutive PE
solution on a semigroup $S$. Then, there exist two elementary abelian
$2$-groups $A$ and $G$, and a non-empty set $X$ such that $S$ may be
identified with $X\times A\times G$ and

$\displaystyle s=\operatorname{Ext}^{\sigma}_{X}(t_{A})\times s_{G},$

for some $\sigma:G\to\operatorname{Sym}(X)$, where $t_{A}$ is the
irretractable involutive PE solution defined on $A$ and $s_{G}$ is the
bijective PE solution on $G$. Moreover, $\operatorname{Ret}(s)=t_{A}$.
In addition, all the involutive PE solutions, up to isomorphism, on a non-
empty set $S$ are in bijective correspondence with decompositions of $S$ as a
product of $X\times A\times G$.

Finally, [10, Corollaty 5.7] estimates how many involutive PE solutions there
are. Namely, assume that $S$ is a non-empty set of cardinality $2^{n}(2m+1)$,
with $n,m\geq 0$. Then, there exists exactly $\binom{n+2}{2}$ involutive PE
solutions on $S$.

##  4 Idempotent PE solutions

This section is devoted to recalling essential features of idempotent PE
solutions. In particular, we mention the description of solutions on monoids
having central idempotents, contained in [22].

First, a PE solution $s(x,y)=(xy,\theta_{x}(y))$ on a semigroup $X$ is
idempotent if, and only if, the following equalities

$\displaystyle
xy\theta_{x}(y)=xy\qquad\&\qquad\theta_{xy}\theta_{x}(y)=\theta_{x}(y)$

are satisfied, for all $x,y\in X$. Below we list some properties of this class
of solutions that involve any idempotents of a semigroup. First, following [9,
p. 22], given a semigroup $X$ and $e\in\operatorname{E}(X)$, then $e$ is a
_left identity_ (or _right identity_) if $ex=x$ (or $xe=x$), for every $x\in
X$, and the sets

$\displaystyle eX$ $\displaystyle=\\{x\in X\,\mid\,ex=x\\}\qquad Xe=\\{x\in
X\,\mid\,xe=x\\}$

are respectively the principal right and left ideals of $X$ generated by $e$.

######  Proposition 4.1.

Let $X$ be a semigroup, $e\in\operatorname{E}(X)$, and
$s(x,y)=(xy,\theta_{x}(y))$ an idempotent PE solution on $X$.

  1. 1.

If $x\in Xe$, then

    1. a.

$x\in X\theta_{x}(e)$,

    2. b.

$\forall y\in X\quad\theta_{y}(x)\in X\theta_{x}(e)$,

    3. c.

$\theta_{e}=\theta_{e}\theta_{x}$.

  2. 2.

If $x\in eS$, then

    1. d.

$\theta_{e}(x)\in\operatorname{E}(X)$,

    2. e.

$x\in X\,\theta_{e}(x)$,

    3. f.

$\forall y\in X\quad\theta_{y}(x)\in X\theta_{e}(x)$,

    4. g.

$\theta_{x}$ is an idempotent map.

All the previous properties hold for the identity $1$ of a monoid $M$. In
particular, we can collect the following properties.

######  Proposition 4.2.

If $M$ is a monoid and $s(x,y)=(xy,\theta_{x}(y))$ an idempotent PE solution
on $M$, then the following hold for every $x\in M$:

  1. 1.

$\theta_{1}(x)\in\operatorname{E}(X)$ and, in particular, $\theta_{1}(1)=1$,

  2. 2.

$\theta_{x}=\theta_{\theta_{1}(x)}$,

  3. 3.

$\theta_{1}=\theta_{1}\theta_{x}$,

  4. 4.

$\theta_{x}$ is idempotent.

As a consequence of the definition, if $M$ is a cancellative monoid the unique
idempotent PE solution on $X$ is the map $s(x,y)=(xy,1)$; it belongs to the
class of PE solutions discussed in 1-$2$. On the other hand, even considering
non-cancellative monoids of small orders, one can note that among the PE
solutions, several idempotent ones do not belong to the class of solutions in
1-$2$. The following is an easy example in [23, Appendix B].

######  Example 7.

Let $M=\\{1,a,b\\}$ be the commutative monoid with identity $1$ and
multiplication given by $a^{2}=a,ab=a,b^{2}=1.$ Then, there are 3 idempotent
solutions, up to isomorphism:

  1. 1.

$s(x,y)=(xy,1)$;

  2. 2.

$r(x,y)=(xy,\gamma(y))$, with $\gamma:M\to M$ defined by
$\gamma(1)=\gamma(b)=1$ and $\gamma(a)=a$;

  3. 3.

$t(x,y)=(xy,\theta_{x}(y))$, with $\theta_{x}:M\to M$ the map given by
$\theta_{x}(1)=1,\,\theta_{x}(a)=a$, for every $x\in M$, and
$\theta_{1}(b)=\theta_{b}(b)=1$ and $\theta_{a}(b)=b$.

Note that, in general, the map $\theta_{1}$ is not a homomorphism, unless we
get in special cases. For example, it is enough to consider the cyclic group
$G=\left\langle a\right\rangle$ of order $6$ and $\theta_{1}$ the map given by
$\theta_{1}(1)=\theta_{1}\left(a^{2}\right)=\theta_{1}\left(a^{4}\right)=1$
and
$\theta_{1}(a)=\theta_{1}\left(a^{3}\right)=\theta_{1}\left(a^{5}\right)=a$.

######  Proposition 4.3.

Let $M$ be a monoid having central idempotents and $s(x,y)=(xy,\theta_{x}(y))$
an idempotent PE solution on $M$. Then, the map $\theta_{1}$ is an idempotent
monoid homomorphism from $M$ to $\operatorname{E}(M)$. Moreover, denoted by
$\ker\theta_{1}=\\{(x,y)\in M\times M\,\mid\,\theta_{1}(x)=\theta_{1}(y)\\}$,
they hold

  1. 1.

$\theta_{1}(M)$ is a system of representatives of $M/\ker\theta_{1}$;

  2. 2.

$(\theta_{x}(y),y)\in\ker\theta_{1}$, for all $x,y\in M$.

In light of the previous results, we describe the idempotent PE solutions on
monoids having central idempotents (see [22, Theorem 19]).

######  Theorem 4.4.

Let $M$ be a monoid having central idempotents and $\mu$ an idempotent monoid
homomorphism from $M$ to $\operatorname{E}(M)$ such that, for every $x\in M$,
$\mu(x)=e_{x}$, with $e_{x}\in\operatorname{E}(M)$ a right identity for $x$.
Moreover, let $\\{\theta_{e}:M\to M\,\mid\,e\in\operatorname{Im}\mu\\}$ be a
family of maps such that $\theta_{1}=\mu$, and for all
$e,f\in\operatorname{Im}\mu$,

$\displaystyle\theta_{e}=\theta_{e}\theta_{ef},$
$\displaystyle\theta_{e}(xy)=\theta_{e}(x)\theta_{h}(y),$
$\displaystyle\theta_{ej}\theta_{e}(x)=\theta_{e}(x),$

for all $x,y\in M$, with $h=\mu(ex)$ and $j=\mu(x)$. Then,
$s(x,y)=(xy,\theta_{\mu(x)}(y))$ is an idempotent PE solution on $M$.
Conversely, every idempotent PE solution on $M$ can be so constructed.

######  Problem 5.

Describing idempotent PE solutions on arbitrary monoids.

######  Problem 6.

Describing idempotent PE solutions on other classes of semigroups.

##  5 Commutative and cocommutative PE solutions

Other classes of PE solutions that can be studied are the commutative and the
cocommutative ones. These classes were introduced in [5] analogy to the
commutative and the cocommutative multiplicative unitary operators, i.e.,
vector solutions defined on Hilbert spaces (for more details, see [1,
Definition 2.1]).

######  Definition 5.1.

A PE solution $s:X\times X\to X\times X$ on a semigroup $X$ is said to be
_commutative_ if $s_{12}s_{13}=s_{13}s_{12}$; _cocommutative_ if
$s_{13}s_{23}=s_{23}s_{13}$.

It is a routine computation to check that a PE solution
$s(x,y)=(xy,\theta_{x}(y))$ on a semigroup $X$ is commutative if and only if

$\displaystyle xzy=xyz\qquad\&\qquad\theta_{x}=\theta_{xy},$

for all $x,y,z\in X$. Instead, $s$ is cocommutative if and only if

$\displaystyle
x\theta_{y}(z)=xz\qquad\&\quad\theta_{x}\theta_{y}=\theta_{y}\theta_{x},$

for all $x,y,z\in X$. There exist PE solutions that are both commutative and
cocommutative, such as the maps in $1.$ of 1. Moreover, according to [10,
Corollary 3.4], if $s$ is an involutive PE solution, then $s$ is both
commutative and cocommutative. Besides, if $X$ is a monoid, the unique
cocommutative PE solution is given by $s(x,y)=(xy,y)$. All the commutative PE
solutions on a monoid $X$ are described in [22, Proposition 5]. The same
results can be observed in the case of a commutative, or cocommutative, PE
solutions on a Clifford semigroup $X$ (see [24, Proposition 9]). We summarize
below:

######  Proposition 5.2.

Let $X$ be a monoid (or a Clifford semigroup). Then, a PE solution
$s(x,y)=(xy,\theta_{x}(y))$ on $X$ is

  1. 1.

commutative if and only if $X$ is a commutative monoid (or Clifford semigroup)
and $\theta_{x}=\gamma$, with $\gamma\in\operatorname{End}(X)$,
$\gamma^{2}=\gamma$, for every $x\in X$;

  2. 2.

cocommutative if and only if $\theta_{x}=\operatorname{id}_{X}$, for every
$x\in X$.

######  Problem 7.

Describing commutative or cocommutative PE solutions on other classes of
semigroups.

## Acknowledgment

This work was partially supported by the Dipartimento di Matematica e Fisica
“Ennio De Giorgi” - Università del Salento. The author is a member of GNSAGA
(INdAM) and the non-profit association ADV-AGTA.
The author would like to thank Ivan Kaygorodov for inviting it to hold a
seminar as part of the “ _European Non-Associative Algebra Seminar_ ” and for
giving it the possibility to share its knowledge on this topic. The author
would also like to thank F. Catino, M.M. Miccoli, V. Pérez-Calabuig, and P.
Stefanelli for their collaboration over the years.

## References

  * [1] S. Baaj, G. Skandalis, Unitaires multiplicatifs et dualité pour les produits croisés de C*-algèbres, Ann. Sci. Éc. Norm. Sup. 26 (4) (1993) 425–488.
URL http://eudml.org/doc/82346

  * [2] S. Baaj, G. Skandalis, Transformations pentagonales, C. R. Acad. Sci. Paris Sér. I Math. 327 (7) (1998) 623–628.
URL https://doi.org/10.1016/S0764-4442(99)80090-1

  * [3] R. J. Baxter, Partition function of the eight-vertex lattice model, Ann. Physics 70 (1972) 193–228.
URL https://doi.org/10.1016/0003-4916(72)90335-1

  * [4] L. C. Biedenharn, J. D. Louck, Angular momentum in quantum physics, vol. 8 of Encyclopedia of Mathematics and its Applications, Addison-Wesley Publishing Co., Reading, MA, 1981, theory and application, With a foreword by Peter A. Carruthers.
  * [5] F. Catino, M. Mazzotta, M. M. Miccoli, Set-theoretical solutions of the pentagon equation on groups, Comm. Algebra 48 (1) (2020) 83–92.
URL https://doi.org/10.1080/00927872.2019.1632331

  * [6] F. Catino, M. Mazzotta, P. Stefanelli, Set-theoretical solutions of the Yang–Baxter and pentagon equations on semigroups, Semigroup Forum 100 (3) (2020) 1–26.
URL https://doi.org/10.1007/s00233-020-10100-x

  * [7] A. H. Clifford, Semigroups admitting relative inverses, Ann. of Math. (2) 42 (1941) 1037–1049.
URL https://doi.org/10.2307/1968781

  * [8] A. H. Clifford, G. B. Preston, The algebraic theory of semigroups. Vol. I, Mathematical Surveys, No. 7, American Mathematical Society, Providence, R.I., 1961\.
  * [9] A. H. Clifford, G. B. Preston, The algebraic theory of semigroups. Vol. I, Mathematical Surveys, No. 7, American Mathematical Society, Providence, R.I., 1961\.
  * [10] I. Colazzo, E. Jespers, Ł. Kubat, Set-theoretic solutions of the pentagon equation, Comm. Math. Phys. 380 (2) (2020) 1003–1024.
URL https://doi.org/10.1007/s00220-020-03862-6

  * [11] A. Dimakis, F. Müller-Hoissen, Simplex and Polygon Equations, SIGMA Symmetry Integrability Geom. Methods Appl. 11 (2015) Paper 042, 49.
URL https://doi.org/10.3842/SIGMA.2015.042

  * [12] V. G. Drinfel′ d, Quasi-Hopf algebras, Algebra i Analiz 1 (6) (1989) 114–148.
  * [13] V. G. Drinfel′ d, On some unsolved problems in quantum group theory, in: Quantum groups (Leningrad, 1990), vol. 1510 of Lecture Notes in Math., Springer, Berlin, 1992, pp. 1–8.
URL https://doi.org/10.1007/BFb0101175

  * [14] J. M. Howie, Fundamentals of semigroup theory, vol. 12 of London Mathematical Society Monographs. New Series, The Clarendon Press, Oxford University Press, New York, 1995, Oxford Science Publications.
  * [15] R. Kashaev, Fully noncommutative discrete Liouville equation, in: Infinite analysis 2010–Developments in quantum integrable systems, RIMS Kôkyûroku Bessatsu, B28, Res. Inst. Math. Sci. (RIMS), Kyoto, 2011, pp. 89–98.
  * [16] R. M. Kashaev, S. M. Sergeev, On pentagon, Ten-Term, and Tetrahedron Relations, Comm. Math. Phys. 195 (2) (1998) 309–319.
URL https://doi.org/10.1007/s002200050391

  * [17] P. Kassotakis, Matrix factorizations and pentagon maps, Proc. R. Soc. A. 479 (2023).
URL http://doi.org/10.1098/rspa.2023.0276

  * [18] K. Kawamura, Pentagon equation arising from state equations of a C*-Bialgebra, Lett. Math. Phys. 93 (3) (2010) 229–241.
URL https://doi.org/10.1007/s11005-010-0413-5

  * [19] M. Kunze, Zappa products, Acta Math. Hungar. 41 (3-4) (1983) 225–239.
URL https://doi.org/10.1007/BF01961311

  * [20] M. V. Lawson, Inverse semigroups, World Scientific Publishing Co., Inc., River Edge, NJ, 1998, the theory of partial symmetries.
URL https://doi.org/10.1142/9789812816689

  * [21] J.-M. Maillet, On pentagon and tetrahedron equations, Algebra i Analiz 6 (2) (1994) 206–214.
  * [22] M. Mazzotta, Idempotent set-theoretical solutions of the pentagon equation, Boll. Unione. Mat. Ital. (2023), in press.
URL https://doi.org/10.1007/s40574-023-00382-8

  * [23] M. Mazzotta, Recent developments of the set-theoretical solutions to the pentagon equation, Ph.D. thesis (2020) Università del Salento.
URL http://dx.doi.org/10.13140/RG.2.2.16416.40969

  * [24] M. Mazzotta, V. Pérez-Calabuig, P. Stefanelli, Set-theoretical solutions of the pentagon equation on clifford semigroups, arXiv preprint: arXiv:2108.02627.
URL https://arxiv.org/abs/https://arxiv.org/abs/2301.09944

  * [25] G. Militaru, The Hopf modules category and the Hopf equation, Comm. Algebra 26 (10) (1998) 3071–3097.
URL https://doi.org/10.1080/00927879808826329

  * [26] G. Militaru, Heisenberg Double, Pentagon Equation, Structure and Classification of Finite-Dimensional Hopf Algebras, J. London Math. Soc. (2) 69 (1) (2004) 44–64.
URL https://doi.org/10.1112/S0024610703004897

  * [27] F. Müller-Hoissen, On the structure of set-theoretic polygon equations, arXiv preprint: arXiv:2305.17974.
URL https://arxiv.org/abs/https://arxiv.org/abs/2305.17974

  * [28] G. Moore, N. Seiberg, Classical and quantum conformal field theory, Comm. Math. Phys. 123 (2) (1989) 177–254.
URL http://projecteuclid.org/euclid.cmp/1104178762

  * [29] M. Petrich, Inverse semigroups, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1984, a Wiley-Interscience Publication.
  * [30] M. Takesaki, Duality and von neumann algebras, Lecture Notes in Math. 247 (1972) 665–786.
  * [31] S. L. Woronowicz, From multiplicative unitaries to quantum groups, Int. J. Math. 7 (01) (1996) 129–149.
URL https://doi.org/10.1142/S0129167X96000086

  * [32] C. N. Yang, Some exact results for the many-body problem in one dimension with repulsive delta-function interaction, Phys. Rev. Lett. 19 (1967) 1312–1315.
URL https://doi.org/10.1103/PhysRevLett.19.1312

  * [33] S. Zakrzewski, Poisson Lie groups and pentagonal transformations, Lett. Math. Phys. 24 (1) (1992) 13–19.
URL https://doi.org/10.1007/BF00429998

  * [34] A. B. Zamolodchikov, Tetrahedra equations and integrable systems in three-dimensional space, Zh. Èksper. Teoret. Fiz. 79 (2) (1980) 641–664.


m\frac{\varepsilon^{\gamma}}{(2-m)^{i}}+f(w^{j-i}(v))\cdot
m\frac{\varepsilon^{\gamma}}{(2-m)^{i}},$

where we have used that for $i=0$ the difference
$\nu_{k^{\star}+i-1}-\nu_{k^{\star}+i}$ equals
$\varepsilon^{\beta}/m^{k^{\star}}$, and that $1/m^{k^{\star}}$ is bounded
above by $m\varepsilon^{\gamma}/\varepsilon^{\beta}$ (see eq. 20). For $i>0$
the bound comes from eq. 21. Next, by the fact that $(2-m)<1$, that $f$ has
bounded variation and eq. 22 we have

$\sum_{i=0}^{j-1}\frac{|\chi_{j,i}(v)|}{(2-m)^{i}}\leq\sum_{i=0}^{j-1}\frac{|\chi_{j,i}(v)|}{(2-m)^{j-1}}\leq
V_{0}^{\overline{v}}(f)\frac{1}{(2-m)}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1\right).$

Hence,

$(A)\geq\frac{1}{m\varepsilon^{\gamma}}\int_{\nu_{k^{\star}+j-1}}^{\nu_{k^{\star}-1}}f(v)dv-
V_{0}^{\overline{v}}(f)\frac{1}{(2-m)}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1\right).$

Now, for $(B)$ we have the following that since
$v\in[\nu_{k^{\star}+j},\nu_{k^{\star}+j-1}]$ then
$w^{k^{\star}-i+j}(v)\in[\nu_{i},\nu_{i-1}]$. So we can always find
$\xi\in[\nu_{i},\nu_{i-1}]$ such that

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

In turn, using that $m>1$ and that $f$ has bounded variation, we have that

$(B)\geq\frac{1}{\varepsilon^{\beta}}\int_{\nu_{k^{\star}-1}}^{\overline{v}}f(v)dv-
V_{0}^{\overline{v}}(f).$

With this, we obtain a lower bound for $\lambda(w(v))$. Recall from eq. 20
that $\varepsilon^{\beta-\gamma}\geq
m^{k^{\star}}\geq\varepsilon^{\beta-\gamma}/m$ then

$\displaystyle\frac{\lambda(w(v))}{(2-m)^{j-1}}$
$\displaystyle\geq\frac{1}{m\varepsilon^{\gamma}}\int_{\nu_{k^{\star}+j-1}}^{\nu_{k^{\star}-1}}f(v)dv-
V_{0}^{\overline{v}}(f)\frac{1}{(2-m)}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1\right)+\frac{m^{k^{\star}}}{\varepsilon^{\beta}}\int_{\nu_{k^{\star}-1}}^{\overline{v}}f(v)dv-m^{k^{\star}}V_{0}^{\overline{v}}(f)$
$\displaystyle\geq\frac{1}{m\varepsilon^{\gamma}}\int_{\nu_{k^{\star}+j-1}}^{\nu_{k^{\star}-1}}f(v)dv-
V_{0}^{\overline{v}}(f)\frac{1}{(2-m)}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1\right)+\frac{1}{m\varepsilon^{\gamma}}\int_{\nu_{k^{\star}-1}}^{\overline{v}}f(v)dv-\varepsilon^{\beta-\gamma}V_{0}^{\overline{v}}(f)$
$\displaystyle=\frac{1}{m\varepsilon^{\gamma}}\bar{F}(\nu_{k^{\star}+j-1})-V_{0}^{\overline{v}}(f)\frac{1}{(2-m)}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1-(2-m)\varepsilon^{\beta-\gamma}\right).$

Note that

$\displaystyle\bar{F}(\nu_{k^{\star}+j-1})$
$\displaystyle=\bar{F}(v)-\int_{v}^{\nu_{k^{\star}+j-1}}f(s)ds$
$\displaystyle\geq\bar{F}(v)-\bar{f}(\nu_{k^{\star}+j-1}-\nu_{k^{\star}+j})$
$\displaystyle\geq\bar{F}(v)-\bar{f}(\nu_{k^{\star}+j-1}-v)$
$\displaystyle\geq\bar{F}(v)-\frac{\varepsilon^{\gamma}}{(2-m)^{j}}$
$\displaystyle\geq\bar{F}(v)-\varepsilon^{\gamma}\frac{1}{(2-m)^{2}}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1\right),$

where in the last inequality we have used eq. 22. In turn,

$\displaystyle\Delta(v)$ $\displaystyle\leq
vf(v)-(2-m)^{2}\varepsilon^{\gamma}\left(\frac{1}{m\varepsilon^{\gamma}}\left\\{\bar{F}(v)-\varepsilon^{\gamma}\frac{1}{(2-m)^{2}}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1\right)\right\\}\right.$
$\displaystyle\left.-V_{0}^{\overline{v}}(f)\frac{1}{(2-m)}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1-(2-m)\varepsilon^{\beta-\gamma}\right)\right)$
$\displaystyle=vf(v)-(2-m)^{2}\left(\frac{1}{m}\left\\{\bar{F}(v)-\varepsilon^{\gamma}\frac{1}{(2-m)^{2}}\left(\frac{(m-1)p^{\star}}{\varepsilon^{\gamma}}+1\right)\right\\}\right.$
$\displaystyle\left.-V_{0}^{\overline{v}}(f)\frac{1}{(2-m)}\left((m-1)p^{\star}+\varepsilon^{\gamma}-(2-m)\varepsilon^{\beta}\right)\right)$
$\displaystyle=vf(v)-\frac{(2-m)^{2}}{m}\bar{F}(v)+\frac{1}{m}\left((m-1)p^{\star}+\varepsilon^{\gamma}\right)+V_{0}^{\overline{v}}(f)(2-m)\left((m-1)p^{\star}+\varepsilon^{\gamma}-(2-m)\varepsilon^{\beta}\right)$
$\displaystyle\leq
vf(v)-\bar{F}(v)-\left(\frac{(2-m)^{2}}{m}-1\right)+\left(1+V_{0}^{\overline{v}}(f)\right)\left((m-1)p^{\star}+\varepsilon^{\gamma}\right)$
$\displaystyle\leq
vf(v)-\bar{F}(v)+\left(1-\frac{(2-m)^{2}}{m}\right)+\left(1+V_{0}^{\overline{v}}(f)\right)\left((m-1)p^{\star}+\varepsilon^{\beta}\right),$

we note that the third term above is positive for $\varepsilon>0$ small enough
and of order $\varepsilon^{\beta}$. The fourth term is also of oder
$\varepsilon^{\beta}$ because $m-1$ is of that order. In conclusion, we proved
that the following holds almost everywhere in $[0,p^{\star}]$

$\Delta(v)\leq-\dot{R}(v)+C\cdot\varepsilon^{\beta},$

for some positive constant $C$. From the last assumption in the statement of
the theorem, we can deduce that for $\varepsilon>0$ small enough
$-\dot{R}(v)+C\cdot\varepsilon^{\beta}<0$ for all $v\leq p^{\star}+\ell$. From
Definition 2.1, for $v\in(p^{\star}-\ell,p^{\star})$ we have that
$-\dot{R}(v)+C\cdot\varepsilon^{\beta}<0$ if

$C\cdot\varepsilon^{\beta}\leq\kappa_{L}\alpha(p^{\star}-v)^{\alpha-1}\Leftrightarrow
v\leq
p^{\star}-\left(\frac{C\cdot\varepsilon^{\beta}}{\kappa_{L}\alpha}\right)^{\frac{1}{\alpha-1}}\triangleq
p_{L}.$

Hence, $\varepsilon>0$ small enough we have

$\int_{0}^{p^{\star}}\Delta^{+}(v)dv=\int_{p_{L}}^{p^{\star}}\Delta^{+}(v)dv\leq\int_{p_{L}}^{p^{\star}}\left(-\dot{R}(v)+C\cdot\varepsilon^{\beta}\right)^{+}dv\leq
C\varepsilon^{\beta}\left(\frac{C\cdot\varepsilon^{\beta}}{\kappa_{L}\alpha}\right)^{\frac{1}{\alpha-1}}=\mathcal{O}\left(\varepsilon^{\beta+\frac{\beta}{\alpha-1}}\right),$

where we have used that $-\dot{R}(v)\leq 0$ for $v\leq p^{\star}$ (this is
implied by the assumptions in the theorem). To conclude note that
$\beta+\frac{\beta}{\alpha-1}=\frac{\alpha}{2\alpha-1}$ if we take
$\beta=(\alpha-1)/(2\alpha-1)$. This gives us the right order and concludes
the proof.

##  8 Proofs for Section 4

###### Proof 8.1

Proof of Theorem 4.1 We first establish that the optimal mechanism in
$m_{\textup{{d}}}\in\mathcal{M}_{\texttt{d}}(\varepsilon)$ is hard/soft
mechanism. We then analyze the quantity
$\Pi(m_{\textup{{d}}})\>-\>\Pi^{\star}(\mathcal{M}(0))\>$, and prove parts i.)
and ii.).

Let $m_{\textup{{d}}}=(x_{\textup{{d}}},t_{\textup{{d}}})$ be the optimal
deterministic mechanism. We show that $m_{\textup{{d}}}$ is a hard/soft floor
mechanism, that is,

$\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}]\\},$

for some appropriately chosen $(p,s)$.

Without loss of generality assume that $x_{\textup{{d}}}(\cdot)$ is right-
continuous (this is possible because $F$ is absolutely continuous). Define

$r\triangleq\inf\\{v\in[0,\overline{v}]:x_{\textup{{d}}}(v)=1\\}.$

Note that $r<\infty$. Indeed, if this is not true then
$x_{\textup{{d}}}(\cdot)\equiv 0$ which, together with (IR), implies that
$t_{\textup{{d}}}(v)\leq 0$ for all $v\in[0,\overline{v}]$. This gives
$\Pi(m_{\textup{{d}}})\leq 0$ which is suboptimal because the associated
mechanism to the posted price $p^{\star}$ is feasible in
$\mathcal{M}_{\texttt{d}}(\varepsilon)$ and $\Pi^{\star}(\mathcal{M}(0))>0$.
Moreover, note that because $x_{\textup{{d}}}(\cdot)$ is right-continuous we
have that $x_{\textup{{d}}}(r)=1$, and $x_{\textup{{d}}}(v)=0$ for all $v<r$.

Next we show that

$t_{\textup{{d}}}(v)\leq\begin{dcases*}0&\mbox{if } $v\in[0,r);$\\\ v\cdot
x_{\textup{{d}}}(v)&\mbox{if } $v\in[r,r+\varepsilon);$\\\
r+\varepsilon&\mbox{if } $v\in[r+\varepsilon,\overline{v}].$\end{dcases*}$
(23)

For $v<r$, (IR) and the definition of $r$ imply that $t_{\textup{{d}}}(v)\leq
v\cdot x_{\textup{{d}}}(v)=0$. For $v\in[r,r+\varepsilon)$ the inequality
follows from (IR). For $v\in[r+\varepsilon,\overline{v}]$,
($\mbox{IC}_{\varepsilon}$) yields

$t_{\textup{{d}}}(v)\leq
t_{\textup{{d}}}(r)+v\cdot(x_{\textup{{d}}}(v)-x_{\textup{{d}}}(r))+\varepsilon\leq
r+\varepsilon,$

where the second inequality follows from $t_{\textup{{d}}}(r)\leq r\cdot
x_{\textup{{d}}}(r)=r$ and $(x_{\textup{{d}}}(v)-x_{\textup{{d}}}(r))\leq 0$.

Since $(x_{\textup{{d}}},t_{\textup{{d}}})$ is optimal, all the inequalities
in eq. 23 must bind. Moreover, we must have $x_{\textup{{d}}}(v)=1$ for
$v\in[r,r+\varepsilon)$. This means that $m_{\textup{{d}}}$ is a hard/soft
floor mechanism with $p=r$ and $s=r+\varepsilon$. Note that this mechanism is
also feasible. Indeed, the mechanism satisfies (IR) because the transfers are
never larger than buyers valuations. It also satisfies
($\mbox{IC}_{\varepsilon}$). A best reporting function is

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

With this, we can see that $u(v)=(v-r)\mathbf{1}\\{v\in[r,\overline{v}]\\}$.
Using the characterization in eq. 6 of ($\mbox{IC}_{\varepsilon}$) and the
definition of $m_{\textup{{d}}}$, it is not hard to check that
$m_{\textup{{d}}}$ verifies ($\mbox{IC}_{\varepsilon}$). This shows that among
the deterministic mechanisms, the hard/soft floor mechanisms are optimal. In
turn, the optimal solution can be find by optimizing over $r$.

Next we analyze the quantity
$\Pi(m_{\textup{{d}}})\>-\>\Pi^{\star}(\mathcal{M}(0))\>$. We use
$m_{\textup{{d}}}(r)$ instead of $m_{\textup{{d}}}$ to highlight the
dependence on $r$. We have

$\Pi(m_{\textup{{d}}}(r))=\int_{r}^{r+\varepsilon}vf(v)dv+(r+\varepsilon)\cdot\overline{F}(r+\varepsilon)=r\cdot\overline{F}(r)+\int_{r}^{r+\varepsilon}\overline{F}(v)dv,$

where in the second inequality we used integration by parts. Hence,

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

where in the first inequality we used that $\overline{F}(v)\leq 1$ and in the
second we used that
$\Pi^{\star}(\mathcal{M}(0))=p^{\star}\cdot\overline{F}(p^{\star})$. This
shows that $\Pi(m_{\textup{{d}}})\>-\>\Pi^{\star}(\mathcal{M}(0))\>$ is
$\mathcal{O}(\varepsilon)$.

We next show a lower bound on performance. By section 2,
$p^{\star}\in(0,\overline{v})$. Hence we can always find $\varepsilon_{0}>0$
such that for all $\varepsilon\leq\varepsilon_{0}$,
$p^{\star}+\varepsilon\in(0,\overline{v})$. Now, by the mean value theorem, we
have that
$\overline{F}(p^{\star}+\varepsilon)-\overline{F}(p^{\star})=-f(\xi(\varepsilon))\cdot\varepsilon$
for $\xi(\varepsilon)\in[p^{\star},p^{\star}+\varepsilon]$. Therefore,

$\displaystyle\Pi^{\star}(\mathcal{M}_{\texttt{d}}(\varepsilon))$
$\displaystyle\geq\Pi(m_{\textup{{d}}}(p^{\star}))$
$\displaystyle=\Pi^{\star}(\mathcal{M}(0))+\int_{p^{\star}}^{p^{\star}+\varepsilon}\overline{F}(v)dv$
$\displaystyle=\Pi^{\star}(\mathcal{M}(0))+\overline{F}(p^{\star}+\varepsilon)\cdot\varepsilon$
$\displaystyle\geq\Pi^{\star}(\mathcal{M}(0))+\overline{F}(p^{\star})\cdot\varepsilon-\overline{f}\cdot\varepsilon^{2},$

where in the last inequality we used that $f(v)\leq\overline{f}$ for all
$v\in[0,\overline{v}]$ (Section 2). This completes the proof of the theorem.

##  9 Proofs for Section 5

###### Proof 9.1

Proof of Proposition 5.2 For ease of notation we use $(x,t)$ in lieu of
$(x_{\textup{{pd}}},t_{\textup{{pd}}})$. Let
$u(v)=\max_{w\in\mathcal{S}}\\{v\cdot x(w)-t(w)\\}$, we want to show that

$u(v)=v\cdot x({v^{\star}}(v))-t({v^{\star}}(v)).$

First observe that the generalize inverse of ${v^{\star}}(\cdot)$, $w(\cdot)$,
is

$w(v)=\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*}$

In turn, we have that $w(v)\geq v$ for all $v\in[0,p^{\star}+\delta]$. Let us
analyze two cases, $v\leq p^{\star}-\delta$ (case 1) and $v\geq
p^{\star}-\delta$ (case 2).

Case 1.  Suppose that $v\leq p^{\star}-\delta$. Define the function

$g(v^{\prime})=v\cdot x(v^{\prime})-t(v^{\prime}),\quad
v^{\prime}\in[0,\overline{v}],$

We need to show that $g({v^{\star}}(v))=g(0)\geq g(v^{\prime})$ for all
$v^{\prime}\in[0,\overline{v}]$. To prove this, we argue that $g(\cdot)$ is
non-increasing. If $v^{\prime}\in[0,p^{\star}-\delta]$ we have

$g(v^{\prime})=(v-v^{\prime})\cdot
x(v^{\prime}),\quad\text{and}\quad\dot{g}(v^{\prime})=-x(v^{\prime})+(v-v^{\prime})\cdot\dot{x}(v^{\prime}).$

In $[0,p^{\star}-\delta]$ the allocation $x(\cdot)$ satisfies the differential
equation $(w(v^{\prime})-v^{\prime})\dot{x}(v^{\prime})=x(v^{\prime})$. In
turn,

$\dot{g}(v^{\prime})=-(w(v^{\prime})-v^{\prime})\dot{x}(v^{\prime})+(v-v^{\prime})\cdot\dot{x}(v^{\prime})=(v-w(v^{\prime}))\cdot\dot{x}(v^{\prime}).$

Note that $w(\cdot)$ is non-decreasing and $v\leq p^{\star}-\delta=w(0)$ hence
we have that $v\leq w(v^{\prime})$ for all
$v^{\prime}\in[0,p^{\star}-\delta]$. Moreover, $x$ is non-decreasing (see
Lemma 9.5 in Section 9.1) which implies that $\dot{g}(v^{\prime})\leq 0$ for
all $v^{\prime}\in[0,p^{\star}-\delta]$. We have thus verified that $g$ is
decreasing in $[0,p^{\star}-\delta]$.

If $v^{\prime}\in[p^{\star}-\delta,p^{\star}+\delta]$ we have that

$g(v^{\prime})=(v-v^{\prime})\cdot
x(v^{\prime})+\int_{0}^{v^{\prime}}x({v^{\star}}(s))ds-\epsilon,\quad\text{and}\quad\dot{g}(v^{\prime})=-x(v^{\prime})+(v-v^{\prime})\cdot\dot{x}(v^{\prime})+x({v^{\star}}(v^{\prime})).$

In this interval the allocation $x$ is a solution to the delayed differential
equation
$x(v^{\prime})+(v^{\prime}-w(v^{\prime}))\dot{x}(v^{\prime})=x({v^{\star}}(v^{\prime}))$.
As before this implies that
$\dot{g}(v^{\prime})=(v-w(v^{\prime}))\cdot\dot{x}(v^{\prime}).$ Note that
because $x$ is non-decreasing (see Lemma 9.5 in Section 9.1) we have that
$\dot{x}(v^{\prime})\geq 0$, and because $w(v^{\prime})\geq v^{\prime}$ and
$v^{\prime}\geq p^{\star}-\delta\geq v$, we can conclude that
$\dot{g}(v^{\prime})\leq 0$. We have thus verified that $g$ is non-increasing
in $[p^{\star}-\delta,p^{\star}+\delta]$.

If $v^{\prime}\in[p^{\star}+\delta,\overline{v}]$ we have

$g(v^{\prime})=(v-v^{\prime})+\int_{0}^{v^{\prime}}x({v^{\star}}(s))ds-\epsilon,\quad\text{and}\quad\dot{g}(v^{\prime})=-1+x({v^{\star}}(v^{\prime})),$

where to derive $\dot{g}(v^{\prime})$ we have used that $x(v^{\prime})=1$ for
all $v^{\prime}\in[p^{\star}+\delta,\overline{v}]$. Note that since
${v^{\star}}(\cdot)$ is non-decreasing, we have that
${v^{\star}}(v^{\prime})\leq p^{\star}+\delta$ for all $v^{\prime}$. In turn,
because $x(\cdot)$ is non-decreasing (see Lemma 9.5 in Section 9.1) we
conclude that $x({v^{\star}}(v^{\prime}))\leq x(p^{\star}+\delta)=1$. That is,
$\dot{g}(v^{\prime})\leq 0$, equivalently, $g$ is decreasing in
$[p^{\star}+\delta,\overline{v}]$.

Finally, since $x$ and $t$ are continuous functions, $g$ is also a continuous
function. This, together with $g$ being decreasing in each of the intervals
$[0,p^{\star}-\delta]$, $[p^{\star}-\delta,p^{\star}+\delta]$ and
$[p^{\star}+\delta,\overline{v}]$, implies that $g$ is decreasing in
$[0,\overline{v}]$, as desired.

Case 2. $v\geq p^{\star}-\delta$: In the previous case we already computed the
derivative of $g(\cdot)$ at different intervals. In particular, we have

$\dot{g}(v^{\prime})=\begin{dcases*}(v-w(v^{\prime}))\cdot\dot{x}(v^{\prime})&\mbox{if
} $v^{\prime}\leq p^{\star}+\delta$\\\ -1+x({v^{\star}}(v^{\prime}))&\mbox{if
} $v^{\prime}\geq p^{\star}+\delta$\end{dcases*}$

Note that the sign of the derivative at $v^{\prime}\in[0,p^{\star}+\delta]$
depends on how $v$ compares to $w(v^{\prime})$. Observe that $w(\cdot)$ is a
non-decreasing continuous function taking values in
$[p^{\star}-\delta,p^{\star}+\delta+\mu]$. Therefore, for any
$v\in[p^{\star}-\delta,p^{\star}+\delta+\mu]$ we have that if
$v^{\prime}<{v^{\star}}(v)$ then $w(v^{\prime})\leq v$, and if
$v^{\prime}>{v^{\star}}(v)$ then $w(v^{\prime})\geq v$. Moreover, as we argued
before $x({v^{\star}}(v^{\prime}))\leq 1$. That is, for any
$v\in[p^{\star}-\delta,p^{\star}+\delta+\mu]$ the function $g(v^{\prime})$ is
first increasing for $v^{\prime}<{v^{\star}}(v)$ and then decreasing for
$v^{\prime}>{v^{\star}}(v)$. Hence, for any
$v\in[p^{\star}-\delta,p^{\star}+\delta+\mu]$ the maximum of $g$ is attained
at ${v^{\star}}(v)$.

If $v\geq p^{\star}+\delta+\mu$ then ${v^{\star}}(v)=p^{\star}+\delta$, and
for any $v^{\prime}\leq p^{\star}+\delta$ we have that $w(v^{\prime})\leq
p^{\star}+\delta+\mu\leq v$. In turn, in this case $g(v^{\prime})$ is
increasing for all $v^{\prime}\leq p^{\star}+\delta$. Since we already saw
that $g$ is decreasing for $v^{\prime}\geq p^{\star}+\delta$ we conclude that
${v^{\star}}(v)$ attains the maximum of $g$. Thus the maximum is still
achieved at ${v^{\star}}(v)$, as desired.

###### Proof 9.2

Proof of Proposition 5.3 Consider the change of variables

$y_{\textup{{pd}}}(v)=x_{\textup{{pd}}}(v)\cdot\frac{\mu}{\varepsilon}\cdot\exp\left(-\frac{v-p^{\star}+\delta+\mu}{\mu}\right).$

To prove the statement, we solve the resulting ordinary and delayed
differential equations for $y_{\textup{{pd}}}(v)$. Under this change of
variables, (ODE) for $v\in[0,p^{\star}-\delta-\mu]$ becomes

$\dot{y}_{\textup{{pd}}}(v)=y_{\textup{{pd}}}(v)\left(\frac{1}{w(v)-v}-\frac{1}{\mu}\right),\quad
y_{\textup{{pd}}}(0)=\frac{\mu}{p^{\star}-\delta}\cdot
e^{\frac{p^{\star}-\delta-\mu}{\mu}},\quad v\in[0,p^{\star}-\delta-\mu].$

This has solution,

$y_{\textup{{pd}}}(v)=\frac{\mu}{p^{\star}-\delta-v}\exp\left(-\frac{v-p^{\star}+\delta+\mu}{\mu}\right).$

For $v\in[p^{\star}-\delta-\mu,p^{\star}-\delta]$ (ODE) becomes
$\dot{y}_{\textup{{pd}}}(v)=0$ with
$y_{\textup{{pd}}}(p^{\star}-\delta-\mu)=1$. Hence, in this interval
$y_{\textup{{pd}}}(v)=1$.

(DDE) becomes

$\dot{y}_{\textup{{pd}}}(v)+\frac{e^{-1}}{\mu}\cdot
y_{\textup{{pd}}}(v-\mu)=0,\quad v\in[p^{\star}-\delta,p^{\star}+\delta];\quad
y_{\textup{{pd}}}(v)=1,\>\>\forall
v\in[p^{\star}-\delta-\mu,p^{\star}-\delta].$ (24)

The delayed differential equation in (24) is a linear delayed differential
equation with constants coefficients. Its solution is unique and it can be
found in Norkin et al. (1973) p.8 and is given by

$y_{\textup{{pd}}}(v)=\sum_{j=0}^{\left\lfloor\frac{v-p^{\star}+\delta}{\mu}\right\rfloor+1}\frac{(-1)^{j}e^{-j}}{j!}\left(\frac{v-p^{\star}+\delta}{\mu}+1-j\right)^{j},\quad
v\in[p^{\star}-\delta,p^{\star}+\delta].$

This solution can also be verified by an inductive argument. In summary, we
have that

$y_{\textup{{pd}}}(v)=\begin{dcases*}\frac{\mu}{p^{\star}-\delta-v}\exp\left(-\frac{v-p^{\star}+\delta+\mu}{\mu}\right)&\mbox{if
} $v\leq p^{\star}-\delta-\mu;$\\\ 1&\mbox{if }
$v\in[p^{\star}-\delta-\mu,p^{\star}-\delta];$\\\
\sum_{j=0}^{\left\lfloor\frac{v-p^{\star}+\delta}{\mu}\right\rfloor+1}\frac{(-1)^{j}e^{-j}}{j!}\left(\frac{v-p^{\star}+\delta}{\mu}+1-j\right)^{j}&\mbox{if
} $v\in[p^{\star}-\delta,p^{\star}+\delta].$\end{dcases*}$ (25)

Finally, we argue that $x_{\textup{{pd}}}$ is strictly positive and monotone
non-decreasing in $[0,p^{\star}+\delta]$. Lemma 9.5 in Section 9.1 establishes
that $x_{\textup{{pd}}}$ is non-decreasing in $[0,p^{\star}+\delta]$. Since
$x_{\textup{{pd}}}(0)=\varepsilon/(p^{\star}-\delta)>0$ and
$x_{\textup{{pd}}}(\cdot)$ is non-decreasing, we deduce that
$x_{\textup{{pd}}}(\cdot)$ is strictly positive.

###### Proof 9.3

Proof of Proposition 5.4 First fix $\varepsilon>0$ and $\mu>\varepsilon\cdot
e$. To show that $\lim_{v\uparrow p^{\star}+\delta}x_{\textup{{pd}}}(v)=1$ it
suffices to prove $x_{\textup{{pd}}}(p^{\star}+\delta)$ can be equal to one.
Given the change of variables from $x_{\textup{{pd}}}(v)$ to
$y_{\textup{{pd}}}(v)$ (see the proof of Proposition 5.3), the latter
condition is equivalent to:

$y_{\textup{{pd}}}(p^{\star}+\delta)=\frac{1}{\varepsilon}\frac{\mu}{e}e^{\frac{-2\delta}{\mu}}.$
(26)

Note that from eq. 25, we have that

$y_{\textup{{pd}}}(p^{\star}+\delta)=\sum_{j=0}^{\left\lfloor\frac{2\delta}{\mu}\right\rfloor+1}\frac{(-1)^{j}e^{-j}}{j!}\left(\frac{2\delta}{\mu}+1-j\right)^{j}\triangleq\Gamma\left(\frac{2\delta}{\mu}\right).$

Then we can cast (26) as

$\Gamma\left(\frac{2\delta}{\mu}\right)=\frac{\mu}{e\varepsilon}e^{\frac{-2\delta}{\mu}}.$
(27)

For fixed $\varepsilon$ and $\mu$ we show that we can find a solution
$\delta(\mu,\varepsilon)$ to Equation 27. Let $z=\frac{2\delta}{\mu}$, then we
need to find $z$ that solves $\Gamma(z)=\frac{\mu}{e\varepsilon}e^{-z}$ or
equivalently $L(z)=0$ with $L(z)=\Gamma(z)-\frac{\mu}{e\varepsilon}e^{-z}$.
Note that for $z=0$, we have $L(0)=1-\frac{\mu}{e\varepsilon}<0$ because
$\Gamma(0)=1$ and, by assumption, $\frac{\mu}{e\varepsilon}>1$. Additionally,
from Lemma 9.7 we have that
$L(z)\geq\left(2e^{-1}z-\frac{\mu}{e\varepsilon}\right)e^{-z}$ and, thus,
$L(z)>0$ for all $z$ large enough. Finally, we have that $L(z)$ is continuous
because $\Gamma(z)=y_{\textup{{pd}}}(\mu z+p^{\star}-\delta)$ and
$y_{\textup{{pd}}}(v)$ is the continuous solution of a delayed differential.
The intermediate value theorem implies that we can always solve Equation 27.
From the bounds Lemma 9.7 we deduce that a solution
$\delta=\delta(\mu,\varepsilon)$ to Equation 26 must satisfy

$\frac{\mu}{e\varepsilon}e^{\frac{-2\delta}{\mu}}=\Gamma\left(\frac{2\delta}{\mu}\right)>2\left(\frac{2\delta}{\mu}\right)e^{-1}e^{-\frac{2\delta}{\mu}}\Leftrightarrow\frac{\mu^{2}}{4\varepsilon}>\delta,$

and, also,

$e^{\frac{2\delta}{\mu}+1}\Gamma\left(\frac{2\delta}{\mu}\right)\leq
2\left(\frac{2\delta}{\mu}+2\right)\Leftrightarrow
e^{\frac{2\delta}{\mu}+1}\left(\frac{\mu}{e\varepsilon}e^{\frac{-2\delta}{\mu}}\right)\leq
2\left(\frac{2\delta}{\mu}+2\right)\Leftrightarrow\frac{\mu}{4\varepsilon}\leq\frac{\delta}{\mu}+1.$

This shows that
$\delta(\mu,\varepsilon)\in\left[\frac{\mu^{2}}{4\varepsilon}-\mu,\frac{\mu^{2}}{4\varepsilon}\right]$.

Next, we show that $m_{\textup{{pd}}}\in\mathcal{M}(\varepsilon)$. First, note
by assumption ${v^{\star}}$ is well defined. Now from Proposition 5.2 and
since $\delta(\mu(\varepsilon),\varepsilon)$ solves (26), we know that
${v^{\star}}(\cdot)$ is a best reporting function for $m_{\textup{{pd}}}$.
Given this property, we can verify that $m_{\textup{{pd}}}$ is feasible. 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 eq. 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. This concludes the proof.

###### Proof 9.4

Proof of Theorem 5.1 We rely on the characterization for
$\Pi(m_{\textup{{pd}}})$ provided in Proposition 5.5. We analyze the order of
$\Pi(m_{\textup{{pd}}})$. We have

$\displaystyle\Pi(m_{\textup{{pd}}})$
$\displaystyle=\int_{0}^{p^{\star}+\delta}x(v)\left(v-\frac{\overline{F}(v+\mu)}{f(v)}\dot{w}(v)\right)f(v)dv+R(p^{\star}+\delta)+\int_{p^{\star}+\delta}^{p^{\star}+\delta+\mu}\overline{F}(v)dv$
$\displaystyle=\int_{0}^{p^{\star}-\delta-\mu}x(v)\left(v-\frac{\overline{F}(v+\mu)}{f(v)}\dot{w}(v)\right)f(v)dv+\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}x(v)\left(v-\frac{\overline{F}(v+\mu)}{f(v)}\dot{w}(v)\right)f(v)dv$
$\displaystyle+R(p^{\star}+\delta)+\int_{p^{\star}+\delta}^{p^{\star}+\delta+\mu}\overline{F}(v)dv$
$\displaystyle=\int_{0}^{p^{\star}-\delta-\mu}x(v)vf(v)dv+\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}x(v)\left(v-\frac{\overline{F}(v+\mu)}{f(v)}\right)f(v)dv+R(p^{\star}+\delta)+\int_{p^{\star}+\delta}^{p^{\star}+\delta+\mu}\overline{F}(v)dv$
$\displaystyle\geq\underbrace{\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}vx(v)f(v)dv-\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}x(v)\bar{F}(v+\mu)dv}_{(A)}+\underbrace{R(p^{\star}+\delta)+\int_{p^{\star}+\delta}^{p^{\star}+\delta+\mu}\bar{F}(v)dv}_{(B)}.$

where we have used that $\dot{w}(v)=0$ for $v\leq p^{\star}-\delta-\mu$ and
$\dot{w}(v)$ in $[p^{\star}-\delta-\mu,p^{\star}+\delta]$. Let us bound $(B)$
first. We use Proposition 5.4 with

$\mu(\varepsilon)=K\cdot\varepsilon^{\beta},\quad\beta\in(0,1).$

Note that we need $\beta\in(0,1)$ so that $\mu>\varepsilon\cdot e$ for all
$\varepsilon>0$ small and $\mu(\varepsilon)/\varepsilon\uparrow\infty$ as
$\varepsilon\downarrow 0$. With this choice, we have

$\delta\leq\frac{K^{2}}{4}\cdot\varepsilon^{2\beta-1}.$

Note that the above further constraints $\beta$ such that $\beta>1/2$. We have

$\displaystyle(B)$
$\displaystyle\geq\bar{F}(p^{\star}+\delta+\mu)\mu+R(p^{\star}+\delta)$
$\displaystyle\geq\bar{F}(p^{\star}+\delta+\mu)\mu+R^{\star}-\kappa_{U}\delta^{\alpha}$
$\displaystyle\geq\bar{F}(p^{\star}+\delta+\mu)\cdot
K\cdot\varepsilon^{\beta}+R^{\star}-\kappa_{U}\left(\frac{K^{2}}{4}\right)^{\alpha}\varepsilon^{(2\beta-1)\alpha}$

Note that in the second inequality above we are using that

$R(p^{\star}+\delta)-R^{\star}=\int_{p^{\star}}^{p^{\star}+\delta}\dot{R}(v)dv\geq\int_{p^{\star}}^{p^{\star}+\delta}-\kappa_{u}\alpha(v-p^{\star})^{\alpha-1}dv=-\kappa_{U}\delta^{\alpha},$
(28)

here we are using Definition 2.1 and $\delta>0$ small such that $\delta<\ell$.
The latter is possible by considering $\varepsilon>0$ small enough. We set
$\beta=\alpha/(2\alpha-1)$ then

$\displaystyle(B)$ $\displaystyle\geq
R^{\star}+\bar{F}(p^{\star}+\delta+\mu)\cdot
K\cdot\varepsilon^{\alpha/(2\alpha-1)}-\kappa_{U}\left(\frac{K^{2}}{4}\right)^{\alpha}\varepsilon^{\alpha/(2\alpha-1)}$
$\displaystyle=R^{\star}+\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)}$

We must make sure that the parenthesis in the last expression above is
strictly positive:

$\bar{F}(p^{\star}+\delta+\mu)>\kappa_{U}\left(\frac{1}{4}\right)^{\alpha}K^{2\alpha-1},$

since $\alpha>1/2$, $\delta(\varepsilon)+\mu(\varepsilon)\downarrow 0$, and
$\bar{F}(p^{\star})>0$, we can always choose $K>0$ small enough such that the
above is true.

Let us bound $(A)$. To do this, we use Definition 2.1 again.

$\displaystyle(A)$
$\displaystyle=\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}vx(v)f(v)dv-\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}x(v)\bar{F}(v+\mu)dv$
$\displaystyle\geq\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}vx(v)f(v)dv-\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}x(v)\bar{F}(v)dv$
$\displaystyle=\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}x(v)\left(vf(v)-\bar{F}(v)\right)dv$
$\displaystyle=\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}x(v)\left(-\dot{R}(v)\right)dv$
$\displaystyle=-x(p^{\star}-\delta)R(p^{\star}-\delta)+x(p^{\star}-\delta-\mu)R(p^{\star}-\delta-\mu)+\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}\dot{x}(v)R(v)dv$
$\displaystyle=-R(p^{\star}-\delta)+\frac{\varepsilon}{\mu}R(p^{\star}-\delta-\mu)+\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}\dot{x}(v)R(v)dv$
$\displaystyle\geq-\left(R^{\star}-\kappa_{L}\delta^{\alpha}\right)+\frac{\varepsilon}{\mu}\left(R^{\star}-\kappa_{U}|\delta+\mu|^{\alpha}\right)+\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}\dot{x}(v)\left(R^{\star}-\kappa_{U}|v-p^{\star}|^{\alpha}\right)dv$
$\displaystyle\geq-\left(R^{\star}-\kappa_{L}\delta^{\alpha}\right)+\frac{\varepsilon}{\mu}\left(R^{\star}-\kappa_{U}(\delta+\mu)^{\alpha}\right)+\left(R^{\star}-\kappa_{U}(\delta+\mu)^{\alpha}\right)\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}\dot{x}(v)dv$
$\displaystyle=-\left(R^{\star}-\kappa_{L}\delta^{\alpha}\right)+\frac{\varepsilon}{\mu}\left(R^{\star}-\kappa_{U}(\delta+\mu)^{\alpha}\right)+\left(R^{\star}-\kappa_{U}(\delta+\mu)^{\alpha}\right)\left(1-\frac{\varepsilon}{\mu}\right)$
$\displaystyle=\kappa_{L}\delta^{\alpha}-\kappa_{U}(\delta+\mu)^{\alpha}$
$\displaystyle\geq-\kappa_{U}(\delta+\mu)^{\alpha}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}-\kappa_{U}(2\delta)^{\alpha}$
$\displaystyle\geq-\kappa_{U}\left(2\frac{K^{2}}{4}\cdot\varepsilon^{2\beta-1}\right)^{\alpha}$
$\displaystyle\geq-\kappa_{U}\left(2\frac{K^{2}}{4}\cdot\right)^{\alpha}\varepsilon^{\alpha/(2\alpha-1)}$

In (a) we use that $\delta>\mu$ when $\lim_{\varepsilon\downarrow
0}\mu(\varepsilon)/\varepsilon=+\infty$ because $\lim_{\varepsilon\downarrow
0}\delta(\mu(\varepsilon),\varepsilon)/\mu(\varepsilon)=+\infty$ which is true
because $\frac{\mu}{4\varepsilon}\leq\frac{\delta}{\mu}+1$, see Proposition
5.4. This, together with the bound we have for (B), yields

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

The parenthesis can be guaranteed to be positive by using a the same reasoning
as before. This concludes the proof.

###  9.1 Auxiliary results for Section 5

###### Lemma 9.5

Let $x(\cdot)$ be a solution to (ODE)-(DDE). Then $x(\cdot)$ is non-decreasing
in $[0,p^{\star}+\delta]$.

###### Proof 9.6

Proof of Lemma 9.5

To see why $x(\cdot)$ is non-decreasing we show that if $x(\cdot)$ is non-
decreasing in $[p^{\star}-\delta+(n-1)\cdot\mu,p^{\star}-\delta+n\cdot\mu]$
then it is also non-decreasing in
$[p^{\star}-\delta+n\cdot\mu,p^{\star}-\delta+(n+1)\cdot\mu]$ for all $n\geq
0$. Indeed, fix $n$ and denote by $x_{0}$ to $x(\cdot)$ in
$[p^{\star}-\delta+(n-1)\cdot\mu,p^{\star}-\delta+n\cdot\mu]$. Suppose that
$x_{0}$ in non-decreasing. Now consider
$v\in[p^{\star}-\delta+n\cdot\mu,p^{\star}-\delta+(n+1)\cdot\mu]$, $x(\cdot)$
must satisfy the following equation

$x(v)=x_{0}(p^{\star}-\delta+n\cdot\mu),\quad\dot{x}(v)=\frac{x(v)-x_{0}(v-\mu)}{\mu},\quad\forall
v\in[p^{\star}-\delta+n\cdot\mu,p^{\star}-\delta+(n+1)\cdot\mu].$ (29)

Consider the alternative ordinary differential equation

$r(v)=x_{0}(p^{\star}-\delta+n\cdot\mu),\quad\dot{r}(v)=\frac{r(v)-x_{0}(p^{\star}-\delta+n\cdot\mu)}{\mu},\quad\forall
v\in[p^{\star}-\delta+n\cdot\mu,p^{\star}-\delta+(n+1)\cdot\mu].$ (30)

Let $f(v,x)$ and $g(v,r)$ be the right-hand side of eq. 29 and eq. 30,
respectively. Note because $x_{0}(\cdot)$ is non-decresing in
$[p^{\star}-\delta+(n-1)\cdot\mu,p^{\star}-\delta+n\cdot\mu]$ we have that
$f(v,x)\geq g(v,x)$. In turn, a standard comparison argument for ordinary
differential equations implies that $x(v)\geq r(v)$ for all
$v\in[p^{\star}-\delta+n\cdot\mu,p^{\star}-\delta+(n+1)\cdot\mu].$ Since the
solution to eq. 30 is $r(v)=x_{0}(p^{\star}-\delta+n\cdot\mu)$, we can
conclude that $x(v)\geq x_{0}(p^{\star}-\delta+n\cdot\mu)$ for all
$v\in[p^{\star}-\delta+n\cdot\mu,p^{\star}-\delta+(n+1)\cdot\mu].$ Therefore,
from eq. 29 we deduce that $\mu\dot{x}(v)\geq
x_{0}(p^{\star}-\delta+n\cdot\mu)-x_{0}(v-\mu)\geq 0$ for all
$v\in[p^{\star}-\delta+n\cdot\mu,p^{\star}-\delta+(n+1)\cdot\mu].$ That is,
$x(\cdot)$ is non-decreasing in
$\in[p^{\star}-\delta+n\cdot\mu,p^{\star}-\delta+(n+1)\cdot\mu]$. To conclude,
note that in $[p^{\star}-\delta-\mu,p^{\star}-\delta]$ $x(\cdot)$ is the
solution to an ordinary differential equation for which it can be easily
verified that the solution in strictly increasing.

###### Lemma 9.7

Let $\Gamma(t)$ be defined by

$\Gamma(t)\triangleq\sum_{j=0}^{\left\lfloor
t\right\rfloor+1}\frac{(-1)^{j}e^{-j}}{j!}\left(t+1-j\right)^{j},\quad t\geq
0.$

Then,

$2(t+1)e^{-1}e^{-t}<\Gamma(t)\leq 2(t+2)e^{-(t+1)},\quad\forall t\geq 0.$

###### Proof 9.8

Proof of Lemma 9.7 To prove the bounds we establish a connection between
$\Gamma(x)$ and renewal theory. We will show that for an appropriate renewal
function $m(t)$, we have that $m(t+1)=e^{t+1}\Gamma(t)-1$. Then we will use
natural bounds on $m(t)$ to derive bounds for $\Gamma(t)$.

Consider the uniform distribution with support in $[0,1]$ with cdf denoted by
$G(t)$. That is, we have a sequence of independent random variables
$\\{X_{i}\\}_{i\geq 1}$ with uniform distribution with support in $[0,1]$ that
represent the time between the $(i-1)$st and the $i$th events. Let

$Z_{0}=0,\quad Z_{k}=\sum_{i=1}^{k}X_{i},\quad k\geq 1,$

that is, $Z_{k}$ is the time of the $k$th event. Then, the number of events up
to time $t$ and the renewal function are given by

$N(t)=\sup\\{k:\>Z_{k}\leq t\\},\quad\text{and}\quad m(t)=\mathsf{E}[N(t)].$

respectively. We will prove that for all $n\geq 0$

$m(t)=\sum_{k=0}^{n}(-1)^{k}e^{t-k}(t-k)^{k}/k!-1,\quad\text{for}\>n\leq t\leq
n+1.$ (31)

The renewal function can be written as (see, e.g., Proposition 3.2.1 in Ross
et al. 1996)

$m(t)=\sum_{\ell=1}^{\infty}\mathbf{P}(Z_{\ell}\leq t).$

Because $Z_{\ell}$ is the sum of $\ell$ independent uniform distributions, it
follows that $Z_{\ell}$ has an Irwin-Hall distribution given by

$\mathbf{P}(Z_{\ell}\leq t)=\begin{dcases*}\frac{1}{\ell!}\sum_{k=0}^{\lfloor
t\rfloor}(-1)^{k}\binom{\ell}{k}(t-k)^{\ell}&\mbox{if } $t<\ell$\\\ 1&\mbox{if
} $t\geq\ell.$\end{dcases*}$

So for $n\leq t\leq n+1$,

$\displaystyle m(t)$
$\displaystyle=\sum_{\ell=1}^{\infty}\mathbf{P}(Z_{\ell}\leq t)$
$\displaystyle=\sum_{\ell=1}^{n}1+\sum_{\ell=n+1}^{\infty}\frac{1}{\ell!}\sum_{k=0}^{\lfloor
t\rfloor}(-1)^{k}\binom{\ell}{k}(t-k)^{\ell}$
$\displaystyle=n+\sum_{\ell=n+1}^{\infty}\frac{1}{\ell!}\sum_{k=0}^{n}(-1)^{k}\binom{\ell}{k}(t-k)^{\ell}$
$\displaystyle=n+\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}\sum_{\ell=n+1}^{\infty}\frac{1}{(\ell-k)!}(t-k)^{\ell}$
$\displaystyle=n+\sum_{k=0}^{n}\frac{(-1)^{k}(t-k)^{k}}{k!}\sum_{\ell=n+1-k}^{\infty}\frac{1}{\ell!}(t-k)^{\ell}$
$\displaystyle=n+\sum_{k=0}^{n}\frac{(-1)^{k}(t-k)^{k}}{k!}\left(e^{t-k}-\sum_{\ell=0}^{n-k}\frac{1}{\ell!}(t-k)^{\ell}\right)$
$\displaystyle=n+\sum_{k=0}^{n}\frac{(-1)^{k}(t-k)^{k}}{k!}e^{t-k}-\sum_{k=0}^{n}\sum_{\ell=0}^{n-k}\frac{(-1)^{k}(t-k)^{k}}{k!}\frac{(t-k)^{\ell}}{\ell!}$
$\displaystyle=\sum_{k=0}^{n}\frac{(-1)^{k}(t-k)^{k}}{k!}e^{t-k}-1,$

where the second equation follows from the Irwin-Hall distribution, the third
because $n\leq t\leq n+1$, the fourth from exchanging the order of summation,
the sixth from the exponential series, and the last equality from the identity
(which can be verified by induction)

$\sum_{k=0}^{n}\sum_{\ell=0}^{n-k}\frac{(-1)^{k}(t-k)^{k}}{k!}\frac{(t-k)^{\ell}}{\ell!}=n+1,\quad\forall
n>0,t.$

This proves Equation 31. Evaluating the renewal function at $t+1$ gives

$\displaystyle m(t+1)$ $\displaystyle=\sum_{k=0}^{\lfloor
t+1\rfloor}(-1)^{k}e^{t+1-k}(t+1-k)^{k}/k!-1=\sum_{k=0}^{\lfloor
t\rfloor+1}(-1)^{k}e^{t+1-k}(t+1-k)^{k}/k!-1$
$\displaystyle=e^{t+1}\Gamma(t)-1.$ (32)

Now we obtain bounds on $m(t)$. Note that $Z_{N(t)+1}>t$ and that $N(t)+1$ is
a stopping time, hence Wald’s equation yields

$\frac{1}{2}(m(t)+1)>t.$

Hence, from (9.8) using $t+1$ we have that

$\Gamma(t)>2(t+1)e^{-1}e^{-t}>2te^{-1}e^{-t}$ (33)

Next, we prove the upper bound for $\Gamma(t)$. Note that $Z_{N(t)+1}\leq t+1$
because the time between renewals are uniformly distributed in [0,1]. Hence,
by Wald’s equation we have that

$\frac{1}{2}(m(t)+1)\leq t+1.$

Using $t+1$ instead of $t$ in the above we deduce that

$e^{t+1}\Gamma(t)\leq 2(t+2).$

###### Proof 9.9

Proof of Proposition 5.5 We exploit the characterization of
$m_{\textup{{pd}}}=(x_{\textup{{pd}}},t_{\textup{{pd}}})$ given in proposition
5.2. For ease of exposition we use $(x,t)$ instead of
$(x_{\textup{{pd}}},t_{\textup{{pd}}})$. We have

$\displaystyle\Pi(m_{\textup{{pd}}})$
$\displaystyle=\int_{0}^{\overline{v}}t_{\textup{{pd}}}(v)f(v)dv$
$\displaystyle=\int_{0}^{\overline{v}}vx(v)f(v)dv+\varepsilon\overline{F}(p^{\star}-\delta)-\int_{p^{\star}-\delta}^{\overline{v}}\int_{0}^{v}x({v^{\star}}(s))f(v)dsdv$
$\displaystyle=\int_{0}^{\overline{v}}vx(v)f(v)dv+\varepsilon\overline{F}(p^{\star}-\delta)-\int_{0}^{p^{\star}-\delta}\int_{p^{\star}-\delta}^{\overline{v}}x({v^{\star}}(s))f(v)dvds$
$\displaystyle-\int_{p^{\star}-\delta}^{\overline{v}}\int_{s}^{\overline{v}}x({v^{\star}}(s))f(v)dvds$
$\displaystyle=\int_{0}^{\overline{v}}vx(v)f(v)dv+\varepsilon\overline{F}(p^{\star}-\delta)-(p^{\star}-\delta)x(0)\overline{F}(p^{\star}-\delta)-\int_{p^{\star}-\delta}^{\overline{v}}x({v^{\star}}(v))\overline{F}(v)dv$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\int_{0}^{\overline{v}}vx(v)f(v)dv-\int_{p^{\star}-\delta}^{p^{\star}+\delta+\mu}x(v-\mu)\overline{F}(v)dv-x(p^{\star}+\delta)\int_{p^{\star}+\delta+\mu}^{\overline{v}}\overline{F}(v)dv$
$\displaystyle=\int_{0}^{\overline{v}}vx(v)f(v)dv-\int_{p^{\star}-\delta-\mu}^{p^{\star}+\delta}x(v)\overline{F}(v+\mu)dv-\int_{p^{\star}+\delta+\mu}^{\overline{v}}\overline{F}(v)dv$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\int_{0}^{p^{\star}+\delta}x(v)\left(v-\frac{\overline{F}(v+\mu)}{f(v)}\dot{w}(v)\right)f(v)dv+\int_{p^{\star}+\delta}^{\overline{v}}vx(v)f(v)dv-\int_{p^{\star}+\delta+\mu}^{\overline{v}}\overline{F}(v)dv$
$\displaystyle=\int_{0}^{p^{\star}+\delta}x(v)\left(v-\frac{\overline{F}(v+\mu)}{f(v)}\dot{w}(v)\right)f(v)dv+\int_{p^{\star}+\delta}^{\overline{v}}(vf(v)-\overline{F}(v))dv+\int_{p^{\star}+\delta}^{p^{\star}+\delta+\mu}\overline{F}(v)dv$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\int_{0}^{p^{\star}+\delta}x(v)\left(v-\frac{\overline{F}(v+\mu)}{f(v)}\dot{w}(v)\right)f(v)dv+R(p^{\star}+\delta)+\int_{p^{\star}+\delta}^{p^{\star}+\delta+\mu}\overline{F}(v)dv,$

where $(a)$ holds because $x(0)=\varepsilon/(p^{\star}-\delta)$; $(b)$ holds
because $\dot{w}(v)=0$ if $v<p^{\star}-\delta-\mu$ and $\dot{w}(v)=1$ if
$v\in(p^{\star}-\delta-\mu,p^{\star}+\delta)$; and $(c)$ holds because the
derivative of $v\overline{F}(v)$ equals $\overline{F}(v)-vf(v)$. This
concludes the proof.

##  10 Auxiliary Results

###### Lemma 10.1

Suppose that $R(v)$ is locally concave around $p^{\star}$ and let
$\alpha\in(1,+\infty)$. Then there exists positive constants
$\tilde{\kappa}_{L},\tilde{\kappa}_{U}$ and a neighborhood of $p^{\star}$,
$\mathcal{N}_{\tilde{\ell}}=(p^{\star}-\tilde{\ell},p^{\star}+\tilde{\ell})\subset(0,\overline{v})$,
such that

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

if and only if there exists 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}.$ (35)

###### Proof 10.2

Proof of Lemma 10.1 We show that under local concavity Equation 34 is
equivalent to Equation 35. To prove that Equation 35 implies Equation 34 we
can simply consider the cases $v<p^{\star}$ and $v>p^{\star}$ and then
integrate Equation 35. The latter immediately delivers Equation 34. To show
that Equation 34 implies Equation 35, we must use the local concavity
assumption. Without loss of generality we will assume that all the calculation
below are performed in the neighborhood where $R(v)$ is concave,
$\mathcal{N}_{c}$, intersected with the neighborhood where Equation 34 holds.
We have that

$\tilde{\kappa}_{L}\cdot|v-p^{\star}|^{\alpha}\leq
R(p)-R(v)=\int_{v}^{p}\dot{R}(s)ds\leq\dot{R}(v)(p-v),$

where the last inequality uses that $\dot{R}(v)$ is non-increasing by
concavity of $R(v)$. Now we establish the upper bound in Equation 35. We
consider the case $v<p^{\star}$ (the case $v>p^{\star}$ is symmetric). Since
$R(v)$ is locally concave, we have that:

$R(x)\leq R(y)+\dot{R}(y)(x-y),\quad\forall x,y\in\mathcal{N}_{c}.$

Consider $z\leq v$, use the previous inequality with $x=z$ and $y=v$, and also
use that $R(z)\geq R(p^{\star})-\tilde{\kappa}_{U}(p^{\star}-z)^{\alpha}$ to
obtain:

$\dot{R}(v)\leq\frac{R(v)-R(z)}{v-z}\leq\frac{R(v)-R(p^{\star})+\tilde{\kappa}_{U}(p^{\star}-z)^{\alpha}}{v-z}\leq\frac{\tilde{\kappa}_{U}(p^{\star}-z)^{\alpha}}{v-z},$

where in the last inequality we used that $R(v)\leq R(p^{\star})$. Consider
$z^{\star}=(\alpha v-p^{\star})/(\alpha-1)$ (which can be obtained by
optimizing the right-hand-side in the last inequality above). By replacing
this choice of $z$ above, we obtain

$\dot{R}(v)\leq\tilde{\kappa}_{U}\alpha\cdot\left(\frac{\alpha}{\alpha-1}\right)^{\alpha-1}(p^{\star}-v)^{\alpha-1}\leq\alpha\cdot
e\tilde{\kappa}_{U}(p^{\star}-v)^{\alpha-1},$

where we have used that $\left(\frac{\alpha}{\alpha-1}\right)^{\alpha-1}$ is
bounded above by $e$. In order to conclude the argument we need to verify that
$z^{\star}\in(0,v)$. If $v$ is taken sufficiently close to $p^{\star}$ then
because $\alpha>1$ we have that $z^{\star}$ can be made positive.
Additionally, $z^{\star}<v$ if and only if $\alpha v-p^{\star}<(\alpha-1)v$
which holds because we are assuming that $v<p^{\star}.$ This yields a new
neighborhood around $p^{\star}$. Taking the intersection of this neighborhood
with $\mathcal{N}_{c}$ and $\mathcal{N}_{\tilde{\ell}}$ implies Equation 35.
This concludes the proof.

##  11 The Revelation Principle

The standard revelation principle can be stated as follows: Given a mechanism
and an equilibrium for that mechanism, there exists a direct mechanism in
which (1) it is an equilibrium for each buyer to report his or her type
truthfully and (2) the outcomes are the same as in the given equilibrium of
the original mechanism. In our case, the statement is similar: Given a
mechanism and an $\varepsilon-$equilibrium for that mechanism, there exists a
direct mechanism in which (1) it is an $\varepsilon$-equilibrium for the buyer
to report her type truthfully and (2) the outcomes are the same as in the
given $\varepsilon$-equilibrium of the original mechanism.

Mathematically, 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, we are interested in $\varepsilon$-equilibria that
satisfy:

$v\cdot\hat{x}(\hat{\theta}(v))-\hat{t}(\hat{\theta}(v))\geq
v\cdot\hat{x}(\hat{\theta}^{\prime})-\hat{t}(\hat{\theta}^{\prime})-\varepsilon,\quad\forall
v,\hat{\theta}^{\prime},$

and the participation constraint:

$v\cdot\hat{x}(\hat{\theta}(v))-\hat{t}(\hat{\theta}(v))\geq 0,\quad\forall
v.$

That is, 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}$. 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
common 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. We let

$x(v)=\hat{x}(\hat{\theta}(v)\quad\text{and}\quad
t(v)=\hat{t}(\hat{\theta}(v)).$

With this transformation, we can optimize over mechanisms that take as input
values. Indeed, we just saw how a solution from the indirect mechanism problem
can be transformed into a solution to the direct mechanism problem. A solution
from the direct mechanism problem is also a solution to the indirect mechanism
problem because every direct mechanism is an indirect mechanism. For this to
work, we use the assumption that we are choosing the best $\varepsilon$-best
response.

## References

  * Azevedo and Budish (2018) Azevedo EM, Budish E (2018) Strategy-proofness in the Large. _The Review of Economic Studies_ 86(1):81–116, ISSN 0034-6527, URL http://dx.doi.org/10.1093/restud/rdy042.
  * Balcan et al. (2005) Balcan MF, Blum A, Hartline JD, Mansour Y (2005) Mechanism design via machine learning. _46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05)_ , 605–614 (IEEE).
  * Balcan et al. (2019) Balcan MF, Sandholm T, Vitercik E (2019) Estimating approximate incentive compatibility.
  * Balseiro et al. (2015) Balseiro SR, Besbes O, Weintraub GY (2015) Repeated auctions with budgets in ad exchanges: Approximations and design. _Management Science_ 61(4):864–884.
  * Balseiro et al. (2019) Balseiro SR, Besbes O, Weintraub GY (2019) Dynamic mechanism design with budget-constrained buyers under limited commitment. _Operations Research_ .
  * Basu et al. (2017) Basu A, Martin K, Ryan CT (2017) Strong duality and sensitivity analysis in semi-infinite linear programming. _Mathematical Programming_ 161(1-2):451–485.
  * Bei and Huang (2011) Bei X, Huang Z (2011) Bayesian incentive compatibility via fractional assignments. _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_ , 720–733 (SIAM).
  * Cai et al. (2021) Cai Y, Oikonomou A, Velegkas G, Zhao M (2021) An efficient $\epsilon$-bic to bic transformation and its application to black-box reduction in revenue maximization. _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 1337–1356 (SIAM).
  * Caroll (2013) Caroll G (2013) A quantitative approach to incentives: Application to voting rules. _working paper_ .
  * Colini-Baldeschi et al. (2020) Colini-Baldeschi R, Leonardi S, Schrijvers O, Sodomka E (2020) _Envy, Regret, and Social Welfare Loss_ , 2913–2919 (New York, NY, USA: Association for Computing Machinery).
  * Conitzer et al. (2020) Conitzer V, Feng Z, Parkes DC, Sodomka E (2020) Welfare-preserving $\varepsilon$-bic to bic transformation with negligible revenue loss. _arXiv preprint arXiv:2007.09579_ .
  * Daskalakis and Weinberg (2012) Daskalakis C, Weinberg SM (2012) Symmetries and optimal multi-dimensional mechanism design. _Proceedings of the 13th ACM conference on Electronic commerce_ , 370–387.
  * Deng and Lahaie (2019) Deng Y, Lahaie S (2019) Testing dynamic incentive compatibility in display ad auctions. _The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 19), August 4-8, 2019, Anchorage, AK, USA. ACM, New York, NY, USA_ , volume 65, 4204–4221.
  * Deng et al. (2020) Deng Y, Lahaie S, Mirrokni V, , Zuo S (2020) A data driven metric of incentive compatibility. _The World Wide Web Conference_ , WWW 20 (New York, NY, USA: Association for Computing Machinery), URL http://dx.doi.org/https://doi.org/10.1145/3366423.3380249.
  * Driver (2012) Driver RD (2012) _Ordinary and delay differential equations_ , volume 20 (Springer Science & Business Media).
  * Dughmi et al. (2021) Dughmi S, Hartline J, Kleinberg RD, Niazadeh R (2021) Bernoulli factories and black-box reductions in mechanism design. _Journal of the ACM (JACM)_ 68(2):1–30.
  * Dütting et al. (2021) Dütting P, Roughgarden T, Talgam-Cohen I (2021) The complexity of contracts. _SIAM Journal on Computing_ 50(1):211–254, URL http://dx.doi.org/10.1137/20M132153X.
  * Feng et al. (2019) Feng Z, Schrijvers O, Sodomka E (2019) Online learning for measuring incentive compatibility in ad auctions. _The World Wide Web Conference_ , 2729?2735, WWW 19 (New York, NY, USA: Association for Computing Machinery), ISBN 9781450366748, URL http://dx.doi.org/10.1145/3308558.3313674.
  * Gorokh et al. (2017) Gorokh A, Banerjee S, Iyer K (2017) From monetary to non-monetary mechanism design via artificial currencies. volume 65, 4204–4221.
  * Hartline et al. (2011) Hartline JD, Kleinberg R, Malekian A (2011) Bayesian incentive compatibility via matchings. _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_ , 734–747 (SIAM).
  * Hartline et al. (2015) Hartline JD, Kleinberg R, Malekian A (2015) Bayesian incentive compatibility via matchings. _Games and Economic Behavior_ 92:401–429.
  * Hartline and Lucier (2010) Hartline JD, Lucier B (2010) Bayesian algorithmic mechanism design. _Proceedings of the forty-second ACM symposium on Theory of computing_ , 301–310 (ACM).
  * Hartline and Lucier (2015) Hartline JD, Lucier B (2015) Non-optimal mechanism design. _American Economic Review_ 105(10):3102–24.
  * Kanoria and Nazerzadeh (2017) Kanoria Y, Nazerzadeh H (2017) Dynamic reserve prices for repeated auctions: Learning from bids. _Available at SSRN 2444495_ .
  * Lahaie et al. (2018) Lahaie S, Medina AM, Sivan B, Vassilvitskii S (2018) Testing incentive compatibility in display ad auctions. _Proceedings of the 2018 World Wide Web Conference, WWW 2018_.
  * Lubin and Parkes (2012) Lubin B, Parkes D (2012) Approximate strategyproofness. _Current Science_ 103(9):4204–4221.
  * Manelli and Vincent (2007) Manelli AM, Vincent DR (2007) Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly. _Journal of Economic Theory_ 137(1):153–185.
  * Martin et al. (2016) Martin K, Ryan CT, Stern M (2016) The slater conundrum: duality and pricing in infinite-dimensional optimization. _SIAM Journal on Optimization_ 26(1):111–138.
  * Milgrom (2011) Milgrom P (2011) Critical issues in the practice of market design. _Economic Inquiry_ 49(2):311–320.
  * Milgrom and Segal (2002) Milgrom P, Segal I (2002) Envelope theorems for arbitrary choice sets. _Econometrica_ 70(2):583–601.
  * MoPub (2013) MoPub (2013) Introducing soft price floors. https://www.mopub.com/2013/04/12/introducing-soft-price-floors, accessed: 2020-02-10.
  * Myerson (1979) Myerson RB (1979) Incentive compatibility and the bargaining problem. _Econometrica: journal of the Econometric Society_ 61–73.
  * Myerson (1981) Myerson RB (1981) Optimal auction design. _Mathematics of operations research_ 6(1):58–73.
  * Nazerzadeh et al. (2013) Nazerzadeh H, Saberi A, Vohra R (2013) Dynamic pay-per-action mechanisms and applications to online advertising. _Operations Research_ 61(1):98–111.
  * Norkin et al. (1973) Norkin SB, et al. (1973) _Introduction to the theory and application of differential equations with deviating arguments_ , volume 105 (Academic Press).
  * Riley and Zeckhauser (1983) Riley J, Zeckhauser R (1983) Optimal Selling Strategies: When to Haggle, When to Hold Firm*. _The Quarterly Journal of Economics_ 98(2):267–289.
  * Ross et al. (1996) Ross SM, Kelly JJ, Sullivan RJ, Perry WJ, Mercer D, Davis RM, Washburn TD, Sager EV, Boyce JB, Bristow VL (1996) _Stochastic processes_ , volume 2 (Wiley New York).
  * Rubinstein and Weinberg (2015) Rubinstein A, Weinberg SM (2015) Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. _16th ACM Conference on Economics and Computation, EC 2015_ , 377–394 (Association for Computing Machinery, Inc).
  * Zeithammer (2019) Zeithammer R (2019) Soft floors in auctions. _Management Science_ 65(9):4204–4221.