Publication Information

{'id': 'https://openalex.org/W2112919139', 'doi': None, 'title': 'The complexity of nash equilibria', 'display_name': 'The complexity of nash equilibria', 'publication_year': 2008, 'publication_date': '2008-01-01', 'ids': {'openalex': 'https://openalex.org/W2112919139', 'mag': '2112919139'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'http://people.csail.mit.edu/costis/thesis.pdf', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': [], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5103200572', 'display_name': 'Christos H. Papadimitriou', 'orcid': 'https://orcid.org/0009-0000-7264-8015'}, 'institutions': [{'id': 'https://openalex.org/I95457486', 'display_name': 'University of California, Berkeley', 'ror': 'https://ror.org/01an7q238', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I95457486']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Christos H. Papadimitriou', 'raw_affiliation_strings': ['University of California, Berkeley'], 'affiliations': [{'raw_affiliation_string': 'University of California, Berkeley', 'institution_ids': ['https://openalex.org/I95457486']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5007697240', 'display_name': 'Konstantinos S. Daskalakis', 'orcid': 'https://orcid.org/0000-0002-3996-5219'}, 'institutions': [{'id': 'https://openalex.org/I95457486', 'display_name': 'University of California, Berkeley', 'ror': 'https://ror.org/01an7q238', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I95457486']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Konstantinos Daskalakis', 'raw_affiliation_strings': ['University of California, Berkeley'], 'affiliations': [{'raw_affiliation_string': 'University of California, Berkeley', 'institution_ids': ['https://openalex.org/I95457486']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 1.376, 'has_fulltext': False, 'cited_by_count': 18, 'citation_normalized_percentile': {'value': 0.845245, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 87, 'max': 88}, 'biblio': {'volume': None, 'issue': None, 'first_page': None, 'last_page': None}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T11031', 'display_name': 'Game Theory and Applications', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1803', 'display_name': 'Management Science and Operations Research'}, 'field': {'id': 'https://openalex.org/fields/18', 'display_name': 'Decision Sciences'}, 'domain': {'id': 'https://openalex.org/domains/2', 'display_name': 'Social Sciences'}}, 'topics': [{'id': 'https://openalex.org/T11031', 'display_name': 'Game Theory and Applications', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1803', 'display_name': 'Management Science and Operations Research'}, 'field': {'id': 'https://openalex.org/fields/18', 'display_name': 'Decision Sciences'}, 'domain': {'id': 'https://openalex.org/domains/2', 'display_name': 'Social Sciences'}}, {'id': 'https://openalex.org/T11182', 'display_name': 'Auction Theory and Applications', 'score': 0.9981, 'subfield': {'id': 'https://openalex.org/subfields/1803', 'display_name': 'Management Science and Operations Research'}, 'field': {'id': 'https://openalex.org/fields/18', 'display_name': 'Decision Sciences'}, 'domain': {'id': 'https://openalex.org/domains/2', 'display_name': 'Social Sciences'}}, {'id': 'https://openalex.org/T10991', 'display_name': 'Game Theory and Voting Systems', 'score': 0.9948, 'subfield': {'id': 'https://openalex.org/subfields/2002', 'display_name': 'Economics and Econometrics'}, 'field': {'id': 'https://openalex.org/fields/20', 'display_name': 'Economics, Econometrics and Finance'}, 'domain': {'id': 'https://openalex.org/domains/2', 'display_name': 'Social Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/risk-dominance', 'display_name': 'Risk dominance', 'score': 0.6658102}, {'id': 'https://openalex.org/keywords/folk-theorem', 'display_name': 'Folk theorem', 'score': 0.6501122}, {'id': 'https://openalex.org/keywords/correlated-equilibrium', 'display_name': 'Correlated equilibrium', 'score': 0.5776101}], 'concepts': [{'id': 'https://openalex.org/C46814582', 'wikidata': 'https://www.wikidata.org/wiki/Q23389', 'display_name': 'Nash equilibrium', 'level': 2, 'score': 0.79685867}, {'id': 'https://openalex.org/C141824439', 'wikidata': 'https://www.wikidata.org/wiki/Q307521', 'display_name': 'Epsilon-equilibrium', 'level': 4, 'score': 0.75535953}, {'id': 'https://openalex.org/C144237770', 'wikidata': 'https://www.wikidata.org/wiki/Q747534', 'display_name': 'Mathematical economics', 'level': 1, 'score': 0.6788457}, {'id': 'https://openalex.org/C22349654', 'wikidata': 'https://www.wikidata.org/wiki/Q2039354', 'display_name': 'Risk dominance', 'level': 5, 'score': 0.6658102}, {'id': 'https://openalex.org/C21603316', 'wikidata': 'https://www.wikidata.org/wiki/Q650738', 'display_name': 'Folk theorem', 'level': 5, 'score': 0.6501122}, {'id': 'https://openalex.org/C32407928', 'wikidata': 'https://www.wikidata.org/wiki/Q2733833', 'display_name': 'Best response', 'level': 3, 'score': 0.5786707}, {'id': 'https://openalex.org/C163630976', 'wikidata': 'https://www.wikidata.org/wiki/Q964667', 'display_name': 'Correlated equilibrium', 'level': 5, 'score': 0.5776101}, {'id': 'https://openalex.org/C16946829', 'wikidata': 'https://www.wikidata.org/wiki/Q1039525', 'display_name': 'Trembling hand perfect equilibrium', 'level': 5, 'score': 0.5436508}, {'id': 'https://openalex.org/C164407509', 'wikidata': 'https://www.wikidata.org/wiki/Q5384490', 'display_name': 'Equilibrium selection', 'level': 4, 'score': 0.46972907}, {'id': 'https://openalex.org/C39637292', 'wikidata': 'https://www.wikidata.org/wiki/Q908207', 'display_name': 'Complexity class', 'level': 3, 'score': 0.432881}, {'id': 'https://openalex.org/C2777212361', 'wikidata': 'https://www.wikidata.org/wiki/Q5127848', 'display_name': 'Class (philosophy)', 'level': 2, 'score': 0.42959344}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.41375357}, {'id': 'https://openalex.org/C311688', 'wikidata': 'https://www.wikidata.org/wiki/Q2393193', 'display_name': 'Time complexity', 'level': 2, 'score': 0.39561796}, {'id': 'https://openalex.org/C177142836', 'wikidata': 'https://www.wikidata.org/wiki/Q44455', 'display_name': 'Game theory', 'level': 2, 'score': 0.3948229}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.35366035}, {'id': 'https://openalex.org/C202556891', 'wikidata': 'https://www.wikidata.org/wiki/Q1584646', 'display_name': 'Repeated game', 'level': 3, 'score': 0.29638132}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.20998529}, {'id': 'https://openalex.org/C154945302', 'wikidata': 'https://www.wikidata.org/wiki/Q11660', 'display_name': 'Artificial intelligence', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'http://people.csail.mit.edu/costis/thesis.pdf', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 82, 'referenced_works': ['https://openalex.org/W1486829250', 'https://openalex.org/W1505310183', 'https://openalex.org/W1540637571', 'https://openalex.org/W1576554202', 'https://openalex.org/W1605188341', 'https://openalex.org/W1725063609', 'https://openalex.org/W1805772200', 'https://openalex.org/W1807884544', 'https://openalex.org/W1855561663', 'https://openalex.org/W1966347268', 'https://openalex.org/W1970494248', 'https://openalex.org/W1972735418', 'https://openalex.org/W1974885059', 'https://openalex.org/W1980813953', 'https://openalex.org/W1985447712', 'https://openalex.org/W1990870166', 'https://openalex.org/W1993474005', 'https://openalex.org/W1997897041', 'https://openalex.org/W2000151369', 'https://openalex.org/W2008968905', 'https://openalex.org/W2009636825', 'https://openalex.org/W2010476628', 'https://openalex.org/W2014217859', 'https://openalex.org/W2015754044', 'https://openalex.org/W2017781790', 'https://openalex.org/W2026177035', 'https://openalex.org/W2033040247', 'https://openalex.org/W2037028865', 'https://openalex.org/W2054129049', 'https://openalex.org/W2055569927', 'https://openalex.org/W2056623179', 'https://openalex.org/W2058787498', 'https://openalex.org/W2060186712', 'https://openalex.org/W2060354090', 'https://openalex.org/W2062102322', 'https://openalex.org/W2062961409', 'https://openalex.org/W2066194644', 'https://openalex.org/W2067151918', 'https://openalex.org/W2070994188', 'https://openalex.org/W2080286264', 'https://openalex.org/W2083639782', 'https://openalex.org/W2089649903', 'https://openalex.org/W2094689434', 'https://openalex.org/W2099111195', 'https://openalex.org/W2102736491', 'https://openalex.org/W2103981148', 'https://openalex.org/W2108113998', 'https://openalex.org/W2109100253', 'https://openalex.org/W2118559710', 'https://openalex.org/W2124580127', 'https://openalex.org/W2125056648', 'https://openalex.org/W2125413339', 'https://openalex.org/W2127470768', 'https://openalex.org/W2131552123', 'https://openalex.org/W2131967794', 'https://openalex.org/W2136105862', 'https://openalex.org/W2140790422', 'https://openalex.org/W2142048307', 'https://openalex.org/W2144846366', 'https://openalex.org/W2145147424', 'https://openalex.org/W2145297839', 'https://openalex.org/W2151033164', 'https://openalex.org/W2153961011', 'https://openalex.org/W2160135758', 'https://openalex.org/W2169359757', 'https://openalex.org/W2170578451', 'https://openalex.org/W2170677670', 'https://openalex.org/W2179957089', 'https://openalex.org/W2256680040', 'https://openalex.org/W2292587149', 'https://openalex.org/W2326915435', 'https://openalex.org/W2330024298', 'https://openalex.org/W2331414215', 'https://openalex.org/W2357840148', 'https://openalex.org/W2477951159', 'https://openalex.org/W2583136912', 'https://openalex.org/W2798655805', 'https://openalex.org/W3100963268', 'https://openalex.org/W3111297213', 'https://openalex.org/W42043901', 'https://openalex.org/W619565225', 'https://openalex.org/W850385441'], 'related_works': ['https://openalex.org/W3154613819', 'https://openalex.org/W3049736005', 'https://openalex.org/W3000000514', 'https://openalex.org/W2971802750', 'https://openalex.org/W2949922918', 'https://openalex.org/W2949789980', 'https://openalex.org/W2949547757', 'https://openalex.org/W2949121607', 'https://openalex.org/W2504967797', 'https://openalex.org/W2408729172', 'https://openalex.org/W2330024298', 'https://openalex.org/W2236957682', 'https://openalex.org/W2145297839', 'https://openalex.org/W2131686835', 'https://openalex.org/W2044952470', 'https://openalex.org/W2002115314', 'https://openalex.org/W1921899629', 'https://openalex.org/W1668627937', 'https://openalex.org/W1513383563', 'https://openalex.org/W120148423'], 'abstract_inverted_index': {'The': [0, 201], 'Internet': [1], 'owes': [2], 'much': [3], 'of': [4, 11, 31, 57, 67, 71, 76, 81, 106, 130, 160, 231, 242, 262, 279, 307], 'its': [5], 'complexity': [6, 129, 203, 241], 'to': [7, 36, 109, 118, 157, 238, 276], 'the': [8, 55, 69, 79, 82, 127, 131, 154, 158, 183, 240, 277, 280], 'large': [9], 'number': [10, 306], 'entities': [12, 20], 'that': [13, 114, 136, 170, 174, 182, 220], 'run': [14], 'it': [15, 171], 'and': [16, 23, 166, 215, 259, 290], 'use': [17], 'it.': [18], 'These': [19, 267], 'have': [21], 'different': [22], 'potentially': [24], 'conflicting': [25], 'interests,': [26], 'so': [27], 'their': [28], 'interactions': [29], 'are': [30, 48, 95, 177, 236, 268], 'a': [32, 64, 86, 104, 112, 138, 149, 197, 222, 226, 256, 295, 304], 'strategic': [33, 72], 'nature.': [34], 'Therefore,': [35], 'understand': [37], 'these': [38], 'interactions,': [39], 'concepts': [40], 'from': [41], 'Economics': [42], 'and,': [43], 'most': [44], 'importantly,': [45], 'Game': [46], 'Theory': [47], 'necessary.': [49], 'An': [50], 'important': [51, 260], 'such': [52, 93, 175], 'concept': [53], 'is': [54, 141, 172, 185, 205, 219, 225, 274], 'notion': [56], 'Nash': [58, 83, 132, 139, 150, 223, 245], 'equilibrium,': [59], 'which': [60, 271], 'provides': [61], 'us': [62], 'with': [63, 247, 303], 'rigorous': [65], 'way': [66], 'predicting': [68], 'behavior': [70], 'agents': [73, 108], 'in': [74, 111, 164, 196, 212, 270, 285], 'situations': [75], 'conflict.': [77], 'But': [78], 'credibility': [80], 'equilibrium': [84, 140, 151, 224], 'as': [85, 186, 188], 'framework': [87], 'for': [88, 208, 300], 'behavior-prediction': [89], 'depends': [90], 'on': [91], 'whether': [92], 'equilibria': [94], 'efficiently': [96], 'computable.': [97], 'After': [98], 'all,': [99], 'why': [100], 'should': [101], 'we': [102, 125, 235, 254], 'expect': [103], 'group': [105], 'rational': [107], 'behave': [110], 'fashion': [113], 'requires': [115], 'exponential': [116], 'time': [117, 297], 'be': [119], 'computed?': [120], 'Motivated': [121], 'by': [122, 146], 'this': [123, 232, 252], 'question,': [124], 'study': [126, 239], 'computational': [128], 'equilibrium.': [133], '\r\nWe': [134], 'show': [135, 180], 'computing': [137, 221, 243], 'an': [142], 'intractable': [143], 'problem.': [144, 228], 'Since': [145], "Nash's": [147], 'theorem': [148], 'always': [152], 'exists,': [153], 'problem': [155, 184], 'belongs': [156], 'family': [159], 'total': [161], 'search': [162], 'problems': [163, 176], 'NP,': [165], 'previous': [167], 'work': [168], 'establishes': [169], 'unlikely': [173], 'NP-complete.': [178], 'We': [179, 293], 'instead': [181], 'hard': [187], 'solving': [189], 'any': [190], 'Brouwer': [191], 'fixed': [192], 'point': [193], 'computation': [194], 'problem,': [195], 'precise': [198, 217], 'complexity-theoretic': [199], 'sense.': [200], 'corresponding': [202], 'class': [204, 261], 'called': [206, 264], 'PPAD,': [207], 'Polynomial': [209], 'Parity': [210], 'Argument': [211], 'Directed': [213], 'graphs,': [214], 'our': [216], 'result': [218], 'PPAD-complete': [227], '\r\nIn': [229], 'view': [230], 'hardness': [233], 'result,': [234], 'motivated': [237], 'approximate': [244], 'equilibria,': [246], 'arbitrarily': [248], 'close': [249], 'approximation.': [250], 'In': [251], 'regard,': [253], 'consider': [255], 'very': [257], 'natural': [258], 'games,': [263, 289], 'anonymous': [265, 301], 'games.': [266], 'games': [269, 302], 'every': [272], 'player': [273], 'oblivious': [275], 'identities': [278], 'other': [281], 'players;': [282], 'examples': [283], 'arise': [284], 'auction': [286], 'settings,': [287], 'congestion': [288], 'social': [291], 'interactions.': [292], 'give': [294], 'polynomial': [296], 'approximation': [298], 'scheme': [299], 'bounded': [305], 'strategies.': [308]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2112919139', 'counts_by_year': [{'year': 2022, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 1}, {'year': 2020, 'cited_by_count': 4}, {'year': 2019, 'cited_by_count': 1}, {'year': 2017, 'cited_by_count': 1}, {'year': 2016, 'cited_by_count': 2}, {'year': 2014, 'cited_by_count': 3}, {'year': 2013, 'cited_by_count': 1}], 'updated_date': '2024-12-14T11:13:33.191841', 'created_date': '2016-06-24'}