# On Multidimensional Congestion Games +
## Appendix B Missing Proofs  
**Theorem A1** (Claim of Theorem 4). : _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}\)._  
Proof. : For the social cost function \(\mathsf{Pres}\), consider the game \((\mathcal{G},\mathcal{C})\) depicted in Figure A1a). First, we show that \(\sigma\) is a pure Nash equilibrium for \((\mathcal{G},\mathcal{C})\), that is, no player can lower her perceived cost by switching to her optimal strategy. Player 1 is paying \(27\cdot 2+46=100\); by switching to \(\sigma_{1}^{*}\), she pays \(7\cdot 4+18\cdot 4=100\). Player 2 is paying \(27\cdot 2+42+56=152\); by switching to \(\sigma_{2}^{*}\), she pays \(17\cdot 4+21\cdot 4=152\). Player 3 is paying \(27\cdot 2+42=96\); by switching to \(\sigma_{3}^{*}\), she pays \(7\cdot 4+17\cdot 4=96\). Player 4 is paying \(27\cdot 2+46+56=156\); by switching to \(\sigma_{4}^{*}\), she pays \(18\cdot 4+21\cdot 4=156\)Player 5 is paying \(7\cdot 3+17\cdot 3+21\cdot 3=135\); by switching to \(\sigma_{5}^{*}\), she pays \(27\cdot 5=135\). Player 6 is paying \(7\cdot 3+18\cdot 3+21\cdot 3=138\); by switching to \(\sigma_{6}^{*}\), she pays \(46\cdot 3=138\). Player 7 is paying \(7\cdot 3+18\cdot 3+17\cdot 3=126\); by switching to \(\sigma_{7}^{*}\), she pays \(42\cdot 3=126\). Player 8 is paying \(18\cdot 3+17\cdot 3+21\cdot 3=168\); by switching to \(\sigma_{8}^{*}\), she pays \(56\cdot 3=168\). The price of anarchy of \((\mathcal{G},\mathcal{C})\) is then lower bounded by the ratio  
\[\frac{100+152+96+156+135+138+126+168}{25+38+24+39+27+46+42+56}=\frac{1071}{297 }=\frac{119}{33}.\]  
For the social cost function \(\mathsf{Perc}\), consider the game \((\mathcal{G}^{\prime},\mathcal{C}^{\prime})\) depicted in Figure A1b). First, we show that \(\sigma\) is a pure Nash equilibrium for \((\mathcal{G}^{\prime},\mathcal{C}^{\prime})\), that is, no player can lower her perceived cost by switching to her optimal strategy. Player 1 is paying \(1418+958+189\cdot 2=2754\); by switching to \(\sigma_{1}^{*}\), she pays \(918\cdot 3=2754\). Player 2 is paying \(616+221+189\cdot 2=1215\); by switching to \(\sigma_{2}^{*}\), she pays \(405\cdot 3=1215\). Player 3 is paying \(1418+616+189\cdot 2=2412\); by switching to \(\sigma_{3}^{*}\), she pays \(804\cdot 3=2412\). Player 4 is paying \(958+221+189\cdot 2=1557\); by switching to \(\sigma_{4}^{*}\), she pays \(519\cdot 3=1557\). Player 5 is paying \((918+405+804)\cdot 2=4254\); by switching to \(\sigma_{5}^{*}\), she pays \(1418\cdot 3=4254\). Player 6 is paying \((918+519)\cdot 2=2874\); by switching to \(\sigma_{6}^{*}\), she pays \(958\cdot 3=2874\). Player 7 is paying \((405+519)\cdot 2=1848\); by switching to \(\sigma_{7}^{*}\), she pays \(616\cdot 3=1848\). Player 8 is paying \(804\cdot 2=1608\); by switching to \(\sigma_{8}^{*}\), she pays \(221\cdot 3+189\cdot 5=1608\). By noting that the perceived cost of the first four players is exactly twice their presumed one, the price of anarchy of \((\mathcal{G}^{\prime},\mathcal{C}^{\prime})\) is then lower bounded by the ratio  
\[\frac{2\cdot(2754+1215+2412+1557)+4254+2874+1848+1608}{1418+958+616+221+189+918 +405+804+519}=\frac{26460}{6048}=\frac{35}{8}.\]  
**Theorem A2** (Claim of Theorem 6). : _For any \(\epsilon>0\), there exist two bidimensional linear congestion games \((\mathcal{G},\mathcal{C})\) and \((\mathcal{G}^{\prime},\mathcal{C}^{\prime})\) such that \(\mathit{PoS}(\mathcal{G},\mathcal{C})\geq\frac{1+\sqrt{5}}{2}-\epsilon\) under the social cost function \(\mathsf{Pres}\) and \(\mathit{PoS}(\mathcal{G}^{\prime},\mathcal{C}^{\prime})\geq\frac{5+\sqrt{12}} {4}-\epsilon\) under the social cost function \(\mathsf{Perc}\)._  
Proof.