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

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$$.

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.

• Thanks for the answer Rahul. In not convinced, however, by the hardness, as this is a special case of congestion game and not general game.
– R B
Feb 11, 2015 at 5:25
• Sorry, I misread your definition - you are interested in singleton congestion games with player-specific payoffs, my answer would apply to say asymmetric network congestion games. I have edited it. Feb 11, 2015 at 7:27
• Thanks Rahul ! If you are interested, I have a related question posted on mathoverflow, where the payoff to the player is dependent on the number of players picking the same strategy, but might drop to 0 if some players pick the same singleton. Thanks again.
– R B
Feb 12, 2015 at 9:14