The complexity of pure Nash equilibria
From MaRDI portal
Publication:3580952
DOI10.1145/1007352.1007445zbMath1192.91042MaRDI QIDQ3580952
Christos H. Papadimitriou, Alex Fabrikant, Kunal Talwar
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007445
91A43: Games involving graphs
91A06: (n)-person games, (n>2)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91-04: Software, source code, etc. for problems pertaining to game theory, economics, and finance
Related Items
Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy, Atomic Congestion Games: Fast, Myopic and Concurrent, The Price of Stochastic Anarchy, On the complexity of constrained Nash equilibria in graphical games, The structure and complexity of Nash equilibria for a selfish routing game, Coordination mechanisms, Computing equilibria: a computational complexity perspective, The complexity of uniform Nash equilibria and related regular subgraph problems, How to find Nash equilibria with extreme total latency in network congestion games?, The price of atomic selfish ring routing, Atomic congestion games: fast, myopic and concurrent, Congestion games with linearly independent paths: convergence time and price of anarchy, Symmetries and the complexity of pure Nash equilibrium, Pure Nash equilibria in player-specific and weighted congestion games, How hard is it to find extreme Nash equilibria in network congestion games?, Weighted congestion games with separable preferences, Nash equilibria in all-optical networks, Designing fast converging cost sharing methods for multicast transmissions, On the convergence of multicast games in directed networks, Selfish routing with incomplete information, Selfish unsplittable flows, On the Complexity of Pareto-optimal Nash and Strong Equilibria, Integer Programming: Optimization and Evaluation Are Equivalent, Computing Approximate Nash Equilibria in Network Congestion Games, $\mathcal{NP}$ -Hardness of Pure Nash Equilibrium in Scheduling and Connection Games, Malicious Bayesian Congestion Games, Management of Variable Data Streams in Networks, Asynchronous Congestion Games
