# On Multidimensional Congestion Games +
## Appendix B Missing Proofs
: Let \((\mathcal{G},\mathcal{C})\) be a bidimensional linear congestion game such that \(|C_{0}|=n_{0}\) and \(|C_{1}|=|C_{2}|=n_{1}\). Each player \(i\in C_{1}\cup C_{2}\) has two strategies \(\sigma_{i}\) and \(\sigma_{i}^{*}\), while all players in \(C_{0}\) have the same strategy \(\overline{s}\). There are three types of resources:* \(n_{1}\) resources \(r_{i}\), \(i\in[n_{1}]\), each with cost function \(\ell_{r_{i}}(x)=\frac{n_{1}+2n_{0}+1+\gamma}{2}x\), where \(\gamma\) is an arbitrarily small positive value. Resource \(r_{i}\) belongs only to \(\sigma_{i}^{*}\);
* \(n_{1}(n_{1}-1)\) resources \(r^{\prime}_{i,j}\), \(i,j\in[n_{1}]\) with \(i\
eq j\), each with cost function \(\ell_{r^{\prime}_{ij}}(x)=\frac{1}{2}x\). Resource \(r^{\prime}_{ij}\) belongs only to \(\sigma_{i}\) and to \(\sigma_{j}^{*}\);
* one resource \(r^{\prime\prime}\) with cost function \(\ell_{r^{\prime\prime}}(x)=1\). Resource \(r^{\prime\prime}\) belongs to \(\sigma_{i}\) for each \(i\in[n_{1}]\) and to \(\overline{s}\). Let \(\sigma\) (resp. \(\sigma^{*}\)) be the strategy profile in which each player \(i\
otin C_{0}\) plays strategy \(\sigma_{i}\) (resp. \(\sigma_{i}^{*}\)). The cost of each player \(i\in C_{j}\), with \(j\in\{1,2\}\), for adopting strategy \(\sigma_{i}\) when there are exactly \(h\) players in \(C_{j}\) adopting the strategy played in \(\sigma\) (and thus there are \(n_{1}-h\) players in \(C_{j}\) adopting the strategy played in \(\sigma^{*}\)) is \(cost_{\sigma}(h)=\frac{2n_{1}-h-1}{2}+n_{0}+h\). Similarly, the cost of each player \(i\in C_{j}\) for adopting strategy \(\sigma_{i}^{*}\) when there are exactly \(h\) players in \(C_{j}\) adopting the strategy played in \(\sigma\) is \(cost_{\sigma^{*}}(h)=\frac{n_{1}+2n_{0}+1+\gamma}{2}+\frac{n_{1}+h-1}{2}\). Since for any \(h\in[n_{1}]\), it holds that \(cost_{\sigma^{*}}(h-1)>cost_{\sigma}(h)\), it follows that \(\sigma\) is the only pure Nash equilibrium for \((\mathcal{G},\mathcal{C})\). The price of stability of \((\mathcal{G},\mathcal{C})\) is then lower bounded by the following ratio  
\[\frac{n_{1}(n_{1}-1)+2n_{1}(n_{1}+n_{0})+n_{0}(2n_{1}+n_{0})}{n_{1}(n_{1}+2n_{ 0}+1+\gamma)+n_{1}(n_{1}-1)+n_{0}^{2}},\]  
which, for \(n_{0}\) going to infinity and \(n_{1}=\frac{1+\sqrt{5}}{2}n_{0}\), tends to \(\frac{1+\sqrt{5}}{2}\). Let \((\mathcal{G}^{\prime},\mathcal{C}^{\prime})\) be a bidimensional linear congestion game such that \(C_{0}=\emptyset\), \(|C_{1}|=n_{1}\) and \(|C_{2}|=n_{2}\). Each player \(i\in C_{1}\) has two strategies \(\sigma_{i}\) and \(\sigma_{i}^{*}\), while all players in \(C_{2}\) have the same strategy \(\overline{s}\). There are three types of resources:  
* \(n_{1}\) resources \(r_{i}\), \(i\in[n_{1}]\), each with cost function \(\ell_{r_{i}}(x)=\frac{n_{1}+1+\gamma}{2}x\), where \(\gamma\) is an arbitrarily small positive value. Resource \(r_{i}\) belongs only to \(\sigma_{i}^{*}\);
* \(n_{1}(n_{1}-1)\) resources \(r^{\prime}_{i,j}\), \(i,j\in[n_{1}]\) with \(i\
eq j\), each with cost function \(\ell_{r^{\prime}_{ij}}(x)=\frac{1}{2}x\). Resource \(r^{\prime}_{ij}\) belongs only to \(\sigma_{i}\) and to \(\sigma_{j}^{*}\);
* one resource \(r^{\prime\prime}\) with cost function \(\ell_{r^{\prime\prime}}(x)=1\). Resource \(r^{\prime\prime}\) belongs to \(\sigma_{i}\) for each \(i\in[n_{1}]\) and to \(\overline{s}\). Let \(\sigma\) (resp. \(\sigma^{*}\)) be the strategy profile in which each player \(i\
otin C_{0}\) plays strategy \(\sigma_{i}\) (resp. \(\sigma_{i}^{*}\)). The cost of each player \(i\in C_{1}\) for adopting strategy \(\sigma_{i}\) when there are exactly \(h\) players in \(C_{1}\) adopting the strategy played in \(\sigma\) (and thus there are \(n_{1}-h\) players in \(C_{1}\) adopting the strategy played in \(\sigma^{*}\)) is \(cost_{\sigma}(h)=\frac{2n_{1}-h-1}{2}+h\). Similarly, the cost of each player \(i\in C_{1}\) for adopting strategy \(\sigma_{i}^{*}\) when there are exactly \(h\) players in \(C_{1}\) adopting the strategy played in \(\sigma\) is \(cost_{\sigma^{*}}(h)=\frac{n_{1}+1+\gamma}{2}+\frac{n_{1}+h-1}{2}\).