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


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

  • 1
    $\begingroup$ 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. $\endgroup$
    – R B
    Commented Feb 11, 2015 at 5:25
  • $\begingroup$ 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. $\endgroup$ Commented Feb 11, 2015 at 7:27
  • $\begingroup$ 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. $\endgroup$
    – R B
    Commented Feb 12, 2015 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.