# On Multidimensional Congestion Games +
## 6 Bounds for Bidimensional Unweighted Games
### Price of Anarchy  
We first consider the price of anarchy. Let \((\mathcal{G},\mathcal{C})\) be an arbitrary \(d\)-dimensional unweighted congestion game, and let \(\sigma\) and \(\sigma^{*}\) be a worst-case equilibrium and a social optimum of \((\mathcal{G},\mathcal{C})\), respectively. For \(\mathsf{SF}=\mathsf{Pres}\), we get the following primal linear program \(\mathsf{LP}(\mathsf{Pres},\sigma,\sigma^{*})\) in variables \((\alpha_{r},\beta_{r})_{r\in R}\), whose optimal solution provides an upper bound to \(\mathit{PoA}(\mathcal{G},\mathcal{C})\):  
\[max \sum_{r\in R}\left(\alpha_{r}\left(\sum_{j=0}^{d}k_{r,j}^{2}+2k_{ r,0}\sum_{j=1}^{d}k_{r,j}\right)+\beta_{r}\sum_{j=0}^{d}k_{r,j}\right)\] \[s.t.\] \[\sum_{r\in R}\left(\alpha_{r}k_{r,0}\sum_{j=0}^{d}k_{r,j}+\beta_{ r}k_{r,0}-\alpha_{r}l_{r,0}\left(1+\sum_{j=0}^{d}k_{r,j}\right)-\beta_{r}l_{r,0} \right)\leq\ 0\] \[\sum_{r\in R}\left(\sum_{j=1}^{d}\left(k_{r,j}\left(\alpha_{r}(k_ {r,j}+k_{r,0}+\beta_{r})\right)-\sum_{j=1}^{d}\left(l_{r,j}\left(\alpha_{r}(k_ {r,j}+k_{r,0}+1)+\beta_{r}\right)\right)\right)\right)\leq\ 0\] \[\sum_{r\in R}\left(\alpha_{r}\left(\sum_{j=0}^{d}l_{r,j}^{2}+2l_{ r,0}\sum_{j=1}^{d}l_{r,j}\right)+\beta_{r}\sum_{j=0}^{d}l_{r,j}\right)=1\] \[\alpha_{r},\beta_{r}\geq 0 \forall r\in R.\]  
The optimal solution of the above linear program is an upper bound to the price of anarchy as the objective function is equal to \(\mathsf{Pres}(\sigma)\), the first two constraints are the pure Nash equilibrium conditions derived in (4) and (6), respectively (which are necessary conditions satisfied by any equilibrium), and the last normalization constraint imposes without loss of generality that \(\mathsf{Pres}(\sigma^{*})=1\) (When applying the primal dual method, we observe that, once \(\sigma\) and \(\sigma^{*}\) are fixed, the coefficients \((\alpha_{r})_{r\in R}\) and \((\beta_{r})_{r\in R}\) are chosen in such a way that the value \(\mathsf{Pres}(\sigma)=\mathsf{Pres}(\sigma)/\mathsf{Pres}(\sigma^{*})\) is maximized, thus getting an upper bound on the price of anarchy. We also observe that \((\alpha_{r})_{r\in R}\) and \((\beta_{r})_{r\in R}\) are the unique variables in the considered LP formulation, and the other quantities (e.g., the congestions) are considered as fixed parameters (w.r.t. the LP formulation). See Reference [11] for further details on the primal-dual method and how to apply it to measure the performance of congestion games under different quality metrics.). By associating the three dual variables \(x\), \(y\) and \(\gamma\), with the three constraints of \(\mathsf{LP}(\mathsf{Pres},\mathbf{\sigma},\mathbf{\sigma}^{*})\), the dual formulation \(\mathsf{DLP}(\mathsf{Pres},\mathbf{\sigma},\mathbf{\sigma}^{*})\) becomes  
\[ \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}^{2}+2l_{r,0}\sum_{j=1}^{d}l_{r,j} \right)\geq\sum_{j=0}^{d}k_{r,j}^{2}+2k_{r,0}\sum_{j=1}^{d}k_{r,j}&\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} \]  
By the Weak Duality Theorem, each feasible solution for \(\mathsf{DLP}(\mathsf{Pres},\mathbf{\sigma},\mathbf{\sigma}^{*})\) provides an upper bound to the optimal solution of \(\mathsf{LP}(\mathsf{Pres},\mathbf{\sigma},\mathbf{\sigma}^{*})\), that is on the price of anarchy achievable by the particular choice of \(\mathbf{\sigma}\) and \(\mathbf{\sigma}^{*}\). Anyway, if the provided dual solution is independent of this choice, we obtain an upper bound on the price of anarchy for any possible game.