On the complexity of Pareto-optimal Nash and strong equilibria (Q372955): Difference between revisions

The authors consider computational complexity of strong and Pareto-optimal Nash equilibria in some classes of noncooperative games. First they show that a recognition task is polynomial for anonymous games, but the existence is NP-hard. The algorithm is based on a perfect matching scheme. It is shown that the recognition and computation task are polynomial for the special class of player-specific singleton congestion games, but existence and recognition are NP-hard in general congestion games.