# On Multidimensional Congestion Games +
## 4 Bounds for the Price of Anarchy
For unweighted games, we simply fix \(w_{i}=1\) for any \(i\in[n]\) and sum the inequality for each \(i\in C_{0}\), thus getting  
\[\sum_{r\in R}\left(\alpha_{r}n_{r,0}(\mathbf{\sigma})\sum_{j=0}^{d}n_{r,j}(\mathbf{ \sigma})+\beta_{r}n_{r,0}(\mathbf{\sigma})-\alpha_{r}n_{r,0}(\mathbf{\sigma}^{*}) \left(1+\sum_{j=0}^{d}n_{r,j}(\mathbf{\sigma})\right)-\beta_{r}n_{r,0}(\mathbf{\sigma} ^{*})\right)\leq 0. \tag{4}\]  
For any player \(i\in C_{j}\), with \(j\in[d]\), the equilibrium condition yields  
\[\sum_{r\in\sigma_{i}}\left(\alpha_{r}\left(n_{r,j}(\mathbf{\sigma})+n_{r,0}(\mathbf{ \sigma})\right)+\beta_{r}\right)-\sum_{r\in\sigma_{i}^{*}}\left(\alpha_{r} \left(n_{r,j}(\mathbf{\sigma})+n_{r,0}(\mathbf{\sigma})+w_{i}\right)+\beta_{r}\right) \leq 0.\]  
For weighted games, again, by using \(w_{i}\leq n_{r,0}(\mathbf{\sigma}^{*})\) for any \(r\in R\) and \(i\in[n]\) such that \(r\in\sigma_{i}\), by multiplying this inequality for \(w_{i}\), and by summing it for each \(i\in C_{j}\), we get  
\[\sum_{r\in R}\left(\alpha_{r}n_{r,j}(\mathbf{\sigma})\left(n_{r,j}(\mathbf{\sigma})+n _{r,0}(\mathbf{\sigma})\right)+\beta_{r}n_{r,j}(\mathbf{\sigma})-\alpha_{r}n_{r,j}(\bm {\sigma}^{*})\left(n_{r,j}(\mathbf{\sigma})+n_{r,0}(\mathbf{\sigma})+n_{r,j}(\mathbf{ \sigma}^{*})\right)-\beta_{r}n_{r,j}(\mathbf{\sigma}^{*})\right)\leq 0.\]  
By further summing for each \(j\in[d]\), we obtain  
\[\sum_{r\in R}\left(\sum_{j=1}^{d}\left(n_{r,j}(\mathbf{\sigma})\left(\alpha_{r}(n_{ r,j}(\mathbf{\sigma})+n_{r,0}(\mathbf{\sigma})+\beta_{r}\right)\right)-\sum_{j=1}^{d}\left(n_{r,j}( \mathbf{\sigma}^{*})\left(\alpha_{r}(n_{r,j}(\mathbf{\sigma})+n_{r,0}(\mathbf{\sigma})+n_ {r,j}(\mathbf{\sigma}^{*}))+\beta_{r}\right)\right)\right)\leq 0. \tag{5}\]  
For unweighted games, by setting \(w_{i}=1\), and by summing the equilibrium constraint for any \(i\in[n]\) and \(j\in[d]\), we analogously get  
\[\sum_{r\in R}\left(\sum_{j=1}^{d}\left(n_{r,j}(\mathbf{\sigma})\left(\alpha_{r}(n_{ r,j}(\mathbf{\sigma})+n_{r,0}(\mathbf{\sigma})+\beta_{r}\right)\right)-\sum_{j=1}^{d}\left(n_{r,j}( \mathbf{\sigma}^{*})\left(\alpha_{r}(n_{r,j}(\mathbf{\sigma})+n_{r,0}(\mathbf{\sigma})+1)+ \beta_{r}\right)\right)\right)\leq 0. \tag{6}\]  
In the sequel, for the sake of conciseness, we adopt \(k_{r,j}\) and \(l_{r,j}\) as short-hands for \(n_{r,j}(\mathbf{\sigma})\) and \(n_{r,j}(\mathbf{\sigma}^{*})\), respectively. Theorem 1 provides an upper bound for the price of anarchy of multidimensional weighted affine congestion games with respect to social cost function \(\mathsf{Pres}\). **Theorem 1**. : _For each \(d\)-dimensional weighted affine congestion game \((\mathcal{G},\mathcal{C})\),_  
\[PoA(\mathcal{G},\mathcal{C})\leq\frac{(\sqrt{d+4}+\sqrt{d})(\sqrt{d}\cdot\sqrt{d +4}+d+4)}{4\sqrt{d+4}}\leq d+2\]  
_under the social cost function_ Pres_._  
Proof. : Let \(\mathbf{\sigma}\) and \(\mathbf{\sigma}^{*}\) be a worst-case equilibrium and a social optimum of \((\mathcal{G},\mathcal{C})\), respectively. Let \(\mathbf{k}_{r}=(k_{r,0},\ldots,k_{r,d})\), \(\mathbf{l}_{r}=(l_{r,0},\ldots,l_{r,d})\), and let \(\mathbf{P}=(p_{ij})_{i,j\in[d]\cup\{0\}}\) be the \((d+1)\times(d+1)\) binary matrix such that: (i) \(p_{ij}=1\) if either \(i=j\), or \(i=0\), or \(j=0\); (ii) \(p_{i,j}=0\) otherwise. By summing inequalities (3) and (5), we get the following compact inequality involving the product between vectors, matrices, and scalars:  
\[\sum_{r\in R}\left(\alpha_{r}(\mathbf{k}_{r}\cdot\mathbf{P}\cdot\mathbf{k}_{r}^{T})+\beta _{r}\sum_{j=0}^{d}k_{r,j}-\alpha_{r}(\mathbf{l}_{r}\cdot\mathbf{P}\cdot\mathbf{k}_{r}^{T}+ \mathbf{l}_{r}\cdot\mathbf{l}_{r}^{T})-\beta_{r}\sum_{j=0}^{d}l_{r,j}\right)\leq 0 \tag{7}\]  
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.