The computational complexity of weak saddles

DOI10.1007/S00224-010-9298-ZMaRDI QIDQ647484zbMATH OpenOpenAlexFDO

Authors Felix Brandt, Markus Brill, Felix Fischer, Jan Hoffmann

Publication date 23 November 2011

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-010-9298-z

zbMATH Keywords

computational complexitygame theorysolution conceptsShapley's saddles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05)

Recommendations

• The computational complexity of weak saddles
• Settling the complexity of computing two-player Nash equilibria
• The complexity of computing a Nash equilibrium
• On the complexity of deciding bimatrix games similarity
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games

Cites work

• scientific article; zbMATH DE number 3137856 (Why is no real title available?)
• scientific article; zbMATH DE number 49749 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3205074 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• Computing the minimal covering set
• Covering sets and a new Condorcet choice correspondence
• Dominated strategies and common knowledge
• Dutta's minimal covering set and Shapley's saddles
• Exact analysis of Dodgson elections
• More complicated questions about maxima and minima, and some closures of NP
• Non-cooperative games
• On the complexity of iterated weak dominance in constant-sum games
• Rationalizable Strategic Behavior
• Rationalizable Strategic Behavior and the Problem of Perfection
• Settling the complexity of computing two-player Nash equilibria
• Strategy subsets closed under rational behavior
• The Complexity of Eliminating Dominated Strategies
• The complexity of computing a Nash equilibrium

Cited in

(2)

• An ordinal minimax theorem
• The computational complexity of weak saddles

This page was built for publication: The computational complexity of weak saddles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q647484)