§ INTRODUCTION AND MAIN RESULT

Let $N\ge 2$ be an integer, and let ${\mathbb{S}}^{N-1}$ denote the unit sphere in ${\mathbb{R}}^N$.
In this paper, we consider the mean-field classical $N$-vector spin models,
where each spin $\sigma_i$ is in ${\mathbb{S}}^{N-1}$, at a complete graph vertex $i$ among $n$ vertices (<cit.>).
The state space is $\Omega_n=({\mathbb{S}}^{N-1})^n$ with product measure $P_n=\mu\times\dots\times \mu$,
where $\mu$ is the uniform
probability measure on ${\mathbb{S}}^{N-1}$.
In the absence of an external field, each spin configuration $\sigma=(\sigma_1,\dots, \sigma_n)$ in the
state space $\Omega_n$ has a Hamiltonian defined by

\[H_n(\sigma)=-\dfrac{1}{2n}\sum_{i=1}^n \sum_{j=1}^n \langle \sigma_i , \sigma_j \rangle,\]

where $\langle \cdot , \cdot \rangle$ is the inner product in ${\mathbb{R}}^N$.
Let $\beta>0$ be the inverse temperature.
The Gibbs measure with Hamiltonian $H_n$ is the probability measure $P_{n,\beta}$ on $\Omega_n$
with density function:

\[dP_{n,\beta}(\sigma)=\dfrac{1}{Z_{n,\beta}}\exp\left( -\beta H_{n}(\sigma)\right)dP_n(\sigma),\]

where $Z_{n,\beta}$ is the partition function:
$Z_{n,\beta}=\int_{\Omega_n}\exp\left(-\beta H_n (\sigma) \right)dP_n(\sigma).$
This model is also called the mean field $O(N)$ model. It reduces to the $XY$ model, the Heisenberg model and the Toy model
when $N=2,3,4$, respectively (see, e.g., <cit.>).

Before proceeding, we
introduce the following notations.
Throughout this paper, $Z$ is a
standard normal random variable, and $\Phi(z)$ is the
probability distribution function of $Z$.
For a real-valued function $f$, we write $\|f\|=\sup_{x}|f(x)|$.
The symbol $C$ denotes a positive constant which depends only on the inverse temperature $\beta$, and its value
may be different for each appearance. For two random variables $X$
and $Y$, the Wasserstein distance $d_{\mathrm{W}}$ and the Kolmogorov distance $d_{\mathrm{K}}$ between ${\mathcal{L}}(X)$ and ${\mathcal{L}}(Y)$ are as follows:

\[d_{\mathrm{W}}({\mathcal{L}}(X),{\mathcal{L}}(Y))=\sup_{\|h'\|\le 1}\left|Eh(X) -Eh(Y)\right|,\]

\[d_{\mathrm{K}}({\mathcal{L}}(X),{\mathcal{L}}(Y))= \sup_{z\in \mathbb{R}}\left|P\left(X\le z\right) -P\left(Y\le z\right)\right|.\]

In the Heisenberg model ($N=3$), Kirkpatrick and Meckes [6] established large deviation,
normal approximation results for total spin
$S_n=\sum_{i=1}^n \sigma_i$ in the
non-critical phase ($\beta\not=3$),
and a non-normal approximation result in the
critical phase
($\beta=3$). The results in [6] are generalized by Kirkpatrick and Nawaz [7]
to the mean field $N$-vector models with $N\ge 2$.

Let $I_{\nu}$ denote the modified Bessel function of the first kind
(see, e.g., <cit.>)

\begin{equation}\label{eq:add00Bessel}
f(x)=\dfrac{I_{\frac{N}{2}}(x)}{I_{\frac{N}{2}-1}(x)},\ x>0.
\end{equation}

By le:boundf in the Appendix, we have

\begin{equation}\label{eq:add01}
\left(\dfrac{f(x)}{x}\right)'<0 \mbox{ for all } x>0.
\end{equation}

We also have

\begin{equation}\label{eq:add02}
\lim_{x\to 0^+}\dfrac{f(x)}{x}=\dfrac{1}{N} \mbox{ and } \lim_{x\to \infty}\dfrac{f(x)}{x}=0.
\end{equation}

In the case $\beta>N$, from (<ref>) and (<ref>), there is a unique strictly positive solution $b$ to
the equation

\begin{align} \label{eq:beta}
x - \beta f(x)= 0.
\end{align}

Based on their large deviations, Kirkpatrick and Nawaz [7]
that in the case $\beta>N$,
there exists $\varepsilon>0$ such that

\[P\left( \left| \dfrac{\beta|S_n|}{n} - b\right| \ge x \right) \le e^{-Cn {x}^2}\]

for all $0\le x\le \varepsilon$, where $S_n=\sum_{i=1}^n \sigma_i$ is total spin. It means that $|S_n|$ is
close to $bn/\beta$ with high probability. On the other hand,
all points on the hypersphere of radius $bn/\beta$
will have equal probability due to symmetry.
Based on these facts, they considered
the fluctuations of the squared-length of total spin:

\begin{align} \label{eq:Wn}
W_n:= \sqrt{n}\left(\dfrac{\beta^2}{n^2 b^2} \Big|S_n \Big|^2 -1 \right),
\end{align}

where $S_n=\sum_{j=1}^n \sigma_j$. Let

\begin{align} \label{eq:B2}
B^2=\dfrac{4\beta^2}{(1-\beta f^{'}(b))b^2}\left[1-\dfrac{(N-1)f(b)}{b}-(f(b))^2 \right].
\end{align}

Kirkpatrick and Nawaz [7] proved
that when $\beta >N$,
the bounded-Lipschitz distance between $W_n/B$ and $Z$ is bounded by $C (\log n/n)^{1/4}$.
Their proof is based on Stein's method for exchangeable pairs
(see Stein [10]).
Recall that a random vector $(W,W')$ is called an exchangeable pair if $(W,W^{'})$ and $(W^{'}, W)$ have the same distribution.
Kirkpatrick and Nawaz [7] construct an exchangeable pair as follows.
Let $W_n$ be as in (<ref>) and let $\sigma' = \{\sigma_1',\ldots,\sigma_n'\}$,
where for each $i$ fixed, $\sigma_i'$ is an independent copy of $\sigma_i$ given $\{\sigma_j, j\ne i\}$, i.e., given $\{\sigma_j, j\ne i\}$,
$\sigma_i'$ and $\sigma_i$ have the same distribution and $\sigma_i'$ is conditionally independent of $\sigma_i$
(see, e.g., <cit.>).
Let $I$ be a random index independent of all others and uniformly distributed over $\{1,\ldots,n\}$, and let

\begin{align} \label{eq:Wcom}
W_{n}^{'} = \sqrt{n}\left(\dfrac{\beta^2}{n^2 b^2}|S_n'|^2 - 1 \right),
\end{align}

where  $S_n' = \sum_{j=1}^n\sigma_j-\sigma_I + \sigma_I'$.
Then $(W_n,W_{n}^{'})$ is an exchangeable pair (see Kirkpatrick and Nawaz <cit.>, Kirkpatrick and Meckes <cit.>).

The bound $C(\log n/n)^{1/4}$ obtained by Kirkpatrick and Nawaz [7]
is not sharp. The aim of this paper is to give
the Kolmogorov and Wasserstein distances between $W_n/B$ and $Z$ with optimal rate $C n^{-1/2}$.

The main result is the following theorem. We recall that, throughout this paper, $C$ is a positive constant which depends only on $\beta$, and its value
may be different for each appearance.

Let $\beta >N$ and $f$ be as in (<ref>). Let $b$ be the unique strictly positive solution to
the equation $x - \beta f(x)= 0$ and $B^2$ as in (<ref>).
For $W_n$ as defined in (<ref>), we have

\begin{equation}\label{eq:W} \sup_{\|h'\|\le 1}\left|Eh(W_n/B) -Eh(Z)\right| \le C n^{-1/2}, \end{equation}

\begin{equation} \label{eq:K} \sup_{z\in \mathbb{R}}\left|P\left(W_n/B\le z\right) -\Phi(z)\right| \le C n^{-1/2}.\end{equation}

The Wasserstein bound in Theorem <ref> will be a consequence of the following proposition,
a version of Stein's method for exchangeable pairs.
It is a special case of
Theorem 2.4 of Eichelsbacher and Löwe [4] or Theorem 13.1 in [3].

Let $(W,W^{'})$ be an exchangeable pair and $\Delta=W-W'$.
If  $E(\Delta|W) = \lambda(W + R)$
for some random variable $R$ and $0 < \lambda <1$, then

\[ \sup_{\|h'\|\le 1}\left|Eh(W) -Eh(Z)\right| \le \sqrt{2/\pi}E\left| 1- \dfrac{1}{2\lambda}E(\Delta^2|W)\right|+\dfrac{1}{2\lambda}E|\Delta|^3+2E|R|.\]

The Kolmogorov distance
is more commonly used in probability and statistics,
and is usually more difficult to handle than the Wasserstein distance.
Recently, Shao and Zhang [9]  proved a very general theorem. Their result is as follows.

Let $(W,W^{'})$ be an exchangeable pair and $\Delta=W-W'$.
Let $\Delta^*:=\Delta^*(W,W')$ be any random variable satisfying $\Delta^*(W,W')=\Delta^*(W',W)$ and $\Delta^*\ge |\Delta|$.
$E(\Delta|W) = \lambda(W + R)$
for some random variable $R$ and $0 < \lambda <1$, then

\[\sup_{z\in\mathbb{R}}\left|P(W\le z) - \Phi(z)\right| \le E\left| 1- \dfrac{1}{2\lambda}E(\Delta^2|W)\right|+\dfrac{1}{\lambda}E\left|E(\Delta \Delta^*|W)\right|+E|R|.\]

Shao and Zhang [9] applied their bound in pr:ShaoZhang to get optimal bound
in many problems, including a bound of $O(n^{-1/2})$ for the Kolmogorov distance in
normal approximation of total spin in the Heisenberg model.
We note that
if $|\Delta|\le a$, then the following result is an immediate corollary
of pr:ShaoZhang. In this case, the bound is much simpler than that of pr:ShaoZhang.

If $|\Delta|\le a$, then

\begin{equation}\label{eq:corSZ01}
\sup_{z\in\mathbb{R}}\left|P(W\le z) - \Phi(z)\right| \le E\left| 1- \dfrac{1}{2\lambda}E(\Delta^2|W)\right|
\end{equation}

In pr:ShaoZhang, let $\Delta^*=a$, then

\begin{equation}\label{eq:corSZ02}
E\left|E(\Delta \Delta^*|W)\right|=aE\left|E(\Delta|W)\right|\le a\lambda (E|W|+E|R|).
\end{equation}

If $E|R|\ge 1$, then (<ref>) is trivial. If $E|R|<1$, then (<ref>) follows
immediately from (<ref>) and pr:ShaoZhang.

For $S_n=\sum_{i=1}^n \sigma_i$, and for $W_n$ and $W_{n}^{'}$ respectively defined in (<ref>) and (<ref>),
we have

\[|\Delta|=|W_n-W_{n}^{'}|=\dfrac{\beta^2}{n^{3/2} b^2}\left||S_n|^2-|S_{n}^{'}|^2\right|\le \dfrac{4\beta^2}{n^{1/2} b^2},\]

since $|S_n|+|S_{n}^{'}|\le 2n$ and $|S_n|-|S_{n}^{'}|\le |\sigma_I-\sigma_{I}^{'}|\le 2.$
Therefore, we will apply co:cor01 to obtain the Kolmogorov bound in th:app2.

§ PROOF OF THE MAIN RESULT

The proof of th:app2 depends on Kirkpatrick and Nawaz's finding [7].
Applying pr:EL and co:cor01, Theorem <ref> follows from the following proposition.

Let $\beta >N$, and let $f$ be as in (<ref>),  $b$ the unique strictly positive solution to
the equation $x - \beta f(x)= 0$. Let $W_n$ and $W_{n}^{'}$ be as in (<ref>) and (<ref>), respectively.
Then the following statements hold:

* (i) $|W_{n}-W_{n}^{'}|\le 4\beta^2 b^{-2} n^{-1/2}$ and $EW_{n}^2\le C,$

* (ii) $
E(W_n-W_{n}^{'}|W_n) = \lambda (W_n + R),$
where $\lambda = \dfrac{1-\beta f'(b)}{n}$ and $R$ is a random variable satisfying  $E|R| \le C  n^{-1/2}$,

* (iii) $E\Big|\dfrac{1}{2\lambda}E((W_n-W_{n}^{'})^2|W_n))-B^2 \Big| \le C n^{-1/2},$
where $B^2$ is defined in (<ref>).

Kirkpatrick and Nawaz's [7] used their large deviation result for total spin $S_n$ to prove that $EW_{n}^2\le C \log n.$
Intuitively, we see that this bound
would be improved to $EW_{n}^2\le C$
since $W_n$ approximates a normal distribution.
By a more careful estimate, we can prove that
$E\left(\beta |S_n|/n-b\right)^2\le C/n$ (see le:lema1).
This will lead to desired bound $EW_{n}^2\le C$.
Kirkpatrick and Nawaz's [7] also
proved that

\[E\Big|\dfrac{1}{2\lambda}E((W_n-W_{n}^{'})^2|W_n))-B^2 \Big| \le C \left(\dfrac{\log n}{n}\right)^{1/4}.\]

To get optimal bound of order $n^{-1/2}$ for this term,
we use a fine estimate of function
$f(x)=I_{\frac{N}{2}}(x)/I_{\frac{N}{2}-1}(x)$ (le:boundf) and a technique developed recently by Shao and Zhang <cit.>.

(i) We have

\begin{align*}
\begin{split}
|W_{n}-W_{n}^{'}|&=\dfrac{\beta^2}{b^2 n^{3/2}}\left| |S_{n}|^2-|S_{n}^{'}|^2\right|=\dfrac{\beta^2}{b^2 n^{3/2}}\left|\langle S_{n}+S_{n}^{'},S_{n}-S_{n}^{'}\rangle \right|\\
&\le \dfrac{2\beta^2n|S_{n}-S_{n}^{'}|}{b^2 n^{3/2}}= \dfrac{2\beta^2|\sigma_I - \sigma_I'|}{b^2 n^{1/2}}\le \dfrac{4\beta^2}{b^2 n^{1/2}}.
\end{split}
\end{align*}

The proof of the first half of (i) is completed. Now, apply le:lema1 given in the Appendix, we have

\begin{align*}
\begin{split}
EW_{n}^2&=nE\left(\left(\dfrac{\beta|S_n|}{nb}+1\right)\left(\dfrac{\beta|S_n|}{nb}-1\right)\right)^2\le CnE\left(\dfrac{\beta|S_n|}{nb}-1\right)^2\le C.\\
\end{split}
\end{align*}

(ii) Kirkpatrick and Nawaz <cit.> showed that

\begin{equation}\label{eq:bound01}
E(W_n-W_{n}^{'}|W_n) = \dfrac{2}{n}W_n +\dfrac{2}{\sqrt{n}} - \dfrac{2\beta}{n^{1/2}b^2}\left(\dfrac{\beta|S_n|}{n}\right)f\left(\dfrac{\beta|S_n|}{n}\right) + R_1,
\end{equation}

where $R_1$ is a random variable satisying $E|R_1| \le C n^{-3/2}$. Set $g(x)=xf(x),x>0$. By Taylor's expansion, we have for some
positive random variable $\xi$:

\begin{equation}\label{eq:bound02}
g\left(\dfrac{\beta|S_n|}{n}\right) =
g(b) + g'(b)\left(\dfrac{\beta|S_n|}{n}-b\right) +\dfrac{g''(\xi)}{2} \left(\dfrac{\beta|S_n|}{n}-b\right)^2.
\end{equation}

we have $1\le V\le C$ and

\begin{equation}\label{eq:bound03}
\begin{split}
\dfrac{\beta|S_n|}{n}-b&=b\left(\dfrac{\beta|S_n|}{nb}-1\right)=\dfrac{bW_n}{\sqrt{n}V}
\end{split}
\end{equation}

Combining (<ref>)-(<ref>) and noting that $b=\beta f(b)$, we have

\begin{align*}
&= \dfrac{2W_n}{n} +\dfrac{2}{\sqrt{n}} +R_1 - \dfrac{2\beta}{n^{1/2}b^2} \left(g(b)
+ g'(b)\left( \dfrac{bW_n}{2\sqrt{n}}-\dfrac{bW_{n}^2}{2nV^2}\right)+\dfrac{g''(\xi)}{2} \left(\dfrac{\beta|S_n|}{n}-b\right)^2\right) \\
&= \dfrac{2W_n}{n} +\dfrac{2}{\sqrt{n}} +R_1-\dfrac{2\beta}{n^{1/2}b^2} \left(\dfrac{b^2}{\beta} + \left(\dfrac{b}{\beta}+bf'(b) \right)\left( \dfrac{bW_n}{2\sqrt{n}}-\dfrac{bW_{n}^2}{2nV^2}\right)+\dfrac{g''(\xi)b^2W_{n}^2}{2nV^2}\right) \\
&= \dfrac{1-\beta f'(b)}{n}(W_n+R),
\end{align*}

\[R=\dfrac{n}{1-\beta f'(b)}\left(R_1+\dfrac{\beta W_{n}^2}{n^{3/2 }V^2} \left(\dfrac{1}{\beta}+f'(b) -g''(\xi)\right)\right).\]

By le:boundf (ii), we have $|g''(\xi)|<6$.
Since $V\ge 1$, $EW_{n}^2\le C$ and $E|R_1|\le Cn^{-3/2}$, we conclude that $E|R|\le Cn^{-1/2}$.
The proof of (ii) is completed.

(iii) Denote $Id$ is the $n\times n$ identity matrix and set
$\sigma^{(i)}=S_n-\sigma_i,\ b_i = \beta |\sigma^{(i)}|/n,\ r_i=\dfrac{\sigma^{(i)}}{|\sigma^{(i)}|}.$
From Kirkpatrick and Nawaz <cit.>, we have

\begin{align*}
E((W_n-W_{n}^{'})^2|\sigma)&= 2\lambda B^2 + \dfrac{4\beta^4}{n^4 b^4}  \sum_{i=1}^n\left(1-\dfrac{N-1}{\beta}\right)\left(|\sigma^{(i)}|^2 - \dfrac{(n-1)^2 b^2}{\beta^2} \right) \\
&\quad  - \dfrac{8\beta^3}{n^4b^3} \sum_{i=1}^n \left(|\sigma^{(i)}|\langle \sigma_i,\sigma^{(i)}\rangle- \dfrac{n^2 b^3}{\beta^3}\right)\\
&\quad + \dfrac{4\beta^4}{n^4 b^4} \sum_{i=1}^n \left(\langle \sigma_i,\sigma^{(i)}\rangle^2  - \left(1-\dfrac{N-1}{\beta}\right)\dfrac{(n-1)^2 b^2}{\beta^2}\right)\\
&\quad + \dfrac{4\beta^4}{n^4 b^4} \sum_{i=1}^n\sum_{j,k\ne i}\sigma_j^T R_i'\sigma_k,
\end{align*}

\[R_i'= \left(\dfrac{f(b_i)}{b_i}- \dfrac{1}{\beta} \right)Id - \left(\dfrac{Nf(b_i)}{b_i}- \dfrac{N}{\beta} \right)P_i - \left(f(b_i)- \dfrac{b}{\beta} \right)(r_i\sigma_i^T+\sigma_i r_i^T),\]

and $P_i$ is orthogonal projection onto $r_i$.

\begin{align} \label{eq:BB}
\frac{1}{2\lambda}E((W_n-W_{n}^{'})^2|\sigma))-B^2
= \dfrac{2\beta^4}{n^3 b^4(1-\beta f'(b))} \left(R_2-\dfrac{2b}{\beta} R_3+R_4+R_5\right),
\end{align}

\begin{align*}
& R_2 = \sum_{i=1}^n\left(1-\dfrac{N-1}{\beta}\right)\left(|\sigma^{(i)}|^2 - \dfrac{(n-1)^2 b^2}{\beta^2} \right), \\
& R_3 = \sum_{i=1}^n \left(|\sigma^{(i)}|\langle \sigma_i,\sigma^{(i)}\rangle - \dfrac{n^2 b^3}{\beta^3}\right),\\
& R_4 = \sum_{i=1}^n \left(\langle \sigma_i,\sigma^{(i)}\rangle^2 - \left(1-\dfrac{N-1}{\beta}\right)\dfrac{(n-1)^2 b^2}{\beta^2}\right), \\
& R_5 =  \sum_{i=1}^n\sum_{j,k\ne i}\sigma_j^T R_i'\sigma_k.
\end{align*}

For $R_2$, noting that $|\sigma^{(i)}-S_n| \le 1$, then by le:lema1, we have

\begin{align}\label{eq:R2a}
\left(E\Big|\dfrac{\beta|\sigma^{(i)}|}{n} - b\Big|\right)^2 \le E\Big|\dfrac{\beta|\sigma^{(i)}|}{n} - b\Big|^2
\le E\Big|\dfrac{\beta|S_n|}{n} - b\Big|^2 +\dfrac{C}{n^2}
\le \dfrac{C}{n}.
\end{align}

\begin{align} \label{eq:R2final}
\begin{split}
E|R_2|  &\le C \sum_{i=1}^n E\left||\sigma^{(i)}|^2 - \dfrac{(n-1)^2b^2}{\beta^2} \right|  \\
&\le C n^2 \sum_{i=1}^n\left( E\left|\dfrac{\beta^2|\sigma^{(i)}|^2}{n^2} - b^2 \right|+\dfrac{(2n-1)b^2}{n^2}\right) \\
&\le C n^2 \left(\sum_{i=1}^n E\left|\dfrac{\beta|\sigma^{(i)}|}{n} - b \right| +C\right)\le Cn^{5/2}.
\end{split}
\end{align}

For $R_3$,
we have

\begin{align}\label{eq:R3final}
\begin{split}
E|R_3| &=  E\left| \sum_{i=1}^n \left(|S_n|\langle \sigma_i,S_n\rangle - \dfrac{n^2 b^3}{\beta^3}
+|\sigma^{(i)}|\langle \sigma_i,\sigma^{(i)}\rangle-|S_n|\langle \sigma_i,S_n\rangle\right)\right|\\
&\le E\left| |S_n|^3 - \dfrac{n^3 b^3}{\beta^3}\right|+E\left|\sum_{i=1}^n |\sigma^{(i)}|\langle \sigma_i,\sigma^{(i)}\rangle-|S_n|\langle \sigma_i,S_n\rangle\right|\\
&\le Cn^2E\left| |S_n| - \dfrac{nb}{\beta}\right|+E\left|\sum_{i=1}^n \left(|\sigma^{(i)}|-|S_n|\right)\langle \sigma_i,\sigma^{(i)}\rangle-|S_n|\langle \sigma_i,\sigma_i\rangle\right|\\
&\le Cn^3E\left| \dfrac{\beta|S_n|}{n}-b\right|+E\sum_{i=1}^n \left(|\langle \sigma_i,\sigma^{(i)}\rangle|+|S_n|\right)\\
&\le Cn^3 E\left| \dfrac{\beta|S_n|}{n}-b\right|+C n^2\le C n^{5/2}.
\end{split}
\end{align}

To bound $E|R_5|$, we note that

\begin{align*}
&\sum_{i=1}^n\sum_{j,k\ne i}\sigma_j^T R_i'\sigma_k\\
& = \sum_{i=1}^n\sum_{j,k\ne i} \left[ \left(\dfrac{f(b_i)}{b_i}- \dfrac{1}{\beta} \right)\langle \sigma_j, \sigma_k\rangle  - \left(f(b_i)- \dfrac{b}{\beta} \right)\sigma_j^T(r_i\sigma_i^T+\sigma_i r_i^T)\sigma_k\right]\\
&\quad -\sum_{i=1}^n\sum_{j,k\ne i} \left(\dfrac{Nf(b_i)}{b_i}- \dfrac{N}{\beta} \right)\sigma_j^T P_i\sigma_k\\
&= \sum_{i=1}^n\left[\left(\dfrac{f(b_i)}{b_i}- \dfrac{1}{\beta} \right)|\sigma^{(i)}|^2-2\left(f(b_i)- \dfrac{b}{\beta} \right) |\sigma^{(i)}|\langle \sigma^{(i)},\sigma_i\rangle\right]\\
&\quad -\sum_{i=1}^n\left(\dfrac{Nf(b_i)}{b_i}- \dfrac{N}{\beta} \right)\sum_{j,k\ne i} \text{Trace}(\sigma_k\sigma_j^T r_i r_i^T)\\
&= \sum_{i=1}^n\left[\left(\dfrac{f(b_i)}{b_i}- \dfrac{1}{\beta} \right)|\sigma^{(i)}|^2-2\left(f(b_i)- \dfrac{b}{\beta} \right) |\sigma^{(i)}|\langle \sigma^{(i)},\sigma_i\rangle\right]\\
&\quad -\sum_{i=1}^n \left(\dfrac{Nf(b_i)}{b_i}- \dfrac{N}{\beta} \right)\langle \sigma^{(i)},r_i \rangle^2 \\
&= \sum_{i=1}^n(1-N)\left(\dfrac{f(b_i)}{b_i}- \dfrac{1}{\beta} \right)|\sigma^{(i)}|^2-2\sum_{i=1}^n\left(f(b_i)- \dfrac{b}{\beta} \right) |\sigma^{(i)}|\langle \sigma^{(i)},\sigma_i\rangle\\
\end{align*}

Since $1/\beta=f(b)/b$ and $b_i=\beta |\sigma^{(i)}|/n$, we have

\begin{align}\label{eq:R51}
\begin{split}
E|R_{51}|&=E\left|\sum_{i=1}^n(1-N)\left(\dfrac{f(b_i)}{b_i}- \dfrac{f(b)}{b} \right)|\sigma^{(i)}|^2\right|\\
& \le Cn^2 \sum_{i=1}^n E|b_i-b| \mbox{ (by \lemref{le:boundf} (iii) and the fact that $|\sigma^{(i)}|\le n$)}\\
& \le Cn^2 \sum_{i=1}^n E\left(\left|\dfrac{\beta |S_n|}{n}-b\right|+\dfrac{\beta}{n}\left(|\sigma^{(i)}|-|S_n|\right)\right)\\
&\le Cn^{5/2}\mbox{ (by \eqref{eq:R2a} and the fact that $||\sigma^{(i)}|-|S_n||\le 1$)}.
\end{split}
\end{align}

\begin{align}\label{eq:R52}
\begin{split}
E|R_{52}|&=E\left|\sum_{i=1}^n(1-N)\left(f(b_i)- f(b) \right)|\sigma^{(i)}|\langle \sigma^{(i)},\sigma_i\rangle\right|\\
& \le Cn^2 \sum_{i=1}^n E|b_i-b| \mbox{ (by \lemref{le:boundf} (i) and the fact that $|\sigma^{(i)}|\le n$)}\\
&\le Cn^{5/2}.
\end{split}
\end{align}

Combining (<ref>) and (<ref>), we have

\begin{align}\label{eq:R5final}
\begin{split}
E|R_{5}|\le Cn^{5/2}.
\end{split}
\end{align}

Bounding $E|R_4|$ is the most difficult part.
Here we follow a technique developed by Shao and Zhang <cit.>.
\[a=\left(1-\dfrac{N-1}{\beta}\right)\dfrac{(n-1)^2 b^2}{\beta^2},\ \sigma^{(1,2)}=S_n-\sigma_1-\sigma_2, V_1=\langle \sigma_1,\sigma^{(1,2)}\rangle^2,\
V_2=\langle \sigma_2,\sigma^{(1,2)}\rangle^2,\]

we have

\[\left|\langle \sigma_1,\sigma^{(1)}\rangle^2-V_1\right|\le Cn,\ \left|\langle \sigma_1,\sigma^{(2)}\rangle^2-V_2\right|\le Cn.\]

It follows that

\begin{align}\label{eq:R4}
\begin{split}
ER_{4}^2&=nE\left(\langle \sigma_1,\sigma^{(1)}\rangle^2-a\right)^2-n(n-1)E\left(\langle \sigma_1,\sigma^{(1)}\rangle^2-a\right)\left(\langle \sigma_2,\sigma^{(2)}\rangle^2-a\right)\\
& \le Cn^5+n(n-1)\left|E\left(\langle \sigma_1,\sigma^{(1)}\rangle^2-V_1+V_1-a\right)\left(\langle \sigma_2,\sigma^{(2)}\rangle^2-V_2+V_2-a\right)\right|\\
& \le Cn^5+n(n-1)|E\left(V_1-a\right)\left(V_2-a\right)|\\
& \le Cn^5+n(n-1)|E\left(V_1-E(V_1|(\sigma_j)_{j>2})\right)\left(V_2-E(V_2|(\sigma_j)_{j>2})\right)|\\
& \quad +n(n-1)|E\left(E(V_1|(\sigma_j)_{j>2})-a\right)\left(E(V_2|(\sigma_j)_{j>2})-a\right)|\\
\end{split}
\end{align}

Define a probability density function

\begin{align} \label{eq:p12}
p_{12}(x,y)=\dfrac{1}{Z_{12}^2}\exp\left(\dfrac{\beta}{n}\langle x+y,\sigma^{(1,2)}\rangle\right), x,y\in {\mathbb{S}}^{N-1},
\end{align}

where $Z_{12}^2$ is the normalizing constant. Let $(\xi_1,\xi_2)\sim p_{12}(x,y)$ given $(\sigma_j)_{j>2}$, and for $i=1,2$

\begin{align}\label{eq:V}
{\tilde{V}}_i=E\left(\langle \xi_i,\sigma^{(1,2)}\rangle^2|(\sigma_j)_{j>2}\right).
\end{align}

Similar to Shao and Zhang <cit.>,
we can show that

\begin{equation}\label{eq:R41a}
\begin{split}
R_{41}&=E\left(\langle \xi_i,\sigma^{(1,2)}\rangle^2-{\tilde{V}}_1\right)\left(\langle \xi_i,\sigma^{(1,2)}\rangle^2-{\tilde{V}}_2\right)+H_1,
\end{split}
\end{equation}

\begin{equation}\label{eq:R42a}
\begin{split}
\end{split}
\end{equation}

where $|H_1|\le Cn^3$ and $|H_2|\le Cn^3$.

\begin{align}\label{eq:B12}
b_{12}=\dfrac{\beta |\sigma^{(1,2)}|}{n}.
\end{align}

By le:boundV and the definition of $a$, we have

\begin{align*}
\begin{split}
&\left| {\tilde{V}}_1-a\right|=\left|\left(1 - \dfrac{(N-1)f(b_{12})}{b_{12}} \right)|\sigma^{(1,2)}|^2-\left(1-\dfrac{N-1}{\beta} \right)\dfrac{(n-1)^2b^2}{\beta^2}\right|\\
&\quad =\left|\left(1-\dfrac{N-1}{\beta} \right)\left(|\sigma^{(1,2)}|^2-\dfrac{(n-1)^2b^2}{\beta^2}\right)+(N-1)\left(\dfrac{1}{\beta}-\dfrac{f(b_{12})}{b_{12}}\right)|\sigma^{(1,2)}|^2\right|\\
&\quad \le Cn^2\left(\left|\dfrac{\beta^2|\sigma^{(1,2)}|^2}{n^2} -\dfrac{(n-1)^2b^2}{n^2}\right|+\left|\dfrac{f(b)}{b}-\dfrac{f(b_{12})}{b_{12}}\right|\right)\\
&\quad \le Cn^2\left(\left|\dfrac{\beta^2|S_n|^2}{n^2} -b^2\right|+\left|b_{12}-b\right|\right)+Cn\\
&\quad \le Cn^2\left(\left|\dfrac{\beta|S_n|}{n} -b\right|+\left|\dfrac{\beta|\sigma^{(1,2)}|}{n}-b\right|\right)+Cn
\le Cn^2\left|\dfrac{\beta|S_n|}{n} -b\right|+Cn.
\end{split}
\end{align*}

Using similar estimate for $\left| {\tilde{V}}_2-a\right|$, then we have

\begin{align}\label{eq:R42c}
\begin{split}
E\left|\left({\tilde{V}}_1-a\right)\left({\tilde{V}}_2-a\right)\right|&\le C\left(n^4E\left|\dfrac{\beta|S_n|}{n} -b\right|^2+n^3E\left|\dfrac{\beta|S_n|}{n} -b\right|+n^2\right)\\
&\le Cn^3\mbox{ (by \lemref{le:lema1})}.
\end{split}
\end{align}

Note that given $(\sigma_j)_{j>2}$, $\xi_1$ and $\xi_2$ are conditionally independent.  It implies that

\begin{equation}\label{eq:R41b}
\begin{split}
E\left(\langle \xi_i,\sigma^{(1,2)}\rangle^2-{\tilde{V}}_1\right)\left(\langle \xi_i,\sigma^{(1,2)}\rangle^2-{\tilde{V}}_2\right)=0.
\end{split}
\end{equation}

Combining (<ref>)-(<ref>), we have $ER_{4}^2\le Cn^5$, and so

\begin{equation}\label{eq:R4final}
\begin{split}
E|R_4|\le Cn^{5/2}.
\end{split}
\end{equation}

Combining (<ref>), (<ref>), (<ref>), (<ref>) and (<ref>), we have

\begin{align*}
E\left|\dfrac{1}{2\lambda}E((W_n-W_{n}^{'})^2|W_n))-B^2 \right| \le C n^{-1/2}.
\end{align*}

The proposition is proved.

§ APPENDIX

In this Section, we will prove the technical results that used in the proof of th:app2.
We have

\[E\Big|\dfrac{\beta|S_n|}{n} - b\Big|^2 \le \dfrac{C}{n}.\]

By the large deviation for $S_n/n$ <cit.> and the argument in <cit.>, one can prove that
there exists $\varepsilon>0$ such that

\[P\left( \left| \dfrac{\beta|S_n|}{n} - b\right| \ge x \right) \le e^{-Cn {x}^2}\]

for all $0\le x\le \varepsilon$. Since
$\left|\dfrac{\beta|S_n|}{n} - b\right|\le C,$
it implies that

\begin{align*}
\begin{split}
E\left|\dfrac{\beta|S_n|}{n} - b\right|^2 &\le 2\int_0^{\varepsilon} x P\left(\left|\dfrac{\beta|S_n|}{n} - b\right|> x\right) dx\\
&\quad +E\left(\left|\dfrac{\beta|S_n|}{n} - b\right|^2 I\left(\left|\dfrac{\beta|S_n|}{n} - b\right|> \varepsilon\right)\right)\\
&\le 2 \int_0^{\varepsilon}xe^{-Cnx^2}dx + C P\left(\left|\dfrac{\beta|S_n|}{n} - b\right|> \varepsilon\right)\\
&\le \dfrac{C}{n} + C e^{-C n\varepsilon^2}
\le \dfrac{C}{n}.
\end{split}
\end{align*}

Let $x>0$ and $f(x) = \dfrac{I_{N/2}(x)}{I_{N/2-1}(x)}$. Then
the following statements hold:

(i) $0 < f'(x) < \dfrac{1}{N-1}\le 1.$

(ii) $|(xf(x))''|< 6.$

(iii) $-5\le \dfrac{-5}{N-1}< \left(\dfrac{f(x)}{x}\right)'<0.$

As was showed in <cit.>, we have

\begin{align} \label{eq:ine01}
f'(x) = 1 - \dfrac{N-1}{x}f(x) - f^2(x).
\end{align}

It implies

\begin{align} \label{eq:ine01a}
\dfrac{f(x)}{x}=\dfrac{1-f'(x)-f^2(x)}{N-1},
\end{align}

\begin{align} \label{eq:ine01b}
f^2(x) = 1 - \dfrac{N-1}{x}f(x) - f'(x).
\end{align}

Amos <cit.> proved that

\begin{align} \label{eq:ine02}
0 < f'(x) < \dfrac{f(x)}{x}.
\end{align}

Combining (<ref>)-(<ref>), we have

\begin{align} \label{eq:ine03a}
0< f'(x) < \dfrac{f(x)}{x}<\dfrac{1}{N-1},
\mbox{
\end{align}

\begin{align*}
\left|(xf(x))''\right| &= \left|2f'(x) + xf''(x)\right|\\
&= \left|2f'(x) + x \left(-f'(x)\left(\dfrac{N-1}{x}+2f(x) \right)+ \dfrac{N-1}{x^2}f(x) \right) \right|\\
&\le 2 + (N-1)f'(x)+ 2xf(x)f'(x)+\dfrac{(N-1)f(x)}{x}\\
&\le 4 + 2f^2(x)\mbox{ (by the first half of \eqref{eq:ine03a})}\\
&\le 6 \mbox{ (by the second half of \eqref{eq:ine03a})}.
\end{align*}

The proof of (i) and (ii) is completed. For (iii), we have

\begin{align}\label{eq:ine05}
\left(\dfrac{f(x)}{x}\right)' &= \dfrac{1}{x}\left(f'(x) -\dfrac{f(x)}{x}\right).
\end{align}

Combining the first half of (<ref>) and (<ref>), we have $\left(\dfrac{f(x)}{x}\right)' < 0$.
It follows from  (<ref>), (<ref>) and (<ref>) that

\begin{align}\label{eq:ine07}
\left(\dfrac{f(x)}{x}\right)' &=\dfrac{1}{x}\left(1 -\dfrac{Nf(x)}{x}\right)-\dfrac{f^2(x)}{x}>\dfrac{1}{x}\left(1 -\dfrac{Nf(x)}{x}\right)-\dfrac{1}{N-1}.
\end{align}

Apply Theorem 2 (a) of Nȧsell [8], we can show that

\begin{align}\label{eq:ine09}
\dfrac{1}{x}\left(1-\dfrac{Nf(x)}{x}\right)>\dfrac{-4}{N-1}.
\end{align}

Combining (<ref>) and (<ref>), we have
$\left(\dfrac{f(x)}{x}\right)' >\dfrac{-5}{N-1}.$
The proof of (iii) is completed.

With the notation in the proof of th:app2, we have

\[\tilde{V}_i= |\sigma^{(1,2)}|^2\left(1 - \dfrac{(N-1)f(b_{12})}{b_{12}} \right),\ i=1,2.\]

Let $A_N=2\pi^{N/2}/\Gamma(N/2)$ the Lebesgue measure of $S^{N-1}$. It follows from (<ref>) that

\begin{align*}
Z_{12}^2&=\int_{S^{N-1}}\int_{S^{N-1}}\exp\left(\dfrac{\beta}{n}\langle x+y,\sigma^{(1,2)} \rangle\right)d\mu(x)d\mu(y)\\
&=\left(\int_{S^{N-1}}\exp\left(\dfrac{\beta}{n}\langle x,\sigma^{(1,2)} \rangle\right)d\mu(x)\right)^2\\
%&=\left(\dfrac{1}{A_N}\int_{0}^{2\pi}\int_{0}^{\pi}\dots\int_{0}^{\pi}\exp\left(\dfrac{\beta|\sigma^{(1,2)}|}{n}\cos\varphi_{N-2}\right)\sin^{N-2} \varphi_{N-2}\dots\sin^{2} \varphi_{2}\sin \varphi_{1}d\varphi_{n-2}\dots d\varphi_1 d \theta\right)^2\\
&=\left(\dfrac{A_{N-1}}{A_N}\int_0^{\pi}e^{b_{12}\cos \varphi_{N-2}} \sin^{N-2}\varphi_{N-2}d\varphi_{N-2}\right)^2\\
&=\left(\dfrac{A_{N-1}}{A_N} \dfrac{\sqrt{\pi} \Gamma(N/2-1/2)}{\left(b_{12}/2\right)^{N/2-1}}I_{N/2-1}(b_{12})\right)^2,
\end{align*}

where we have used formula

\[I_{\nu}(z)=\dfrac{1}{\sqrt{\pi}\Gamma(\nu+1/2)}\left(\dfrac{\nu}{2}\right)^{\nu}\int_{0}^{\pi}\exp(z\cos \theta)\sin^{2\nu}\theta d\theta\]

(see, e.g., Exercise 11.5.4 in [2]) in the last equation. For $i=1,2$, we have

\begin{align*}
\tilde{V}_i &= \dfrac{1}{Z_{12}}\int_{\mathbb{S}^{N-1}} \langle\theta, \sigma^{(1,2)}\rangle^2 \exp\left[ \dfrac{\beta}{n} \langle \theta, \sigma^{(1,2)}\rangle\right]d\mu(\theta)\\
&= \dfrac{1}{Z_{12}}\int_{\mathbb{S}^{N-1}} |\sigma^{(1,2)}|^2\left\langle\theta, \dfrac{\sigma^{(1,2)}}{|\sigma^{(1,2)}|}\right\rangle^2 \exp\left( \dfrac{\beta|\sigma^{(1,2)}|}{n} \left\langle\theta, \dfrac{\sigma^{(1,2)}}{|\sigma^{(1,2)}|}\right\rangle\right)d\mu(\theta) \\
&= |\sigma^{(1,2)}|^2\dfrac{A_{N-1}}{A_N Z_{12}}\int_0^{\pi} \cos^2\varphi_{N-2}\sin^{N-2}\varphi_{N-2}e^{b_{12}\cos\varphi_{N-2}} d\varphi_{N-2}\\
&= |\sigma^{(1,2)}|^2\dfrac{A_{N-1}}{A_N Z_{12}}\int_0^{\pi}e^{b_{12} \cos\varphi_{N-2}}\sin^{N-2}\varphi_{N-2} d\varphi_{N-2}\\
&\quad -\int_{0}^{\pi}e^{b_{12}\cos\varphi_{N-2}}\sin^{N}\varphi_{N-2} d\varphi_{N-2}\\
&= \left(1-\dfrac{A_{N-1}}{A_N Z_{12}}\int_{0}^{\pi}e^{b_{12}\cos\varphi_{N-2}}\sin^{N}\varphi_{N-2} d\varphi_{N-2} \right)|\sigma^{(1,2)}|^2\\
&= \left(1-\dfrac{A_{N-1}}{A_N Z_{12}}\dfrac{\sqrt{\pi} \Gamma(N/2+1/2)}{\left(b_{12}/2\right)^{N/2}}I_{N/2}(b_{12}) \right)|\sigma^{(1,2)}|^2\\
&= \left(1 - \dfrac{(N-1)f(b_{12})}{b_{12}} \right)|\sigma^{(1,2)}|^2.
\end{align*}

Finally, we would like to note again that pr:EL is a special case of
Theorem 2.4 of Eichelsbacher and Löwe [4] or Theorem 13.1 in [3], but the constants
in the bound may be different from those of Theorem 2.4 in [4] or Theorem 13.1 in [3]. Since the proof is short and simple, we will present here.

Let $h: \mathbb{R}\to\mathbb{R}$ such that $\|h'\|\le 1$ and $E|h(Z)|<\infty$, and
let $f:=f_h$ be the unique solution to the Stein's equation
Since $(W,W^{'})$ is an exchangeable pair and $E(W-W'|W) = \lambda(W + R)$,

\begin{align*}
&=E(W-W')(f(W')-f(W))+2\lambda Ef(W)E(W-W'|W)\\
&=E\Delta(f(W')-f(W))+2\lambda EWf(W)+2\lambda Ef(W)R.
\end{align*}

It thus follows that

\begin{align}\label{eq:Kanto}
\begin{split}
&=\left|E\left( f'(W)+\dfrac{1}{2\lambda}E\Delta(f(W')-f(W))+Ef(W)R\right)\right|\\
&= \left|E\left(f'(W)\left(1-\dfrac{1}{2\lambda}E(\Delta^2|W)\right)+\dfrac{1}{2\lambda}\Delta\left(f(W')-f(W)+\Delta f'(W)\right)+f(W)R\right)\right|\\
&\le \|f'\| E\left|1-\dfrac{1}{2\lambda}E(\Delta^2|W)\right|+\dfrac{1}{4\lambda}\|f''\|E\left|\Delta\right|^3+\|f\|E|R|.
\end{split}
\end{align}

By Lemma 2.4 in [3] we have

\begin{align}\label{eq:boundCGS}
\|f\|\le 2,\ \|f'\|\le \sqrt{2/\pi},\ \|f''\|\le 2.
\end{align}

The conclusion of the proposition follows from (<ref>) and (<ref>).

[1]
Amos, D.E.: Computation of modified bessel functions and their ratios. Math. Comput.  28 (1974), no. 125, 239–251. 0333287

[2]
Arfken, G. B.  and Weber, H. J.: Mathematical methods for Physicists. Elsevier Academic Press, 6th edition, 2005.  xii+1182 pp.

[3] Chen, L. H. Y., Goldstein, L. and Shao, Q. M.:
Normal approximation by Stein's method. Probability and its Applications (New York). Springer, Heidelberg, 2011. xii+405 pp.

[4] Eichelsbacher, P. and Löwe, M.: Stein's method for dependent random variables occuring in statistical mechanics. Electron. J. Probab. 15 (2010), no. 30, 962–988.

[5] Friedli, S. and Velenik, Y. Statistical mechanics of lattice systems. A concrete mathematical introduction. Cambridge University Press, Cambridge, 2018. xix+622 pp. 3752129

[6] Kirkpatrick, K.  and Meckes, E.: Asymptotics of the mean-field Heisenberg model. J. Stat. Phys., 152 (2013), 54–92. 3067076

[7] Kirkpatrick, K.  and Nawaz, T.: Asymptotics of mean-field O(N) model. J. Stat. Phys., 165 (2016), no. 6, 1114–1140. 3575640

[8]
Nȧsell, I.: Rational bounds for ratios of modified Bessel functions. SIAM J. Math. Anal. 9 (1978), no. 1, 1–11.  0466662

[9]Shao, Q.M.  and Zhang,  Z. S.: Berry-Esseen bounds of normal and nonnormal approximation for unbounded exchangeable pairs.
Ann. Probab. 47 (2019), no. 1, 61–108. 3909966

[10]
Stein, C.: Approximate computation of expectations. Institute
of Mathematical Statistics Lecture Notes Monograph Series, 7. Institute of Mathematical Statistics, Hayward, CA. 1986. iv+164 pp.

We are grateful to the Associate Editor and an anonymous referee whose comments have been very
useful to make our development clearer and more comprehensive.


# Analytic conjugation between planar differential systems and potential
systems

F. J. S. NASCIMENTO111 Geology Collegiate, Federal University of Vale do São
Francisco, Senhor do Bonfim, Bhaia, Brazil
Email<EMAIL_ADDRESS>
ORCID:0009-0004-9536-7979

###### Abstract

In this article it is proved that an analytical planar vector field with a
non-degenerate center at $(0,0)$ is analytically conjugate, in a neighborhood
of $(0,0)$, to a Hamiltonian vector field of the form
$y\frac{\partial}{\partial x}-V^{\prime}(x)\frac{\partial}{\partial y}$, where
$V$ is an analytic function defined in a neighborhood of the origin such that
$V(0)=V^{\prime}(0)=0$ and $V^{\prime\prime}(0)>0.$

##  1 Introduction

Let $\Omega$ be an open subset of $\mathds{R}^{2}$ and
$C^{\omega}(\Omega,\mathds{R}^{d})$ the set of the real analytic functions
defined on $\Omega$ with values on $\mathds{R}^{d}$, $d\in\\{1,2\\}$. Let
$P,Q\in C^{\omega}(\Omega,\mathds{R})$ and consider the analytic differential
system

$\dot{x}=P(x,y),\quad\dot{y}=Q(x,y),\quad(x,y)\in\Omega.$ (1.1)

The system (1.1) define on $\Omega$ the planar vector field $X=(P,Q)\in
C^{\omega}(\Omega,\mathds{R}^{2})$. In this paper the vector field $X=(P,Q)$
it will often be represented by the differential operator

$X=P\frac{\partial}{\partial x}+Q\frac{\partial}{\partial y}.$ (1.2)

A point $p\in\Omega$ such that $X(p)=(0,0)$ is called a singular point of $X$.
A singular point $p$ is non-degenerate if the determinant of Jacobian matrix
$DX(p)$ of $X$ at $p$ is non-zero, that is, if
$P_{x}(p)Q_{y}(p)-P_{y}(p)Q_{x}(p)\neq 0$. A singular point $p$ is called a
center of $X$ if there exists an open neighborhood $U$ of $p$ such that each
solution of (1.1) with initial condition on $U-\\{p\\}$ defines a periodic
orbit surrounding $p$. The largest neighborhood $\mathcal{A}$ with this
property is called the period annulus of $p$. Let $p$ be a center of $X$ and
let $T(q)$ denote the period of orbit passing through $q\in\mathcal{A}$. The
function $q\to T(q)$ is called the period function associated with the center
$p$.

Let $\Omega_{1}$ and $\Omega_{2}$ be open sets of $\mathds{R}^{2}$. The vector
fields $X\in C^{\omega}(\Omega_{1},\mathds{R}^{2})$ and $Y\in
C^{\omega}(\Omega_{2},\mathds{R}^{2})$ are analytically equivalent (or
analytically conjugacy) if exists an analytic diffeomorphism
$h:\Omega_{1}\to\Omega_{2}$ such that

$D_{q}hX(q)=Y(h(p))\quad\text{for every }\quad q\in\Omega_{1}.$ (1.3)

The diffeomorphism $h$ maps singular points to singular points, and periodic
orbits to periodic orbits, preserved the period of the periodic orbits. Let
$p$ be a singular point $p$ of $X$, we say that $X$ is locally analytically
conjugate to a vector field $Y$ if equality (1.3) holds on a neighborhood of
$p$. In this paper, we shall show the following

######  Theorem 1.1.

Let $\Omega$ be an open subset of $\mathds{R}^{2}$ such that $(0,0)\in\Omega$
and suppose that the vector field $X\in C^{\omega}(\Omega,\mathds{R}^{2})$ has
a non-degenerate center at $(0,0)$. Then $X$ is analytically conjugate, on a
neighborhood of $(0,0)$, to the vector field

$Y=y\frac{\partial}{\partial x}-V^{\prime}(x)\frac{\partial}{\partial y},$
(1.4)

where $V$ is an analytic function defined in a neighborhood of the origin such
that $V(0)=V^{\prime}(0)=0$ and $V^{\prime\prime}(0)>0.$

The vector field (1.4) defines the Hamiltonian system

$\dot{x}=y,\quad\dot{y}=-V^{\prime}(x).$ (1.5)

This system is called a potential system and has been the subject of study by
several researchers. Among the issues addressed, two stand out, and both are
related to the period function associated with the center of system (1.5). The
first question is dedicated to the study of the monotonicity of the period
function. This issue is addressed in several articles, for example, [1], [2],
[3], [4]. The second question concerns the possibility of constructing a
potential function V from a positive function T. This question is called the
inverse problem and has been addressed in several articles, for example, [5],
[6], [7], [8], [9], [10], [11]. In [1] Chicone questions under what conditions
a vector field $X$ with a center at $(0,0)$ is conjugate to a Hamiltonian
vector field of type (1.4). The theorem (1.1) is an answer to the question
proposed by Chicone for the particular case in which $X$ is analytic and the
center at $(0,0)$ is non-degenerate.

##  2 Proof of Theorem 1.1

The central idea of the proof consists of constructing a vector field of the
type (1.4), from the period function of the vector field $X$, in such a way
that the period function of $Y$ is equal to the period function of $X$. The
proof will be divided into some lemmas.

######  Lemma 2.1.

Let $X=P\frac{\partial}{\partial u}+Q\frac{\partial}{\partial v}$ be an
analytical vector field with a non-degenerate center at $(0,0)$. Then $X$ is
analytically conjugate, on a neighborhood of $(0,0)$, to the vector field

$X(\xi,\eta)=f(\xi^{2}+\eta^{2})\bigg{(}\eta\frac{\partial}{\partial\xi}-\xi\frac{\partial}{\partial\eta}\bigg{)},$
(2.6)

where $f$ is an analytic function defined in a neighborhood of the origin such
that $f(0)>0.$

###### Proof.

It is an immediate consequence of the Poincaré Normal Form Theorem (see [12]).
∎

Note that (2.6) is a Hamiltonian vector field with Hamiltonian function
$H(\xi,\eta)=F(\xi^{2}+\eta^{2})$, where $F$ is the analytic function defined
by

$F(z)=\frac{1}{2}\int_{0}^{z}f(s)ds.$ (2.7)

Therefore, the periodic orbits of (2.6) are contained in the level curves
$H(\xi,\eta)=E.$

######  Lemma 2.2.

Let $E\geq 0$, the period function $T(E)$ of (2.6) parameterized by
$H(\xi,\eta)=E$ is the analytic function given by

$T(E)=\frac{\pi}{F^{\prime}(F^{-1}(E))}=\pi\frac{d}{dE}F^{-1}(E).$ (2.8)

###### Proof.

In polar coordinates (2.6) becomes

$X(r,\theta)=f(r^{2})\frac{\partial}{\partial\theta},$ (2.9)

where $r^{2}=\xi^{2}+\eta^{2}$ and
$\theta=\arctan\big{(}\frac{\eta}{\xi}\big{)}$. Thus, the origin is a center
with the periodic orbits inside the circles $\xi^{2}+\eta^{2}=r^{2}.$
Therefore the period of the periodic orbit of (2.6) inside the circle of
radius $r$ is given by

$\hat{T}(r)=\frac{2\pi}{f(r^{2})}.$ (2.10)

Let $E>0$ be such that $H(\xi,\eta)=F(\xi^{2}+\eta^{2})=E$. Since
$F^{\prime}(0)=f(0)>0$ we have that $F$ has an analytic inverse in a
neighborhood of zero. Therefore, $r^{2}=\xi^{2}+\eta^{2}=F^{-1}(E)$ in a
neighborhood of zero. Substituting $r=\sqrt{F^{-1}(E)}$ in (2.10) we get

$T(E)=\hat{T}(\sqrt{F^{-1}(E)})=\frac{2\pi}{f(F^{-1}(E))}\overset{(\ref{eq7})}{=}\frac{\pi}{F^{\prime}(F^{-1}(E))}.$
(2.11)

Note that, by definition, $T(E)$ is analytic in a neighborhood of zero with
$T(0)=\pi/F^{\prime}(0)>0$. ∎

######  Lemma 2.3.

Let $T(E)$ be the analytic function definite in (2.11). Then exist an analytic
function $V$, defined in a neighborhood of zero, such that
$V(0)=V^{\prime}(0)=0$ and $V^{\prime\prime}(0)>0$. Furthermore, the period
function of the Hamiltonian vector field, defined in a neighborhood of
$(0,0)$, by

$Y(x,y)=y\frac{\partial}{\partial x}-V^{\prime}(x)\frac{\partial}{\partial
y},$ (2.12)

is equal to $T(E)$.

###### Proof.

Since $F^{-1}(E)$ is analytic in the neighborhood of zero, with $F^{-1}(0)=0$,
there exists a sequence of real numbers $(a_{n})_{n\geq 1}$ such that

$\displaystyle F^{-1}(E)=\sum_{n\geq 1}a_{n}E^{n}.$ (2.13)

Therefore,

$\displaystyle\big{(}F^{-1}\big{)}^{\prime}(E)=\sum_{n\geq 1}na_{n}E^{n-1}.$
(2.14)

Since $\big{(}F^{-1}\big{)}^{\prime}(0)=1/F^{\prime}(0)$, we have that
$a_{1}=1/F^{\prime}(0)>0.$ Let $(b_{n})_{n\geq 1})$ be the sequence of real
numbers defined by

$\displaystyle b_{n}=\frac{n\sqrt{2\pi}\Gamma(n)}{4\Gamma(n+1/2)}a_{n},$
(2.15)

where $\Gamma$ is Euler’s gamma function. Since

$\lim\limits_{n\to\infty}\frac{\Gamma(n)}{\Gamma(n+1/2)}=0,$

there is a constant $M>0$ such that $|b_{n}|\leq nM|a_{n}|.$ Therefore, the
function $\varphi(E)$ defined by

$\displaystyle\varphi(z)=\sum_{n\geq 1}b_{n}z^{2n-1}$ (2.16)

is analytic in a neighborhood of zero , with $\varphi(0)=0$ and
$\varphi^{\prime}(0)=b_{1}=\sqrt{2}a_{1}/2>0.$ Let $\zeta(E)$ be defined in a
neighborhood of zero by

$\displaystyle\zeta(E)=\varphi(\sqrt{E})=\sum_{n\geq 1}b_{n}E^{(2n-1)/2}.$
(2.17)

Since

$\zeta^{\prime}(E)=\frac{\varphi^{\prime}(E)}{2\sqrt{E}},$

it follows that $\lim\limits_{E\to 0^{+}}\zeta^{\prime}(E)=+\infty$ and,
consequently, $\zeta(E)$ is invertible in a neighborhood of zero. Let $V$ be
the function defined in a neighborhood of zero by
$V(\tilde{x})=\zeta^{-1}(\tilde{x})$. By definition, $V$ is analytic in a
neighborhood of zero with $V(0)=V^{\prime}(0)=0$ and $V^{\prime\prime}(0)>0$.
In fact, since $\varphi^{\prime}(0)>0$, $\varphi(z)$ is invertible in a
neighborhood of zero. Therefore, $x=\zeta(E)=\varphi(\sqrt{E})$ implies that
$\zeta^{-1}(x)=[\varphi^{-1}(x)]^{2}$. So
$V(x)=\zeta^{-1}(x)=[\varphi^{-1}(x)]^{2}$ is analytic in a neighborhood from
zero. Furthermore, it follows from the definition of $V$ that
$V(0)=V^{\prime}(0)=0$ and

$V^{\prime\prime}(0)=2(\varphi^{-1})^{\prime}(0)=2/\varphi^{\prime}(0)=2/b_{1}>0.$

Note that, by definition, $V$ is an even function. Let $Y$ be the Hamiltonian
vector field defined by

$Y(x,y)=y\frac{\partial}{\partial x}-V^{\prime}(x)\frac{\partial}{\partial
y}.$ (2.18)

Note that, by definition, $Y$ is analytic in a neighborhood of $(0,0)$ and has
a non-degenerate center at $(0,0)$. Therefore, the periodic orbits of (2.18)
are contained in the level curves $H(x,y)=E,$ where $H$ is the Hamiltonian
function defined in a neighborhood of $(0,0)$ by

$\displaystyle H(x,y)=\frac{y^{2}}{2}+V(x).$ (2.19)

Let $\hat{T}(E)$ be the period of the periodic orbit with $H(x,y)=E$ of the
vector field (2.18). By (2.19) we have to

$\displaystyle y=\pm\sqrt{2(E-V(x))}.$ (2.20)

Then

$\displaystyle\hat{T}$ $\displaystyle=$ $\displaystyle
2\int_{V_{-}^{-1}(E)}^{V_{+}^{-1}(E)}\frac{dx}{y}=2\int_{V_{-}^{-1}(E)}^{V_{+}^{-1}(E)}\frac{dx}{\sqrt{2(E-V(x))}}$
$\displaystyle=$
$\displaystyle\sqrt{2}\int_{0}^{V_{+}^{-1}(E)}\frac{dx}{\sqrt{E-V(x)}}-\sqrt{2}\int_{0}^{V_{-}^{-1}(E)}\frac{dx}{\sqrt{E-V(x)}},$

where $V_{-}^{-1}$ and $V_{+}^{-1}$ denote the inverse of $V$ at $x<0$ and
$x>0$ respectively. The change of coordinates $x=V_{+}^{-1}(E)$ and
$x=V_{-}^{-1}(E)$ in the first and second integral above respectively yield

$\displaystyle\hat{T}(E)=\sqrt{2}\int_{0}^{E}\frac{\big{(}V_{+}^{-1}(s)-V_{-}^{-1}(s)\big{)}^{\prime}ds}{\sqrt{E-s}}.$
(2.21)

Since $V$ is even, we have that $V_{-}^{-1}(E)=-V_{+}^{-1}(E)$ and,
consequently, $V_{+}^{-1}(E)-V_{-}^{-1}(E)=2V_{+}^{-1}(E)=2V^{-1}(E)$.
Therefore, the period function $\hat{T}(E)$ of (2.18) parameterized by the
energy levels $H=E$ is the analytical function defined by

$\hat{T}(E)=2\sqrt{2}\int_{0}^{E}\frac{(V^{-1})^{\prime}(s)ds}{\sqrt{E-s}}.$
(2.22)

By definition,

$V^{-1}(E)=\varphi(\sqrt{E})\overset{(\ref{zeta})}{=}\sum_{n\geq
1}b_{n}E^{(2n-1)/2}$

and, therefore,

$(V^{-1})^{\prime}(E)=\sum_{n\geq 2}\frac{(2n-1)}{2}b_{n}E^{(2n-3)/2}.$

Substituting the series of $(V^{-1})^{\prime}(E)$ into (2.22), we obtain

$\displaystyle\hat{T}(E)$ $\displaystyle=$ $\displaystyle 2\sqrt{2}\sum_{n\geq
2}\frac{(2n-1)}{2}b_{n}\int_{0}^{E}\frac{s^{(2n-3)/2}ds}{\sqrt{(E-s)}}$
$\displaystyle=$ $\displaystyle 2\sqrt{2}\sum_{n\geq
2}\frac{(2n-1)}{2}b_{n}\int_{0}^{1}\frac{(Et)^{(2n-3)/2}Edt}{\sqrt{(E-Et)}}$
$\displaystyle=$ $\displaystyle 2\sqrt{2}\sum_{n\geq
2}\frac{(2n-1)}{2}b_{n}E^{n-1}\int_{0}^{1}\frac{t^{(2n-3)/2}dt}{\sqrt{(1-t)}}$
$\displaystyle=$ $\displaystyle 2\sqrt{2}\sum_{n\geq
1}\frac{(2n-1)}{2}b_{n}E^{n-1}2\frac{\sqrt{\pi}\Gamma(n-1/2)}{\Gamma(n)}$
$\displaystyle=$ $\displaystyle 2\sqrt{2}\sum_{n\geq
1}b_{n}\frac{\sqrt{\pi}\Gamma(n+1/2)}{\Gamma(n)}E^{n-1}.$

By definition, $b_{n}=\frac{n\sqrt{2\pi}\Gamma(n)}{4\Gamma(n+1/2)}a_{n}.$ Then

$b_{n}\frac{\sqrt{\pi}\Gamma(n+1/2)}{\Gamma(n)}E^{n-1}=\frac{n\sqrt{2\pi}\Gamma(n)}{4\Gamma(n+1/2)}a_{n}\cdot\frac{\sqrt{\pi}\Gamma(n+1/2)}{\Gamma(n)}=\frac{\sqrt{2}\pi
na_{n}}{4}.$

Therefore

$\hat{T}(E)=2\sqrt{2}\sum_{n\geq 1}\frac{\sqrt{2}\pi
na_{n}}{4}E^{n-1}=\pi\sum_{n\geq
1}na_{n}E^{n-1}\overset{(\ref{eq14})}{=}\pi(F^{-1})^{\prime}(E)=\frac{\pi}{F^{\prime}(F^{-1}(E))}\overset{(\ref{eq08})}{=}T(E).$

∎

###  2.1 Conclusion of the proof of Theorem 1.1.

By construction, the vector field (2.18) has a non-degenerate center at
$(0,0)$. Then, by lemma 2.1 (2.18) is analytically conjugate, on a
neighborhood of $(0,0)$, to the vector field

$Y(\xi,\eta)=g(\xi^{2}+\eta^{2})\bigg{(}\eta\frac{\partial}{\partial\xi}-\xi\frac{\partial}{\partial\eta}\bigg{)},$
(2.23)

where $g$ is an analytic function defined in a neighborhood of the origin such
that $g(0)>0.$ By lemma 2.2, the period function $\hat{T}(E)$ of (2.23)
parameterized by $H(\xi,\eta)=E$ is the analytic function given by

$\hat{T}(E)=\frac{\pi}{G^{\prime}(G^{-1}(E))}=\pi\frac{d}{dE}G^{-1}(E),$
(2.24)

where $G$ is the analytic function defined by

$G(z)=\frac{1}{2}\int_{0}^{z}g(s)ds.$ (2.25)

By construction, $\hat{T}(E)=T(E)=\pi\frac{d}{dE}F^{-1}(E)$ and therefore

$\pi\frac{d}{dE}G^{-1}(E)=\pi\frac{d}{dE}F^{-1}(E).$

Since $G^{-1}(0)=F^{-1}(0)=0$, we have that

$G^{-1}(E)=\int_{0}^{E}\frac{d}{dE}G^{-1}(s)ds=\int_{0}^{E}\frac{d}{dE}F^{-1}(s)ds=F^{-1}(E).$

Therefore $G$ coincides with $F$ in a neighborhood of zero. This implies that
the vector fields (2.6) and (2.23) coincide in a neighborhood of $(0,0)$.
Therefore, the vector field $X$ from the definition of theorem (1.1) is
analytically conjugate, in a neighborhood of $(0,0)$, to the Hamiltonian
vector field defined in (2.18).∎

In ([13], Corollary 4.3) it was proved that two Hamiltonian systems with non-
degenerate centers at $(0,0)$ are analytically conjugate if and only if both
centers have the same period function. The idea of proof the theorem 1.1 was
based on this result.

A linear application $R:\mathds{R}^{2}\to\mathds{R}^{2}$ is called a linear
involution over $\mathbb{R}^{2}$ if $R\neq id$ and $R^{2}=id$. A vector field
$X:\Omega\subseteq\mathds{R}^{2}\to\mathds{R}^{2}$ is reversible with respect
to $R$ or $R$-reversible in $\Omega$ if $R\circ X(q)=-X\circ R(q)\text{ for
all }q\in\Omega.$

######  Corollary 2.1.

Let $X=P\frac{\partial}{\partial u}+Q\frac{\partial}{\partial v}$ be an
analytic vector field in a neighborhood of $(0,0)$ with $X(0,0)=(0,0)$ and
$P_{x}(0,0)Q_{y}(0,0)-P_{y}(0,0)Q_{x}(0,0)>0$. Suppose $X$ is $R$-reversible,
with $R(x,y)=(u,-v)$. Then $X$ is analytically conjugate, on a neighborhood of
$(0,0)$, to the vector field $Y=y\frac{\partial}{\partial
x}-V^{\prime}(x)\frac{\partial}{\partial y}$, where $V$ is an analytic
function defined in a neighborhood of the origin such that
$V(0)=V^{\prime}(0)=0$ and $V^{\prime\prime}(0)>0.$

###### Proof.

Under these conditions $X$ has a non-degenerate center at $(0,0)$, see ([14],
Theorem 1). ∎

The global equivalence between vector fields of the form
$X(u,v)=v\partial_{u}+f(u,v^{2}/2)\partial_{v}$ and the form
$Y(x,y)=y\frac{\partial}{\partial x}-V^{\prime}(x)\frac{\partial}{\partial y}$
was studied in [15] and in the Ph.D. Thesis (in Portuguese) of the author
(FJSN). The global version of theorem 1.1 is part of a manuscript by the
author in collaboration with C. Grota Ragazzo.

## References

  * [1] Carmen Chicone.  The monotonicity of the period function for planar hamiltonian vector fields.  Journal of Differential equations, 69(3):310–321, 1987.
  * [2] Armengol Gasull, Antoni Guillamon, V Manosa, and Francesc Mañosas.  The period function for hamiltonian systems with homogeneous nonlinearities.  Journal of Differential Equations, 139(2):237–260, 1997.
  * [3] Javier Chavarriga and Marco Sabatini.  A survey of isochronous centers.  Qualitative theory of Dynamical Systems, 1:1–70, 1999.
  * [4] Andrea Sfecci.  From isochronous potentials to isochronous systems.  Journal of Differential Equations, 258(5):1791–1800, 2015.
  * [5] Minoru Urabe.  Relations between periods and amplitudes of periodic solutions of $\ddot{x}+g(x)=0$.  Funkcialaj Ekvacioj, 6:63–88, 1964.
  * [6] Minoru Urabe.  Potential forces which yield periodic motions of a fixed period.  Journal of Mathematics and Mechanics, pages 569–578, 1961.
  * [7] Barbara Alfawicka.  Inverse problems connected with periods of oscillations described by $\ddot{x}+g(x)=0$.  Ann. Polon. Math., 32(44):297–308, 1984.
  * [8] Barbara Alfawicka.  Inverse problem connected with half-period function analytic at the origin.  Bull. Pol. Acad. Sci. Math., 32(5–6):267–274, 1984.
  * [9] F Mañosas and Pedro J Torres.  Two inverse problems for analytic potential systems.  Journal of Differential Equations, 245(12):3664–3673, 2008.
  * [10] Yutaka Kamimura.  Global existence of a restoring force realizing a prescribed half-period.  Journal of Differential Equations, 248(10):2562–2584, 2010.
  * [11] Yutaka Kamimura and Takeshi Kaneya.  Global determination of a nonlinearity from a periodic motion.  Journal of Mathematical Analysis and Applications, 403(2):506–521, 2013.
  * [12] P Mardesic, Christiane Rousseau, and Bourama Toni.  Linearization of isochronous centers.  Journal of Differential Equations, 121(1):67–108, 1995.
  * [13] F Manosas and J Villadelprat.  Area-preserving normalizations for centers of planar hamiltonian systems.  Journal of Differential Equations, 179(2):625–646, 2002.
  * [14] Marco Antonio Teixeira and Jiazhong Yang.  The center-focus problem and reversibility.  Journal of Differential Equations, 174(1):237–251, 2001.
  * [15] C Ragazzo.  Scalar autonomous second order ordinary differential equations.  Qualitative Theory of Dynamical Systems, 11(2):277–415, 2012.


# Concave Pro-rata Games

Nicholas A. G. Johnson
<EMAIL_ADDRESS>Theo Diamandis
<EMAIL_ADDRESS>Alex Evans
<EMAIL_ADDRESS>Henry de Valence
<EMAIL_ADDRESS>Guillermo Angeris
<EMAIL_ADDRESS>
(October 2022)

###### Abstract

In this paper, we introduce a family of games called concave pro-rata games.
In such a game, players place their assets into a pool, and the pool pays out
some concave function of all assets placed into it. Each player then receives
a pro-rata share of the payout; i.e., each player receives an amount
proportional to how much they placed in the pool. Such games appear in a
number of practical scenarios, including as a simplified version of batched
decentralized exchanges, such as those proposed by Penumbra. We show that this
game has a number of interesting properties, including a symmetric pure
equilibrium that is the unique equilibrium of this game, and we prove that its
price of anarchy is $\Omega(n)$ in the number of players. We also show some
numerical results in the iterated setting which suggest that players quickly
converge to an equilibrium in iterated play.

## Introduction

Existing blockchain systems come to consensus on transactions in batches,
called blocks. Yet the economic mechanisms those transactions interact with
are generally designed to process each individual transaction sequentially,
making their behavior reliant on the ordering of transactions within the
batch. This abstraction mismatch is the primary source of miner extractible
value (MEV), defined as economic value that can be captured by the block
proposer (originally the miner) who selects and sequences the transactions to
be included in the batch [6].

However, rather than trying to blind the block proposer, or choose a “fair”
ordering (which is difficult, if not impossible, to construct in any direct
sense on current systems) within a batch, we could alternatively attempt to
design economic mechanisms which do not depend on the order of transactions
within a block, and instead, process each batch of transactions ‘all at once’.
These mechanisms would then be aligned with the actual ordering provided by
the consensus mechanism, stepping from one batch of transactions to the next
in the same discrete time steps in which consensus happens.

One such mechanism is a ‘pro-rata mechanism’. In this mechanism, there is some
known notion of value: for example, every user might want to trade some asset
$A$ for another, say $B$, and everyone ‘pitches in’ some amount of asset $A$
into a pool. After everyone has placed their amounts, the pool, as a whole, is
traded on an exchange for some amount of asset $B$, and the resulting amount
of asset $B$ is distributed back to each player, in proportion to how much of
asset $A$ each player placed in the pool. It is not difficult to show that
such a mechanism has the desired property: the order in which players placed
asset $A$ into the collective pool does not change how much of asset $B$ each
player receives. Using some ideas from cryptography, this game can
additionally be implemented in a way that does not reveal any one player’s
contributions or identity [9], and so may be considered a simultaneous game.

On the other hand, mechanisms of this form often lead to interesting phenomena
as users must now consider the possible actions of other users when planning
their own actions. A natural framework to study these kinds of problems, where
players must reason about the strategies of other players, recursively, is via
game theory and the study of the equilibria of games [12]. This paper serves
to cleanly set up the game resulting from a pro-rata mechanism in a simple
mathematical framework and derive a number of useful results for such games.

#### This paper.

The paper is organized as follows. We introduce the concave pro-rata game in
§1 and show a few interesting properties under mild conditions. Such
properties include the existence and uniqueness of a symmetric pure strategy
equilibrium and an explicit way of efficiently computing this equilibrium by
solving a single variable, unimodal optimization problem. We also show some
simple bounds for the price of anarchy. In §2 we then describe how this type
of game connects to a recent proposal for a batched decentralized exchange. We
run a number of simulations in §A and §B, illustrating the price of anarchy
and showing that in the iterated setting agents appear to converge quickly to
the specified equilibrium.

##  1 The concave pro-rata game

We will define the _pro-rata game_ with $n$ players as the game with the
following payoff for player $i=1,\dots,n$:

$U_{i}(x)=\frac{x_{i}}{\mathbf{1}^{T}x}f(\mathbf{1}^{T}x).$ (1)

Here, $f:{\mbox{\bf R}}_{+}\to{\mbox{\bf R}}$ is some function satisfying
$f(0)=0$, while $x\in{\mbox{\bf R}}_{+}^{n}$ is a nonnegative vector whose
$i$th entry is the action performed by the $i$th player. We will say the game
is a _concave_ pro-rata game if the function $f$ is a concave function. This
game has a simple interpretation: every player ‘pitches in’ some amount
$x_{i}$ into a pool, totaling $\mathbf{1}^{T}x$, and the pool pays out
$f(\mathbf{1}^{T}x)$ depending only on the total amount pitched in by all
players. The amount paid out by the pool is then distributed among the players
in a pro-rata way; i.e., each player $i$ receives an amount proportional to
how much she put into the pool. For the remainder of this paper, we will
assume that the function $f$ is concave. We note that concave pro-rata games
consist of a special case of aggregative games in which the payoff of each
player is a function of their strategy and the sum of the strategies of all
players (cf., [11]).

#### Concavity.

The payoff $U_{i}$ is concave in the $i$th entry, holding the remaining
entries constant. To see this, first define $y=\mathbf{1}^{T}x-x_{i}$ (i.e.,
$y$ is the sum of all entries of $x$ except the $i$th entry). Overloading
notation slightly for $U_{i}$, we have that

$U_{i}(x_{i},y)=\frac{x_{i}}{x_{i}+y}f(x_{i}+y).$

We can write $U_{i}(\cdot,y)$ as the composition of the following two
functions

$U_{i}(x_{i},y)=g(x_{i},h(x_{i})),$

where

$g(x_{i},t)=tf\left(\frac{x_{i}}{t}\right)\qquad\text{and}\qquad
h(x_{i})=\frac{x_{i}}{x_{i}+y},$

which are defined for nonnegative real inputs. We will use this rewriting to
show that this function is concave in $x_{i}$, since, using the basic convex
composition rules (cf., [3, §3.2.4]) it suffices to show that (a) $h$ is
concave and (b) $g$ is concave and nondecreasing in its second argument.

First, note that $h$ is (strictly) concave since

$h(x_{i})=1-\frac{y}{x_{i}+y},$

which is evidently (strictly) concave in $x_{i}$ since $y$ is a constant. We
can see that $g$ is jointly concave in its arguments as it is the perspective
transform of the function $f$, which preserves concavity (cf., [3, §3.2.6]).
Finally, we need to show that $g$ is nondecreasing in its second argument. To
see this, let $0\leq t\leq t^{\prime}$, then we have

$\displaystyle
g(x_{i},t^{\prime})=t^{\prime}f\left(\frac{x_{i}}{t^{\prime}}\right)$
$\displaystyle=t^{\prime}f\left(\frac{t}{t^{\prime}}\frac{x_{i}}{t}+\left(1-\frac{t}{t^{\prime}}\right)0\right)$
(2) $\displaystyle\geq
tf\left(\frac{x_{i}}{t}\right)+\left(1-\frac{t}{t^{\prime}}\right)f(0)=tf\left(\frac{x_{i}}{t}\right)=g(x_{i},t).$

The inequality follows from the definition of concavity, while the second-to-
last equality follows from the fact that $f(0)=0$.

#### Selfish maximum.

The fact that $g$ is nondecreasing in its second argument also has an
interesting consequence: a player never does better in the pro-rata game when
compared to the ‘selfish’ version. In other words, for a fixed $x_{i}$, player
$i$ has the largest payoff when all other players $j\neq i$ have $x_{j}=0$.
This is easy to see since

$t=\frac{x_{i}}{\mathbf{1}^{T}x}\leq 1$

so

$U_{i}(x)=g(x_{i},t)\leq g(x_{i},1)=f(x_{i}),$

where $g$ is as defined above. The inequality follows from the monotonicity of
$g$ in its second argument.

#### Strict concavity.

In the important special case where $f$ satisfies

$f(\alpha t)>\alpha f(t),$ (3)

for every $t>0$ and $0<\alpha<1$, then the function $U_{i}(\cdot,y)$ is
strictly concave in its first argument. (We will show this soon.) Property (3)
has the interpretation that any chord of the function, drawn between $(0,0)$
and any other point on the graph, lies strictly below the function itself. For
example, a sufficient condition is that the function $f$ is strictly concave,
though this condition is not a necessary one as there are functions which are
not strictly concave that satisfy (3). See appendix C for a more general
condition.

Since we know that $h$ is a strictly concave function and $g$ is a concave
function, we can show that $g(x_{i},h(x_{i}))$ is strictly concave in $x_{i}$
by showing that $g$ is strictly increasing in its second argument. Strict
concavity of $g$ follows from the usual composition rules (see [3, §3.2.4]).
To show that $g$ is strictly increasing in its second argument, let
$0<t<t^{\prime}$, then:

$g(x_{i},t^{\prime})=t^{\prime}f\left(\frac{x_{i}}{t^{\prime}}\right)=t^{\prime}f\left(\frac{t}{t^{\prime}}\frac{x_{i}}{t}\right)>t^{\prime}\frac{t}{t^{\prime}}f\left(\frac{x_{i}}{t}\right)=tf\left(\frac{x_{i}}{t}\right)=g(x_{i},t),$

where the inequality follows from an application of (3) with
$\alpha=t/t^{\prime}$.

#### Definitions.

For completeness, we state several important game theoretic definitions [12].
To each player $i=1,\dots,n$, we associate a _strategy_ , which is a
probability distribution $\pi_{i}$ over the possible actions of player $i$,
the nonnegative real numbers. We say a strategy is _pure_ if $\pi_{i}$ is a
deterministic distribution or point mass. In other words, we say a strategy is
pure when the probability of choosing a specific action $z$ is always one;
i.e., $\pi_{i}(\\{z\\})=1$ for some $z\geq 0$. Otherwise, we say the strategy
is _mixed_.

A _Nash equilibrium_ (simply an _equilibrium_ from here on out) is a
collection of strategies $\pi_{i}$ for each player $i=1,\dots,n$ such that no
individual player can achieve a strictly better outcome by choosing a
different strategy. Concretely, let $x_{i}\sim\pi_{i}$ be a random variable
chosen by player $i$’s strategy (mixed or pure) and let $y_{i}\sim\pi_{-i}$ be
a random variable denoting the sums of random variables from other players’
strategies. The collection of strategies $(\pi_{i})$ consists of an
equilibrium if, for each player $i$, we have

$\mathbf{E}_{x_{i}\sim\pi_{i},~{}y_{i}\sim\pi_{-i}}\left[{U_{i}(x_{i},y_{i})}\right]\geq\mathbf{E}_{x_{i}\sim\tilde{\pi}_{i},~{}y_{i}\sim\pi_{-i}}\left[{U_{i}(x_{i},y_{i})}\right],$

where $\tilde{\pi}_{i}$ denotes any strategy. (For the remainder of the paper,
we will drop the $x_{i}$ and $y_{i}$ in the definition of the expectation to
shorten notation.) If the above condition holds with strict inequality for all
$i$ except when $\tilde{\pi}_{i}=\pi_{i}$, the equilibrium is said to be
_strict_. In words, an equilibrium is strict if each player would achieve a
strictly worse outcome by choosing a different strategy. In general, we say an
equilibrium is pure if all strategies of that equilibrium are pure, and mixed
otherwise.

#### Pure equilibria.

With those definitions, we note that the strict concavity of $U_{i}(x_{i},y)$
in $x_{i}$ has an important, direct consequence: every equilibrium of this
game is a pure equilibrium. Let $x_{i}\sim\pi_{i}$ be any strategy that is not
pure, while $y_{i}\sim\pi_{-i}$ is a random variable denoting the sums of the
other players’ strategies, then

$\mathbf{E}_{\pi_{i},\pi_{-i}}\left[{U_{i}(x_{i},y_{i})}\right]=\mathbf{E}_{\pi_{-i}}\left[\mathbf{E}_{\pi_{i}}\left[{U_{i}(x_{i},y_{i})}\right]\right]<\mathbf{E}_{\pi_{-i}}\left[{U_{i}(\mathbf{E}_{\pi_{i}}[x_{i}],y_{i})}\right],$

where the strict inequality is a result of strict concavity of
$U_{i}(\cdot,y)$ for all $y$ and the fact that $\pi_{i}$ is not a point mass.
In other words, if $x_{i}\sim\pi_{i}$ is a mixed strategy for player $i$, then
this player is always strictly better off playing the pure strategy
$\mathbf{E}_{\pi_{i}}[x_{i}]$ instead. For the remainder of this paper, we
will assume that $f$ is concave and satisfies condition (3), unless otherwise
stated. Additionally we will only discuss pure equilibria for the remainder of
the paper, as all equilibria must be pure, so talking about a strategy as as a
specific action $x_{i}\in{\mbox{\bf R}}_{+}$ is reasonable.

#### Extensions.

A simple immediate extension to the concave pro-rata game is to consider
payoff functions of the form:

$U_{i}(x)=\frac{c_{i}x_{i}}{c^{T}x}f\left(c^{T}x\right),$

for some strictly positive vector $c\in{\mbox{\bf R}}_{++}^{n}$. A more
general extension is when we have a collection of $n$ strictly increasing
functions $\varphi_{i}:{\mbox{\bf R}}_{+}\to{\mbox{\bf R}}$, where
$\varphi_{i}(0)=0$ and $\varphi_{i}(t)\to\infty$ when $t\to\infty$ for
$i=1,\dots,n$, and

$U_{i}(x)=\left(\frac{\varphi_{i}(x_{i})}{\sum_{i=1}^{n}\varphi_{i}(x_{i})}\right)f\left(\sum_{i=1}^{n}\varphi_{i}(x_{i})\right).$

In either case, all of the same properties given above apply to this slightly
more general game with nearly identical proofs, but we will only consider the
(often useful) special case where $\varphi_{i}(t)=t$.

###  1.1 Symmetric pure strict equilibrium

There is a strict, pure equilibrium where all players have equal strategies,
given by $x=(q/n)\mathbf{1}$ where $q$ is the optimizer of the following
problem:

maximize $\displaystyle q^{n-1}f(q)$ (4) subject to $\displaystyle q\geq 0,$

with variable $q\in{\mbox{\bf R}}$. We will show some properties of this
result first and then show that the pure strategy $x=(q/n)\mathbf{1}$ is,
indeed, an equilibrium.

#### Solution properties.

This problem has a (unique) and finite solution $q>0$ provided $f(z)>0$ and
$f(w)=0$ for some $0<z<w$. The fact that $q>0$ follows by noting that that $q$
must satisfy $q^{n-1}f(q)\geq z^{n-1}f(z)>0$ since it is optimal. On the other
hand, the fact that $q$ is finite follows from the fact that, for any $r\geq
w$, we have

$\frac{w}{r}f(r)+\left(1-\frac{w}{r}\right)f(0)\leq f(w)=0,$

where the first inequality follows from the definition of concavity. Since, by
assumption, $f(0)=0$ and $w/r>0$, we have that $f(r)\leq 0$ so $r$ cannot be
optimal. (In fact, both statements combined prove the stronger fact that
$0<q<w$, but this is not necessary for what follows.) The uniqueness of the
solution to problem (4) follows from observing that the logarithm of the
objective function is strictly concave. (This is true since $\log$ is strictly
increasing and $\log\circ f$ is concave if $f$ is concave.)

#### Discussion.

It may appear that the condition placed on $f$ is very strong, but in fact,
any $f$ not satisfying the above condition has only trivial (or no)
equilibria. In particular, since $f$ is concave, if $f$ does not satisfy the
above condition, either (a) $f$ is strictly positive everywhere except at
$f(0)=0$, (b) $f$ is strictly negative everywhere except at $f(0)=0$, or (c)
$f=0$. In the first case, there is no equilibrium as any player can improve
their payoff by increasing their strategy. In the second case, any player who
plays a nonzero strategy receives negative payoff (whereas playing the zero
strategy would give 0 payoff). While, in the third case, any strategy is an
equilibrium.

#### Equilibrium properties.

The collection of strategies $x=(q/n)\mathbf{1}$ is clearly pure and
symmetric. To see that $x=(q/n)\mathbf{1}$ is a strict equilibrium, note that
the best response for any player $i$, when every other player plays strategy
$q/n$ is:

maximize $\displaystyle\frac{x_{i}}{x_{i}+(1-1/n)q}f(x_{i}+(1-1/n)q)$ (5)
subject to $\displaystyle x_{i}\geq 0,$

with variable $x_{i}\in{\mbox{\bf R}}$. We will show that the solution to (5)
is $x_{i}=q/n$ in two steps. First, we will show that any solution must have
$x_{i}>0$ and therefore that the first order optimality conditions applied to
the objective suffice. We will then show that $x_{i}=q/n$ is a solution to the
optimality conditions. This result, combined with the fact that the objective
is strictly concave, implies that $x_{i}=q/n$ is the unique solution to the
optimality conditions, which proves the final claim that this equilibrium is
strict.

To see that any solution to the best response problem (5) must have $x_{i}>0$,
note that $q/n$ is feasible and achieves an objective value of $f(q)/n>0$,
which is strictly greater than the objective value of zero achieved by
$x_{i}=0$.

Next, note that $q>0$ must satisfy the first order optimality conditions of
(4):

$(n-1)f(q)+qf^{\prime}(q)=0.$ (6)

On the other hand, the first order optimality conditions for the objective of
problem (5) are that $x_{i}$ must satisfy (writing $q^{\prime}=(1-1/n)q$ for
convenience)

$\frac{q^{\prime}}{x_{i}+q^{\prime}}f(x_{i}+q^{\prime})+x_{i}f^{\prime}(x_{i}+q^{\prime})=0.$

Choosing $x_{i}=q/n$ clearly satsfies this condition, since plugging this
value in gives

$\left(1-\frac{1}{n}\right)f(q)+\frac{qf^{\prime}(q)}{n}=\frac{1}{n}((n-1)f(q)+qf^{\prime}(q))=0,$

as required. Since the objective is strictly concave, this is the unique
$x_{i}$ satisfying the optimality conditions and is therefore the best
response. Additionally, while we have assumed that $f$ is differentiable, a
very similar proof using subgradient calculus gives an identical result.

###  1.2 Uniqueness of equilibrium

In fact, it is not hard to show that the symmetric, pure, strict equilibrium
is, surprisingly, the unique equilibrium for this game, under the same
conditions as (4); i.e., that $f(z)>0$ and $f(w)=0$ for some $0<z<w$. This
proof can be broken down into a few steps. First, we will show that any
equilibrium $x$ satisfies $f(\mathbf{1}^{T}x)>0$ and $x_{i}>0$ for each $i$.
This will then be used to show that there is no non-symmetric equilibrium,
and, since we know that any symmetric equilibrium must satisfy equation (4),
which has a unique solution, we then know that it is the unique equilibrium of
this game.

#### Positivity of equilibria.

First we will show that $f(v)>0$ for every $0<v<w$. To see this, note that the
function $f$ is bounded from below by all of its chords, as it is a concave
function. Note that the chord with endpoints $(0,0)$ and $(z,f(z))$ lies above
the $x$-axis, except at $(0,0)$, while the chord with endpoints $(z,f(z))$ and
$(w,f(w))=(w,0)$ lies above the $x$-axis, except at $(w,0)$, which leads to
the final result.

Now, suppose a collection of (pure) strategies satisfies
$f(\mathbf{1}^{T}x)<0$. Since $f(0)=0$, there is some index $i$ such that
$x_{i}>0$. This implies that $U_{i}(x_{i},\mathbf{1}^{T}x-x_{i})<0$. But then
player $i$ can achieve a payoff equal to $0$ by employing the strategy
$\tilde{x}_{i}=0$, which is strictly better than a negative payoff, so $x$
cannot be an equilibrium.

On the other hand, if a collection of strategies satisfies
$f(\mathbf{1}^{T}x)=0$, then, from the previous discussion, we must have
either $\mathbf{1}^{T}x=0$ or $\mathbf{1}^{T}x=w$. If $\mathbf{1}^{T}x=0$, any
player $i$ can obtain a strictly positive payoff by playing the strategy
$\tilde{x}_{i}=z$. If, instead, $\mathbf{1}^{T}x=w>0$, there is some index $i$
such that $x_{i}>0$. We have that the player’s payoff is
$U_{i}(x_{i},\mathbf{1}^{T}x-x_{i})=0$ which means that

$U_{i}(x_{i}-\varepsilon,\mathbf{1}^{T}x-x_{i})=\frac{x_{i}-\varepsilon}{\mathbf{1}^{T}x-\varepsilon}f(\mathbf{1}^{T}x-\varepsilon)>0,$

for $\varepsilon>0$ small enough since $f(w-\varepsilon)>0$, so $x$ is not an
equilibrium.

Putting all of these statements together means that any equilibrium $x$
satisfies $f(\mathbf{1}^{T}x)>0$ and $\mathbf{1}^{T}x<w$. To see that any
equilibrium must also satisfy $x>0$, note that if there exists an index $i$
with $x_{i}=0$ for a collection of strategies with $f(\mathbf{1}^{T}x)>0$,
player $i$ can always achieve a strictly positive payoff by playing
$\tilde{x}_{i}=\varepsilon>0$, for $\varepsilon$ small enough.

#### Symmetry of equilibria.

Next, we will show that if $x_{i}$ is a best response for player $i$, then any
$j$ for which $x_{j}>x_{i}$ is not a best response for player $j$, and vice
versa. This will immediately show that any equilibrium must satisfy
$x_{i}=x_{j}$ (i.e., it is symmetric). We will show this in the case that $f$
is differentiable, but a similar proof holds in the more general case, using
subgradient calculus.

Let $x$ be an equilibrium with $x_{j}>x_{i}$. Given that $x_{i}$ is a best
response, then the optimality conditions for (5) imply that:

$\left(\frac{\mathbf{1}^{T}x-x_{i}}{(\mathbf{1}^{T}x)^{2}}\right)f(\mathbf{1}^{T}x)+\frac{x_{i}}{\mathbf{1}^{T}x}f^{\prime}(\mathbf{1}^{T}x)=0.$

Since $x$ is an equilibrium, from the previous discussion, we have that
$f(\mathbf{1}^{T}x)>0$, $x_{i}>0$, and $\mathbf{1}^{T}x>x_{i}$, so
$f^{\prime}(\mathbf{1}^{T}x)<0$. On the other hand, differentiating the
objective of the best response problem (5) for player $j$ gives

$\left(\frac{\mathbf{1}^{T}x-x_{j}}{(\mathbf{1}^{T}x)^{2}}\right)f(\mathbf{1}^{T}x)+\frac{x_{j}}{\mathbf{1}^{T}x}f^{\prime}(\mathbf{1}^{T}x)<\left(\frac{\mathbf{1}^{T}x-x_{i}}{(\mathbf{1}^{T}x)^{2}}\right)f(\mathbf{1}^{T}x)+\frac{x_{i}}{\mathbf{1}^{T}x}f^{\prime}(\mathbf{1}^{T}x)=0,$

where the inequality follows from the fact that, since $x_{i}<x_{j}$ we have

$\frac{\mathbf{1}^{T}x-x_{j}}{(\mathbf{1}^{T}x)^{2}}<\frac{\mathbf{1}^{T}x-x_{i}}{(\mathbf{1}^{T}x)^{2}}\quad\text{and}\quad\frac{x_{j}}{\mathbf{1}^{T}x}>\frac{x_{i}}{\mathbf{1}^{T}x},$

so $x_{j}$ cannot be a best response as it is not optimal for (5). The
converse case, when $x_{j}<x_{i}$ with $x_{i}$ being a best response, follows
from a nearly identical proof. This immediately implies that any equilibrium
must be symmetric, so, from the preceding discussion, the unique equilibrium
is the one given by the solution to problem (4).

###  1.3 Equilibrium payoff

Conditioned on each player receiving the same payoff (a fairness condition),
the optimal allocation every player would get is

$\frac{1}{n}\sup f,$

which is, by definition, at least as good as the equilibrium payoff:

$\frac{1}{n}f(q),$

where $q>0$ is the solution to (4). In fact, we can show that the optimal fair
allocation is always strictly better than the equilibrium payoff. To see this,
note that, under the assumptions on $f$ introduced above, we know $\sup f$ is
achieved by some value $0<q^{\star}<w$, satisfying $f^{\prime}(q^{\star})=0$.
Rearranging the first order optimality condition for $q$ in problem (4) gives

$f^{\prime}(q)=-(n-1)\frac{f(q)}{q}<0,$

for all $n>1$ since $f(q)>0$. This means that $q$ does not satisfy the
optimality condition for maximizing $f$, so $f(q)<f(q^{\star})=\sup f$. (In
fact, this says slightly more: using the concavity of $f$, we have that
$q>q^{\star}$, i.e., that players ‘overpay’ at equilibria when $n>1$.)

#### Price of anarchy.

Given the same assumptions as the beginning of §1.2 on the function $f$, it is
not difficult to show that the price of anarchy satisfies

$\frac{\sup f}{f(q)}\geq\Omega(n)$

as the number of players $n$ becomes large for some constant $C$. To see this,
consider the first order optimality conditions for $y$ (4):

$(n-1)f(q)+qf^{\prime}(q)=0.$

Note that $f^{\prime}(q)<0$ since $q>0$ and $f(q)>0$, so

$f(q)=-\frac{qf^{\prime}(q)}{n-1}>0,$

whenever $n>1$. Since $f$ is concave, then $f^{\prime}$ is monotonically
nonincreasing, and, since $q\leq w$ for every $n$ we have that

$f(q)=-\frac{qf^{\prime}(q)}{n-1}\leq-\frac{wf^{\prime}(w)}{n-1}\leq
O\left(\frac{1}{n}\right).$

Finally, we know that $\sup f$ is constant in the number of players, so

$\frac{\sup f}{f(q)}\geq\Omega(n).$

##  2 Batched decentralized exchanges

In this section, we will show some basic applications of the above properties
to a batched decentralized exchange, which we describe below.

#### Decentralized exchanges.

A _decentralized exchange_ (or DEX, for short) is a type of exchange that
exists on a blockchain. Such exchanges enable any agent to trade currencies
without the need for a centralized intermediary. In many cases, these
exchanges are organized as constant function market makers (see, e.g., [1] for
a general introduction to this type of exchange), a special type of automated
market maker that uses a specific function to price assets.

#### Batched DEXs.

A _batched_ decentralized exchange is a DEX where the trades are batched
before they are executed. Specifically, the trades are aggregated in some way
(depending on the type of batching performed) and then traded ‘all together’
through the DEX, before being disaggregated and passed back to the users.
Though the idea of a batched exchange has been proposed many times in
different contexts (see, e.g., [4] and [13]), presently, almost all major
decentralized exchanges are not batched. Recent work has suggested that
batching is useful for privacy [5] and Penumbra [9] has proposed a design for
a fully-private decentralized exchange which makes use of batching as a method
for avoiding certain information leakage [2]. We describe a very simplified
version of this proposal below, which will suffice for our discussion.

#### Batching design.

In this scenario, we have traders $i=1,\dots,n$ who all wish to trade some
amount, say $\Delta_{i}\in{\mbox{\bf R}}$ of asset $A$ for some other asset,
which we will call asset $B$. In this case, negative values of $\Delta_{i}$
denote that trader $i$ wishes to receive some amount of asset $A$ (and will
instead tender asset $B$ to the protocol). For convenience, we will assume
that $\mathbf{1}^{T}\Delta>0$, i.e., on net, traders want more of asset $B$
than asset $A$. The batching protocol of penumbra first clears all trades to
get a nonnegative vector of ‘residual’ trades $\Delta^{\prime}\in{\mbox{\bf
R}}_{+}^{n}$ with $\mathbf{1}^{T}\Delta=\mathbf{1}^{T}\Delta^{\prime}$. (In
other words, the protocol does not generate debts in any one side.) We can
view $\Delta^{\prime}$ as the ‘excess demand’ for asset $B$ over $A$ and leave
the mechanism for constructing $\Delta^{\prime}$ otherwise unspecified,
requiring only the additional condition that, if $\Delta\geq 0$, then
$\Delta^{\prime}=\Delta$. (This condition can be roughly stated as: if the
only trades are due to excess demand, then no clearing happens.) The protocol
then pools the residual demand, $\mathbf{1}^{T}\Delta^{\prime}$ and trades it
against a constant function market maker, represented by some function $g$, to
receive $g(\mathbf{1}^{T}\Delta^{\prime})$ of asset $B$, which it then
distributes to each agent $i$ in a pro-rata way, leading to an identical form
to that of the pro-rata payoff (1) with $x=\Delta^{\prime}$. Constant function
market makers always have concave $g$, known sometimes as the _forward
exchange function_ (cf., [1, §4]), with $g(0)=0$, and, in many practical
cases, these functions are strictly concave.

###  2.1 Arbitrage

A common way of analyzing markets is through the lens of _arbitrage_ : the
ability to exploit price differences in order to make essentially risk-free
profit. From before, we will write $g$ for the forward exchange function of a
constant function market maker, used by the batching design presented above.

#### Existence.

Assuming $g$ is differentiable at $0$, we can interpret $g^{\prime}(0)$ as the
marginal amount of asset $B$ that one would receive for a marginal amount of
$A$. (The function $g$ is often not differentiable at $0$, but is one-sided
differentiable at $0^{+}$, which suffices.) If $g^{\prime}(0)$ is larger than
the price of an external market, say $c>0$, then anyone who can directly trade
with $g$ can make risk-free profit by trading some (potentially small) amount,
$t>0$ of asset $A$ for $g(t)$ of asset $B$, and then sell this amount of asset
$B$ to get $g(t)/c-t>0$ of profit. (One simple way to see this is true is to
use the definition of a derivative on $g(t)/c$ and send $t\downarrow 0$.)

#### Optimal arbitrage.

Since an agent can make risk-free profit in these cases, it is reasonable to
ask: what is the maximum amount of profit an agent can make with this
strategy? This is known as the _optimal arbitrage problem_ , written:

maximize $\displaystyle g(t)-ct$ subject to $\displaystyle t\geq 0,$

with variable $t\in{\mbox{\bf R}}$. From before, if we know that
$g^{\prime}(0)>c$, then this problem has an optimal value that is strictly
positive. If $g$ is differentiable, the optimal solution $t^{\star}$ satisfies

$g^{\prime}(t^{\star})=c,$

which we can see from the first-order optimality conditions for this problem.
This has the interpretation that the marginal price of the CFMM after the
trade $t^{\star}$, given by $g^{\prime}(t^{\star})$ should be equal to the
price of the external market, which we defined to be $c$.

#### The (aggregated) arbitrage game.

In the batched exchange above, arbitrageurs cannot directly trade with the
constant function market maker, but must instead go through the batching
process. Assuming there are $n$ arbitrageurs competing to maximize their
profit, the next question is: what are the properties of this game? Defining

$f(t)=g(t)-ct,$

then this game is a concave pro-rata game with function $f$, since the payoff
(1) for player $i$ is

$U_{i}(x_{i},y_{i})=\frac{x_{i}}{x_{i}+y_{i}}f(x_{i}+y_{i})=\frac{x_{i}}{x_{i}+y_{i}}g(x_{i}+y_{i})-cx_{i}.$

Note that this is exactly the amount received from the DEX with forward
exchange function $g$, minus the cost of trading $x_{i}$ with the external
market, for player $i$. This game inherits all of the properties derived in
§1. We show some numerical simulations of iterated behavior for some utility
functions of this form in appendices A and B.

##  3 Conclusion

We introduced concave pro-rata games and established several useful properties
under relatively mild conditions. In particular, we showed the existence of a
unique equilibrium that is symmetric and pure. This equilibrium can be
computed efficiently by solving a single variable, unimodal optimization
problem. We further established that the price of anarchy is $\Omega(n)$ in
the number of players, relative to the optimal ‘fair’ allocation. We
illustrated how concave pro-rata games connect to a recent proposal for a
batched decentralized exchange and numerically studied the behavior of agents
engaged in such a game in the iterated setting for a specific form of utility
function. Future work includes further study of the optimal arbitrage problem
for batched decentralized exchanges.

## References

  * [1] Angeris, G., Agrawal, A., Evans, A., Chitra, T., Boyd, S.: Constant Function Market Makers: Multi-asset Trades via Convex Optimization. In: Handbook on Blockchain, p. 31. Springer, first edn. (2022)
  * [2] Angeris, G., Evans, A., Chitra, T.: A Note on Privacy in Constant Function Market Makers (Mar 2021)
  * [3] Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, UK; New York (2004)
  * [4] Budish, E., Cramton, P., Shim, J.: The High-Frequency Trading Arms Race: Frequent Batch Auctions as a Market Design Response. The Quarterly Journal of Economics 130(4), 1547–1621 (Nov 2015). https://doi.org/10.1093/qje/qjv027
  * [5] Chitra, T., Angeris, G., Evans, A.: Differential Privacy in Constant Function Market Makers. Financial Cryptography and Data Security 2022 (2022)
  * [6] Daian, P., Goldfeder, S., Kell, T., Li, Y., Zhao, X., Bentov, I., Breidenbach, L., Juels, A.: Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In: 2020 IEEE Symposium on Security and Privacy (SP). pp. 910–927 (2020). https://doi.org/10.1109/SP40000.2020.00040
  * [7] Diamond, S., Boyd, S.: CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research 17(83), 1–5 (2016)
  * [8] O’Donoghue, B., Chu, E., Parikh, N., Boyd, S.: Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications 169(3), 1042–1068 (June 2016), http://stanford.edu/~boyd/papers/scs.html
  * [9] Penumbra Labs: ZSwap - The Penumbra Protocol. https://protocol.penumbra.zone/main/zswap.html
  * [10] Rosen, J.B.: Existence and Uniqueness of Equilibrium Points for Concave N-Person Games. Econometrica 33(3), 520 (Jul 1965). https://doi.org/10.2307/1911749
  * [11] Selten, R.: Preispolitik der Mehrproduktenunternehmung in der statischen Theorie (1970)
  * [12] Von Neumann, J., Morgenstern, O.: Theory of games and economic behavior. In: Theory of games and economic behavior. Princeton university press (2007)
  * [13] Walther, T.: Multi-token Batch Auctions with Uniform Clearing Prices (Jul 2018)

##  Appendix A Numerics

The results of §1 provide insight into the equilibrium behavior of concave
pro-rata games. Here we explore the transient behavior of such games through
simulation.

#### Game setup.

Suppose that the game is played iteratively, and, at each iteration $t$,
player $i$ chooses some action $x_{i}^{t}$ as the best response to the actions
chosen by the other players in the previous round (denoted as $x_{-i}^{t-1}$),
possibly subject to additional constraints. We consider the following
scenarios:

  1. 1.

At iteration $t$, player $i$ takes action equal to the best response to
$x_{-i}^{t-1}$.

  2. 2.

At iteration $t$, player $i$ takes action equal to the best response to
$x_{-i}^{t-1}$ subject to a budget constraint ($x_{i}^{t}\in[0,M_{i}]$).

#### Payoff functions.

For these simulations, we use functions $f$ of the form $f(t)=g(t)-ct$ where
$c>0$ and $g(t)=\frac{\gamma R_{2}t}{R_{1}+\gamma t}$ with $0<\gamma\leq 1$,
$R_{1},R_{2}>0$. The function $g(t)$ is the forward exchange function for a
Uniswap V2 swap pool with reserves $R\in{\mbox{\bf R}}^{2}_{+}$ and fee
parameter $\gamma$ when asset $1$ is being tendered and asset $2$ is being
received. This setting simulates $n$ arbitrageurs competing to maximize their
profit, where $c$ denotes the external market price of asset $2$. For
simulations using a somewhat more simple payoff function, see appendix B. Note
that $f$ is strictly concave and therefore satisfies condition (3), and
clearly $f(0)=0$.

#### Shared equilibrium.

The (unique) symmetric pure equilibrium strategy is the solution to problem
(4). This is easy to compute using the first order optimality conditions for
problem (4) given in (6). Plugging in this particular form of $f$, we obtain
the following quadratic equation:

$(cn\gamma^{2})q^{2}+q(\gamma^{2}R_{2}+2cnR_{1}\gamma-\gamma^{2}nR_{2})+(cnR_{1}^{2}-\gamma
nR_{1}R_{2})=0.$ (7)

The equilibrium is then given by $x_{i}=q/n$, for each player $i=1,\dots,n$
where $q$ denotes the positive root of (7).

#### Best responses.

The best response of player $i$, given the budget constraint $0\leq x_{i}\leq
M_{i}$ and other players’ strategies $y_{i}=\mathbf{1}^{T}x-x_{i}$, is given
by

maximize $\displaystyle U(x_{i},y_{i})$ (8) subject to $\displaystyle
x_{i}\in[0,M_{i}],$

with variable $x_{i}\in{\mbox{\bf R}}$. This is a single-variable convex
optimization problem that is easily solved in practice by any number of off-
the-shelf packages [7, 8]. When $x_{i}$ is unconstrained, the optimal value of
(8) is given by

$x_{i}=\frac{1}{\gamma}\left(\sqrt{\frac{\gamma
R_{1}R_{2}+\gamma^{2}R_{2}y}{c}}-R_{1}\right)-y$

For more details, the code is available at (anonymized for review).

Figure 1: Number of iterations to reach equilibrium versus the number of
players in Scenario 1.

#### Simulation results.

In our simulations, we fix $\gamma=0.99$, $R_{1}=200$, $R_{2}=250$, and $c=1$.
We average each reported value over $100$ trials. In figure 1, the intial
strategy of each player is drawn uniformly at random from the interval
$(0,w/n)$, where $w$ is a value such that $f(w)=0$.

Figure 1 illustrates that the number of iterations needed to reach the unique
equilibrium, in the absence of budget constraints, scales superlinearly in the
number of players. We define the number of iterations to reach equilibrium as
the number iterations until the strategy of every player is equal to the
unique equilibrium up to the first decimal place; i.e., the first round $t$
such that

$\max_{i}|x_{i}^{t}-x^{\star}|<0.1,$

where $x^{\star}$ denotes the equilibrium strategy.

Figure 2: Percent increase in whale strategy and whale profit versus the
number of fish when compared to the unconstrained equilibrium strategy and
profit.

In figure 2, we consider the setting where there is one player who has
unlimited budget (whom we will call a _whale_) and all remaining players have
some budget $M_{i}<q/n$ (these players are referred to as _fish_). The budgets
of the fish are drawn uniformly from the interval $M_{i}\sim[0,q/n]$ and the
initial strategy of each fish is drawn uniformly at random from the interval
$[0,M_{i}]$. The equilibrium strategy chosen by the fish is to use their
entire budget, while the whale chooses a strategy in excess of the
unconstrained equilibrium strategy and is, as a result, able to extract
greater profit. Figure 2 illustrates that the whale chooses an increasingly
large strategy and receives an increasing profit as the number of fish
increases.

#### Price of anarchy.

In §1 we established the order of growth of the price of anarchy. Here we
illustrate the price of anarchy numerically for the specific family of payoff
functions introduced previously in this section. We again fix
$\gamma=0.99,R_{1}=200,R_{2}=250$ and $c=1$. The left plot of figure 3
illustrates the optimal payoff function and the equlibrium payoff function as
a function of the number of players $n$ while the right plot of figure 3
illustrates the price of anarchy as function of $n$.

Figure 3: (Left) Individual payoff of a player versus the number of players.
(Right) Ratio of the optimal payoff divided by the equilibrium payoff versus
the number of players.

##  Appendix B Additional Numerics

Here we expand on the simulations introduced in appendix A using a class of
utility function that allows us to express many quantities of interest in
closed form.

#### Game setup.

We consider the following three scenarios:

  1. 1.

At iteration $t$, player $i$ takes action equal to the best response to
$x_{-i}^{t-1}$.

  2. 2.

At iteration $t$, player $i$ takes action equal to the best response to
$x_{-i}^{t-1}$ subject to a bounded update constraint
($|x_{i}^{t}-x_{i}^{t-1}|\leq\delta$).

  3. 3.

At iteration $t$, player $i$ takes action equal to the best response to
$x_{-i}^{t-1}$ subject to a budget constraint ($x_{i}^{t}\in[0,M_{i}]$).

#### Payoff functions.

For these simulations, we use functions $f$ of the form $f(t)=t^{\beta}-\gamma
t$ where $0<\beta<1$ and $\gamma>0$. Note that $f$ is concave as it is the sum
of two concave functions and $f(0)=0$. These functions also satisfy the strict
concavity property (3) since

$f(\alpha t)=\alpha^{\beta}t^{\beta}-\alpha\gamma t>\alpha
t^{\beta}-\alpha\gamma t=\alpha f(t),$

for $0<\alpha<1$.

#### Shared equilibrium.

The (unique) symmetric pure equilibrium strategy is the solution to problem
(4). This is easy to compute using the first order optimality conditions for
problem (4) given in (6). Plugging in this particular form of $f$, we have:

$(n-1)(q^{\beta}-\gamma q)+q(\beta q^{\beta-1}-\gamma)=0,$

which has a solution

$q=\left(\frac{\beta+n-1}{n\gamma}\right)^{1/(1-\beta)}.$

The equilibrium is then given by $x_{i}=q/n$, for each player $i=1,\dots,n$.

Figure 4: (Left) Number of iterations to reach equilibrium versus the number
of players in Scenario 1. (Right) Number of iterations to reach equilibrium
versus $\delta$ in Scenario 2 (with $n=10$ players).

#### Simulation results.

In our simulations, we fix $\beta=0.5$ and $\gamma=0.05$. We average each
reported value over $100$ trials. In figure 4, the intial strategy of each
player is drawn uniformly at random from the interval $(0,w/n)$, where $w$ is
a value such that $f(w)=0$.

The left plot of figure 4 illustrates that the number of iterations needed to
reach the unique equilibrium, in the absence of budget constraints, scales
superlinearly in the number of players. The right plot demonstrates that in
the scenario of bounded strategy updates, for small values of $\delta$, the
number of iterations required to reach equilibrium increases significantly
when compared to the unbounded strategy update scenario.

Figure 5: Percent increase in whale strategy and whale profit versus the
number of fish when compared to the unconstrained equilibrium strategy and
profit.

In figure 5, we consider the setting where there is one player who has
unlimited budget (whom we will call a _whale_) and all remaining players have
some budget $M_{i}<q/n$ (these players are referred to as _fish_). The budgets
of the fish are drawn uniformly from the interval $M_{i}\sim[0,q/n]$ and the
initial strategy of each fish is drawn uniformly at random from the interval
$[0,M_{i}]$. The equilibrium strategy chosen by the fish is to use their
entire budget, while the whale chooses a strategy in excess of the
unconstrained equilibrium strategy and is, as a result, able to extract
greater profit. Figure 5 illustrates that the whale chooses an increasingly
large strategy and receives an increasing profit as the number of fish
increases.

#### Price of Anarchy

The equilibrium payoff can easibly be found to be

$\frac{1}{n}f(q)=\bigg{(}\frac{n+\beta-1}{\gamma
n}\bigg{)}^{\beta/(1-\beta)}\bigg{(}\frac{1-\beta}{n^{2}}\bigg{)}.$

Similarly, it can be show that the optimal payoff conditioned on every agent
receving the same payoff is given by

$\frac{1}{n}\sup
f=\bigg{(}\frac{\beta}{\gamma}\bigg{)}^{\beta/(1-\beta)}\bigg{(}\frac{1-\beta}{n}\bigg{)}.$

We obtain the price of anarchy by taking the ratio of the equilibrium payoff
and the optimal payoff:

$\frac{\sup f}{f(q)}=n\bigg{(}\frac{\beta
n}{n+\beta-1}\bigg{)}^{\beta/(1-\beta)}.$

We again fix $\beta=0.5$ and $\gamma=0.05$. The left plot of figure 6
illustrates the optimal payoff function and the equlibrium payoff function as
a function of the number of players $n$ while the right plot of figure 6
illustrates the price of anarchy as function of $n$.

Figure 6: (Left) Individual payoff of a player versus the number of players.
(Right) Ratio of the optimal payoff divided by the equilibrium payoff versus
the number of players.

##  Appendix C Relaxing strict concavity

We do not, in fact, need strict concavity in the proofs above. Instead, we
only need that $f$ has ‘some curvature’ at $0$. Specifically, it suffices that
for all $t$ and $t^{\prime}$ such that $0<t<t^{\prime}$, we have

$f(t)>\frac{f(t^{\prime})}{t^{\prime}}t.$

Written in English, this is the condition that the chord from $0$ to $t$
always lies strictly below the function. This condition is sometimes difficult
to confirm for general functions $f$, so we will show that this is equivalent
to the (potentially simpler-to-handle) property that all supergradients at $0$
lie strictly above the function at all points. We will show that, for any
concave function $f:{\mbox{\bf R}}_{+}\to{\mbox{\bf R}}$ with $f(0)=0$, the
following two statements are equivalent: (a) there is some $s^{\prime}>0$ and
$\alpha\in{\mbox{\bf R}}$ such that for every $s$ with $0\leq s\leq
s^{\prime}$ we have

$f(s)=\alpha s,$

and (b) there exists some $0<t<t^{\prime}$ such that

$\frac{f(t)}{t}=\frac{f(t^{\prime})}{t^{\prime}}.$ (9)

The statement above follows from the negation of both (a) and (b). This
equivalence has a simple interpretation: if the point $(0,0)$ is collinear
with any other two points on the graph of $f$, $\\{(s,f(s))\mid s>0\\}$, then
the function $f$ is a piecewise function with a linear segment starting at
$0$. The converse of this is that if the function $f$ has no linear segment
around $0$ (i.e., every linear overestimator around $0$ lies strictly above
$f$) then any chord must lie strictly below the function.

#### Proof.

The forward implication is very easy: pick $t^{\prime}=s^{\prime}$ and let $t$
be any $0<t<s^{\prime}$, then we have

$\frac{f(t^{\prime})}{t^{\prime}}=\alpha=\frac{f(t)}{t}.$

Now we’ll consider the reverse implication. Given $0<t<t^{\prime}$ satisfying
(9), we will show that, for any $0\leq s\leq t$ we have

$f(s)=\frac{f(t)}{t}s,$

which satisfies the original claim with $\alpha=f(t)/t$. First, it is easy to
show that

$f(s)\geq\frac{f(t)}{t}s,$ (10)

since

$f(s)=f\left(\frac{s}{t}t+\left(1-\frac{s}{t}\right)0\right)\geq\frac{s}{t}f(t),$

where the inequality follows from the concavity of $f$ and the fact that
$f(0)=0$. We will now show that any function $f$ satisfying (10) strictly,
i.e.,

$f(s)>\frac{f(t)}{t}s,$ (11)

for some $0<s<t$ cannot be concave. The result follows from the
contrapositive. To see this, let $0<\gamma\leq 1$ such that $t=\gamma
s+(1-\gamma)t^{\prime}$, then

$\gamma
f(s)+(1-\gamma)f(t^{\prime})>\gamma\frac{f(t)}{t}s+(1-\gamma)\frac{f(t)}{t}t^{\prime}=f(t)=f(\gamma
s+(1-\gamma)t^{\prime}),$

so $f$ cannot be concave. The inequality follows directly from conditions (9)
and (11), and both the first and second equalities follow from the definition
of $\gamma$.

##  Appendix D Rosen condition

Pro-rata games, even concave ones, do not satisfy the Rosen condition [10] for
the uniqueness of equilibria in concave games. The Rosen condition for
uniqueness is that if, there exists some $z\geq 0$ with $z\neq 0$ such that

$\Phi(x)=\begin{bmatrix}z_{1}\partial_{1}U_{1}(x)\\\ \vdots\\\
z_{n}\partial_{n}U_{n}(x)\end{bmatrix}$

is a strictly monotone operator; i.e., for any $x\neq y$ we have

$(y-x)^{T}(\Phi(y)-\Phi(x))>0,$

then there is a unique equilibrium that is also pure. (Here, $\partial_{i}$
denotes the $i$th partial derivative.) This is a common condition used to
prove the uniqueness of pure equilibria in games. We will show that this
condition does not hold in general for concave pro-rata games, even under most
‘niceness’ assumptions such as strict concavity or even strong concavity and
differentiability.

Setting $2x=y=\mathbf{1}$ then the condition can be written as (using the
definition of $U$)

$(\mathbf{1}^{T}z/2)((1/n)(f^{\prime}(n)-f^{\prime}(n/2))+(1-1/n)(f(n)-2f(n/2)))>0,$

but this can be rewritten (since $\mathbf{1}^{T}z>0$)

$(1/n)(f^{\prime}(n)-f^{\prime}(n/2))+(1-1/n)(f(n)-2f(n/2))>0,$

which is clearly not true for all concave functions $f$, since picking
$f(t)=\min\\{t,3n\\}$ suffices. (A mollifying argument would show that this
also gives a reasonable counterexample even in the case that $f$ is strictly
concave and differentiable.) A more direct counterexample that is
differentiable and strictly concave is $f(t)=(4n)^{2}-(4n-t)^{2}$, which is
slightly more difficult to verify.