TY - GEN

T1 - The computational complexity of weak saddles

AU - Brandt, Felix

AU - Brill, Markus

AU - Fischer, Felix

AU - Hoffmann, Jan

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=71549145987&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04645-2_22

DO - 10.1007/978-3-642-04645-2_22

M3 - Conference contribution

AN - SCOPUS:71549145987

SN - 3642046444

SN - 9783642046445

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 238

EP - 249

BT - Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings

T2 - 2nd International Symposium on Algorithmic Game Theory, SAGT 2009

Y2 - 18 October 2009 through 20 October 2009

ER -