The computational complexity of weak saddles

Felix Brandt, Markus Brill, Felix Fischer, Jan Hoffmann

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


We continue the recently initiated study of the computational aspects of weak saddles, an ordinal set-valued solution concept proposed by Shapley. Brandt et al. gave a polynomial-time algorithm for computing weak saddles in a subclass of matrix games, and showed that certain problems associated with weak saddles of bimatrix games are NP-complete. The important question of whether weak saddles can be found efficiently was left open. We answer this question in the negative by showing that finding weak saddles of bimatrix games is NP-hard, under polynomial-time Turing reductions. We moreover prove that recognizing weak saddles is coNP-complete, and that deciding whether a given action is contained in some weak saddle is hard for parallel access to NP and thus not even in NP unless the polynomial hierarchy collapses. Our hardness results are finally shown to carry over to a natural weakening of weak saddles.

Original languageEnglish
Title of host publicationAlgorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings
Number of pages12
StatePublished - 2009
Externally publishedYes
Event2nd International Symposium on Algorithmic Game Theory, SAGT 2009 - Paphos, Cyprus
Duration: 18 Oct 200920 Oct 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5814 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference2nd International Symposium on Algorithmic Game Theory, SAGT 2009


Dive into the research topics of 'The computational complexity of weak saddles'. Together they form a unique fingerprint.

Cite this