# On Multidimensional Congestion Games +
## 3 Existence of Pure Nash Equilibria  
In this section, we prove that multidimensional unweighted (resp. weighted affine) congestion games are graphical unweighted (resp. weighted affine) congestion games defined by an underlying undirected social knowledge graph. This allows us to use a result in Reference [24] (resp. [25]) stating that these games are potential games, thus admitting pure Nash equilibria. A _graphical weighted congestion game_\((\mathcal{G},\mathcal{G})\) consists of a weighted congestion game \(\mathcal{G}\) and a directed graph \(G=(N,A)\) such that each node of \(N\) is associated with a player in \(\mathcal{G}\) and there exists a directed edge from node \(i\) to node \(j\) if and only if player \(i\) has full information about player \(j\). The congestion presumed by player \(i\) on resource \(r\) in the profile \(\sigma\) is \(\tilde{n}_{r,i}(\sigma)=\sum_{p\in N:r\in\sigma_{p},(i,p)\in A}w_{p}+w_{i}\) and the presumed cost paid by player \(i\) in \(\sigma\) is \(\tilde{c}_{i}(\sigma)=\sum_{r\in\sigma_{i}}\ell_{r}(\tilde{n}_{r,i}(\sigma))\). A _graphical weighted affine congestion game_ is a pair \((\mathcal{G},G)\) such that \(\mathcal{G}\) is an affine weighted congestion game. The _independence number_\(\delta(\mathcal{G})\) of \((\mathcal{G},\mathcal{G})\) is the cardinality of a maximum independent set of graph \(\mathcal{G}\). A function \(\Phi:\Sigma\to\mathbb{R}\) is a _weighted potential function_ for a graphical weighted congestion game \((\mathcal{G},\mathcal{G})\), if for any profile \(\sigma\), any player \(i\in[n]\) and any strategy \(s\in S_{i}\), it holds that \(\Phi(\sigma)-\Phi(\sigma_{-i},s)=a_{i}(\tilde{c}_{i}(\sigma)-\tilde{c}_{i}( \sigma_{-i},s))\) for some \(a_{i}>0\); if \(a_{i}=1\), \(\Phi\) is an _exact potential function_. In Reference [24](resp. [25]), it is shown that each graphical unweighted (resp. weighted affine) congestion game \((\mathcal{G},G)\) such that \(G\) is undirected admits an exact potential function (resp. weighted potential function). The following result shows that \(d\)-dimensional weighted congestion games are a subclass of graphical weighted congestion games. **Proposition 1**. : _Each \(d\)-dimensional weighted congestion game is a graphical weighted congestion game whose social knowledge graph is undirected._  
Proof. : Fix a \(d\)-dimensional weighted congestion game \((\mathcal{G},\mathcal{C})\). We define a graph \(G=(N,A)\) such that each node in \(N\) is associated with a player in \(\mathcal{G}\) and there is an undirected edge \(\{u,v\}\in A\) if and only if either \(u,v\in C_{i}\) for some \(0\leq i\leq d\) or \(u\in C_{0}\). We show that, for any strategy profile \(\sigma\) of \(\mathcal{G}\) and for any \(i\in[n]\), \(\hat{c}_{i}(\sigma)=\tilde{c}_{i}(\sigma)\). Consider first an omniscient player \(i\in C_{0}\). In \((\mathcal{G},\mathcal{C})\), it holds that  
\[\hat{c}_{i}(\sigma)=\sum_{r\in\sigma_{i}}\ell_{r}(n_{r}(\sigma))=\sum_{r\in \sigma_{i}}\ell_{r}\left(\sum_{p\in[n]r\in\sigma_{p}}w_{p}\right),\]  
while in \((\mathcal{G},G)\), it holds that  
\[\tilde{c}_{i}(\sigma)=\sum_{r\in\sigma_{i}}\ell_{r}(\bar{n}_{r,i}(\sigma))= \sum_{r\in\sigma_{i}}\ell_{r}\left(\sum_{p\in N:r\in\sigma_{p},\{i,p\}\in A}w _{p}+w_{i}\right)=\sum_{r\in\sigma_{i}}\ell_{r}\left(\sum_{p\in[n]r\in\sigma_ {p}}w_{p}\right),\]  
where the last equality follows from the fact that, by construction of \(G\), it holds that \(\{i,p\}\in A\), for any \(p\in[n]\) with \(p\
eq i\). Next, consider an ignorant player \(i\in C_{j}\) for some \(j\in[d]\).