Structure and complexity of extreme Nash equilibria

DOI10.1016/j.tcs.2005.05.011zbMath1121.91020OpenAlexW1976009178MaRDI QIDQ2570130

Burkhard Monien, Martin Gairing, Marios Mavronicolas, Thomas Lücking, Paul G. Spirakis

Publication date: 26 October 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.05.011

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Games involving graphs (91A43) Approximation algorithms (68W25)

Related Items (15)

On the complexity of constrained Nash equilibria in graphical games ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ The price of anarchy for polynomial social cost ⋮ On the structure and complexity of worst-case equilibria ⋮ Performance guarantees of jump neighborhoods on restricted related parallel machines ⋮ Cost sharing mechanisms for fair pricing of resource usage ⋮ A new model for selfish routing ⋮ Selfish routing with incomplete information ⋮ Nash equilibria in discrete routing games with convex latency functions ⋮ Extending the notion of rationality of selfish agents: second order Nash equilibria ⋮ Facets of the fully mixed Nash equilibrium conjecture ⋮ Computing Nash equilibria for scheduling on restricted parallel links ⋮ The Influence of Link Restrictions on (Random) Selfish Routing ⋮ Facets of the Fully Mixed Nash Equilibrium Conjecture ⋮ How hard is it to find extreme Nash equilibria in network congestion games?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon
• Approximate equilibria and ball fusion
• On the complexity of price equilibria
• Non-cooperative games
• A linear time approximation algorithm for multiprocessor scheduling
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• The price of selfish routing
• Algorithms, games, and the internet
• Mathematical Foundations of Computer Science 2003
• Completely Mixed Strategies in Bimatrix Games
• Equilibrium points in n -person games
• Inequalities: theory of majorization and its applications
• Improving local search heuristics for some scheduling problems. II

This page was built for publication: Structure and complexity of extreme Nash equilibria