Is there always a pure Nash equilibrium in a resource selection game?

Question

Denote $[r]\triangleq\{1,2,\ldots,r\}$.

Consider a game with $n$ players, $[n]$, each has $m$ strategies, $[m]$.

Each player $i$ has an associated payoff function, which considers only his selected strategy, and the number of players selected the same strategy: $$U_i:[m]\times[n]\to[0,1]$$

Furthermore, the utility function is monotonically decreasing in the number of players which picked the same strategy, i.e. $$\forall i\in[n],j\in[m],k\in[n-1]:U_i(j,k)\geq U_i(j,k+1)$$

Does this game always have a pure Nash equilibrium?

Can we (computationally) find it efficiently?

---

Notice that the special case, where all players are symmetric ($\forall i,j\in[n]: U_i\equiv U_j\equiv U$), the game reduces to an exact potential game and therefore is guaranteed to have a pure Nash equilibrium.

The potential function for the symmetric case would be, given a strategy profile $s$: $$\phi(s) = \sum_{j\in[m]}\sum_{k=1}^{\#_j(s)} U(j,k)$$

Where $\#_j(s)$ is the number of players in $s$ playing strategy $j$.

Answer 1

Yes, there is always a pure Nash equilibrium. See:

I Milchtaich (1996). Congestion games with player-specific payoff functions. Games and economic behavior 13 (1), 111-124.

You are interested in the special case of singleton congestion games with player-specific payoff functions.

And yes, they can be computed in polynomial time. See Corollary 7 in:

Heiner Ackermann, Heiko Röglin, Berthold Vöcking (2009). Pure Nash equilibria in player-specific and weighted congestion games. Theoretical Computer Science 410 (17), 1552-1563.