{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:11:55Z","timestamp":1750306315298,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,10,25]],"date-time":"2016-10-25T00:00:00Z","timestamp":1477353600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2017,5,31]]},"abstract":"<jats:p>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\u2019s saddles, Harsanyi and Selten\u2019s primitive formations, Basu and Weibull\u2019s CURB sets, and Dutta and Laslier\u2019s 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.<\/jats:p>","DOI":"10.1145\/2963093","type":"journal-article","created":{"date-parts":[[2016,10,26]],"date-time":"2016-10-26T13:20:01Z","timestamp":1477488001000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Dominance-Based Solution Concepts"],"prefix":"10.1145","volume":"5","author":[{"given":"Felix","family":"Brandt","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Brill","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,10,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/2171725"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.01.017"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.02.003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1765(91)90179-O"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1892211.1892224"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911196"},{"key":"e_1_2_1_7_1","unstructured":"E. Borel. 1921. La th\u00e9orie du jeu et les \u00e9quations int\u00e9grales \u00e0 noyau sym\u00e9trique. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences 173 (1921) 1304--1308.  E. Borel. 1921. La th\u00e9orie du jeu et les \u00e9quations int\u00e9grales \u00e0 noyau sym\u00e9trique. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences 173 (1921) 1304--1308."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/2951557"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2011.05.004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9282-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9298-z"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2015.12.010"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-011-0638-y"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2008.04.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064019"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-012-0696-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1996.0085"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003550000059"},{"key":"e_1_2_1_21_1","unstructured":"J. Duggan and M. Le Breton. 2014. Choice-Theoretic Solutions for Strategic Form Games. (2014). Mimeo. Available at http:\/\/www.johnduggan.net.  J. Duggan and M. Le Breton. 2014. Choice-Theoretic Solutions for Strategic Form Games. (2014). Mimeo. Available at http:\/\/www.johnduggan.net."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(88)90096-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003550050158"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01763120"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(94)00212-V"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2307\/2324486"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190190208"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.3.553"},{"volume":"6386","volume-title":"Proc. of 3rd International Symposium on Algorithmic Game Theory (SAGT\u201910)","author":"Hansen K. A.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","unstructured":"J. C. Harsanyi and R. Selten. 1988. A General Theory of Equilibrium Selection in Games. MIT Press.  J. C. Harsanyi and R. Selten. 1988. A General Theory of Equilibrium Selection in Games. MIT Press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-011-0638-2"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(88)90075-2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1993.1010"},{"key":"e_1_2_1_34_1","unstructured":"R. D. Luce and H. Raiffa. 1957. Games and Decisions: Introduction and Critical Survey. John Wiley 8 Sons.  R. D. Luce and H. Raiffa. 1957. Games and Decisions: Introduction and Critical Survey. John Wiley 8 Sons."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/2111098"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.2307\/1959383"},{"volume-title":"Game Theory: Analysis of Conflict","year":"1991","author":"Myerson R. B.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911197"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11229-007-9217-2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(92)90020-S"},{"volume-title":"Advances in Game Theory","author":"Shapley L.","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"e_1_2_1_46_1","unstructured":"J. von Neumann and O. Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press.  J. von Neumann and O. Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(70)90018-9"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2963093","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2963093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:04Z","timestamp":1750222444000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2963093"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,25]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,5,31]]}},"alternative-id":["10.1145\/2963093"],"URL":"https:\/\/doi.org\/10.1145\/2963093","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2016,10,25]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}