Loading...
Please wait, while we are loading the content...
Similar Documents
Computing Dominance-Based Solution Concepts
| Content Provider | ACM Digital Library |
|---|---|
| Author | Brandt, Felix Brill, Markus |
| Copyright Year | 2016 |
| Description | Author Affiliation: University of Oxford, Oxford, UK(Technische universität münchen, Germany (Brandt, Felix; Brill, Markus)) |
| 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. |
| Starting Page | 1 |
| Ending Page | 22 |
| Page Count | 22 |
| File Format | |
| ISSN | 21678375 |
| e-ISSN | 21678383 |
| DOI | 10.1145/2963093 |
| Volume Number | 5 |
| Issue Number | 2 |
| Journal | ACM Transactions on Economics and Computation (TEAC) |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2016-10-25 |
| Publisher Place | New York |
| Access Restriction | One Nation One Subscription (ONOS) |
| Subject Keyword | CURB sets Game theory Shapley’s saddles Solution concepts |
| Content Type | Text |
| Resource Type | Article |
| Subject | Economics and Econometrics Marketing Computational Mathematics Statistics and Probability Computer Science |
