Asymptotic growth of the price of anarchy for polynomial latency functions in selfish routing

Question

In Proposition 5.1 in http://timroughgarden.org/papers/indep.pdf the claim is that $$ \left(1 - \frac{p}{(p+1)^{\frac{p+1}{p}}}\right) = \Theta\left(\frac{\ln(p)}{p}\right) $$ but it is never proven. Asking wolframalpha.com it indeed gives this result. It does something with a generalized Puiseux series of which I have never heard. Is there an easy way to obtain this asymptotic behavior?

Answer 1

Start with $$A={(p+1)^{\frac{p+1}{p}}}\implies \log(A)={\frac{p+1}{p}}\log(p+1)$$ $$\log(A)=\log \left({p}\right)+\frac{1+\log \left({p}\right)}{p}+\frac{1}{2 p^2}-\frac{1}{6 p^3}+O\left(\frac{1}{p^4}\right)$$ $$A=e^{\log(A)}=p+\left(1+\log \left({p}\right)\right)+\frac{\left(1+\log \left({p}\right)\right)^2+1}{2 p}+O\left(\frac{1}{p^2}\right)$$ Continuing the process $$\left(1 - \frac{p}{(p+1)^{\frac{p+1}{p}}}\right)=\frac{1+\log \left({p}\right)}{p}-\frac{(2+\log \left({p}\right)) \log \left({p}\right)}{2p^2}+O\left(\frac{1}{p^3}\right)$$

Trying for $p=10$, the exact value is $0.2847$ while the truncated expansion gives $0.2807$

Edit

We could do a better approximation using Padé-like approximants to get for the expression $$\frac{6 p+4}{6 p^2+4 p+3}+\frac{2 p-1 }{2 p^2+p+1}\log (p)-\frac{\log ^2(p)}{2 \left(p^2+p+1\right)}+\frac{\log ^3(p)}{6 p \left(p^2+p+1\right)}$$ which, for $p=10$, would give $0.28483$ while the exact value is $0.28473$