# Sharp bounds for Joint moments of the Riemann zeta function

Michael J. Curran  Mathematical Institute, University of Oxford, Oxford, OX2
6GG, UK<EMAIL_ADDRESS>and  André Heycock  Department of
Mathematics, University of Manchester, Manchester, M13 9PL, UK.
<EMAIL_ADDRESS>
###### Abstract.

In [8], the first author obtained conjecturally sharp upper bounds for the
joint moments of the $(2k-2h)^{\text{th}}$ power of the Riemann zeta function
with the $2h^{\text{th}}$ power of its derivative on the critical line in the
range $1\leq k\leq 2$, $0\leq h\leq 1$. Unconditionally, we extend these upper
bounds to all $0\leq h\leq k\leq 2$, and obtain lower bounds for all $0\leq
h\leq k+1/2$. Assuming the Riemann hypothesis, we give sharp bounds for all
$0\leq h\leq k$. We also prove upper bounds of the conjectured order for more
general joint moments of zeta with its higher derivatives.

##  1\. Introduction

This paper is concerned with the joint moments of the Riemann zeta function
with its derivative on the critical line and other natural variants of these
moments. Work of Hall [11], Hughes [15], and Keating and Snaith [17, 18] has
led to the conjecture that for $k>-\tfrac{1}{2}$ and
$-\tfrac{1}{2}<h<k+\tfrac{1}{2}$,

$\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k-2h}\left|\zeta^{\prime}(\tfrac{1}{2}+it)\right|^{2h}\
dt\sim C(k,h)T(\log T)^{k^{2}+2h}$ (1)

as $T\rightarrow\infty$ for certain constants $C(k,h)$. These constants can be
expressed as the product of a natural number theoretic factor and a factor
coming from conjectural connections of the Riemann zeta function with random
matrix theory. The arithmetic factor is given by a product over primes, while
the random matrix factor can be expressed using Painlevé trancendents. For
finite $N$, the random matrix factor can be expressed using the solution to a
Painlevé V differential equation [5], while the random matrix factor in the
limit $N\rightarrow\infty$ is related to the solution of a Painlevé III
differential equation [3, 4, 5, 9]. This asymptotic (1) is currently only
known to hold for integer $h,k$ satisfying $0\leq h\leq k\leq 2$ due to work
of Ingham [16] and Conrey [7].

Since the asymptotic (1) seems out of reach for all remaining values of $h$
and $k$, it is natural to ask if we can at least obtain upper bounds of the
right order. The work of Heap, Radziwiłł, and Soundararajan [13] shows that we
have upper bounds of the expected order for (1) for $h=0,k\leq 2$. In fact,
lower bounds of the conjectured order are also known for all $k\geq 0$ when
$h=0$ due to work of Heap and Soundararajan [14]. By using Conrey’s asymptotic
for the fourth moment of the derivative of zeta [7] along with Hölder’s
inequality, one also sees that an upper bound of the expected order for (1)
holds for $k=2$ and $h\leq 2$. Finally, the first author recently showed [8]
that the an upper bound of the expected order for (1) holds in the larger
range where $0\leq h\leq 1$ and $1\leq k\leq 2$. The paper [8] uses the work
of Heap, Radziwiłł, and Soundararajan [2] along with the observation that if
we have an upper bound of the expected order in (1) for a given pair $k,h$,
then we also have an upper bound of the expected order for the pair
$k,h^{\prime}$ for any $0\leq h^{\prime}\leq h$. This latter observation is a
simple consequence of Hölder’s inequality and will be quite useful in this
paper.

Our primary aim is to prove the upper bound (1) for all $0\leq h\leq k\leq 2$.
The method of proof extends straightforwardly to joint moments with higher
derivatives. Assuming the Riemann hypothesis, the bound extends to all $0\leq
h\leq k$.

######  Theorem 1.1.

Let $n\in\mathbb{Z}_{>0}$, $0\leq k\leq 2$, and $h_{j}\geq 0$ for $1\leq j\leq
n$, with $h:=h_{1}+\cdots+h_{n}\leq k$. Then

$\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k-2h}\prod_{j=1}^{n}|\zeta^{(j)}(\tfrac{1}{2}+it)|^{2h_{j}}\
dt\ll_{k,n,h_{1},\dots,h_{n}}T(\log T)^{k^{2}+2\sum_{j=1}^{n}jh_{j}},$ (2)

unconditionally for $k\leq 2$, and under the assumption of the Riemann
hypothesis for $k>2$.

The upper bound in Theorem 1.1 is the same order of magnitude one would
predict using random matrix theory. The case of integral joint moments of a
product of two derivatives of characteristic random unitary matrices has been
extensively studied by Keating and Wei [19, 20].

When $n=1$, Theorem 1.1 provides an upper bound of the expected order in (1)
for all $0\leq h\leq k$, assuming the Riemann hypothesis. We also obtain
unconditional lower bounds for all $k\geq 0$ with $0\leq h<k+\tfrac{1}{2}$, so
the upper bounds in (1) are of the correct order.

######  Theorem 1.2.

Let $k\geq 0$ and $0\leq h<k+\tfrac{1}{2}$. Then

$\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k-2h}|\zeta^{\prime}(\tfrac{1}{2}+it)|^{2h}\
dt\gg_{k,h}T(\log T)^{k^{2}+2h}.$

Lower bounds for joint moments involving higher derivatives will be considered
in future work of the second author.

We will begin by showing that Theorem 1.2 is a short consequence of the lower
bounds for the $2k^{\text{th}}$ moments of zeta for $k\geq 0$ obtained by Heap
and Soundararajan [14]. The argument we give is essentially the same argument
used in Conrey’s [7] proof of the explicit lower bound

$\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{3}|\zeta^{\prime}(\tfrac{1}{2}+it)|\
dt\geq(1+o(1))\frac{173}{672\pi^{2}}T(\log T)^{5}.$

Since obtaining good implicit constants is not our concern in this paper, a
slightly simpler version of the argument in [7] will suffice.

We will then move onto proving the upper bounds. Using Hölder’s inequality, we
will demonstrate that it suffices to prove Theorem 1.1 in the case of a single
moment,

$\mathcal{I}_{T}^{(n)}(k):=\int_{T}^{2T}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{2k}dt$

where $n\in\mathbb{Z}_{\geq 0}$, $k\geq 0$. The proof then splits into two
partially overlapping cases. If $k\geq 1/2$, one can represent the derivative
of zeta by a contour integral and can use Hölder’s or Jensen’s inequality to
essentially bound (1) by $(\log T)^{2nk}$ times the $2k^{\text{th}}$ moment of
zeta. The argument here is similar to one in work of Milinovich [21] on
moments of derivatives of zeta, and the proof fails for small $k$ because
$x\mapsto x^{2k}$ is not convex when $k<1/2$.

Our argument in the range $0\leq k\leq 2$ is similar to work of Heap,
Radziwiłł, and Soundararajan [13]. However, we initially apply Holder’s
inequality, instead of Young’s inequality, to obtain a sharp bound for
$|\zeta^{(n)}(\tfrac{1}{2}+it)|^{2k}$ averaged over a set $S\subseteq[T,2T]$
in terms of a product of the mean value of
$|\zeta^{(n)}(\tfrac{1}{2}+it)|^{4}$ times the exponential of a Dirichlet
polynomial and the mean value of the exponential of another Dirichlet
polynomial. Splitting $[T,2T]$ into subsets based on the longest permissible
Dirichlet polynomial approximation to $\log|\zeta(\tfrac{1}{2}+it)|$, one then
bounds the exponentials of Dirichlet polynomials by truncating the exponential
to a Taylor polynomial. This reduces the theorem to a variety of twisted
moment calculations. For Dirichlet polynomials, these have already been
essentially computed in [13]. For twisted fourth moments of higher derivatives
of the Riemann zeta function, we adapt the method of [8, Lem. 2].

## Acknowledgements

Part of this work was written during a visit by the first author to the
University of Manchester. He would like to thank Hung Bui and that institution
for their hospitality and support, as well as his advisor Jon Keating for
useful comments. The second author would like to thank his advisor, Hung Bui,
for helpful discussions. Finally both authors would like to thank Winston Heap
for comments on an early draft of the paper, and to thank Soundararajan for
bringing the argument in [7] to their attention.

##  2\. Lower Bounds: Proof of Theorem 1.2

We begin by writing

$\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k-2h}|\zeta^{\prime}(\tfrac{1}{2}+it)|^{2h}\
dt=\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k}\left(\left|\textup{Re
}\frac{\zeta^{\prime}}{\zeta}(\tfrac{1}{2}+it)\right|^{2}+\left|\textup{Im
}\frac{\zeta^{\prime}}{\zeta}(\tfrac{1}{2}+it)\right|^{2}\right)^{h}\ dt.$

It is a standard consequence of Stirling’s approximation and the functional
equation that for large $T$,

$\textup{Re
}\frac{\zeta^{\prime}}{\zeta}(\tfrac{1}{2}+it)=-\frac{1}{2}\log\frac{t}{2\pi}+O(|t|^{-1}).$

Therefore for large $T$,

$\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k-2h}|\zeta^{\prime}(\tfrac{1}{2}+it)|^{2h}\
dt\gg_{k,h}(\log T)^{2h}\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k}\ dt.$

Theorem 1.2 now follows after an application of the main theorem in [14], that
the integral on the right-hand side above is $\gg_{k}T(\log T)^{k^{2}}$. ∎

##  3\. Upper Bounds: Proof of Theorem 1.1 for $0\leq k\leq 2$

###  3.1. Initial reduction

First apply Hölder’s inequality to separate out each derivative:

$\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k-2h}\prod_{j=1}^{n}|\zeta^{(j)}(\tfrac{1}{2}+it)|^{2h_{j}}\
dt\\\ \leq\left(\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it)|^{2k}\
dt\right)^{1-h/k}\times\prod_{j=1}^{n}\left(\int_{T}^{2T}|\zeta^{(j)}(\tfrac{1}{2}+it)|^{2k}\
dt\right)^{h_{j}/k}.$ (3)

Theorem 1.1 follows once we show for all $n\in\mathbb{Z}_{>0}$ that

$\mathcal{I}^{(n)}_{T}(k):=\int_{T}^{2T}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{2k}\
dt\ll_{k,n}T(\log T)^{k^{2}+2nk},$ (4)

unconditionally for $k\leq 2$ and on RH for $k>2$. Going forward we will omit
the subscripts in our asymptotic notation, so the implicit constants may
depend on $k$ and $n$. Note that the case $n=0$ is proved in [13]
unconditionally for $k\leq 2$ and [12] on RH. The remainder of this section
completes the proof when $0\leq k\leq 2$.

###  3.2. Notation

Throughout, our parameters will depend on the value of $k$. Let $\log_{j}$
denote the $j$-fold iterated logarithm, set $T_{0}=1$,

$T_{j}:=\exp\left(\frac{\log T}{(\log_{j+1}T)^{2}}\right)$

for $j\geq 1$, and

$J:=\max\left\\{j:\log_{j}T\geq 10^{4}\right\\}.$

For $1\leq j\leq J$ set

$\mathcal{P}_{j}(s):=\sum_{T_{j-1}<p\leq T_{j}}\frac{1}{p^{s}},\quad
P_{j}:=\sum_{T_{j-1}<p\leq T_{j}}\frac{1}{p}.$

Next define the Dirichlet polynomials

$\mathcal{N}_{j}(s;\beta)=\sum_{\begin{subarray}{c}p\mid n\Rightarrow
p\in(T_{j-1},T_{j}]\\\ \Omega(n)\leq
10K_{j}\end{subarray}}\frac{\beta^{\Omega(n)}g(n)}{n^{s}},$

where $|\beta|\leq 2$,

$K_{j}:=50P_{j},\ g(n)=\prod_{p^{r}\|n}\tfrac{1}{r!},\ \text{ and
}\Omega(n)=\sum_{p^{r}\|n}r.$

Note $\mathcal{N}_{j}(s;\beta)$ is a Dirichlet polynomial of length $\leq
T_{j}^{500P_{j}}$, so $\prod_{j\leq J}\mathcal{N}_{j}(s;\beta)$ has length at
most $T_{1}^{500P_{1}}T_{2}^{500P_{2}}\cdots T_{J}^{500P_{J}}\leq T^{1/10}$.

We will decompose the interval $[T,2T]$ depending on the sizes of the
$\mathcal{P}_{j}(s)$. Define the good set

$\mathcal{G}:=\left\\{t\in[T,2T]:|\mathcal{P}_{j}(\tfrac{1}{2}+it)|\leq
K_{j}\text{ for all }j\leq J\right\\},$

and the bad sets

$\mathcal{B}_{r}:=\\{t\in[T,2T]:|\mathcal{P}_{j}(\tfrac{1}{2}+it)|\leq
K_{j}\text{ for all }1\leq j<r\text{ but
}|\mathcal{P}_{r}(\tfrac{1}{2}+it)|>K_{r}\\}.$

A similar decomposition occurs in the work of Harper [12] and also occurs
implicitly in the work of Radziwiłł and Soundararajan [22] and related papers
[8, 13, 14]. In our argument, it will be important to keep careful track of
which values $t$ are good or bad because we will use an interpolation
inequality separately on each set of our partition of $[T,2T]$. Throughout we
will use the following lemmata. The second is essentially contained in
Proposition 1 of [13], while the first is an analogue of their use of Young’s
inequality there.

######  Lemma 3.1.

For $0\leq\beta\leq 2$, $r\leq J+1$, and $S\subseteq[T,2T]$ measurable

$\begin{split}\int_{S}|\zeta(\tfrac{1}{2}+it)|^{2\beta}\
dt&\ll\left(\int_{S}|\zeta(\tfrac{1}{2}+it)|^{4}\exp\left((2\beta-4)\sum_{j<r}\textup{Re
}\mathcal{P}_{j}(\tfrac{1}{2}+it)\right)\ dt\right)^{\beta/2}\\\
&\qquad\times\left(\int_{S}\exp\left(2\beta\sum_{j<r}\textup{Re
}\mathcal{P}_{j}(\tfrac{1}{2}+it)\right)\ dt\right)^{1-\beta/2}.\end{split}$

###### Proof.

For convenience let $V(t)=\sum_{j<r}\textup{Re
}\mathcal{P}_{j}(\tfrac{1}{2}+it)$, and write

$\displaystyle\int_{S}|\zeta(\tfrac{1}{2}+it)|^{2\beta}\
dt=\int_{S}|\zeta(\tfrac{1}{2}+it)|^{2\beta}\exp\left(\beta(\beta-2)V(t)\right)\cdot\exp\left(\beta(2-\beta)V(t)\right)\
dt.$

The claim follows by applying Hölder’s inequality with exponent $p=2/\beta$
for the first factor
$|\zeta(\tfrac{1}{2}+it)|^{2\beta}\exp(\beta(\beta-2)V(t))$ and
$q=2/(2-\beta)$ for the second factor. ∎

######  Lemma 3.2.

If $|\beta|\leq 2$, $j\leq J$ and $|\mathcal{P}_{j}(s)|\leq K_{j}$, then

$\exp\left(2\beta\textup{Re
}\mathcal{P}_{j}(s)\right)=(1+O(e^{-P_{j}}))|\mathcal{N}_{j}(s;\beta)|^{2}.$

###### Proof.

By Taylor expansion of the exponential up to the $10K_{j}^{\text{th}}$ term we
find

$\left|\exp(\beta\mathcal{P}_{j}(s))-\mathcal{N}_{j}(s;\beta)\right|\leq
e^{-10K_{j}}$

since $|\beta\mathcal{P}_{j}(s)|\leq 2K_{j}$. Therefore

$\exp\left(2\beta\textup{Re
}\mathcal{P}_{j}(s)\right)=|\exp(\beta\mathcal{P}_{j}(s))|^{2}=|\mathcal{N}_{j}(s;\beta)+\theta
e^{-10K_{j}}|^{2}$

where $\theta$ denotes a quantity depending on $s$ with $|\theta|\leq 1$.
Finally by assumption $|\exp(\beta\mathcal{P}_{j}(s))|\geq e^{-K_{j}}$ and
therefore also $|\mathcal{N}_{j}(s;\beta)|\geq e^{-K_{j}/2}$, so we may turn
the additive error into a multiplicative error. ∎

###  3.3. Reduction to twisted moments

Theorem 1.1 will follow from the bounds

$\int_{\mathcal{G}}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{2k}\ dt\ll T(\log
T)^{k^{2}+2nk}$ (5)

and

$\int_{\mathcal{B}_{r}}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{2k}\ dt\ll T(\log
T)^{k^{2}+2nk}e^{-10P_{r}}$ (6)

after summing over $1\leq r\leq J$.

For $t\in\mathcal{G}$, applying Lemma 3.1 and then Lemma 3.2 with $r=J+1$
yields

$\begin{split}\int_{\mathcal{G}}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{2k}\
dt&\ll\left(\int_{\mathcal{G}}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{4}\prod_{j<J+1}|\mathcal{N}_{j}(\tfrac{1}{2}+it,k-2)|^{2}\
dt\right)^{\frac{k}{2}}\\\
&\qquad\times\left(\int_{\mathcal{G}}\prod_{j<J+1}|\mathcal{N}_{j}(\tfrac{1}{2}+it,k)|^{2}\
dt\right)^{1-\frac{k}{2}}.\end{split}$ (7)

Here we have used that $\prod_{j<J+1}(1+O(e^{-P_{j}}))=O(1)$. The range of
integration for each integral on the right-hand side can then be extended to
$[T,2T]$ since both integrands are non-negative.

The moments over the sets $\mathcal{B}_{r}$ for $1\leq r\leq J$ are handled in
a completely analogous manner — the only differences are that we apply Lemma
3.2 with the sum truncated at $r$ instead of $J+1$ and that we multiply the
integrand by $|\mathcal{P}_{r}(s)/(50P_{r})|^{2\left\lceil
50P_{r}\right\rceil}$, which majorises the indicator function of
$\mathcal{B}_{r}$. Finally, we extend the range of integration to all of
$[T,2T]$ and obtain

$\begin{split}\int_{\mathcal{B}_{r}}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{2k}\
dt&\ll\left(\int_{T}^{2T}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{4}\prod_{j<r}\left|\mathcal{N}_{j}(\tfrac{1}{2}+it,k-2)\right|^{2}\left|\frac{\mathcal{P}_{r}(\tfrac{1}{2}+it)}{50P_{r}}\right|^{2\lceil
50P_{r}\rceil}\ dt\right)^{\frac{k}{2}}\\\
&\qquad\times\left(\int_{T}^{2T}\prod_{j<r}\left|\mathcal{N}_{j}(\tfrac{1}{2}+it,k)\right|^{2}\left|\frac{\mathcal{P}_{r}(\tfrac{1}{2}+it)}{50P_{r}}\right|^{2\lceil
50P_{r}\rceil}\ dt\right)^{1-\frac{k}{2}}.\end{split}$ (8)

Thus the problem is reduced to a handful of twisted moment or mean value
calculations.

###  3.4. Twisted fourth moment bound for $\zeta^{(n)}(\tfrac{1}{2}+it)$

To bound the first integrands on the right-hand sides of (7) and (8), we will
require a bound for the twisted fourth moment of $\zeta(\tfrac{1}{2}+it)$.

######  Lemma 3.3.

Let $n\in\mathbb{Z}_{>0}$, and let $A(s):=\sum_{\ell\leq L}a_{\ell}\ell^{-s}$
with $a_{\ell}\in\mathbb{C}$ be a Dirichlet polynomial of length $L\ll
T^{\theta}$, $\theta<1/4$. Then

$\int_{T}^{2T}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{4}|A(\tfrac{1}{2}+it)|^{2}\
dt\ll T(\log T)^{4+4n}\max_{|z_{j}|=\frac{3^{j}}{\log
T}}|G(z_{1},z_{2},z_{3},z_{4})|,$

where

$\displaystyle G(z_{1},z_{2},z_{3},z_{4})$ $\displaystyle:=\sum_{h,k\leq
L}\frac{a_{h}\overline{a_{k}}}{[h,k]}B_{z_{1},z_{2},z_{3},z_{4}}\left(\frac{h}{(h,k)}\right)B_{z_{3},z_{4},z_{1},z_{2}}\left(\frac{k}{(h,k)}\right),$
$\displaystyle A(z_{1},\dots,z_{4}):=$
$\displaystyle\frac{\zeta(1+z_{1}+z_{3})\zeta(1+z_{1}+z_{4})\zeta(1+z_{2}+z_{3})\zeta(1+z_{2}+z_{4})}{\zeta(2+z_{1}+z_{2}+z_{3}+z_{4})},$
$\displaystyle B_{z_{1},\dots,z_{4}}$
$\displaystyle(n):=\prod_{p^{m}\|n}\left(\frac{\sum_{j\geq
0}p^{-j}\sigma_{z_{1},z_{2}}(p^{j+m})\sigma_{z_{3},z_{4}}(p^{j})}{\sum_{j\geq
0}p^{-j}\sigma_{z_{1},z_{2}}(p^{j})\sigma_{z_{3},z_{4}}(p^{j})}\right),$
$\displaystyle\quad\Delta(z_{1},\dots,z_{4}):=\prod_{1\leq j<\ell\leq
4}(z_{j}-z_{\ell}).$

###### Proof.

This adapts the proof of [8, Lem. 2]. One initially has

$\begin{split}I_{T}(\alpha_{1},\dots,\alpha_{4})&=\int_{T}^{2T}\zeta(\tfrac{1}{2}+it+\alpha_{1})\zeta(\tfrac{1}{2}+it+\alpha_{2})\zeta(\tfrac{1}{2}-it+\alpha_{3})\zeta(\tfrac{1}{2}-it+\alpha_{4})|A(\tfrac{1}{2}+it)|^{2}\
dt\\\ &=\frac{1}{(2\pi
i)^{4}}\oint\oint\oint\oint\int_{\mathbb{R}}A(z_{1},z_{2},-z_{3},-z_{4})G(z_{1},z_{2},-z_{3},-z_{4})\Delta(z_{1},z_{2},z_{3},z_{4})^{2}\\\
&\qquad\qquad\qquad\times\left(\prod_{j=1}^{4}\frac{\tau^{-\alpha_{j}/2}}{(z_{1}-\alpha_{j})(z_{2}-\alpha_{j})(z_{3}+\alpha_{j})(z_{4}+\alpha_{j})}\right)\\\
&\qquad\qquad\qquad\qquad\times\tau^{\frac{z_{1}+z_{2}-z_{3}-z_{4}}{2}}\phi(t/T)\
dt\ dz_{1}\ dz_{2}\ dz_{3}\ dz_{4}+O(T^{1-\delta}),\end{split}$ (9)

where $\tau=t/(2\pi)$, $\delta$ is a small positive quantity, the contour for
each $z_{j}$ is an anticlockwise circle $|z_{j}|=3^{j}/\log T$, and the error
term is uniform in $|\alpha_{j}|\ll 1/\log T$.

By the same argument as in [8, Lem. 2], we may differentiate $n$ times with
respect to each $\alpha_{j}$, under the integral and evaluate at
$\alpha_{1}=\dots=\alpha_{4}=0$, so that

$\begin{split}\frac{\partial^{4n}}{\partial\alpha_{1}^{n}\dots\partial\alpha_{4}^{n}}\Bigg{|}_{\alpha_{j}=0}I_{T}(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})&=\int_{T}^{2T}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{2}|A(\tfrac{1}{2}+it)|^{2}\phi(t/T)\
dt+O(T^{1-\delta}).\end{split}$

The integrand in (9) consists of factors independent of the $\alpha_{j}$, and
for each $1\leq j\leq 4$ a factor on the penultimate line depending on
$\alpha_{j}$. Write this factor as

$\tau^{-\alpha_{j}/2}(P_{4}(\alpha_{j}))^{-1}=\frac{\tau^{-\alpha_{j}/2}}{(z_{1}-\alpha_{j})(z_{2}-\alpha_{j})(z_{3}+\alpha_{j})(z_{4}+\alpha_{j})},$

so $P_{4}(\alpha_{j})$ is a degree $4$ polynomial in $\alpha_{j}$ with
coefficients depending on $z_{1},\dots,z_{4}$.

We claim that the $n$th derivative of this with respect to $\alpha_{j}$ is
$\ll(\log T)^{4+n}$. In fact, this derivative equals

$\sum_{m=0}^{n}\binom{n}{m}(-\tfrac{1}{2}\log\tau)^{k}\frac{\partial^{n-m}}{\partial\alpha_{j}^{n-m}}(P_{4}(\alpha_{j})^{-1}),$

so it suffices to show that
$\frac{\partial^{n}}{\partial\alpha_{j}^{n}}(P_{4}(\alpha_{j}))^{-1}\ll(\log
T)^{4+n}$. A Laurent expansion of $P_{4}(\alpha_{j})^{-1}$ at $\alpha_{j}=0$
then reveals that its $n$th derivative is a rational function of
$z_{1},\dots,z_{4}$ with denominator of degree $\leq n$; since
$|z_{1}|,\dots,|z_{4}|\gg 1/\log T$, this proves the claim.

By choice of contour for the $z_{j}$, one also has the bounds

$\displaystyle
A(z_{1},z_{2},-z_{3},-z_{4})\ll\log^{4}T,\quad\Delta^{2}(z_{1},z_{2},z_{3},z_{4})\ll(\log
T)^{-12}.$

Applying Jensen’s inequality to the integral expression for
$\frac{\partial^{4n}}{\partial\alpha_{1}^{n}\dots\partial\alpha_{4}^{n}}I_{T}(\alpha_{1},\dots,\alpha_{4})$,
noting that each contour for $z_{j}$ has length $\ll 1/\log T$, and collecting
logarithms proves (9). ∎

###  3.5. Applying the moment bounds

For $1\leq r\leq J$, let

$A_{r}(s):=\left(\prod_{j<r}\mathcal{N}_{j}(s,k-2)\right)\cdot\left(\frac{\mathcal{P}_{r}(\tfrac{1}{2}+it)}{50P_{r}}\right)^{\lceil
50P_{r}\rceil},$

and let $A_{J+1}(s)=\prod_{j<J+1}\mathcal{N}(s,k-2)$. In the proof of
Proposition 3 in [13, Section 6], it is shown for these choices of $A_{r}(s)$
that

$\displaystyle\max_{|z_{j}|=3^{j}/\log T}|G(z_{1},z_{2},z_{3},z_{4})|\ll(\log
T_{r})^{k^{2}-4}18^{r}r!$ $\displaystyle P_{r}^{r}e^{P_{r}}\textrm{ for }1\leq
r\leq J,$ $\displaystyle\max_{|z_{j}|=3^{j}/\log
T}|G(z_{1},z_{2},z_{3},z_{4})|\ll(\log T)^{k^{2}-4}$ $\displaystyle\textrm{
for }r=J+1$

respectively. Note that each $A_{r}$ has length $\ll T^{1/10}$. Therefore by
Lemma 3.3, for each $r$

$\int_{T}^{2T}|\zeta^{(n)}(\tfrac{1}{2}+it)|^{4}|A_{r}(\tfrac{1}{2}+it)|^{2}\
dt\ll T(\log T)^{4+4n}\max_{|z_{j}|=3^{j}/\log T}|G(z_{1},\dots,z_{4})|.$ (10)

To bound the moments of Dirichlet polynomials on the right-hand sides of (7),
(8), we have the bounds from [13, Proposition 2] (for $1\leq r\leq J$),

$\displaystyle\int_{T}^{2T}\prod_{j<r}\left|\mathcal{N}_{j}(\tfrac{1}{2}+it,k)\right|^{2}\left|\frac{\mathcal{P}_{r}(\tfrac{1}{2}+it)}{50P_{r}}\right|^{2\lceil
50P_{r}\rceil}\ $ $\displaystyle dt\ll T(\log T_{r})^{k^{2}}(r!P^{r}_{r}),$
(11)
$\displaystyle\int_{T}^{2T}\prod_{j<J+1}\left|\mathcal{N}_{j}(\tfrac{1}{2}+it,k)\right|^{2}\
dt\ll$ $\displaystyle T(\log T)^{k^{2}}.$ (12)

From Mertens’ estimates and Stirling’s approximation, for $1\leq r\leq J$,

$\displaystyle T(\log T_{r})^{k^{2}}(r!P_{r}^{r})\ll T(\log T)^{k^{2}}$
$\displaystyle e^{-10P_{r}},$ $\displaystyle T(\log T)^{4}(\log
T_{r})^{k^{2}-4}(18^{r}r!P^{r}_{r}e^{P_{r}})\ll$ $\displaystyle T(\log
T)^{k^{2}}e^{-10P_{r}}.$

Equations (5) and (6) now follow from substituting the moment bounds (10)–(12)
into (7) and (8). This proves Theorem 1.1 when $k\leq 2$.

##  4\. Upper Bounds: Proof of Theorem 1.1 for $k\geq\tfrac{1}{2}$

It suffices to prove (4). The starting point of the proof is the formula

$\zeta^{(n)}(s)=\frac{1}{n!\cdot 2\pi i}\oint_{|z|=1/\log
T}\frac{\zeta(s+z)}{z^{n+1}}dz.$

Applying Hölder’s inequality and then switching the order of the integrals
gives

$\displaystyle\mathcal{I}^{(n)}_{T}(k)$
$\displaystyle\ll\int_{T}^{2T}\left(\oint_{|z|=1/\log
T}\frac{|\zeta(\tfrac{1}{2}+it+z)|}{|z|^{n+1}}\ d|z|\right)^{2k}\ dt$
$\displaystyle\ll\int_{T}^{2T}\left(\oint_{|z|=1/\log
T}|\zeta(\tfrac{1}{2}+it+z)|^{2k}\ d|z|\right)(\log T)^{2nk+1}\ dt$
$\displaystyle\ll(\log T)^{2nk+1}\oint_{|z|=1/\log
T}\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it+z)|^{2k}\ dt$ $\displaystyle\ll(\log
T)^{2nk}\max_{|z|=1/\log T}\int_{T}^{2T}|\zeta(\tfrac{1}{2}+it+z)|^{2k}\ dt.$

This last integral may now be bounded by $\ll T(\log T)^{k^{2}}$ uniformly in
$|z|=1/\log T$. To see this, we may reduce to the case that $\textup{Re }z\geq
0$ by using the functional equation (see Lemma 22 of [1]). The claim now
follows from combining Theorem 1 of [13] (for $k\leq 2$ unconditionally) or
[12] (assuming RH) and Theorem 7.1 of [23] with Theorem 2 of [10]. While
Theorem 2 of Gabriel’s paper [10] only holds for functions analytic in a
strip, we may still use his result by approximating the indicator function of
the rectangle $1/2\leq\sigma\leq 3/2$, $T\leq t\leq 2T$ by a suitable analytic
function, see Lemma 3.5 of [2]. Alternatively, one may show this follows by a
straightforward modification of the argument in [13] for $0\leq k\leq 2$
unconditionally, or [12] for all $k\geq 0$ assuming RH. This concludes the
proof of Theorem 1.1. ∎

## References

  * [1] L. P. Arguin, P. Bourgade, and M. Radziwiłł. The Fyodorov-Hiary-Keating conjecture. I. _Preprint, arXiv:2007.00988_ , 2020.
  * [2] L. P. Arguin, F. Ouimet, and M. Radziwiłł. Moments of the Riemann zeta function on short intervals of the critical line. _Ann. Probab._ , 49(6):3106–3141, 2021.
  * [3] T. Assiotis, J. P. Keating, and J. Warren. On the joint moments of the characteristic polynomials of random unitary matrices. _Preprint, arXiv:2005.13961_ , 2020.
  * [4] E. C. Bailey, S. Bettin, G. Blower, J. B. Conrey, A. Prokhorov, M. O. Rubinstein, and N. C. Snaith. Mixed moments of characteristic polynomials of random unitary matrices. _J. Math. Phys._ , 60(8), 2019.
  * [5] E. Basor, R. Bleher, P. Buckingham, T. Grava, A. Its, E. Its, and J. P. Keating. A representation of joint moments of CUE characteristic polynomials in terms of Painlevé functions. _Nonlinearity_ , 32:4033, 2019.
  * [6] H. M. Bui and A. Florea. Negative moments of the Riemann zeta-function. _Preprint, arXiv:2302.07226_ , 2023.
  * [7] J. B. Conrey. The fourth moment of derivatives of the Riemann zeta-function. _Q. J. Math._ , 39:21–36, 1988.
  * [8] M. J. Curran. Upper bounds for fractional joint moments of the Riemann zeta function. _Acta Arith._ , 204:83–96, 2022.
  * [9] P. J. Forrester and N. S. Witte. Application of the $\tau$-function theory of Painlevé equations to random matrices: $P_{VI}$, the JUE, CyUE, cJUE and scaled limits. _Nagoya Math. J._ , 174:29–114, 2004.
  * [10] R. M. Gabriel. Some results concerning the integrals of moduli of regular functions along certain curves. _J. London Math. Soc._ , 2:112–117, 1972.
  * [11] R. R. Hall. A Wirtinger type inequality and the spacing of the zeros of the Riemann zeta-function. _J. Number Theory_ , 93(2):235–245, 2002.
  * [12] A. J. Harper. Sharp conditional bounds for moments of the Riemann zeta function. _Preprint, arXiv:1305.4618_ , 2013.
  * [13] W. Heap, M. Radziwiłł, and K. Soundararajan. Sharp upper bounds for fractional moments of the Riemann zeta function. _Q. J. Math._ , 70(4):1387–1396, 2019.
  * [14] W. Heap and K. Soundararajan. Lower bounds for moments of zeta and $L$-functions revisited. _Preprint, arXiv:2007.13154_ , 2020.
  * [15] C. P. Hughes. On the characteristic polynomial of a random unitary matrix and the Riemann zeta function. _PhD thesis, University of Bristol_ , 2000.
  * [16] A. E. Ingham. Mean-value theorems in the theory of the Riemann zeta function. _Proc. London Math. Soc._ , 27:273–300, 1926.
  * [17] J. P. Keating and N. C. Snaith. Random matrix theory and $L$-functions at $s=\tfrac{1}{2}$. _Comm. Math. Phys._ , 214(1):91–100, 2000.
  * [18] J. P. Keating and N. C. Snaith. Random matrix theory and $\zeta(\tfrac{1}{2}+it)$. _Comm. Math. Phys._ , 214:57–89, 2000.
  * [19] J. P. Keating and F. Wei. Joint moments of higher order derivatives of CUE characteristic polynomials I: asymptotic formulae. _Preprint, arXiv:2307.01625_ , 2023.
  * [20] J. P. Keating and F. Wei. Joint moments of higher order derivatives of CUE characteristic polynomials II: structures, recursive relations, and applications. _Preprint, arXiv:2307.02831_ , 2023.
  * [21] M. B. Milinovich. Moments of the Riemann zeta-function at its relative extrema on the critical line. _Bull. Lond. Math. Soc._ , 43:1119–1129, 2011.
  * [22] M. Radziwiłł and K. Soundararajan. Moments and distribution of central $L$-values of quadratic twists of elliptic curves. _Invent. Math._ , 202(3):1029–1068, 2015.
  * [23] E. C. Titchmarsh. _The Theory of the Riemann Zeta-Function_. Oxford University Press, New York, 1986.


# Aligning with Heterogeneous Preferences for
Kidney Exchange

Rachel Freedman
University of California, Berkeley
<EMAIL_ADDRESS>
###### Abstract

AI algorithms increasingly make decisions that impact entire groups of humans.
Since humans tend to hold varying and even conflicting preferences, AI
algorithms responsible for making decisions on behalf of such groups encounter
the problem of preference aggregation: combining inconsistent and sometimes
contradictory individual preferences into a representative aggregate. In this
paper, we address this problem in a real-world public health context: kidney
exchange. The algorithms that allocate kidneys from living donors to patients
needing transplants in kidney exchange matching markets should prioritize
patients in a way that aligns with the values of the community they serve, but
allocation preferences vary widely across individuals. In this paper, we
propose, implement and evaluate a methodology for prioritizing patients based
on such heterogeneous moral preferences. Instead of selecting a single static
set of patient weights, we learn a distribution over preference functions
based on human subject responses to allocation dilemmas, then sample from this
distribution to dynamically determine patient weights during matching. We find
that this methodology increases the average rank of matched patients in the
sampled preference ordering, indicating better satisfaction of group
preferences. We hope that this work will suggest a roadmap for future
automated moral decision making on behalf of heterogeneous groups.

##  1 Introduction

As AI algorithms become increasingly powerful and more widely deployed, it is
vital that they act in a way that aligns with human values. Unfortunately, in
most real-world domains, people do not unanimously agree on a single set of
“human values” that AI algorithms can model and instantiate. Instead, groups
of humans tend to hold varying and even conflicting moral preferences, and AI
algorithms responsible for making decisions on behalf of these heterogeneous
groups must aggregate and arbitrate between these preferences.

Many existing approaches to preference aggregation for AI rely on determining
a single representative objective or decision for the AI to implement [9, 16,
6]. However, humans are known for their variable and contradictory
preferences, meaning that many individuals will hold preferences that differ
greatly from the mean. Better techniques are required to model such
heterogeneous human preferences, implement them in AI algorithms, and measure
their satisfaction in practice.

One domain in which this is particularly apparent is that of kidney exchange.
In a kidney exchange, patients who need kidney transplants and have found
willing but medically incompatible donors are matched and exchange kidneys
with other such incompatible patient-donor pairs [12]. Many countries,
including the United States [7], the United Kingdom [10] and much of Europe
[4] use algorithms developed in the AI community to automate this matching.
Since the prognosis for patients who do not receive kidney transplants is
quite poor, these automated decisions have life-or-death consequences and
great moral import. It is therefore vital that these allocation decisions are
made in a way that aligns with societal values. Previous work has sought to
learn a single static utility function that kidney allocation algorithms can
use to prioritize certain types of matching [8]. However, that work disregards
the empirical heterogeneity in human ethical judgements in this domain. We
seek to instead model this heterogeneity by developing a methodology that
represents the full distribution of human judgements.

In this work, we draw on preference aggregation and social welfare theory to
design, implement and evaluate a methodology for autonomously allocating
kidneys to patients in matching markets based on the heterogeneous moral
preferences expressed by surveyed human participants. We propose an alternate
model for aggregating preferences drawn from the economics literature and an
alternate domain-specific measure of group welfare based on individual
preference rankings. We show that our proposed model, which aggregates
individual preferences into a distribution over utility functions instead of a
single function, improves the average rank of the matched kidney donations in
individuals’ preference orderings, without reducing the number of patients
that can be matched overall. Incorporating the model into this real-world AI
system leads to more beneficial outcomes according to our proposed measure of
social welfare.

We hope that this work will both highlight the preference aggregation
challenges present in many allocative AI systems, and serve as a roadmap for
developing systems that directly address these challenges in other real-world
contexts.

##  2 Kidney Exchanges

###  2.1 Graph Formulation

In a kidney exchange, patients who need a kidney transplant and donors who are
willing to donate to them but are medically incompatible can be matched with
other such patient-donor pairs [12]. For example, if the donor of pair $i$ is
compatible with the patient of pair $j$, and the donor of pair $j$ is likewise
compatible with the patient of pair $i$, they can form a matching, in which
donor $d_{i}$ donates to patient $p_{j}$ and donor $d_{j}$ donates to patient
$p_{i}$.

In the standard formulation, a kidney exchange is described by a compatibility
graph $G=\langle V,E\rangle$ [12, 13]. We construct one vertex $v$ for each
patient-donor pair, then add a directed edge $e_{i,j}$ from $v_{i}$ to $v_{j}$
if $d_{i}$ is compatible with $p_{j}$. A cycle $c$ is a possible sequence of
valid transplants, in which each donor in the cycle donates a kidney and each
patient receives one. A matching $M$ is a set of disjoint cycles. An example
compatibility graph is shown in Figure 1. Each oval in the figure represents a
vertex, and each arrow represents a directed edge signifying donor-patient
compatibility. There are two cycles in this particular compatibility graph:
$c_{A}=\\{v_{1},v_{2}\\}$ and $c_{B}=\\{v_{2},v_{3}\\}$. However, these two
cycles are not disjoint, because they share vertex $v_{2}$. The $v_{2}$ donor
cannot donate both of their kidneys, so these exchanges cannot both take
place. This compatibility graph therefore has two valid matchings,
$M_{A}=\\{c_{A}\\}$ and $M_{B}=\\{c_{B}\\}$, each with cardinality 2.

Figure 1: Example compatibility graph. Donor and patient blood types are in
parentheses and arrows indicate possible valid donations. This graph has two
valid donation cycles: $c_{A}=\\{v_{1},v_{2}\\}$ and
$c_{B}=\\{v_{2},v_{3}\\}$. However, both contain $v_{2}$, so only one set of
donations can take place.

###  2.2 Clearing Algorithm

The clearing house problem in kidney exchange is to find the optimal valid
matching, according to some utility function [1]. Finding valid matchings with
a finite limit on cycle lengths is NP-hard [1] and difficult to approximate
[3], so this problem is typically solved by formulating it as a linear program
(LP) and solving it with an LP-solver such as CPLEX.

We typically assign a weight $w_{e}$ to each edge $e$ to represent the utility
of that particular donation taking place. In the national US exchange, these
weights are set ad-hoc by a committee [15], but in this work we will adapt an
alternative method that learns these weights based on human responses to
allocation dilemmas [8]. The clearing house problem is to find the optimal
matching $M^{*}$ which maximizes some utility function
$u:M\rightarrow\mathbb{R}$. This is typically formalized as the graph-
theoretic problem of finding the maximum weighted cycle cover $u(M)=\sum_{c\in
M}\sum_{e\in c}w_{e}$. To solve this via linear programming, let $C(L)$ be the
set of all cycles of length no more than $L$, let $w_{c}=\sum_{c\in
C(L)}w_{e}$, create an activation variable $x_{c}\in{0,1}$ for each cycle
$c\in C(L)$, then solve the following linear program:

$\max\sum_{c\in C(L)}w_{c}\ x_{c}\qquad\mathit{s.t.}\qquad\sum_{c:v\in
c}x_{c}\leq 1\quad\forall v\in V.$ (1)

using an LP-solver such as CPLEX. The final matching $M$ is the set of cycles
$c$ with an activation $x_{c}=1$. If all edge weights $w_{e}$ are equal, then
solving this LP gives a maximum-cardinality matching. In cases where there are
multiple valid matchings of equivalent cardinality, such as $M_{A}$ and
$M_{B}$ in Figure 1, this LP-solver must choose between them randomly.
However, if the edge weights are set according to some utility function, then
the solution can prioritize certain types of matches. This allows us to
incorporate societal preferences.

###  2.3 Incorporating Preferences

Profile | Age | Drinking | Cancer
---|---|---|---
1 | 30 | rare | healthy
2 | 30 | frequently | healthy
3 | 30 | rare | cancer
4 | 30 | frequently | cancer
5 | 70 | rare | healthy
6 | 70 | frequently | healthy
7 | 70 | rare | cancer
8 | 70 | frequently | cancer
Table 1: Patient profile descriptions enumerated and (arbitrarily) numbered by
Freedman et al.

Previous work has attempted to improve the matching prioritization in kidney
exchanges based on sampled human ethical preferences [8]. All else equal, it
is obviously morally preferable to save lives by matching as many patient-
donor pairs as possible. However, in cases such as the one in Figure 1, there
can be multiple maximum-cardinality matchings. In this case, the algorithm
requires a utility function that distinguishes between them, ideally in a way
that aligns with human values. The US national kidney exchange attempts to do
this, but they prioritize matches in an opaque and ad-hoc fashion via
committee [15]. This excludes most of the societal members who will actually
participate in the exchange from the discussion, and leaves the committee with
the still-unsolved problem of designing a utility function that captures the
ethical preferences of an entire society. Freedman et al. propose an
alternative methodology for learning domain-relevant ethical preferences from
actual human decisions in kidney allocation dilemmas, revising the LP in Eq 1
to take these into account, and then evaluating the impact on a simulated
exchange. Our work proposes an improvement on Freedman et al.’s methodology
for aggregating preferences and evaluating results, so we will briefly outline
their full methodology here.

Freedman et al. conducted two surveys on participants from Amazon’s Mechanical
Turk platform (“MTurk”). The first survey asked participants ($N=100$) to read
a brief description of the kidney transplant waiting list process, and then
asked them to propose which patient characteristics they thought “morally
ought” to be used to prioritize patients. The three most popular categories of
responses were “age”, “health – behavioral” (including aspects of health
believed to be under personal control, such as diet and drinking), and “health
– general” (including aspects of health unrelated to kidney disease). The
second survey asked a new set of participants ($N=289$) to decide how to
allocate kidneys between pairs of fictional patient “profiles” that vary
according to these attributes. In order to make the profiles more concrete,
drinking behavior (“1 alcoholic drink per month” or “5 alcoholic drinks per
day”) was used as a proxy for behavioral health, and cancer (“skin cancer in
remission” or “no other major health problems”) was used as a proxy for
general health. For example, a sample question asked participants to choose
between “Patient W.A. [who] is 30 years old, had 1 alcoholic drink per month
(prior to diagnosis), and has no other major health problems” and “Patient
R.F. [who] is 70 years old, had 5 alcoholic drinks per day (prior to
diagnosis), and has skin cancer in remission”. They defined 8 such patient
profiles, with characteristics described in Table 1, and asked each
participant to compare each pair of profiles. We will use these profile
descriptions and this preference data in our own work.

Freedman et al. used the Bradley-Terry Model (“BT Model”) to estimate a “BT-
score” for each patient profile. The BT model assumes that each profile $x$
has an underlying score $p_{x}$ that represents the value that survey
participants collectively place on donating to a patient with that profile.
Under this model, the probability that profile $i$ will be preferred to
profile $j$ is:

$P(i>j)=\frac{p_{i}}{p_{i}+p_{j}}$ (2)

Patient profiles that are almost always selected by our survey participants
(such as profile 1 in Table 1) will therefore have the highest scores, and
profiles that are rarely selected (such as profile 8), will therefore have the
lowest scores. Freedman et al. use this model to estimate a single set of
scores based on the pooled pairwise comparisons from every survey respondent.
This allows them to aggregate all preferences into a single set of scores.

They then revised the LP from Eq 1, setting the weight of each edge $e_{i,j}$
to be the BT-score of the recipient $p_{j}$ and adding a cardinality
constraint to require that the LP still only produce maximum-cardinality
matchings. Let $w_{BT(v)}$ be the BT-score of the patient in vertex $v$, and
let $Q$ be the maximum matching cardinality possible for the compatibility
graph. Then the revised LP is:

$\begin{array}[]{lll}\max&\sum_{c\in C(L)}\left[\sum_{(u,v)\in
c}w_{BT(v)}\right]\ x_{c}&\\\ \mathrm{s.t.}&\sum_{c:v\in c}x_{c}\leq 1&\forall
v\in V\\\ &\sum_{c\in C(L)}|c|x_{c}\geq Q&\\\ \end{array}$ (3)

They evaluated this revised algorithm on a simulated kidney exchange and found
that it matched significantly more of the higher-scoring profiles and
significantly fewer of the lower-scoring ones. However, this methodology
relies on the assumption that societal preferences are sufficiently
homogeneous to be captured by a single static utility function. An algorithm
using this methodology will always choose to save a patient of profile 1 over
a patient of profile 2. However, the preferences expressed in the survey data
actually varied greatly, and participants did sometimes prefer patients of
profile 2 to profile 1. Presumably the preferences of a representative sample
of the actual US population would be even more heterogeneous. In this sense,
both the static profile scoring and the assessment of the algorithm by the
proportion of each profile matched are flawed. In this work, we improve upon
both of these elements by removing the requirement for a single utility
function and developing an alternate methodology for modifying and evaluating
the algorithm.

##  3 Incorporating Heterogeneous Preferences

In our work we improve upon the methodology presented in Section 2.3 by
removing the unrealistic assumption that societal preferences can be captured
by a single utility function. We propose 1) an alternative preference
aggregation method that better captures the variation in expressed
preferences, 2) modifications to the kidney allocation algorithm to take this
new preference aggregation into account, and 3) an alternative evaluation
metric for the resulting matchings that lends more consideration to individual
welfare.

###  3.1 Preference Aggregation Model: BLP

Instead of learning a single score for each profile as in previous work [8],
we use the Berry-Levinsohn-Pakes Model (“BLP Model”) to estimate a
distribution over possible utility functions. We propose that learning and
sampling from this distribution better satisfies individual preferences than
learning a single utility function. The BLP model is an extension of the logit
discrete choice model that is widely used in estimating consumer discrete-
choice demand for differentiated products [2, 11]. When we apply this model to
kidney exchange, the “consumers” are members of the population that the
exchange serves, and the “products” are the patients who may potentially be
matched with donors. Using this model allows us to predict how the general
population wants the exchange to prioritize patients.

For a graph $G=\langle V,E\rangle$, we wish to define a utility function
$\mathcal{U}:V\rightarrow\mathbb{R}$ that determines the utility of the
patient in each vertex receiving a utility function. The BLP model defines the
utility function $\mathcal{U}(v)=X_{p(v)}^{\top}\beta+\epsilon$ where
$X_{p(v)}=\\{\mathbbm{1}(v_{age}=30),\mathbbm{1}(v_{drinking}=rare),\mathbbm{1}(v_{cancer}=healthy)\\}$
are the binary features of the patient profile of vertex $v$,
$\beta\sim\mathcal{N}(\mu,\Sigma)$ gives the weight of each feature, and
$\epsilon$ is an error term following a type-II extreme value distribution.

We use maximum likelihood estimation to fit the distribution parameters
$(\mu,\Sigma)$ to the pairwise comparison survey data gathered by Freedman et
al. Let $P$ be the set of all patient profiles described in Table 1, and for
each pair of profiles $i,j\in P$, let $c_{k}(i,j)$ be survey respondent $k$’s
preferred profile. This allows us to define the likelihood function

$L_{k}(\mu,\Sigma\mid
c_{k})=\mathbb{E}_{\beta\sim\mathcal{N}(\mu,\Sigma)}\left[\prod_{i,j}{\frac{\exp(X_{c_{k}(i,j)}^{\top}\beta)}{\exp(X_{i}^{\top}\beta)+\exp(X_{j}^{\top}\beta)}}\right]$
(4)

and to estimate the maximum likelihood distribution parameters

$\hat{\mu},\hat{\Sigma}=\underset{\mu,\Sigma}{argmax}{\frac{1}{N}\sum_{k=1}^{N}\mathrm{log}({L_{k}(\mu,\Sigma\mid
c_{k}))}}$ (5)

###  3.2 Algorithm

Each time a new patient-donor pair enters the exchange, we add a corresponding
vertex $u$ to the graph, randomly sample a
$\beta_{u}\sim\mathcal{N}(\hat{\mu},\hat{\Sigma})$ from the learned
distribution, and weight outgoing edges $u\rightarrow v$ using the resulting
“BLP function”: $BLP(u,v)=X_{p(v)}^{\top}\beta_{u}+\epsilon_{uv}$. In this
way, we represent the full distribution of preferences. Note that the BLP
function indicates a random sample from the surveyed population’s preference
distribution – it does not represent the preferences of donor $u$
specifically. Letting $w_{BLP(u,v)}$ be the score that vertex $u$’s sampled
BLP function places on donating to the patient in vertex $v$, we modify the LP
in Eq 3 to be:

$\begin{array}[]{lll}\max&\sum_{c\in C(L)}\left[\sum_{(u,v)\in
c}w_{BLP(u,v)}\right]\ x_{c}&\\\ \mathrm{s.t.}&\sum_{c:v\in c}x_{c}\leq
1&\forall v\in V\\\ &\sum_{c\in C(L)}|c|x_{c}\geq Q&\\\ \end{array}$ (6)

###  3.3 Evaluation Metric

We further define the $rank$ of a donation $u\rightarrow v$ to be the position
of $v$’s patient profile in the preference ordering induced by $u$’s BLP
function. For example, if the BLP function associated with vertex $u$ weights
the profile of the patient in vertex $v$ above all other profiles,
$rank(u,v)=1$. Conversely, if the BLP function weights the profile below the
other seven possible patient profiles, $rank(u,v)=8$. In this context, rank
functions as a proxy for individual welfare because it represents the extent
to which an individual’s domain-relevant values were fulfilled. We claim that
the average rank of matched donations is a better measure of the extent to
which an algorithm values individual welfare than the proportion of each
profile matched because the ranks of all matches depend on the full BLP
distribution. In contrast, the proportion matched measure relies on the false
assumption that everyone’s preferences are better satisfied if patients with
higher BT-scores are matched more often.

We run both algorithms on a simulated kidney exchange, along with a third
algorithm that weights all donations equally as a baseline. We evaluate the
resulting matchings both on the proportion of each profile matched, and on our
proposed average rank measure. We find that our proposed algorithm
consistently outperforms both others on the rank measure, suggesting that it
better represents the full distribution of societal preferences.

##  4 Experiments

###  4.1 Conditions

We tested three versions of the matching algorithm: the baseline one that
weights all donations equally, the one with a single utility function
described in Section 2.3, and one with a distribution over utility functions
proposed in Section 3.1.

#### Condition 1: EQUAL

The EQUAL algorithm matches kidney exchange participants using the LP in Eq 1.
That is, it weights all participants equally and chooses randomly amongst the
highest-cardinality matchings. We use this condition as a baseline because it
describes the case in which ethical preferences are not incorporated into the
algorithm at all.

#### Condition 2: HOMOGENEOUS

The HOMOGENEOUS algorithm matches participants using the LP in Eq 3. It
assigns edge weights based on the BT-score of the recipient, relying on the
assumption that individual preferences are sufficiently homogeneous to be
captured by a single static utility function. This is the algorithm proposed
by Freedman et al.. See Table 2 for the weights used in the EQUAL  and
HOMOGENEOUS  conditions.

#### Condition 3: HETEROGENEOUS

The HETEROGENEOUS algorithm matches participants using the LP in Eq 6. It
samples a BLP function when each vertex is added to the graph, normalizes the
scores produced by that function to the range $[0,1]$, and uses that function
and the profile of the recipient to weight each new outgoing edge. This allows
for the possibility that heterogeneous individual preferences are better
captured by a distribution than by a single utility function. This is the
novel algorithm that we propose in this work.

Profile ID | EQUAL | HOMOGENEOUS
---|---|---
1 | 1.000 | 1.000
2 | 1.000 | 0.103
3 | 1.000 | 0.236
4 | 1.000 | 0.036
5 | 1.000 | 0.070
6 | 1.000 | 0.012
7 | 1.000 | 0.024
8 | 1.000 | 0.003
Table 2: Patient profile weights for the EQUAL and HOMOGENEOUS experimental
conditions. The EQUAL algorithm values all profiles equally, so all have
weight $1.0$. However, the HOMOGENEOUS algorithm weights profiles according to
their BT-scores. The HETEROGENEOUS algorithm samples BLP functions throughout
matching and so does not have a static weight for each profile.

###  4.2 Measures

We evaluate each algorithm according to both the measure we propose in Section
3 and the measure used by Freedman et al.

#### Average Rank

The average rank of a matching is the average rank of each donation in the
matching, where $rank(u,v)$ of a donation $u\rightarrow v$ is as defined in
Section 3.3. Recall that lower ranks indicate higher preference satisfaction
and, since there are 8 profiles, all possible ranks fall in the range
$[1.0,8.0]$. For each run of each algorithm, we recorded the average rank of
every matching in the simulation, then averaged these to get the average rank
value for that algorithm.

#### Proportion Matched

The proportion matched of a profile is the proportion of patients of that type
that entered the kidney exchange pool and were subsequently matched. A
proportion matched of $100\%$ means that all patients of that type were
matched, and a proportion matched of $0\%$ means that none were. For each run
of each algorithm, we recorded the number of patients with each profile that
entered the pool and the number of patients of each profile that were
eventually matched, and used this to calculate proportion matched.

###  4.3 Experimental Setup

We built a simulator111All code for this paper can be found in the Variation
package of github.com/RachelFreedman/KidneyExchange to mimic daily matching
using the EQUAL, HOMOGENEOUS, or HETEROGENEOUS algorithms based on previously
developed tools [7, 8]. Each simulated “day”, some pairs enter the pool, some
pairs exit the pool, and then the matching algorithm is run on the pairs that
remain. The unmatched pairs remain in the pool to potentially be matched in
the future. For each algorithm, we executed 50 runs of 5 years of simulated
daily matching, and recorded the average matching rank and profile proportions
matched for each run.

##  5 Results

#### Average Rank

Since lower donation ranks indicate that the recipient is higher in the
sampled preference ordering, we propose that algorithms that induce lower
average ranks better satisfy population preferences. As expected, the proposed
HETEROGENEOUS algorithm consistently produces matchings with the lowest
average rank (Figure 2). The HOMOGENEOUS algorithm produces the next-lowest
average rank, followed by the EQUAL algorithm, which produces the highest
average rank. This is because the EQUAL algorithm weights all edges equally,
matching recipients without any consideration of the personal characteristics
used to define their weight. The HOMOGENEOUS algorithm improves upon this by
considering the characteristics of donation recipients, but fails to
approximate preferences as closely as HETEROGENEOUS.

Figure 2: Average rank of donations in each simulated run ($N=50$). Lower
ranks indicate more-preferred matches. The HETEROGENEOUS algorithm produces
the lowest average ranks (median = $3.24$), followed by the HOMOGENEOUS
algorithm (median = $3.66$), then the EQUAL algorithm (median = $4.06$).

#### Proportion Matched

Freedman et al. quantified the impact of their modified algorithm by comparing
the proportions of patients of each profile type matched by their algorithm
against the proportions matched by the unmodified algorithm, so for the sake
of comparison we do the same. The proportions of each profile matched by the
EQUAL algorithm, the HOMOGENEOUS algorithm (proposed by Freedman et al.) and
the HETEROGENEOUS algorithm (proposed in this work) are shown in Figure 3.

Since it doesn’t take patient profiles into account, the EQUAL algorithm
matched approximately the same percentage of patients across all profiles.
Since it prioritizes patients solely based on profile, the HOMOGENEOUS
algorithm matched the more popular profiles (1-3) more often and the less
popular profiles (4-8) less. Notably, the HOMOGENEOUS algorithm almost always
matches patients of profile 1, indicating that a patient’s profile can be one
of the major factors in determining whether they receive a kidney. However,
the HETEROGENEOUS algorithm prioritizes patients not directly based on their
profile, but based on the sampled BLP function’s valuation of their profile.
As a result, this algorithm still tends to match more of the commonly-
preferred profiles and fewer of the commonly-dispreferred ones, but sometimes
samples a BLP function from the tails of the distribution that prioritizes
patient profiles very differently.

If the survey preferences had been completely homogeneous, then the
HETEROGENEOUS algorithm would have produced the same results as the
HOMOGENEOUS algorithm. However, because preferences expressed in the survey
data sometimes differ from the utility function used for the HOMOGENEOUS
algorithm, sometimes different matches are made. For example, while most
survey participants preferred patient profile 1 to all other profiles, some
did not, so the HETEROGENEOUS algorithm respects this heterogeneity by
sometimes prioritizing matching other profiles over profile 1. This difference
in matching is a further indication that our proposed algorithm more
faithfully represents the full distribution over preferences.

Figure 3: Proportion of patients of each profile matched in each simulated run
($N=50$). All algorithms match approximately $62\%$ of patients overall, but
the HOMOGENEOUS algorithm disproportionately matches profiles with higher BT-
scores, the EQUAL algorithm matches all profiles approximately equally, and
the proportions matched by the HETEROGENEOUS algorithm lie between the other
two.

##  6 Discussion

Faithfully instantiating the collective values of groups with heterogeneous
individual preferences is a frequent challenge for real-world AI systems. For
example, we commonly use AI systems to allocate scarce resources – such as
kidney donors, food donations [9] and interview slots [14] – amongst group
members in a way that we hope maximizes group welfare. Moreover, our roads may
soon be populated with autonomous vehicles, which will have to make moral
tradeoffs – such determining who to sacrifice in unavoidable collisions [5] –
based on the complex and often contradictory moral frameworks of the
communities in which they operate. It is therefore vital that the AI community
develop techniques for faithfully aggregating such heterogeneous preferences
and use them to develop socially beneficial AI systems.

In this paper, we proposed, instantiated, and evaluated one such technique for
incorporating heterogeneous ethical preferences into a specific real-world AI
system: an algorithm for matching patient-donor pairs in kidney exchange.
Instead of weighting all potential kidney recipients equally, deciding how to
prioritize them in an opaque and ad-hoc way [15], or prioritizing them based
on a single static utility function [8], we proposed learning a distribution
over surveyed preferences and then sampling from this distribution for dynamic
weighting during matching. We furthermore proposed donation rank as a better
measure of preference satisfaction. We implemented our proposed algorithm and
compare it to predecessor algorithms on a kidney exchange simulation, finding
that our algorithm better satisfies survey participant preferences.

Our model was estimated based on preference data elicited from MTurk survey
participants, who are assuredly not representative of society in general.
Future work should elicit preferences from a more representative sample, and
perhaps privilege preferences expressed by domain experts and stakeholders
such as doctors, policy-makers and kidney exchange participants. However, we
believe that our sample was not more heterogeneous than the US population as a
whole, so we expect the challenge of heterogeneity and our methodology to
continue to be relevant for this expanded sample. Moreover, since even a
representative sample of the general public would still lack relevant domain-
specific knowledge about kidney transplants, future work should also
investigate methodologies that allow domain experts to correct or moderate the
outcomes of this process.

We hope that the challenges highlighted and methodology prototyped in this
work will suggest a roadmap for developing techniques for automating moral
decision making in other domains.

## Acknowledgements

We thank Yunhao Huang for implementing the BLP model, the Duke Moral AI team
for sharing the human subject data, Dr. John Dickerson for building an earlier
version of the kidney exchange simulation, and Dr. Peter Eckersley for early
discussions of the idea.

## References

  * Abraham et al. [2007] David J Abraham, Avrim Blum, and Tuomas Sandholm.  Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges.  In Proceedings of the 8th ACM conference on Electronic commerce, pages 295–304, 2007.
  * Berry et al. [1995] Steven Berry, James Levinsohn, and Ariel Pakes.  Automobile prices in market equilibrium.  Econometrica: Journal of the Econometric Society, pages 841–890, 1995.
  * Biro and Cechlarova [2007] Peter Biro and Katarina Cechlarova.  Inapproximability of the kidney exchange problem.  Information Processing Letters, 101(5):199–202, 2007.
  * Biró et al. [2017] Péter Biró, Lisa Burnapp, Bernadette Haase, Aline Hemke, Rachel Johnson, Joris van de Klundert, and David Manlove.  Kidney exchange practices in Europe, 2017.  First Handbook of the COST Action CA15210: European Network for Collaboration on Kidney Exchange Programmes.
  * Bonnefon et al. [2016] Jean-François Bonnefon, Azim Shariff, and Iyad Rahwan.  The social dilemma of autonomous vehicles.  Science, 352(6293):1573–1576, 2016.
  * Conitzer et al. [2015] Vince Conitzer, Markus Brill, and Rupert Freeman.  Crowdsourcing societal tradeoffs.  In Proceedings of the 2015 international conference on autonomous agents and multiagent systems, pages 1213–1217, 2015.
  * Dickerson and Sandholm [2015] John P Dickerson and Tuomas Sandholm.  Futurematch: Combining human value judgments and machine learning to match in dynamic environments.  In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015\.
  * Freedman et al. [2020] Rachel Freedman, Jana Schaich Borg, Walter Sinnott-Armstrong, John P Dickerson, and Vincent Conitzer.  Adapting a kidney exchange algorithm to align with human values.  Artificial Intelligence, page 103261, 2020.
  * Lee et al. [2018] Min Kyung Lee, Daniel Kusbit, Anson Kahng, Ji Tae Kim, Xinran Yuan, Allissa Chan, Ritesh Noothigattu, Daniel See, Siheon Lee, Christos-Alexandros Psomas, et al.  Webuildai: Participatory framework for fair and efficient algorithmic governance.  Preprint, 2018.
  * Manlove and O’Malley [2015] David Manlove and Gregg O’Malley.  Paired and altruistic kidney donation in the UK: Algorithms and experimentation.  ACM Journal of Experimental Algorithmics, 19(1), 2015.
  * Nevo [2001] Aviv Nevo.  Measuring market power in the ready-to-eat cereal industry.  Econometrica, 69(2):307–342, 2001.
  * Roth et al. [2004] Alvin E Roth, Tayfun Sönmez, and M Utku Ünver.  Kidney exchange.  The Quarterly journal of economics, 119(2):457–488, 2004.
  * Roth et al. [2005] Alvin E Roth, Tayfun Sönmez, et al.  A kidney exchange clearinghouse in new england.  American Economic Review, 95(2):376–380, 2005.
  * Schumann et al. [2019] Candice Schumann, Zhi Lang, Jeffrey Foster, and John Dickerson.  Making the cut: A bandit-based approach to tiered interviewing.  In Advances in Neural Information Processing Systems, pages 4641–4651, 2019.
  * UNOS [2015] UNOS.  Revising kidney paired donation pilot program priority points, 2015.  OPTN/UNOS Public Comment Proposal.
  * Zhang and Conitzer [2019] Hanrui Zhang and Vincent Conitzer.  A pac framework for aggregating agents’ judgments.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2237–2244, 2019.


is symmetric. If $m(X)-m(\mathcal{D})\geq r$ then we sample from the
distribution $\left(1-\frac{rL}{2}\right)\mathcal{D}^{\prime}$ conditional on
being on the right of $m(X)$. If $m(X)-m(\mathcal{D})\leq r$ then we first
flip a coin $B_{i}\overset{d}{=}\mathrm{Bernoulli}(\frac{rL}{2})$ and with
probability $\frac{rL}{2}$ (that is when $B_{i}=1$) we sample from
$\mathrm{Unif}[m(\mathcal{D})-r,m(\mathcal{D})+r]$ conditional on being on the
right of $m(X)$ and with probability $1-\frac{rL}{2}$ (that is when $B_{i}=0$)
we sample from some distribution $\mathcal{D}^{\prime}$ conditional on being
on the right of $m(X)$.

Third, observe that both the event of interests in the statement Lemma B.3 of
becomes less probable when we restrict ourselves to only a subset of the $n$
samples. Hence, since we want to prove a lower bound on the probability of the
event we can restrict ourselves to an arbitrary subset.

Now, using (B.4) by neglecting an event of probability
$2e^{-nL^{2}r^{2}/8}\leq e^{-\Theta\left(L^{2}r^{2}n\right)}$ from now on we
condition on $|m(X)-m(\mathcal{D})|\leq r/2$. Now using the three observations
above, we restrict ourselves only on the $n_{1}\leq n$ samples that satisfy
$B_{i}=C_{i}=1$, that is they are samples from
$\mathrm{Unif}[m(\mathcal{D})-r,m(\mathcal{D})+r]$ conditional on being on the
right of $m(X)$. We denote these samples by $X_{1},\ldots,X_{n_{1}}$ for
simplicity. Notice that $\mathrm{Unif}[m(\mathcal{D})-r,m(\mathcal{D})+r]$
conditional on being on the right of $m(X)$ is just distributed as
$\mathrm{Unif}[m(X),m(\mathcal{D})+r]$. Hence, conditioning on the value of
$n_{1}$, the density of the conditional distribution of each
$X_{1},\ldots,X_{n_{1}}$ given the $m(X)$ can be straightforwardly check to
satisfy for each $i=1,2,\ldots,n_{1},$

$\frac{2}{3r}\leq f_{X_{i}}(u|m(X),|m(X)-m(\mathcal{D})|\leq
r/2)\leq\frac{2}{r},u\in[m(X),m(\mathcal{D})+r].$ (B.6)

Combining the above, to prove our result it suffices to prove

$\displaystyle\mathbb{P}\left(\bigcap_{\kappa\in[T,\frac{Lr}{2C}n]\cap\mathbb{Z}}\sum_{i\in[n_{1}]}\mathbf{1}\\{X_{i}-m(X)\in[0,\frac{C\kappa}{Ln}]\\}\geq\kappa+1\right)\geq
1-O\left((8Ce\exp\left(-\frac{C}{8}\right)))^{\lceil
T\rceil}+e^{-\Theta\left(L^{2}r^{2}n\right)}\right).$

Since $m(X)=X_{i}$ for some $i$ by definition of the left empirical median, it
suffices to prove that for

$J_{\kappa}\mathrel{\mathop{\mathchar
58\relax}}=(m(X),m(X)+\frac{C\kappa}{Ln}],\text{ }\kappa=\lceil T\rceil,\lceil
T\rceil+1,\ldots,\lfloor\frac{Lr}{2C}n\rfloor-1$

and sequence of events

$A_{\kappa}\mathrel{\mathop{\mathchar
58\relax}}=\\{\sum_{i\in[n_{1}]}\mathbf{1}\\{X_{i}\in
J_{\kappa}\\}\geq\kappa\\},\text{ }\kappa=\lceil T\rceil,\lceil
T\rceil+1,\ldots,\lfloor\frac{Lr}{2C}n\rfloor-1$

it holds

$\mathbb{P}\left(\bigcap_{\kappa=\lceil
T\rceil}^{\lfloor\frac{Lr}{2C}n\rfloor-1}A_{\kappa}\bigg{|}|m(X)-m(\mathcal{D})|\leq
r/2\right)\geq 1-O\left((8Ce\exp\left(-\frac{C}{8}\right)))^{\lceil
T\rceil}+e^{-\Theta\left(L^{2}r^{2}n\right)}\right)).$

Using a union bound it suffices to show

$\sum_{\kappa=\lceil
T\rceil}^{\lfloor\frac{Lr}{2C}n\rfloor-1}\mathbb{P}\left(A^{c}_{\kappa}\cap\bigcap_{s=\lceil
T\rceil}^{\kappa-1}A_{s}\bigg{|}|m(X)-m(\mathcal{D})|\leq r/2\right)\leq
O\left((8Ce\exp\left(-\frac{C}{8}\right)))^{\lceil
T\rceil}+e^{-\Theta\left(L^{2}r^{2}n\right)}\right).$

Observe that as we are conditioning on $|m(X)-m(\mathcal{D})|\leq r/2$ for all
$\kappa$ of interest

$J_{\kappa}\subseteq[m(\mathcal{D})-r,m(\mathcal{D})+r].$

Hence using (B.6) we have that, conditioned on $n_{1}$, for each $i\in[n_{1}]$
and $\kappa$,

$\mathbb{P}\left(X_{i}\in J_{\kappa}|m(X),|m(X)-m(\mathcal{D})|\leq
r/2\right)\in[\frac{2}{3r}|J_{\kappa}|,\frac{2}{r}|J_{\kappa}|].$ (B.7)

Furthermore recall that
$n_{1}\overset{d}{=}\mathrm{Binom}\left(\lfloor\frac{n-1}{2}\rfloor,\frac{Lr}{2}\right)$
and that it holds $\kappa\leq\frac{Lrn}{2C}.$ Since $C>5$ by standard
concentration inequalities, we have that with probability
$1-e^{-\Theta\left(L^{2}r^{2}n\right)},$ it holds for all $\kappa$ of interest

$\kappa<\frac{Lrn}{9}<\frac{n_{1}}{2}<Lrn.$ (B.8)

In what follows we condition on the event (B.8). Suppose $\kappa=\lceil
T\rceil$. Then using (B.7) by definition the probability of $A^{c}_{\lceil
T\rceil}$ is at most the probability a sample from a binomial distribution
with $N\mathrel{\mathop{\mathchar 58\relax}}=n_{1}$ draws and probability
$\frac{2}{r}|J_{\lceil T\rceil}|=\frac{2C\lceil T\rceil}{nLr}$ is at most
$\lceil T\rceil$. Now conditioning on $n_{1}$ and denoting the Binomial random
variable by $Z$ we have by the additive form of the Chernoff’s inequality,

$\displaystyle\mathbb{P}\left(A^{c}_{\lceil
T\rceil}\bigg{|}m(X),|m(X)-m(\mathcal{D})|\leq r/2,n_{1}\right)$
$\displaystyle\leq\mathbb{P}\left(Z\leq\lceil T\rceil\right)$
$\displaystyle\leq\exp\left(-\frac{\left(\frac{2n_{1}C\lceil
T\rceil}{Lnr}-\lceil T\rceil\right)^{2}}{2n_{1}\frac{2C\lceil
T\rceil}{Lnr}\left(1-\frac{2C\lceil T\rceil}{Lnr}\right)}\right)$

Using now that we condition on (B.8) it holds $\frac{2Lnr}{9}<n_{1}<2Lrn$ and
$T<\frac{Lnr}{4C}$ we have

$\displaystyle\mathbb{P}\left(A^{c}_{\lceil
T\rceil}\bigg{|}|m(X)-m(\mathcal{D})|\leq r/2\right)$
$\displaystyle=\mathbb{E}_{m(X),n_{1}}\left[\mathbb{P}\left(A^{c}_{\lceil
T\rceil}\bigg{|}m(X),|m(X)-m(\mathcal{D})|\leq r/2,n_{1}\right)\right]$
$\displaystyle\leq\exp\left(-\frac{\left(\frac{4}{9}C-1\right)^{2}\lceil
T\rceil^{2}}{2C\lceil T\rceil}\right)$

which since $C>5>\frac{9}{7}$ gives that

$\displaystyle\mathbb{P}\left(A^{c}_{\lceil
T\rceil}\bigg{|}|m(X)-m(\mathcal{D})|\leq r/2\right)$
$\displaystyle\leq\exp\left(-\frac{C\lceil T\rceil}{8}\right).$ (B.9)

Now for every $\kappa>\lceil T\rceil$ notice that the event
$A^{c}_{\kappa}\cap\bigcap_{s=0}^{\kappa-1}A_{s}$ can happen if and only if
$\kappa$ of the samples belong in $J_{\kappa-1}$ and the rest $n_{1}-\kappa$
samples belong to $J^{c}_{\kappa}$. Therefore using the above observations and
(B.7),

$\displaystyle\mathbb{P}\left(A^{c}_{\kappa}\cap\bigcap_{s=\lceil
T\rceil}^{\kappa-1}A_{s}\bigg{|}m(X),|m(X)-m(\mathcal{D})|\leq
r/2,n_{1}\right)$
$\displaystyle\leq\binom{n_{1}}{\kappa}\left(\frac{2}{r}|J_{\kappa-1}|\right)^{\kappa}\left(1-\frac{2}{3r}|J_{\kappa}|\right)^{n_{1}-\kappa}$
$\displaystyle\leq\binom{n_{1}}{\kappa}\left(\frac{2C(\kappa-1)}{nLr}\right)^{\kappa}\left(1-\frac{2C\kappa}{3Lrn}\right)^{n_{1}-\kappa}$
$\displaystyle\leq\left(\frac{n_{1}e}{\kappa}\right)^{\kappa}\left(\frac{2C\kappa}{Lrn}\right)^{\kappa}\exp\left(-C\frac{2(n_{1}-\kappa)\kappa}{3Lrn}\right)$
$\displaystyle\leq\left(2Ce\frac{n_{1}}{Lrn}\right)^{\kappa}\exp\left(-C\frac{2(n_{1}-\kappa)\kappa}{3Lrn}\right),$

where we used the elementary inequalities
$\binom{m}{m^{\prime}}\leq\left(\frac{me}{m^{\prime}}\right)^{m^{\prime}}$,
$1+x\leq e^{x}$ and that by definition $n_{1}\leq n.$

The last displayed inequality conditioned on the event (B.8) implies

$\displaystyle\mathbb{P}\left(A^{c}_{\kappa}\cap\bigcap_{s=\lceil
T\rceil}^{\kappa-1}A_{s}\bigg{|}|m(X)-m(\mathcal{D})|\leq r/2\right)$
$\displaystyle=\mathbb{E}_{m(X),n_{1}}\left[\mathbb{P}\left(A^{c}_{\kappa}\cap\bigcap_{s=0}^{\kappa-1}A_{s}\bigg{|}m(X),|m(X)-m(\mathcal{D})|\leq
r/2,n_{1}\right)\right]$
$\displaystyle\leq\mathbb{E}_{n_{1}}\left[\left(4Ce\right)^{\kappa}\exp\left(-\frac{2C}{3}\frac{(n_{1}-\frac{n_{1}}{2})\kappa}{Lrn}\right)\right]$
$\displaystyle\leq\mathbb{E}_{n_{1}}\left[\left(4Ce\right)^{\kappa}\exp\left(-\frac{2C}{3}\frac{\frac{n_{1}}{2}\kappa}{Lrn}\right)\right]$
$\displaystyle\leq\mathbb{E}_{n_{1}}\left[\left(4Ce\right)^{\kappa}\exp\left(-\frac{2C}{27}\kappa\right)\right]$
$\displaystyle=\left(4Ce\exp\left(-\frac{2C}{27}\right)\right)^{\kappa}$
(B.10)

Using (B.9) for the first term and since
$4Ce\exp\left(-\frac{2C}{27}\right)<1/2$ a geometric summation over
$\kappa\geq\lceil T\rceil$ for the rest terms, we have that conditional on
(B.8),

$\displaystyle\sum_{\kappa=\lceil
T\rceil}^{\lfloor\frac{Lr}{2C}n\rfloor-1}\mathbb{P}\left(A^{c}_{\kappa}\cap\bigcap_{s=\lceil
T\rceil}^{\kappa-1}A_{s}\bigg{|}|m(X)-m(\mathcal{D})|\leq r/2\right)$
$\displaystyle\leq\exp\left(-\frac{C\lceil
T\rceil}{8}\right)+(8Ce\exp\left(-\frac{2C}{27}\right))^{\lceil T\rceil}.$

Taking now into account the probability of the conditioned event we have
(B.8),

$\displaystyle\sum_{\kappa=\lceil
T\rceil}^{\lfloor\frac{Lr}{2C}n\rfloor-1}\mathbb{P}\left(A^{c}_{\kappa}\cap\bigcap_{s=\lceil
T\rceil}^{\kappa-1}A_{s}\bigg{|}|m(X)-m(\mathcal{D})|\leq r/2\right)$
$\displaystyle\leq\exp\left(-\frac{C\lceil
T\rceil}{8}\right)+(8Ce\exp\left(-\frac{2C}{27}\right))^{\lceil
T\rceil}+e^{-\Theta\left(L^{2}r^{2}n\right)}$ $\displaystyle\leq
2(8Ce\exp\left(-\frac{C}{8}\right))^{\lceil
T\rceil}+e^{-\Theta\left(L^{2}r^{2}n\right)}$

where in the last line since $\frac{C}{8}>\frac{2C}{27}$ and $8Ce>1$ under our
assumptions it holds for all $T\geq 0$

$\exp\left(-\frac{C\lceil
T\rceil}{8}\right)+(8Ce\exp\left(-\frac{2C}{27}\right))^{\lceil T\rceil}\leq
2(8Ce\exp\left(-\frac{C}{8}\right))^{\lceil T\rceil}.$

The proof is complete.

∎

###  B.5 Proof of Theorem 3.6

We establish instead the following slightly more general result which does not
assume that $C$ is a constant, but could scale with $n$.

######  Theorem B.5.

Suppose $C>0$, possibly scaling with $n$, is bigger than a sufficiently large
constant, $\varepsilon\in(0,1)$, $\mathcal{D}$ is an admissible distribution
and $\mathcal{A}$ is the $\varepsilon$-differentially private algorithm
defined above. Then for any $\alpha\in(0,r)$ and $\beta\in(0,1)$ for some

$n=O\left(\frac{\log\left(\frac{1}{\beta}\right)}{L^{2}\alpha^{2}}+C\frac{\log\left(\frac{1}{\beta}\right)}{\varepsilon
L\alpha}+\frac{\log\left(\frac{R}{\alpha}+1\right)}{\varepsilon Lr}\right)$

it holds
$\quad\quad\quad\mathbb{P}_{X_{1},X_{2},\ldots,X_{n}\overset{iid}{\sim}\mathcal{D}}[|\mathcal{A}(X_{1},\ldots,X_{n})-m\left(\mathcal{D}\right)|\geq\alpha]\leq\beta.$

###### Proof.

Let $X=(X_{1},\ldots,X_{n})$ the $n$-tuple of i.i.d. samples from
$\mathcal{D}.$ Let us use a parameter $\gamma\in(0,1)$ which we later choose a
polynomial function of $\beta.$ We consider the event

$\mathcal{T}_{\gamma}\mathrel{\mathop{\mathchar 58\relax}}=\\{\exists
X^{\prime}\in\mathcal{H}\text{ s.t. }d_{H}\left(X,X^{\prime}\right)\leq
C^{\prime}\log\frac{1}{\gamma},m(X^{\prime})=m(X)\\},$

where $C^{\prime}=C^{\prime}(C)$ is chosen to satisfy the conclusion of Lemma
B.4. In particular it holds $C^{\prime}(C)=\Theta(\frac{1}{C})$ as $C$ grows
to infinity.

Notice that since $\alpha\leq r$ for some
$n=O\left(\frac{\log\frac{1}{\gamma}}{L^{2}\alpha^{2}}\right)$ it holds $n\geq
D\frac{\log\frac{1}{\gamma}}{L^{2}r^{2}}$ for the $D>0$ defined in Lemma B.4.
Furthermore, we can assume $C>5$ is sufficiently large such that
$4Ce\exp\left(-\frac{2C}{27}\right)<1/2$. Hence, by applying Lemma B.4 we have

$\displaystyle\mathbb{P}\left[|\mathcal{A}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha\right]$
$\displaystyle\leq\mathbb{P}\left[|\mathcal{A}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha,X\in\mathcal{T}_{\gamma}\right]+\mathbb{P}\left[X\not\in\mathcal{T}_{\gamma}\right]$
$\displaystyle\leq\mathbb{P}\left[|\mathcal{A}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha|X\in\mathcal{T}_{\gamma}\right]+\gamma.$
(B.11)

Now conditioning on $X\in\mathcal{T}_{\gamma}$ we have that there exists an
$X^{\prime}\in\mathcal{H}$ with $d_{H}\left(X,X^{\prime}\right)\leq
C^{\prime}\log\frac{1}{\gamma}$ and $m(X^{\prime})=m(X)$. Since the algorithm
$\mathcal{A}$ is $\varepsilon$-differentially private by its definition, we
have that $\mathcal{A}(X)$ and $\mathcal{A}(X^{\prime})$ assigns to each
output value the same probability mass up to a multiplicative factor of
$e^{\varepsilon d_{H}(X,X^{\prime})}\leq e^{\varepsilon
C^{\prime}\log\frac{1}{\gamma}}\leq e^{C^{\prime}\log\frac{1}{\gamma}},$ where
in the last inequality we use that $\varepsilon<1.$ Hence

$\displaystyle\mathbb{P}\left[|\mathcal{A}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha|X\in\mathcal{T}_{\gamma}\right]$
$\displaystyle\leq\mathbb{E}\left[e^{\varepsilon
d_{H}(X,X^{\prime})}\mathbb{P}\left[|\mathcal{A}\left(X^{\prime}\right)-m\left(\mathcal{D}\right)|\geq\alpha|X\in\mathcal{T}_{\gamma}\right]\right]$
$\displaystyle\leq\frac{e^{C^{\prime}\log\frac{1}{\gamma}}}{\mathbb{P}\left[X\in\mathcal{T}_{\gamma}\right]}\max_{X^{\prime}\in\mathcal{H},m(X^{\prime})=m(X)}\mathbb{P}\left[|\mathcal{A}\left(X^{\prime}\right)-m\left(\mathcal{D}\right)|\geq\alpha\right]$
$\displaystyle\leq\frac{e^{C^{\prime}\log\frac{1}{\gamma}}}{1-\gamma}\max_{X^{\prime}\in\mathcal{H},m(X^{\prime})=m(X)}\mathbb{P}\left[|\mathcal{A}\left(X^{\prime}\right)-m\left(\mathcal{D}\right)|\geq\alpha\right]$
$\displaystyle=\frac{e^{C^{\prime}\log\frac{1}{\gamma}}}{1-\gamma}\max_{X^{\prime}\in\mathcal{H},m(X^{\prime})=m(X)}\mathbb{P}\left[|\hat{\mathcal{A}}\left(X^{\prime}\right)-m\left(\mathcal{D}\right)|\geq\alpha\right],$
(B.12)

where in the last line we use that for all $X^{\prime}\in\mathcal{H},$ it
holds $\mathcal{A}(X^{\prime})\overset{d}{=}\hat{\mathcal{A}}(X^{\prime}).$

According to Lemma B.2 for some
$n=O\left(C\frac{\log\frac{1}{\gamma}}{\varepsilon
L\alpha}+\frac{\log\left(\frac{R}{\alpha}+1\right)}{\varepsilon Lr}\right)$ we
can guarantee

$\displaystyle\max_{X^{\prime}\in
H,m(X^{\prime})=m(X)}\mathbb{P}\left[|\hat{\mathcal{A}}\left(X\right)-m\left(X\right)|\geq\frac{\alpha}{2}\right]\leq\gamma.$
(B.14)

Using classical results we have that for some
$n=O\left(\frac{\log(\frac{1}{\gamma})}{L^{2}\alpha^{2}}\right)$ it holds

$\mathbb{P}[|m(X)-m\left(\mathcal{D}\right)|\geq\frac{\alpha}{2}]\leq\gamma.$
(B.15)

Combining the (B.14) and (B.15) we have for some
$n=O\left(\frac{\log(\frac{1}{\gamma})}{L^{2}\alpha^{2}}+C\frac{\log\frac{1}{\gamma}}{\varepsilon
L\alpha}+\frac{\log\left(\frac{R}{\alpha}+1\right)}{\varepsilon Lr}\right)$ it
holds

$\displaystyle\max_{X^{\prime}\in
H,m(X^{\prime})=m(X)}\mathbb{P}\left[|\hat{\mathcal{A}}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha\right]\leq
2\gamma.$ (B.16)

or, combining with (B.12),

$\displaystyle\mathbb{P}\left[|\mathcal{A}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha|X\in\mathcal{T}_{\gamma}\right]$
$\displaystyle\leq\frac{e^{C^{\prime}\log\frac{1}{\gamma}}}{1-\gamma}2\gamma.$

or, combining with (B.11),

$\displaystyle\mathbb{P}\left[|\mathcal{A}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha\right]\leq\frac{e^{C^{\prime}\log\frac{1}{\gamma}}}{1-\gamma}2\gamma+\gamma.$

Since $C^{\prime}(C)=\Theta(\frac{1}{C})$ we can assume $C>0$ sufficiently
large so that $C^{\prime}(C)<\frac{1}{2}$. Hence for these values of $C$ some
$n=O\left(\frac{\log(\frac{1}{\gamma})}{L^{2}\alpha^{2}}+C\frac{\log\frac{1}{\gamma}}{\varepsilon
L\alpha}+\frac{\log\left(\frac{R}{\alpha}+1\right)}{\varepsilon Lr}\right)$ it
holds

$\displaystyle\mathbb{P}\left[|\mathcal{A}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha\right]\leq\frac{\sqrt{\gamma}}{1-\gamma}2\gamma+\gamma.$

Choosing $\gamma$ appropriately of the order
$\gamma=\Theta\left(\beta^{\frac{2}{3}}\right)$ we conclude that

$n=O\left(\frac{\log(\frac{1}{\beta})}{L^{2}\alpha^{2}}+C\frac{\log\frac{1}{\beta}}{\varepsilon
L\alpha}+\frac{\log\left(\frac{R}{\alpha}+1\right)}{\varepsilon Lr}\right)$

it holds

$\displaystyle\mathbb{P}\left[|\mathcal{A}\left(X\right)-m\left(\mathcal{D}\right)|\geq\alpha\right]\leq\beta.$

The proof is complete.

∎

##  Appendix C Proof for Section 3.4: Lower Bounds

###### Proof of Proposition 3.7.

We argue by contradiction and consider an algorithm $\mathcal{A}$ satisfying
the negation of the statement of the proposition.

We first prove that

$\displaystyle
n=\Omega\left(\frac{r^{2}\log(\frac{1}{\beta})}{\alpha^{2}}\right)$ (C.1)

and then

$\displaystyle
n=\Omega\left(\frac{\log\left(\frac{1}{\beta}\right)}{L^{2}\alpha^{2}}(1-2Lr)\right).$
(C.2)

Notice that combined the lower bounds imply

$n=\Omega\left(\frac{r^{2}\log(\frac{1}{\beta})}{\alpha^{2}}+\frac{\log\left(\frac{1}{\beta}\right)}{L^{2}\alpha^{2}}(1-2Lr)\right)=\Omega\left(\frac{\log(\frac{1}{\beta})}{\alpha^{2}}\frac{(1-Lr)^{2}}{L^{2}}\right)=\Omega\left(\frac{\log\left(\frac{1}{\beta}\right)}{L^{2}\alpha^{2}}\right),$

where for the last equality we use $Lr\leq\frac{1}{2}.$ The last displayed
equation yields the desired contradiction.

To prove C.1 notice that all uniform distributions which are supported on an
interval of width $2r$ inside $[-R-r,R+r]$ are admissible. Observe now that
for a uniform distribution the mean and the median of it are identical. For
this reason, $\mathcal{A}$ to satisfy the negation of our statement, it should
learn the mean of these uniform distributions of width $r$ from $n$ samples
with accuracy $\alpha$ with probability $1-\beta.$ Standard learning theory
implies that it should hold
$n=\Omega\left(\frac{r^{2}\log(\frac{1}{\beta})}{\alpha^{2}}\right).$

We now turn to C.2. Notice that if $Lr=\frac{1}{2}$ the lower bound on $n$ is
trivial. Hence, to establish C.2, we focus on the case where $Lr<\frac{1}{2}.$

Recall the standard fact that learning the parameter $p$ of a Bernoulli random
variable $\mathrm{Bernoulli}\left(p\right)$ at accuracy $\gamma>0$ with
probability $1-\beta$ requires
$\Omega\left(\frac{\log\left(\frac{1}{\beta}\right)}{\gamma^{2}}\right)$
samples.

We know fix $p$. We construct the admissible distribution $\mathcal{D}$ which
assigns probability mass $(1-2Lr)(1-p)$ at $-2r$, probability mass $(1-2Lr)p$
at $2r$ and with probability $2Lr$ samples from the uniform distribution on
$[-r,r].$ It can be easily checked that $\mathcal{D}$ is admissible with the
assumed parameters and median $p\left(\frac{1}{L}-2r\right)+r-\frac{1}{2L}$.
In particular, learning the median at accuracy $\alpha$ is equivalent with
learning the parameter $p$ at accuracy $\alpha\frac{2L}{1-2Lr}$ which from our
assumption on $Lr<\frac{1}{2}$ is $\Theta\left((1-2Lr)^{-1}L\alpha\right).$
Furthermore, notice that for learning the parameter $p$ using the samples from
$\mathcal{D}$ one needs to focus only the samples from which are equal to
either $2r$ or $-2r$. Therefore the task of learning the median of
$\mathcal{D}$ with $n$ samples at accuracy $\alpha$, reduces to learning the
parameter $p$ of a $\mathrm{Bernoulli}(p)$ distribution with
$N_{1}=\mathrm{Binom}(n,1-2Lr)$ samples at accuracy
$\Theta\left((1-2Lr)^{-1}L\alpha\right).$ Using the standard fact mentioned
above and this equivalence, we have that conditional on the event, call it
$\mathcal{E}_{\alpha,\beta}(\mathcal{D}),$ that we can learn the median of
$\mathcal{D}$ with $n$ samples at accuracy $\alpha$ it holds

$N_{1}=\Omega\left(\frac{\log\left(\frac{1}{\beta}\right)}{\alpha^{2}L^{2}}(1-2Lr)^{2}\right).$

Now recall that we assume that $\mathcal{A}$ can learn the median of
$\mathcal{D}$ with $n$ samples at accuracy $\alpha$ holds with probability at
least $1-\beta.$ Hence
$\mathbb{P}\left(\mathcal{E}_{\alpha,\beta}(\mathcal{D})\right)\geq 1-\beta$.
Combined with the last observation of the paragraph above, we conclude

$\displaystyle\mathbb{E}[N_{1}]\geq\mathbb{P}\left(\mathcal{E}_{\alpha,\beta}(\mathcal{D})\right)\mathbb{E}[N_{1}|\mathcal{E}_{\alpha,\beta}(\mathcal{D})]\geq(1-\beta)\Omega\left(\frac{\log\left(\frac{1}{\beta}\right)}{\alpha^{2}L^{2}}(1-2Lr)^{2}\right).$

Using that $\mathbb{E}[N_{1}]=(1-2Lr)n$ and that $\beta\in(0,\frac{1}{2})$ we
have

$(1-2Lr)n=\Omega\left(\frac{\log\left(\frac{1}{\beta}\right)}{L^{2}\alpha^{2}}(1-2Lr)^{2}\right).$

Using that $Lr<\frac{1}{2}$ we have
$n=\Omega\left(\frac{\log\left(\frac{1}{\beta}\right)}{L^{2}\alpha^{2}}(1-2Lr)\right).$
The proof is complete.

∎

###### Proof of Proposition 3.8.

We argue by contradiction and consider an algorithm $\mathcal{A}$ satisfying
the negation of our statement. Since $R>2\alpha$, for $\eta>0$ sufficiently
small it holds $2\alpha+\eta<R.$ We consider a $\mathcal{D}_{1}$ which assigns
mass $\frac{1}{2}-Lr$ to $-r-R,$ mass $\frac{1}{2}-Lr$ to $r+R$ and with
probability $2Lr$ samples from the uniform distribution on $[-r,r]$ and a
$\mathcal{D}_{2}$ which assigns mass $\frac{1}{2}-Lr$ to $-r-R,$ mass
$\frac{1}{2}-Lr$ to $r+R$ and with probability $2Lr$ samples from the uniform
distribution on $[-r+2\alpha+\eta,r+2\alpha+\eta]$. Note that they are both
admissible with the desired parameters and it also holds
$m(\mathcal{D}_{1})=0,m(\mathcal{D}_{2})=2\alpha+\eta.$

Using the accuracy guarantee of $\mathcal{A}$ and that the medians of the two
distribution have distance strictly bigger than $2\alpha$, it necessarily
holds

$\mathbb{P}_{X_{1},X_{2},\ldots,X_{n}\overset{iid}{\sim}\mathcal{D}_{1}}[|\mathcal{A}(X)-m\left(\mathcal{D}_{2}\right)|\leq\alpha]\leq\mathbb{P}_{X_{1},X_{2},\ldots,X_{n}\overset{iid}{\sim}\mathcal{D}_{1}}[|\mathcal{A}(X)-m\left(\mathcal{D}_{1}\right)|\geq\alpha]\leq\beta.$
(C.3)

The two distribution can be coupled in the following way: we first sample from
$\mathcal{D}_{1}.$ If it falls in $[-r+2\alpha+\eta,r]$ we keep the sample
from $\mathcal{D}_{1}$ as is, and translate it by $+2r$ if it falls into
$[-r,-r+2\alpha+\eta]$, to form a sample from $\mathcal{D}_{2}.$ In
particular, notice that by sampling two $n$-tuples
$X,X^{\prime}\in\mathbb{R}^{n}$ of samples in an i.i.d. sense from
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ respectively, under this coupling the
$d_{H}(X,X^{\prime})$ follows a
$\mathrm{Binom}\left(n,(2\alpha+\eta)L\right)$. Hence using the definition of
$\varepsilon$-differential privacy

$\mathbb{E}\left[e^{-\varepsilon
d_{H}(X,X^{\prime})}\mathbb{P}_{X^{\prime}\overset{iid}{\sim}\mathcal{D}_{1}}[|\mathcal{A}(X^{\prime})-m\left(\mathcal{D}_{2}\right)|\leq\alpha]\right]\leq\mathbb{P}_{X_{1},X_{2},\ldots,X_{n}\overset{iid}{\sim}\mathcal{D}_{1}}[|\mathcal{A}(X)-m\left(\mathcal{D}_{2}\right)|\geq\alpha],$
(C.4)

where the expectation is over the coupling mentioned above. Combining (C.3),
(C.4) and the assumption on the accuracy performance of $\mathcal{A}$ we have

$\mathbb{E}\left[e^{-\varepsilon
d_{H}(X,X^{\prime})}\right]\leq\frac{\beta}{1-\beta}.$

Using the moment generating function of the Binomial distribution we conclude

$\left(1-L(2\alpha+\eta)\left(1-e^{-\varepsilon}\right)\right)^{n}\leq\frac{\beta}{1-\beta}$

which by basic asymptotics since $\beta<1/2$ translates to
$n=\Omega\left(\frac{\log\left(\frac{1}{\beta}\right)}{\varepsilon
L(\alpha+\eta)}\right).$ Since $\eta>0$ can be taken arbitrarily small, the
proof of the proposition is complete.

∎

###### Proof of Proposition 3.9.

We argue by contradiction and consider an algorithm $\mathcal{A}$ satisfying
the negation of our statement.

We consider the partition of the interval $[-R,R]$ into
$N=\Omega\left(\frac{R}{\alpha}+1\right)$ consecutive intervals of width
$3\alpha$ and let $m_{i},i=1,2,\ldots,N+1$ be the endpoints of these
intervals.

Now consider $N$ admissible distributions $\mathcal{D}_{i},i=1,2,\ldots,N$
which for each $i,$ assign mass $\frac{1}{2}-Lr$ at each of the data-points
$-2(R+r)$ and $2(R+r)$ and with probability $2Lr$ it draws a sample from the
uniform distribution on $[m_{i}-r,m_{i}+r].$

By assumption for all $i=1,2,\ldots,N$ it holds

$\mathbb{P}_{X_{1},X_{2},\ldots,X_{n}\overset{iid}{\sim}\mathcal{D}_{i}}[|\mathcal{A}(X_{1},X_{2},\ldots,X_{n})-m_{i}|\leq\alpha]\geq
1-\beta.$ (C.5)

Now since for all $i=2,\ldots,N+1$ ($i\not=1$) the distributions
$\mathcal{D}_{1},\mathcal{D}_{i}$ differ only on the interval that they are
uniform on which they fall with probability $2Lr$, we can straightforwardly
couple the $n$-tuples $X,X^{\prime}$ sampled in an i.i.d. fashion from
$\mathcal{D}_{1},\mathcal{D}_{i}$ such that $d_{H}(X,X^{\prime})$ follows a
$\mathrm{Binom}\left(n,2Lr\right).$ Hence from the definition of
$\varepsilon$-differential privacy it holds for all $i=2,3,\ldots,N+1$

$\mathbb{E}\left[e^{-\varepsilon
d_{H}(X,X^{\prime})}\mathbb{P}_{X^{\prime}\overset{iid}{\sim}\mathcal{D}_{i}}[|\mathcal{A}(X^{\prime})-m_{i}|\leq\alpha]\right]\leq\mathbb{P}_{X\overset{iid}{\sim}\mathcal{D}_{1}}[|\mathcal{A}(X)-m_{i}|,\leq\alpha]$
(C.6)

where the expectation of the left hand side is under the aforementioned
coupling. Now using (C.5) and the moment generating function of the Binomial
distribution, it holds for all $i=2,3,\ldots,N+1$

$(1-\beta)\left(1-2Lr\left(1-e^{-\varepsilon}\right)\right)^{n}\leq\mathbb{P}_{X\overset{iid}{\sim}\mathcal{D}_{1}}[|\mathcal{A}(X)-m_{i}|\leq\alpha]$

Now notice that the intervals $[m_{i}-\alpha,m_{i}+\alpha],i=2,3,\ldots,N$ are
disjoint and therefore

$(1-\beta)N\left(1-2Lr\left(1-e^{-\varepsilon}\right)\right)^{n}\leq\mathbb{P}_{X\overset{iid}{\sim}\mathcal{D}_{1}}[\bigcup_{i=2}^{N+1}\\{|\mathcal{A}(X)-m_{i}|\leq\alpha\\}]\leq
1.$

By standard asymptotics and as $Lr\leq\frac{1}{2}$,
$\left(1-2Lr\left(1-e^{-\varepsilon}\right)\right)^{n}=\Omega\left(e^{-Lr\varepsilon
n}\right).$ Hence combining with the last displayed inequality, it holds

$\left(1-\beta\right)N=O\left(e^{Lr\varepsilon n}\right).$

As $\beta<1/2$ and $N=\Omega\left(\frac{R}{\alpha}+1\right)$ we conclude

$n=\Omega\left(\frac{\log\left(\frac{R}{\alpha}+1\right)}{\varepsilon
Lr}\right).$

The proof is complete.

∎

##  Appendix D Comments about Truncated-Sampling

In this last subsection, for the sake of completeness, we will present how we
can simulate a random generator for Categorical, Bernoulli, Uniform, Laplace,
(Negative) Exponential Distribution and their truncated versions in an
interval $I$ in $O(1)$ time and $O(1)$ random queries of $\mathrm{Unif}[0,1]$
using the standard “inverse-CDF” sampling method.

The general inverse-CDF sampling method works as follows:

//Suppose that we want to simulate a distribution $\mathcal{D}$ s.t its cdf
$F_{\mathcal{D}}$ is invertible.  1. Generate a random number $u$ from the
standard uniform distribution in the interval $\displaystyle[0,1]$, e.g. from
$\displaystyle U\sim\mathrm{Unif}[0,1].$ 2. Find the inverse of the desired
CDF, e.g. $\displaystyle F_{\mathcal{D}}^{-1}(x)$. 3. Output $\displaystyle
X=F_{\mathcal{D}}^{-1}(u)$.

Indeed, the computed random variable ${\displaystyle X}$ follows the
distribution $\mathcal{D}$, since

$\Pr(X\leq x)=\Pr(F_{\mathcal{D}}^{-1}(U)\leq x)=\Pr(U\leq
F_{\mathcal{D}}(x))=F_{\mathcal{D}}(x).$

###  D.1 Uniform

We start with an arbitrary uniform distribution in an interval $I=[a,b]$:

$u\leftarrow$ Sample from $\displaystyle U\sim\mathrm{Unif}[0,1]$

$s\leftarrow a+(b-a)\times u$

return $s$

Algorithm 8 $\textsc{Uniform}\left[I=[a,b]\right]$

###  D.2 $k-$nary coin

We continue with a $k-$nary coin, known as Categorical distribution, which is
a discrete probability distribution that describes the possible results of a
random variable that can take on one of $k$ possible categories, with the
probability of each category separately specified.

$u\leftarrow$ Sample from $\displaystyle U\sim\mathrm{Unif}[0,1]$

Compute CDF vector
$(q_{0},q_{1},q_{2},\cdots,q_{k-1},q_{k})=(0,p_{1},p_{1}+p_{2},\cdots,\sum_{i=1}^{k-1}p_{i},\sum_{i=1}^{k}p_{i}=1)$

for  _$i\in[k]$_ do

if  _$q_{i-1}\leq s <q_{i}$_ then

$s\leftarrow o_{i}$

return $s$

Algorithm 9 $k-$nary coin $\\{o_{1},\cdots,o_{k}\\}$ with probability
$p_{1},\cdots,p_{k}$

###  D.3 TruncatedExponential

Our next probability distibution is the truncated (Positive/Negative)
Exponential distribution
$\mathcal{D}_{\text{TruncExponential}}\sim\exp\left(\alpha\omega+\beta\right)\quad\omega\in
I=[\texttt{left},\texttt{right}]$.

  * •

If $\alpha=0$ then the actual distribution is the uniform.

  * •

If $\alpha\neq 0$ we get the CDF of $\mathcal{D}_{\text{TruncExponential}}$ is

$F_{\mathcal{D}_{\text{TruncExponential}}}(x|\alpha,\beta)=\dfrac{\exp\left(\alpha
x+\beta\right)-\exp\left(\alpha\cdot\texttt{left}+\beta\right)}{\exp\left(\alpha\cdot\texttt{right}+\beta\right)-\exp\left(\alpha\cdot\texttt{left}+\beta\right)}.$

Thus we get that:

$F_{\mathcal{D}_{\text{TruncExponential}}}^{-1}(x|\alpha,\beta)=\frac{1}{\alpha}\ln\Big{(}\exp\left(\alpha\cdot\texttt{left}+\beta\right)+x\left(\exp\left(\alpha\cdot\texttt{right}+\beta\right)-\exp\left(\alpha\cdot\texttt{left}+\beta\right)\right)\Big{)}-\beta$

$u\leftarrow$ Sample from
$\textsc{Uniform}\left[I=[0,1]=[F_{\mathcal{D}_{\text{TruncExponential}}}(\texttt{left}),F_{\mathcal{D}_{\text{TruncExponential}}}(\texttt{right})]\right]$

$s\leftarrow F_{\mathcal{D}_{\text{TruncExponential}}}^{-1}(u)$

return $s$

Algorithm 10
$\textsc{TruncatedExponential}\left[\alpha\mathrel{\mathop{\mathchar
58\relax}}\text{scale},\beta\mathrel{\mathop{\mathchar
58\relax}}\text{shift},I=[\texttt{left},\texttt{right}]\right]$

###  D.4 TruncatedLaplace

Our last probability distibution is the truncated Laplace distribution
$D_{\text{TruncLaplace}}\sim\frac{1}{2\sigma}\exp\left(-\frac{|\omega-\mu|}{\sigma}\right)\quad\omega\in
I=[\texttt{left},\texttt{right}]$. Here we firstly present the CDF and its
inverse of the classical non-truncated version of Laplace distribution.

  * •

$F_{\mathcal{D}_{\text{Laplace}}}(x|\mu,\sigma)=\frac{1}{2}+\frac{1}{2}\operatorname{sign}(x-\mu)\left(1-\frac{1}{\sigma}\exp\left(-\frac{|\omega-\mu|}{\sigma}\right)\right)$

  * •

$F_{\mathcal{D}_{\text{Laplace}}}^{-1}(x|\mu,\sigma)=\mu+\sigma\operatorname{sign}(x-\frac{1}{2})\ln\left(1-2|x-0.5|\right)$

$F_{\mathcal{D}_{\text{TruncLaplace}}}(x|\mu,\sigma)=\frac{F_{\mathcal{D}_{\text{Laplace}}}(x|\mu,\sigma)-F_{\mathcal{D}_{\text{Laplace}}}(\texttt{left}|\mu,\sigma)}{F_{\mathcal{D}_{\text{Laplace}}}(\texttt{right}|\mu,\sigma)-F_{\mathcal{D}_{\text{Laplace}}}(\texttt{left}|\mu,\sigma)}.$

Thus we get that:

$F_{\mathcal{D}_{\text{TruncLaplace}}}^{-1}(x|\mu,\sigma)=F_{\mathcal{D}_{\text{Laplace}}}^{-1}\left(F_{\mathcal{D}_{\text{Laplace}}}(\texttt{left}|\mu,\sigma)+x\times\left(F_{\mathcal{D}_{\text{Laplace}}}(\texttt{right}|\mu,\sigma)-F_{\mathcal{D}_{\text{Laplace}}}(\texttt{left}|\mu,\sigma)\right)|\mu,\sigma\right)$

$u\leftarrow$ Sample from
$\textsc{Uniform}\left[I=[0,1]=[F_{\mathcal{D}_{\text{TruncLaplace}}}(\texttt{left}),F_{\mathcal{D}_{\text{TruncLaplace}}}(\texttt{right})]\right]$

$s\leftarrow F_{\mathcal{D}_{\text{TruncLaplace}}}^{-1}(u)$

return $s$

Algorithm 11 $\textsc{TruncatedLaplace}\left[\mu\mathrel{\mathop{\mathchar
58\relax}}\text{location},\sigma\mathrel{\mathop{\mathchar
58\relax}}\text{scale},I=[\texttt{left},\texttt{right}]\right]$