The Library
The computational complexity of weak saddles
Tools
Brandt, Felix, Brill, Markus, Fischer, Felix and Hoffmann, Jan (2011) The computational complexity of weak saddles. Theory of Computing Systems, 49 (1). pp. 139-161. doi:10.1007/s00224-010-9298-z ISSN 1432-4350.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s00224-010-9298-z
Abstract
We study the computational aspects of weak saddles, an ordinal set-valued solution concept proposed by Shapley. F. Brandt et al. recently 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-hard. 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. Most of our hardness results are shown to carry over to a natural weakening of weak saddles.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Theory of Computing Systems | ||||||
Publisher: | Springer | ||||||
ISSN: | 1432-4350 | ||||||
Official Date: | July 2011 | ||||||
Dates: |
|
||||||
Volume: | 49 | ||||||
Number: | 1 | ||||||
Page Range: | pp. 139-161 | ||||||
DOI: | 10.1007/s00224-010-9298-z | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |