# On Multidimensional Congestion Games +
## Appendix A Technical Lemmas  
In this section we gather all technical lemmas needed to prove our main theorems. For any \(d\geq 0\), let \(\mathbf{Q}=(q_{i,j})_{i,j\in[d]\cup\{0\}}\) be the \((d+1)\times(d+1)\) matrix such that: (i) \(q_{i,j}=\sqrt{d}\) if \(i=j\); (ii) \(q_{i,j}=1\) if either \(i=0\), or \(j=0\), with \((i,j)\
eq(0,0)\); (iii) \(q_{i,j}=0\) otherwise. We have that \(\mathbf{Q}\) is a positive-semidefinite matrix. Proof. : To show the claim, we resort to the Sylvester's criterion, stating that a symmetric matrix \(\mathbf{M}\) is positive-semidefinite if and only if the determinant of each principal minor of \(\mathbf{M}\) (i.e., each upper upper left \(h\)-by-\(h\) corner of \(\mathbf{M}\)) is non-negative. Let \(\mathbf{A}_{h,x}=(a_{h,x,i,j})_{i,j\in[h]}\) be a \(h\times h\) matrix such that: (i) \(a_{h,x,i,j}=x\) if \(i=j\); (ii) \(a_{h,x,i,j}=1\) if \((i,j)\
eq(1,1)\), and, either \(i=1\), or \(j=1\); (iii) \(a_{h,x,i,j}=0\) otherwise. We have that each principal minor of matrix \(\mathbf{Q}\) is of type \(\mathbf{A}_{h,\sqrt{d}}\) for some \(h\in[d+1]\). Thus, it is sufficient showing that the determinant of matrix \(\mathbf{A}_{h,\sqrt{d}}\), denoted as \(Det(\mathbf{A}_{h,\sqrt{d}})\), is non-negative for any \(h\in[d+1]\). We first show by induction on integers \(h\geq 1\) that \(Det(\mathbf{A}_{h,x})=x^{h}-(h-1)\cdot x^{h-2}\) for any fixed \(x\in\mathbb{R}\). If \(h=0\) we trivially get \(Det(\mathbf{A}_{h,x})=x=x^{h}-(h-1)\cdot x^{h-2}\). Now, we assume that \(Det(\mathbf{A}_{h,x})=x^{h}-(h-1)x^{h-2}\) holds for some \(h\geq 1\), and we show that \(Det(\mathbf{A}_{h+1,x})=x^{h+1}-h\cdot x^{h-1}\). We get \(Det(\mathbf{A}_{h+1,x})=x\cdot Det(\mathbf{A}_{h,x})-x^{h-1}=x(x^{h}-(h-1)x^{h-2})-x^ {h-1}=x^{h+1}-h\cdot x^{h-1}\), where the first equality comes from the Laplace expansion for computing the determinant, and the second equality comes from the inductive hypothesis. By using the fact that \(Det(\mathbf{A}_{h,x})=x^{h}-(h-1)\cdot x^{h-2}\) holds for any \(x\in\mathbb{R}\) and any integer \(h\geq 1\), we have that \(Det(\mathbf{A}_{h,\sqrt{d}})=(\sqrt{d})^{h}-(h-1)(\sqrt{d})^{h-2}\geq 0\) for any \(h\in[d+1]\), where the last inequality holds since quantity \(x^{h}-(h-1)x^{h-1}\) is always non-negative for any \(x\geq\sqrt{h-1}\) if \(h\leq d+1\). Thus each principal minor of \(\mathbf{Q}\) has a non-negative determinant, and the claim follows. Let \(\theta:\mathbb{Z}_{\geq 0}^{6}\to\mathbb{Q}\) be the function such that \(\theta(a,b,c,d,e,f)=18a^{2}-a(b+c+51d-e-f)+50 bf+50 ce-34 bc+\overline{11}9d^{2 }-51d+e+f-238 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. : 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. We first show that, in such an extended scenario, \(\theta\) attains its minimum for 6-tuples \((a,b,c,d,e,f)\) such that \(b=c\) and \(e=f\). Consider to this aim the 6-tuple \((a,b,b+h,d,e,e+k)\), where \(h,k\in\mathbb{R}\). By definition of \(\theta\), we get \(\theta(a,b+\frac{h}{2},b+\frac{h}{2},d,e+\frac{k}{2},e+\frac{k}{2})=\theta(a, b,b+h,d,e,e+k)-\frac{17h^{2}-50 hk+119k^{2}}{2}\leq\theta(a,b,b+h,d,e,e+k)-\frac{(4h-10k)^{2} }{2}\leq\theta(a,b,b+h,d,e,e+k)\). Hence, we do not lose in generality by restricting to 6-tuples of non-negative real values \((a,b,b,d,e,e)\) such that \(a\geq 2b\) and \(d\geq 2e\). In this case \(\theta\) becomes \(18a^{2}-a(2b+51d-2e)-34b^{2}+100 be+119d^{2}-51d-238e^{2}+2e\). Consider the two partial derivatives \(\frac{\theta\theta}{3b}=100e-2a-68b\) and \(\frac{\theta\theta}{3e}=2(a+50b+1-238e)\). Since they are linear and decreasing in \(b\) and \(e\), respectively, it follows that \(\theta\) is minimized at one of the following four cases: \(b=0\wedge e=0\), \(b=0\wedge e=\frac{d}{2}\), \(b=\frac{a}{2}\wedge e=0\) and \(b=\frac{a}{2}\wedge e=\frac{d}{2}\). In the first case, \(\theta\) becomes \(18a^{2}-51 ad+119d^{2}-51d\).