7

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


2

This proposition is in general not true. One can show that it is true in the case $n=2$ and $m=2$. Here, I exhibit a counter example when $n=3$ and $m=2$. A brief comment. We can rephrase the question in words: does a Nash equilibrium that is "more random" ($e'$ versus $e$) is less efficient? Intuitively, as more mixed strategies are played, the realized ...


Only top voted, non community-wiki answers of a minimum length are eligible