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

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

• 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
• 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