# On Multidimensional Congestion Games +
## Appendix A Technical Lemmas
Since \(\frac{\theta\theta}{\delta a}=36a-51d\), \(\theta\) is minimized at \(a=\frac{17d}{12}\). By substituting, \(\theta\) becomes \(\frac{1}{8}(663d^{2}-408d)\) which is always non-negative for any \(d\in\mathbb{Z}\). In the second case, \(\theta\) becomes \(36a^{2}-100 ad+119d^{2}-100d\). Since \(\frac{\theta\theta}{\delta a}=36a-50d\), \(\theta\) is minimized at \(a=\frac{25d}{18}\). By substituting, \(\theta\) becomes \(\frac{1}{9}(223d^{2}-450d)\) which is always non-negative for any \(d\in\mathbb{Z}\setminus\{1,2\}\). In the third case, \(\theta\) becomes \(\frac{17}{2}(a^{2}-6 ad+14d^{2}-6d)\). Since \(\frac{\theta\theta}{\delta a}=17(a-3d)\), \(\theta\) is minimized at \(a=3d\). By substituting, \(\theta\) becomes \(\frac{17}{2}(5d^{2}-6d)\) which is always non-negative for any \(d\in\mathbb{Z}\setminus\{1\}\). In the fourth case, \(\theta\) becomes \(\frac{1}{2}(17a^{2}-50 ad+119d^{2}-100d)\). Since \(\frac{\delta\theta}{\delta a}=17a-25d\), \(\theta\) is minimized at \(a=\frac{25d}{17}\). By substituting, \(\theta\) becomes \(\frac{1}{17}(699d^{2}-850d)\) which is always non-negative for any \(d\in\mathbb{Z}\setminus\{1\}\). Hence, in order to complete the proof, we are left to settle the following cases: \((a,0,0,1,0,0)\), \((a,0,0,2,1,1)\), \((a,0,0,1,1,0)\), \((a,0,0,1,0,1)\), \((a,\frac{a}{2},\frac{a}{2},1,1,0)\), \((a,\frac{a}{2},\frac{a}{2},1,0,1)\) and \((a,\frac{a}{2},\frac{a}{2},1,0,0)\). In the case \((a,0,0,1,0,0)\), \(\theta\) becomes \(18a^{2}-51a+68\) which is always non-negative for any \(a\in\mathbb{R}\). In the case \((a,0,0,2,1,1)\), \(\theta\) becomes \(18a^{2}-100a+138\) which is always non-negative for any \(a\in\mathbb{Z}\). In the cases \((a,0,0,1,1,0)\) and \((a,0,0,1,0,1)\), \(\theta\) becomes \(18a^{2}-50a+69\) which is always non-negative for any \(a\in\mathbb{R}\). In the cases \((a,\frac{a}{2},\frac{a}{2},1,1,0)\) and \((a,\frac{a}{2},\frac{a}{2},1,0,1)\), \(\theta\) becomes \(\frac{17a^{2}-50a+138}{2}\) which is always non-negative for any \(a\in\mathbb{R}\). Finally, in the case \((a,\frac{a}{2},\frac{a}{2},1,0,0)\), \(\theta\) becomes \(\frac{17a^{2}-50a+138}{2}\) which is always non-negative for any \(a\in\mathbb{Z}\setminus\{3\}\). Hence, we are only left to consider the case \((3,b,c,1,0,0)\) for which \(\theta\) becomes \(77-34 bc-3(b+c)\). Since \(b+c\leq 3\), it holds that \(77-34 bc-3(b+c)\geq 68-34 bc\) which is always non-negative since \(bc\leq 2\) for any \(b,c\in\mathbb{Z}_{\geq 0}\) such that \(b+c\leq 3\). **Lemma A3**. : _Let \(\lambda:\mathbb{Z}_{\geq 0}^{2}\to\mathbb{Q}\) be the function such that \(\lambda(a,d)=a^{2}-3 ad+5d^{2}-3d\). For any \((a,d)\in\mathbb{Z}_{\geq 0}^{2}\) such that \(d\
eq 1\), it holds that \(\lambda(a,d)\geq 0\)._  
Proof. : Since \(\frac{\delta\lambda}{\delta a}=2a-3d\), \(\lambda\) is minimized at \(a=\frac{3}{2}d\). By substituting, we get \(11d^{2}-12d\) which is non-negative for any \(d\in\mathbb{Z}\setminus\{1\}\). **Lemma A4**. : _Let \(\lambda:\mathbb{Z}_{\geq 0}^{2}\to\mathbb{Q}\) be the function such that \(\lambda(a,d)=a^{2}-6 ad+14d^{2}-6d\). For any \((a,d)\in\mathbb{Z}_{\geq 0}^{2}\) such that \(d\
eq 1\), it holds that \(\lambda(a,d)\geq 0\)._  
Proof. : Since \(\frac{\delta\lambda}{\delta a}=2a-6d\), \(\lambda\) is minimized at \(a=3d\). By substituting, we get \(5d^{2}-6d\) which is non-negative for any \(d\in\mathbb{Z}\setminus\{1\}\). **Lemma A5**. : _Let \(\lambda:\mathbb{Z}_{\geq 0}^{2}\to\mathbb{Q}\) be the function such that \(\lambda(a,d)=20a^{2}-84 ad+259d^{2}-168d\). For any \((a,d)\in\mathbb{Z}_{\geq 0}^{2}\), it holds that \(\lambda(a,d)\geq 0\)._  
Proof. : Since \(\frac{\delta\lambda}{\delta a}=40a-84d\), \(\lambda\) is minimized at \(a=\frac{21}{10}d\). By substituting, we get \(61d^{2}-60d\) which is non-negative for any \(d\in\mathbb{Z}\). **Lemma A6**. : _Let \(\lambda:\mathbb{Z}_{\geq 0}^{2}\to\mathbb{Q}\) be the function such that \(\lambda(a,d)=13a^{2}-21 ad+35d^{2}-21d\). For any \((a,d)\in\mathbb{Z}_{\geq 0}^{2}\), it holds that \(\lambda(a,d)\geq 0\)._  
Proof.