# On Multidimensional Congestion Games +
### Motivations  
Traditional (weighted) congestion games are defined under a _full information_ scenario--each player knows all the other participants in the game as well as their available strategies. These requirements, anyway, become too strong in many practical applications, where players may be unaware about even the mere existence of other potential competitors. This observation, together with the widespread of competitive applications in social networks, has drawn some attention on the model of _graphical (weighted) congestion games_[23; 24; 25].  
A graphical (weighted) congestion game \((\mathcal{G},G)\) is obtained by coupling a traditional (weighted) congestion game \(\mathcal{G}\) with a _social knowledge graph_\(G\) expressing the _social context_ in which the players operate. In \(G\), each node is associated with a player of \(\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\). A basic property of (weighted) congestion games is that the congestion of a resource \(r\) in a given strategy profile \(\sigma\) is the same for all players. The existence of a social context in graphical (weighted) congestion games, instead, makes the congestion of each resource player dependent. In these games, in fact, the congestion presumed by player \(i\) on resource \(r\) in the strategy profile \(\sigma\) is obtained by excluding from the set of players choosing \(r\) in \(\sigma\) those of whom player \(i\) has no knowledge. Clearly, if \(G\) is complete, then there is no difference between \((\mathcal{G},G)\) and \(\mathcal{G}\). In all the other cases, however, there may be a big difference between the cost that a player _presumes_ to pay on a certain strategy profile and the real cost that she effectively _perceives_ because of the presence of players she was unaware of during her decisional process (We observe that the model of graphical congestion games is sufficiently powerful to describe an alternative scenario in which players never perceive their real costs, which are perceived and evaluated by a central entity only. In such case, the central entity aims at evaluating the global and real impact on the performance of the game caused by the players' strategic behaviour).  
Graphical congestion games have been introduced by [PERSON] et al. in Reference [24]. They focus on affine cost functions and provide a complete characterization of the cases in which existence of pure Nash equilibria can be guaranteed. In particular, they show that equilibria always exist if and only if \(G\) is either undirected or directed acyclic. Then, for all these cases, they give bounds on the price of anarchy and stability expressed as a function of the number of players in the game and of the maximum degree of \(G\). These metrics are defined with respect to both the sum of the perceived costs and the sum of the presumed ones.  
[PERSON] et al. [25] argue that the maximum degree of \(G\) is not a proper measure of the level of social ignorance in a graphical congestion game and propose to bound the prices of anarchy and stability as a function of the independence number of \(G\), denoted by \(\delta(G)\). They focus on graphical weighted congestion games with affine cost functions and show that they still admit a potential function when \(G\) is undirected. Then, they prove that the price of anarchy is between \(\delta(G)(\delta(G)+1)\) and \(\delta(G)(\delta(G)+2+\sqrt{\delta(G)^{2}+4\delta(G)})/2\) with respect to both the sum of the perceived costs and the sum of the presumed ones, and that the price of stability is between \(\delta(G)\) and \(2\delta(G)\) with respect to the sum of the perceived costs.