# On Multidimensional Congestion Games +
## 6 Bounds for Bidimensional Unweighted Games
### Price of Anarchy
For the case of the social cost function \(\mathsf{Perc}\), we only need to replace the objective function and the third constraint in \(\mathsf{LP}(\mathsf{Pres},\mathbf{\sigma},\mathbf{\sigma}^{*})\), respectively, with  
\[\sum_{r\in R}\left(\alpha_{r}\left(\sum_{j=0}^{d}k_{r,j}\right)^{2}+\beta_{r} \sum_{j=0}^{d}k_{r,j}\right)\ \ \text{and}\ \ \sum_{r\in R}\left(\alpha_{r}\left(\sum_{j=0}^{d}l_{r,j}\right)^{2}+\beta_{r} \sum_{j=0}^{d}l_{r,j}\right)=1.\]  
This results in the following dual program \(\mathsf{DLP}(\mathsf{Perc},\mathbf{\sigma},\mathbf{\sigma}^{*})\):  
\[ \begin{array}{ll}min&\gamma\\ s.t.&\\ &x\left(k_{r,0}\sum_{j=0}^{d}k_{r,j}-l_{r,0}-l_{r,0}\sum_{j=0}^{d}k_{r,j} \right)+y\sum_{j=1}^{d}\left(k_{r,j}(k_{r,j}+k_{r,0})-l_{r,j}(k_{r,j}+k_{r,0}+ 1)\right)\\ &\quad+\gamma\left(\sum_{j=0}^{d}l_{r,j}\right)^{2}\geq\left(\sum_{j=0}^{d}k_ {r,j}\right)^{2}&\forall r\in\ R\\ &x(k_{r,0}-l_{r,0})+y\sum_{j=1}^{d}(k_{r,j}-l_{r,j})+\gamma\sum_{j=0}^{d}l_{r, j}\geq\sum_{j=0}^{d}k_{r,j}&\forall r\in\ R\\ &x,y\geq 0.\end{array} \]  
Note that the second constraint is the same in both \(\mathsf{DLP}(\mathsf{Pres},\mathbf{\sigma},\mathbf{\sigma}^{*})\) and \(\mathsf{DLP}(\mathsf{Perc},\mathbf{\sigma},\mathbf{\sigma}^{*})\). For the sake of conciseness, in the sequel, we shall drop the subscript \(r\) from the notation; moreover, when fixed a dual solution, we shall denote the first and second constraint of a given dual program as \(g_{1}(\mathbf{k},\mathbf{I})\geq 0\) and \(g_{2}(\mathbf{k},\mathbf{I})\geq 0\), respectively, where we set \(\mathbf{k}=(k_{0},\ldots,k_{d})\) and \(\mathbf{I}=(l_{0},\ldots,l_{d})\). When \(d=2\), we exploit an equivalent, but nicer, representation of the dual inequalities. With this aim, we set \(k_{r}:=n_{r}(\mathbf{\sigma})\) and \(l_{r}:=n_{r}(\mathbf{\sigma}^{*})\) and replace \(k_{r,0}\) and \(l_{r,0}\) with \(k_{r}-k_{r,1}-k_{r,2}\) and \(l_{r}-l_{r,1}-l_{r,2}\), respectively. By substituting and rearranging, \(\mathsf{DLP}(\mathsf{Pres},\mathbf{\sigma},\mathbf{\sigma}^{*})\) becomes \[ \begin{array}{ll}min&\gamma\\ s.t.&\\ &x\left((k_{r}-k_{r,1}-k_{r,2})k_{r}-(l_{r}-l_{r,1}-l_{r,2})(k_{r}+1)\right)\\ &\quad+y\left(k_{r,1}(k_{r}-k_{r,2})-l_{r,1}(k_{r}-k_{r,2}+1)+k_{r,2}(k_{r}-k_{r,1})-l_{r,2}(k_{r}-k_{r,1}+1)\right)\\ &\quad+\gamma\left(l_{r}^{2}-2l_{r,1}l_{r,2}\right)\geq k_{r}^{2}-2k_{r,1}k_{r,2}&\forall r\in\ R\\ &x(k_{r}-k_{r,1}-k_{r,2}-l_{r}+l_{r,1}+l_{r,2})+y(k_{r,1}+k_{r,2}-l_{r,1}-l_{r,2})+\gamma l_{r}\geq k_{r}&\forall r\in\ R\\ &x,y\geq 0.\end{array} \]  
Similarly, the dual program \(\mathsf{DLP}(\mathsf{Perc},\mathbf{\sigma},\mathbf{\sigma}^{*})\) can be rewritten as:  
\[ \begin{array}{ll}min&\gamma\\ s.t.&\\ &x\left((k_{r}-k_{r,1}-k_{r,2})k_{r}-(l_{r}-l_{r,1}-l_{r,2})(k_{r}+1)\right)\\ &\quad+y\left(k_{r,1}(k_{r}-k_{r,2})-l_{r,1}(k_{r}-k_{r,2}+1)+k_{r,2}(k_{r}-k_{ r,1})-l_{r,2}(k_{r}-k_{r,1}+1)\right)+\gamma l_{r}^{2}\geq k_{r}^{2}&\forall r\in\ R\\ &x(k_{r}-k_{r,1}-k_{r,2}-l_{r}+l_{r,1}+l_{r,2})+y(k_{r,1}+k_{r,2}-l_{r,1}-l_{r,2})+\gamma l_{r}\geq k_{r}&\forall r\in\ R\\ &x,y\geq 0.\end{array} \]  
In the following theorem we provide upper bounds for the price of anarchy of bidimensional affine congestion games under social cost functions \(\mathsf{Pres}\) and \(\mathsf{Perc}\). Theorem 3.2: _For each bidimensional affine congestion game \((\mathcal{G},\mathcal{C})\), \(PoA(\mathcal{G},\mathcal{C})\leq\frac{119}{33}\) under the social cost function \(\mathsf{Pres}\) and \(PoA(\mathcal{G},\mathcal{C})\leq\frac{35}{8}\) under the social cost function \(\mathsf{Perc}\)._  
We now show the existence of two matching lower bounding instances (the proof is deferred to the Appendix B). Theorem 3.3: _There exist two bidimensional linear congestion games \((\mathcal{G},\mathcal{C})\) and \((\mathcal{G}^{\prime},\mathcal{C}^{\prime})\) such that \(PoA(\mathcal{G},\mathcal{C})\geq\frac{119}{33}\) under the social cost function \(\mathsf{Pres}\) and \(PoA(\mathcal{G}^{\prime},\mathcal{C}^{\prime})\geq\frac{35}{8}\) under the social cost function \(\mathsf{Perc}\) Appendix B._