Computing Nash Equilibria in Multidimensional Congestion Games

We study pure-strategy Nash equilibrium (PSNE) computation in 𝑘-dimensional congestion games (𝑘-DCGs) where the weights or demands of the players are 𝑘-dimensional vectors. We first show that deciding the existence of a PSNE in a 𝑘-DCG is NP-complete even for games when players have binary and unit demand vectors. We then focus on computing PSNE for 𝑘-DCGs and their variants with general, linear, and exponential cost functions. For general cost functions (potentially non-monotonic), we provide the first configuration-space framework to find a PSNE if one exists. For linear and exponential cost functions, we provide potential functionbased algorithms to find a PSNE. These algorithms run in polynomial time under certain assumptions. We also study structured demands and cost functions, giving polynomial-time algorithms to compute PSNE for several cases. For general cost functions, we give a constructive proof of existence for an (𝛼, 𝛽)-PSNE (for certain 𝛼 and 𝛽), where 𝛼 and 𝛽 are multiplicative and additive approximation factors, respectively.