# On Multidimensional Congestion Games +
## Appendix A Technical Lemmas
: _Let \(\lambda:\mathbb{Z}_{\geq 0}^{2}\rightarrow\mathbb{Q}\) be the function such that \(\lambda(a,d)=\frac{3-\sqrt{7}}{2}a^{2}+(1+\sqrt{7}-2d)a+(3+\sqrt{7})(\frac{d^ {2}}{2}-d)\). For any \((a,d)\in\mathbb{Z}_{\geq 0}^{2}\setminus\{(0,1),(1,1),(1,2)\}\), it holds that \(\lambda(a,d)\geq 0\)._  
Proof. : Since \(\frac{\delta\lambda}{\delta a}=(3+\sqrt{7})a-2d+1+\sqrt{7}\), \(\lambda\) is minimized at either \(a=0\) or \(a=\frac{2d-1-\sqrt{7}}{3+\sqrt{7}}\). In the first case, \(\lambda\) becomes \(\frac{3-\sqrt{7}}{2}d(d-2)\) which is always non-negative for any \(d\in\mathbb{Z}_{\geq 0}\setminus\{1\}\). In the second case, \(\lambda\) becomes \(\frac{1}{2}(3(\sqrt{7}-1)d^{2}+2d(\sqrt{7}-7)+\sqrt{7}-5)\) which is always non-negative for any \(d\in\mathbb{Z}_{\geq 0}\setminus\{1,2\}\). For the leftover case \(d=2\), \(\lambda\) becomes \(\frac{3-\sqrt{7}}{2}a^{2}+(\sqrt{7}-3)a\) which is always non-negative for any \(a\in\mathbb{Z}\setminus\{1\}\). For the other case \(d=1\), \(\lambda\) becomes \(\frac{3-\sqrt{7}}{2}a^{2}+(\sqrt{7}-1)a-\frac{3+\sqrt{7}}{2}\) which is always non-negative for any \(a\in\mathbb{Z}\setminus\{0,1\}\). **Lemma A9**. : _Let \(\theta:\mathbb{Z}_{\geq 0}^{6}\rightarrow\mathbb{Q}\) be the function such that \(\theta(a,b,c,d,e,f)=a^{2}(3-\sqrt{7})-a(2d-1-\sqrt{7})+2 bc(\sqrt{7}-3)+2(bf+ ce)+(d^{2}-d)(3+\sqrt{7})-2(3+\sqrt{7})ef\). 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. : Note first, that for 6-tuples of the form \((0,b,c,1,e,f)\), it holds that \(\theta=0\), since \(a=0\Rightarrow b=c=0\) and \(d=1\Rightarrow ef=0\), for 6-tuples of the form \((1,b,c,1,e,f)\), it holds that \(\theta=2(1+bf+ce)>0\), since \(a=d=1\Rightarrow bc=ef=0\), and for 6-tuples of the form \((1,b,c,2,e,f)\), it holds that \(\theta=2 bf+2 ce-2(3+\sqrt{7})ef+2(3+\sqrt{7})\geq 0\), since \(d=2\Rightarrow ef\leq 1\). Hence, in the sequel of the proof, we avoid to consider the cases \(a=0\wedge d=1\), \(a=d=1\) and \(a=1\wedge d=2\). 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 it holds that \(\frac{\delta\theta}{\delta c}=2(b(\sqrt{7}-3)+e)\) and \(\frac{\delta\theta}{\delta f}=2(b-(\sqrt{7}+3)e)\), \(\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=(3-\sqrt{7})a^{2}+(\sqrt{7}+1-2d)a+(3+\sqrt{7})(d^{2}-d)\). The claim follows by applying Lemma A8, since \(\theta\geq\lambda\). any \(a\in\mathbb{R}\). For the other case of \(d=1\), \(\lambda\) becomes \(a(11a+32)-\frac{4225}{211}\) which is non-negative for any \(a\in\mathbb{Z}_{\geq 0}\setminus\{0\}\). **Lemma A13**. : _Let \(\theta:\mathbb{Z}_{\geq 0}^{6}\to\mathbb{Q}\) be the function such that \(\theta(a,b,c,d,e,f)=49a^{2}+a(62b+62c-68d-62e-62f+81)+130 bf+130 ce-422 bc+211d^{2} -149d+162 ef-62e-62f\). 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 it holds that \(\frac{\delta\theta}{\delta c}=62a-42b+130e\) and \(\frac{\delta\theta}{\delta f}=-2(31a-65b-81e+31)\), \(\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=49a^{2}+a(62b-68d-62e+81)+211d^{2}-149d-62e\). Since \(\frac{\delta\theta}{\delta c}=-62(a+1)\), \(\theta\) is minimized at \(e=d\), which yields \(\theta=49a^{2}+a(62b-130d+81)+211d^{2}-211d\). Since \(\frac{\delta\theta}{\delta\theta}=62a\), \(\theta\) is minimized for \(b=0\). In this case, \(\theta\) becomes \(49a^{2}+a(81-130d)+211d^{2}-211d\). The claim follows by applying Lemma A10.