  This paper investigates optimal error bounds and convergence rates for
general Mann iterations for computing fixed-points of non-expansive maps. We
look for iterations that achieve the smallest fixed-point residual after $n$
steps, by minimizing a worst-case bound $\|x^n-Tx^n\|\le R_n$ derived from a
nested family of optimal transport problems. We prove that this bound is tight
so that minimizing $R_n$ yields optimal iterations. Inspired from numerical
results we identify iterations that attain the rate $R_n=O(1/n)$, which we also
show to be the best possible. In particular, we prove that the classical
Halpern iteration achieves this optimal rate for several alternative stepsizes,
and we determine analytically the optimal stepsizes that attain the smallest
worst-case residuals at every step $n$, with a tight bound
$R_n\approx\frac{4}{n+4}$. We also determine the optimal Halpern stepsizes for
affine non-expansive maps, for which we get exactly $R_n=\frac{1}{n+1}$.
Finally, we show that the best rate for the classical Krasnosel'ski\u{\i}-Mann
iteration is $\Omega(1/\sqrt{n})$, and present numerical evidence suggesting
that even extended variants cannot reach a faster rate.
