Proof of Asymptotic Lower Bound for the Recentred N-Agent Cost without Uniform Control-Moment Hypotheses

Throughout, "the ledger lemma" is the ledger decomposition lemma, "the energy lemma" is the tracked energy bound lemma, "the cascade lemma" is the block cascade lemma and "the squares theorem" is the completion-of-squares theorem. For an admissible $\pi$ we write $K$, $t_{k}$, $L_{k}$, $\Lambda_{\star}$, $\Upsilon_{\mathrm{esc}}$, $\Upsilon_{\mathrm{lev}}$, $\mathcal{Z}$, $\mathcal{S}^{\mathrm{tr}}$, $\mathcal{P}$, $\mathcal{N}$, $\mathcal{B}_{N}$, $\mathcal{T}^{\mathrm{nr}}_{k}(s)$ and $C_{\Psi}$, $C_{\mathcal{N}}$ for the corresponding objects of the ledger lemma formed from $\pi$ for the $N$-th solution. Since admissibility is exactly the conjunction of the parameter-dependent requirements of the ledger lemma, and the parameter-free standing hypotheses are assumed here, the ledger lemma and everything it adopts — in particular the energy lemma and the cascade lemma — apply to the $N$-th solution for every admissible $\pi$ and every $N$.

Conclusion (a). Fix an admissible $\pi$ satisfying the absorption condition. Write, as in claim 4 of the energy lemma,

By (I$'$), $\kappa_{0}\le\kappa^{\sharp}$ for every $N$, so the last two summands are at most $\bigl(4R^{2}Tc_{\star}+2C_{\mathcal{D}}T+2C_{\mathcal{D}G}\bigr)c_{Q}\kappa^{\sharp}q_{0}^{-4}N^{-1}$, a fixed constant times $N^{-1}$; choose a natural number $N_{1}'$ beyond which their sum is at most $1$. Then, for $N\ge N_{1}'$, and using $\epsilon\le1$,

a real independent of $N$.

Step 1: a crude $N$-free bound. The absorption condition is the hypothesis of claim 5 of the energy lemma, and $\mathcal{J}_{N}\le\mathcal{J}^{\sharp}$ by (CB). That claim therefore gives, for every $N\ge N_{1}'$,

a finite real not depending on $N$ (the right-hand side of claim 5 is nondecreasing in $\mathcal{R}_{N}$ and in $\mathcal{J}^{\sharp}$).

Step 2: absorption at large $N$. By Step 1 and the monotonicity of $x\mapsto x^{3/4}$ on $[0,\infty)$,

and the right-hand side tends to $0$; choose $N_{1}\ge N_{1}'$ beyond which it is at most $1$. For $N\ge N_{1}$, claim 4 of the energy lemma and (CB) give

by the absorption condition. Since $\mathcal{Z}$ is finite (claim 1 of the energy lemma), the term $\tfrac{c_{\star}}{4}\mathcal{Z}$ may be subtracted, giving $\tfrac{3}{4}c_{\star}\mathcal{Z}\le\mathcal{J}^{\sharp}+1+\mathcal{R}^{\sharp}$, that is $\mathcal{Z}\le\mathcal{Z}^{\sharp}(\pi)$ after substituting the value of $\mathcal{R}^{\sharp}$. Finally claim 1(b) of the ledger lemma and (I$'$) give

Conclusion (b). Let $\varepsilon'>0$. We choose the entries of $\pi$ in the following order; at each step the quantities already fixed are treated as constants.

Step 1 ($T_{0}$, $\lambda_{c}$, $\lambda_{o}$). Put $\lambda_{c}=\lambda_{o}=T_{0}$, so that $\Lambda_{\star}=\max(4C_{a}^{2}K_{2}^{2}T_{0},T_{0})=c_{1}T_{0}$ with $c_{1}=\max(4C_{a}^{2}K_{2}^{2},1)$, a constant of the common data. By claim 1 of the cascade lemma $K$ is the least natural number with $KT_{0}\ge T$, so $K\le TT_{0}^{-1}+1$ and $\sqrt{K}\le(TT_{0}^{-1}+1)^{1/2}$, whence

using $T_{0}(TT_{0}^{-1}+1)^{1/2}=T_{0}^{1/2}(T+T_{0})^{1/2}$. The right-hand side tends to $0$ as $T_{0}$ decreases to $0$. Choose $T_{0}\in(0,T]$ so small that

This fixes $K$, the grid $t_{k}$, and the numbers $\mathcal{Z}^{\sharp}(\pi)$ and $W^{\sharp}(\pi)$, none of which depends on the remaining entries of $\pi$.

Step 2 ($\epsilon$). Choose $\epsilon\in(0,1]$ with $2\epsilon\bigl(C_{S}^{2}\mathcal{Z}^{\sharp}(\pi)+c_{Q}^{1/2}(\kappa^{\sharp})^{1/2}\bigr)\le\varepsilon'/6$ and $2\epsilon C_{S}^{2}\le c_{\star}/8$. Together with Step 1 this gives the absorption condition $2C^{\vee}_{tg}\Lambda_{\star}+2\epsilon C_{S}^{2}\le c_{\star}/4$. Fix $\rho^{*}_{G}>0$ for this $\epsilon$ as prescribed in the ledger lemma.

Step 3 ($\eta$, $\varrho$). Choose $\eta>0$ with $\eta\,W^{\sharp}(\pi)\le\varepsilon'/6$, fix a radius $\rho_{\eta}>0$ for it as in the ledger lemma, and put $\varrho=\rho_{\eta}/2$.

Step 4 ($\delta_{\mathrm{cl}}$). Choose $\delta_{\mathrm{cl}}\in(0,\rho^{*}/2]$.

Step 5 ($\varepsilon_{1}$, $q_{0}$). All of the following hold as soon as the positive real $\varepsilon_{1}+q_{0}$ is small enough, each condition being satisfied on an interval $(0,c]$ for some $c>0$ determined by the quantities already fixed: $(\varepsilon_{1}+q_{0})^{2}+\delta_{\mathrm{cl}}^{2}\le(\rho^{*})^{2}$ (possible since $\delta_{\mathrm{cl}}\le\rho^{*}/2$), $C_{3}(\varepsilon_{1}+q_{0})^{2}\le\tfrac{r_{0}}{4}\delta_{\mathrm{cl}}^{2}$, $\varepsilon_{1}+q_{0}\le\varepsilon_{tg}$ — these three are (SM) — together with $\varepsilon_{1}+q_{0}\le\rho^{*}_{G}$, with $(\varepsilon_{1}+q_{0})^{2}+\varrho^{2}\le\rho_{\eta}^{2}$, which is (SN) and holds as soon as $(\varepsilon_{1}+q_{0})^{2}\le\tfrac{3}{4}\rho_{\eta}^{2}$, and with

Choose $\varepsilon_{1}>0$ and $q_{0}>0$ accordingly. The tuple $\pi$ is now admissible and satisfies the absorption condition, and it determines $\Upsilon_{\mathrm{esc}}$ and $\Upsilon_{\mathrm{lev}}$, which are finite positive reals independent of $N$.

Step 6 ($N_{0}$). Let $N_{1}$ be as in conclusion (a) for this $\pi$. By claim 1 of the energy lemma, $P(\mathcal{N})\le c_{Q}\kappa_{0}q_{0}^{-4}N^{-2}\le c_{Q}\kappa^{\sharp}q_{0}^{-4}N^{-2}$, so $NP(\mathcal{N})\le c_{Q}\kappa^{\sharp}q_{0}^{-4}N^{-1}$; and by claim 1(d) of the ledger lemma together with conclusion (a), $\mathcal{P}\le\Lambda_{\star}\mathcal{Z}^{\sharp}(\pi)\Upsilon_{\mathrm{lev}}N^{-1}$ for $N\ge N_{1}$. Each of the four quantities

is therefore bounded by a constant independent of $N$ times a strictly negative power of $N$ — for the first and third this uses the substitution of the bound $\mathcal{P}\le\Lambda_{\star}\mathcal{Z}^{\sharp}(\pi)\Upsilon_{\mathrm{lev}}N^{-1}$ just displayed, which turns $\mathcal{P}^{1/2}$ into a constant times $N^{-1/2}$ and $\mathcal{P}$ into a constant times $N^{-1}$ — so all four tend to $0$. Moreover $P(\Omega_{0})=1$ and $|\mathfrak{s}_{0}|\le2\sqrt{N}$, so $\mathbb{E}[\mathbf{1}_{\Omega_{0}}\mathfrak{s}_{0}\cdot Z_{0}\mathfrak{s}_{0}]=\sum_{\gamma,\delta}Z^{\gamma\delta}_{0}\mathbb{E}[\mathfrak{s}^{\gamma}_{0}\mathfrak{s}^{\delta}_{0}]$ by linearity of the expectation, and by (I) each of the $l^{2}$ summands converges to $Z^{\gamma\delta}_{0}\Pi^{\gamma\delta}_{0}$. Choose $N_{0}\ge N_{1}$ so that for every $N\ge N_{0}$ the sum of the four displayed quantities is at most $\varepsilon'/6$ and

Conclusion. Let $N\ge N_{0}$. By conclusion (a), $\mathcal{Z}\le\mathcal{Z}^{\sharp}(\pi)$ and $\mathcal{S}^{\mathrm{tr}}+\mathcal{Z}\le W^{\sharp}(\pi)$. Every summand of $\mathcal{B}_{N}$ is nondecreasing in $\mathcal{Z}$, in $\mathcal{S}^{\mathrm{tr}}+\mathcal{Z}$, in $\mathcal{P}$ and in $\kappa_{0}$, so, grouping the summands of $\mathcal{B}_{N}$ as in Steps 1, 2, 3, 5 and 6 and using the five displayed bounds,

Claim 7 of the ledger lemma gives

and replacing $\mathbb{E}[\mathbf{1}_{\Omega_{0}}\mathfrak{s}_{0}\cdot Z_{0}\mathfrak{s}_{0}]$ by $\sum_{\gamma,\delta}Z^{\gamma\delta}_{0}\Pi^{\gamma\delta}_{0}$ at the cost of a further $\varepsilon'/6$ gives conclusion (b). The displayed sum is nonnegative by claim 2 of the ledger lemma.

Conclusion (c). Let $\varepsilon'>0$ and let $\pi$ and $N_{0}$ be as furnished by (b). Discarding the nonnegative filtering sum from the inequality of (b) gives $\mathcal{J}_{N}\ge V_{0}-\varepsilon'$ for every $N\ge N_{0}$, which is the assertion. $\square$