The Library
Computing dominance-based solution concepts
Tools
Brandt, Felix and Brill, Markus (2017) Computing dominance-based solution concepts. ACM Transactions on Economics and Computation, 5 (2). pp. 1-22. doi:10.1145/2963093 ISSN 2167-8375.
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.1145/2963093
Abstract
Two common criticisms of Nash equilibrium are its dependence on very demanding epistemic assumptions and its computational intractability. We study the computational properties of less demanding set-valued solution concepts that are based on varying notions of dominance. These concepts are intuitively appealing, always exist, and admit unique minimal solutions in important subclasses of games. Examples include Shapley’s saddles, Harsanyi and Selten’s primitive formations, Basu and Weibull’s CURB sets, and Dutta and Laslier’s minimal covering set. Based on a unifying framework proposed by Duggan and Le Breton, we formulate two generic algorithms for computing these concepts and investigate for which classes of games and which properties of the underlying dominance notion the algorithms are sound and efficient. We identify two sets of conditions that are sufficient for polynomial-time computability and show that the conditions are satisfied, for instance, by saddles and primitive formations in normal-form games, minimal CURB sets in two-player games, and the minimal covering set in symmetric matrix games. Our positive algorithmic results explain regularities observed in the literature, but also apply to several solution concepts whose computational complexity was previously unknown.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Journal or Publication Title: | ACM Transactions on Economics and Computation | ||||||||
Publisher: | ACM | ||||||||
ISSN: | 2167-8375 | ||||||||
Official Date: | May 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 5 | ||||||||
Number: | 2 | ||||||||
Page Range: | pp. 1-22 | ||||||||
DOI: | 10.1145/2963093 | ||||||||
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 |