<p>Yes, there is always a pure Nash equilibrium. See:</p>

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

<p>You are interested in the special case of <strong>singleton</strong> congestion games with player-specific payoff functions.</p>

<p>And yes, they can be computed in polynomial time. See Corollary 7 in:</p>

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

CC BY-SA 3.0
2015-02-11T05:25:55.093Z
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
CC BY-SA 3.0
2015-02-11T07:27:48.907Z
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
CC BY-SA 3.0
2015-02-12T09:14:47.540Z
Thanks Rahul ! If you are interested, I have a related question posted on [mathoverflow](http://mathoverflow.net/questions/196083/when-does-a-stable-assignment-of-buyers-into-goods-exist), 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
CC BY-SA 3.0
2015-02-10T23:48:00.387Z
2015-02-11T07:33:03.680Z
2015-02-11T07:33:03.680Z
Rahul Savani
<p>Denote <span class="math-container">$[r]\triangleq\{1,2,\ldots,r\}$</span>.</p>
<p>Consider a game with <span class="math-container">$n$</span> players, <span class="math-container">$[n]$</span>, each has <span class="math-container">$m$</span> strategies, <span class="math-container">$[m]$</span>.</p>
<p>Each player <span class="math-container">$i$</span> has an associated payoff function, which considers only his selected strategy, and the number of players selected the same strategy:
<span class="math-container">$$U_i:[m]\times[n]\to[0,1]$$</span></p>
<p>Furthermore, the utility function is monotonically decreasing in the number of players which picked the same strategy, i.e.
<span class="math-container">$$\forall i\in[n],j\in[m],k\in[n-1]:U_i(j,k)\geq U_i(j,k+1)$$</span></p>
<blockquote>
<p><strong>Does this game always have a pure Nash equilibrium?</strong></p>
<p><strong>Can we (computationally) find it efficiently?</strong></p>
</blockquote>
<hr />
<p>Notice that the <strong>special case</strong>, where all players are symmetric (<span class="math-container">$\forall i,j\in[n]: U_i\equiv U_j\equiv U$</span>), the game reduces to an exact potential game and therefore is guaranteed to have a pure Nash equilibrium.</p>
<p>The potential function for the symmetric case would be, given a strategy profile <span class="math-container">$s$</span>:
<span class="math-container">$$\phi(s) = \sum_{j\in[m]}\sum_{k=1}^{\#_j(s)} U(j,k)$$</span></p>
<p>Where <span class="math-container">$\#_j(s)$</span> is the number of players in <span class="math-container">$s$</span> playing strategy <span class="math-container">$j$</span>.</p>

<game-theory><computation><nash-equilibrium><congestion-games>
Is there always a pure Nash equilibrium in a resource selection game?
R B
# Is there always a pure Nash equilibrium in a resource selection game?

(Asked by: username_0 on 2015-02-09)

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

**Tags:** game-theory, computation, nash-equilibrium, congestion-games

---

## 1 answers

### Answer by username_1 on 2015-02-10. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: Thanks Rahul ! If you are interested, I have a related question posted on [mathoverflow](http://mathoverflow.net/questions/196083/when-does-a-stable-assignment-of-buyers-into-goods-exist), 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.  

---

