The complexity of pure Nash equilibria

DOI10.1145/1007352.1007445zbMath1192.91042OpenAlexW2145297839MaRDI QIDQ3580952

Kunal Talwar, Alex Fabrikant, Christos H. Papadimitriou

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

Mathematics Subject Classification ID

Games involving graphs (91A43) (n)-person games, (n>2) (91A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Related Items (only showing first 100 items - show all)

Some results of Maria Serna on strategic games: complexity of equilibria and models ⋮ The complexity of welfare maximization in congestion games ⋮ Concurrent imitation dynamics in congestion games ⋮ An abstraction-refinement methodology for reasoning about network games ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ Coordination mechanisms ⋮ Computation of equilibria and the price of anarchy in bottleneck congestion games ⋮ Efficient coordination mechanisms for unrelated machine scheduling ⋮ Strong equilibria in games with the lexicographical improvement property ⋮ On spectrum sharing games ⋮ Decentralized dynamics for finite opinion games ⋮ On the convergence of multicast games in directed networks ⋮ Computing equilibria: a computational complexity perspective ⋮ Equilibrium computation in resource allocation games ⋮ Computing approximate Nash equilibria in network congestion games ⋮ Generalized mirror descents in congestion games ⋮ Convergence of incentive-driven dynamics in Fisher markets ⋮ Network-formation games with regular objectives ⋮ On the performance of mildly greedy players in cut games ⋮ Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions ⋮ On the complexity of Pareto-optimal Nash and strong equilibria ⋮ Computing pure Nash and strong equilibria in bottleneck congestion games ⋮ Pure Nash equilibria in a generalization of congestion games allowing resource failures ⋮ Metastability of Asymptotically Well-Behaved Potential Games ⋮ Nash equilibria with minimum potential in undirected broadcast games ⋮ \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games ⋮ Sharing Non-anonymous Costs of Multiple Resources Optimally ⋮ Timing matters: online dynamics in broadcast games ⋮ Dynamics in network interaction games ⋮ Unique end of potential line ⋮ The power of one evil secret agent ⋮ Convergence to equilibria in distributed, selfish reallocation processes with weighted tasks ⋮ Capacitated network design games ⋮ Congestion games with capacitated resources ⋮ Minimizing expectation plus variance ⋮ Convergence to approximate Nash equilibria in congestion games ⋮ Strategic multiway cut and multicut games ⋮ On the performance of approximate equilibria in congestion games ⋮ Graphical congestion games ⋮ Convergence and approximation in potential games ⋮ Many-one reductions and the category of multivalued functions ⋮ A logarithmic approximation for polymatroid congestion games ⋮ Incentive-based search for efficient equilibria of the public goods game ⋮ Tight bounds for selfish and greedy load balancing ⋮ Computational aspects of uncertainty profiles and angel-daemon games ⋮ Designing fast converging cost sharing methods for multicast transmissions ⋮ Performance of one-round walks in linear congestion games ⋮ Characterizing the existence of potential functions in weighted congestion games ⋮ Equilibria, fixed points, and complexity classes ⋮ Selfish splittable flows and NP-completeness ⋮ Equilibria problems on games: complexity versus succinctness ⋮ Greediness and equilibrium in congestion games ⋮ Stability vs. optimality in selfish ring routing ⋮ Convergence of best-response dynamics in games with conflicting congestion effects ⋮ On best response dynamics in weighted congestion games with polynomial delays ⋮ Computing solutions of the multiclass network equilibrium problem with affine cost functions ⋮ The complexity of uniform Nash equilibria and related regular subgraph problems ⋮ Resource buying games ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ The complexity of pure equilibria in mix-weighted congestion games on parallel links ⋮ Network topology and equilibrium existence in weighted network congestion games ⋮ Chance-constrained games with mixture distributions ⋮ Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game ⋮ Pairwise-Interaction Games ⋮ Settling the Complexity of Local Max-Cut (Almost) Completely ⋮ Network movement games ⋮ Selfish routing with incomplete information ⋮ Computational aspects of the colorful Carathéodory theorem ⋮ Synthesis from component libraries with costs ⋮ Computing equilibria of Cournot oligopoly models with mixed-integer quantities ⋮ Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games ⋮ Metastability of logit dynamics for coordination games ⋮ Approximate Nash equilibria in anonymous games ⋮ The impact of social ignorance on weighted congestion games ⋮ 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 ⋮ Competitive routing over time ⋮ Optimization of multi-criteria facility-based systems via vector potential approach ⋮ On influence, stable behavior, and the most influential individuals in networks: a game-theoretic approach ⋮ The complexity of the parity argument with potential ⋮ Leadership in singleton congestion games: what is hard and what is easy ⋮ Symmetries and the complexity of pure Nash equilibrium ⋮ Pure Nash equilibria in player-specific and weighted congestion games ⋮ Complexity and Optimality of the Best Response Algorithm in Random Potential Games ⋮ Computing All Solutions of Nash Equilibrium Problems with Discrete Strategy Sets ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic ⋮ How hard is it to find extreme Nash equilibria in network congestion games? ⋮ Weighted congestion games with separable preferences ⋮ Convergence method, properties and computational complexity for Lyapunov games ⋮ Nash equilibria in all-optical networks ⋮ Computing equilibrium in network utility-sharing and discrete election games ⋮ Combinatorial auctions with endowment effect ⋮ Selfish unsplittable flows ⋮ Self-organizing flows in social networks ⋮ Enforcing efficient equilibria in network design games via subsidies ⋮ Self-organizing Flows in Social Networks ⋮ Timed network games

This page was built for publication: The complexity of pure Nash equilibria