7

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

Community
  • 1
R B
  • 620
  • 3
  • 13

1 Answers1

8

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.

Rahul Savani
  • 286
  • 1
  • 5
  • 1
    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 '15 at 05: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. – Rahul Savani Feb 11 '15 at 07: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 '15 at 09:14