# On Multidimensional Congestion Games +
## 2 Model and Definitions  
For an integer \(n\geq 2\), we denote \([n]:=\{1,2,\ldots,n\}\). In a _weighted congestion game_\(\mathcal{G}\), we have \(n\) players and a set of resources \(R\), where each resource \(r\in R\) has an associated cost function \(\ell_{r}\). The set of strategies for each player \(i\in[n]\), denoted as \(S_{i}\), can be any subset of the powerset of \(R\), that is, \(S_{i}\subseteq 2^{R}\). Each player \(i\in[n]\) is associated with a positive weight \(w_{i}>0\). Given a strategy profile \(\mathbf{\sigma}=(\sigma_{1},\ldots,\sigma_{n})\), the congestion of resource \(r\) in \(\mathbf{\sigma}\), denoted as \(n_{r}(\mathbf{\sigma})\), is the total weight of players choosing \(r\) in \(\mathbf{\sigma}\), that is, \(n_{r}(\mathbf{\sigma})=\sum_{i\in[n]:r\in\sigma_{i}}w_{i}\). The perceived cost paid by player \(i\) in \(\mathbf{\sigma}\) is \(c_{i}(\mathbf{\sigma})=\sum_{r\in\sigma_{i}}\ell_{r}(n_{r}(\mathbf{\sigma}))\). An _unweighted congestion game_ (congestion game, for brevity) is a weighted congestion game in which all players have unitary weights. An _affine weighted congestion game_ is a weighted congestion game such that, for any \(r\in R\), it holds that \(\ell_{r}(x)=\alpha_{r}x+\beta_{r}\), with \(\alpha_{r},\beta_{r}\geq 0\); the game is _linear_ if \(\beta_{r}=0\) for any \(r\in R\). For any integer \(d\geq 2\), a _\(d\)-dimensional weighted congestion game_\((\mathcal{G},\mathcal{C})\) consists of a weighted congestion game \(\mathcal{G}\) whose set of players is partitioned into \(d+1\) clusters \(C_{0},C_{1},\ldots,C_{d}\). For a player \(i\), we denote by \(f(i)\in\{0,\ldots,d\}\) the cluster she belongs to. We say that players in \(C_{0}\) are _omniscient_ and that players in \(C_{i}\), for any \(i\in[d]\), are _ignorant_. Given a strategy profile \(\mathbf{\sigma}\), we denote by \(n_{r,j}(\mathbf{\sigma})\) the total weight of players belonging to \(C_{j}\) who are using resource \(r\) in \(\mathbf{\sigma}\). The presumed cost of a player \(i\) in \(\mathbf{\sigma}\) is \(\hat{c}_{i}(\mathbf{\sigma})=\sum_{r\in\sigma_{i}}\ell_{r}(n_{r,f(i)}(\mathbf{\sigma}) +n_{r,0}(\mathbf{\sigma}))\) if she is ignorant and \(\hat{c}_{i}(\mathbf{\sigma})=\sum_{r\in\sigma_{i}}\ell_{r}(\sum_{j=0}^{d}n_{r,j}( \mathbf{\sigma}))=\sum_{r\in\sigma_{i}}\ell_{r}(\sum_{j=0}^{d}n_{r,j}(\mathbf{\sigma}))\)\(\sum_{r\in\sigma_{i}}\ell_{r}(n_{r}(\sigma))=c_{i}(\sigma)\) if she is omniscient. A _\(d\)-dimensional weighted affine congestion game_ is a pair \((\mathcal{G},\mathcal{C})\) such that \(\mathcal{G}\) is an affine weighted congestion game. Given a strategy profile \(\sigma\) and a strategy \(s\in S_{i}\) for a player \(i\in[n]\), we denote with \((\sigma_{-i},s)\) the strategy profile obtained from \(\sigma\) by replacing the strategy \(\sigma_{i}\) played by \(i\) in \(\sigma\) with \(s\). A _pure Nash equilibrium_ is a strategy profile \(\sigma\) such that, for any player \(i\in[n]\) and for any strategy \(s\in S_{i}\), it holds that \(\hat{c}_{i}(\sigma_{-i},s)\geq\hat{c}_{i}(\sigma)\). Let \(\Sigma\) be the set of all possible strategy profiles which can be realized in \((\mathcal{G},\mathcal{C})\). We denote with \(\mathcal{NE}(\mathcal{G},\mathcal{C})\subseteq\Sigma\) the set of pure Nash equilibria of \((\mathcal{G},\mathcal{C})\). Let \(\mathsf{SF}:\Sigma\to\mathbb{R}_{\geq 0}\) be a _social cost function_ measuring the overall quality of each strategy profile in \(\Sigma\). We denote with \(\sigma^{*}\) a _social optimum_ of \((\mathcal{G},\mathcal{C})\) with respect to \(\mathsf{SF}\), that is, a strategy profile minimizing the social cost function \(\mathsf{SF}\). We consider two social cost functions, namely, the (weighted) sum of the presumed costs of all players and the (weighted) sum of their perceived ones denoted, respectively, as \(\mathsf{Pres}\) and \(\mathsf{Perc}\).