# On Multidimensional Congestion Games +
## Appendix A Technical Lemmas
: Since \(\frac{\delta\lambda}{\delta a}=26a-21d\), \(\lambda\) is minimized at \(a=\frac{21}{26}d\). By substituting, we get \(197d^{2}-156d\) which is non-negative for any \(d\in\mathbb{Z}\). **Lemma A7**. : _Let \(\theta:\mathbb{Z}_{\geq 0}^{6}\to\mathbb{Q}\) be the function such that \(\theta(a,b,c,d,e,f)=7a^{2}+3a(2b+2c-5d-2e-2f)+21 bf+21 ce-42 bc+35d^{2}-15d-6e-6f\). For any \((a,b,c,d,e,f)\in\mathbb{Z}_{\geq 0}^{6}\) such that \(a\geq b+c\) and \(d\geq e+f\), it holds that \(\theta(a,b,c,d,e,f)\geq 0\)._  
Proof. : At a first glance, in order to use standard arguments from calculus, we allow the \(6\)-tuples \((a,b,c,d,e,f)\) to take values in the set of non-negative real numbers. Since \(\frac{\delta\theta}{\delta c}=3(2a-14b+7e)\) and \(\frac{\delta\theta}{\delta f}=3(7b-2a-2)\), \(\theta\) is minimized at one of the following four cases: \(c=0\wedge f=0\), \(c=0\wedge f=d-e\), \(c=a-b\wedge f=0\) and \(c=a-b\wedge f=d-e\). In the first case, we get \(\theta=7a^{2}+3a(2b-5d-2e)+35d^{2}-15d-6e\). Since \(\frac{\delta\theta}{\delta\theta}=6a\), \(\theta\) is minimized at \(b=0\) which yields \(\theta=7a^{2}-3a(5d+2e)+35d^{2}-15d-6e\). Since \(\frac{\delta\theta}{\delta e}=-6(a+1)\), \(\theta\) is minimized at \(e=d\) which yields \(\theta=7(a^{2}-3 ad+5d^{2}-3d)\). The claim then follows for any \(d\
eq 1\) by applying Lemma A3. For the leftover tuples of the form \((a,0,0,1,1)\), we get \(\theta=7(a^{2}-3a+2)\) which is always non-negative for any \(a\in\mathbb{Z}\). In the second case, we get \(\theta=7a^{2}+3a(2b-7d)+7(3b(d-e)+5d^{2}-3d)\). Since \(\frac{\delta\theta}{\delta b}=3(2a+7(d-e))\), \(\theta\) is minimized at \(b=0\), which yields \(\theta=7(a^{2}-3 ad+5d^{2}-3d)\). The claim then follows for any \(d\
eq 1\) by applying Lemma A3. For the leftover tuples of the form \((a,0,0,1,e,1-e)\), we get \(\theta=7(a^{2}-3a+2)\) which is always non-negative for any \(a\in\mathbb{Z}\). In the third case, we get \(\theta=13a^{2}-3a(14b+5(d-e))+42b^{2}-21 be+35d^{2}-15d-6e\). Since \(\frac{\delta\theta}{\delta c}=3(5a-7b-2)\), \(\theta\) is minimized at either \(e=0\) or \(e=d\). For \(e=d\), we get \(\theta=13a^{2}-42 ab+42b^{2}-21 bd+35d^{2}-21d\). Since \(\frac{\delta\theta}{\delta b}=-21(2a-4b+d)\), \(\theta\) is minimized at \(b=\frac{2a+d}{4}\). This yields \(\theta=20a^{2}-84 ad+259d^{2}-168d\) and the claim then follows by applying Lemma A5. For \(e=0\), we get \(\theta=13a^{2}-3a(14b+5d)+42b^{2}+35d^{2}-15d\). Since \(\frac{\delta\theta}{\delta b}=42(2b-a)\), \(\theta\) is minimized at \(b=\frac{a}{2}\) which yields \(\theta=5(a^{2}-6 ad+14d^{2}-6d)\) and the claim then follows for any \(d\
eq 1\) by applying Lemma A4. For the leftover tuples of the form \((a,\frac{a}{2},\frac{a}{2},1,0,0)\), we get \(\theta=\frac{5}{2}(a^{2}-6a+8)\) which is always non-negative for any \(a\in\mathbb{Z}\setminus\{3\}\). Hence, we are still left to prove what happens for the tuples of the form \((3,b,3-b,1,0,0)\). In this case, we get \(\theta=42b^{2}-126b+92\) which is always non-negative for any \(b\in\mathbb{Z}\). In the fourth case, we get \(\theta=13a^{2}-21a(2b+d-e)+7(6b^{2}+3b(d-2e)+5d^{2}-3d)\). Since \(\frac{\delta\theta}{\delta c}=21(a-2b)\), \(\theta\) is minimized at either \(e=0\) or \(e=d\). For \(e=0\), we get \(\theta=13a^{2}-21a(2b+d)+7(6b^{2}+3 bd+5d^{2}-3d)\). Since \(\frac{\delta\theta}{\delta b}=-21(2a-4b-d)\), \(\theta\) is minimized at either \(b=0\) or \(b=\frac{2a-d}{4}\). The first case yields \(\theta=13a^{2}-21 ad+35d^{2}-21d\) and the claim then follows by applying Lemma A6, while the second one yields \(\theta=\frac{20a^{2}-84 ad+259d^{2}-168d}{8}\) and the claim then follows by applying Lemma A5. For \(e=d\), we get \(\theta=13a^{2}-41 ab+7(6b^{2}-3 bd+5d^{2}-3d)\). Since \(\frac{\delta\theta}{\delta b}=-21(2a-4b+d)\), \(\theta\) is minimized at \(b=\frac{2a+d}{4}\) which yields \(\theta=\frac{20a^{2}-84 ad+259d^{2}-168d}{8}\) and the claim then follows by applying Lemma A5. **Lemma A8**.