Publication Information

{'id': 'https://openalex.org/W2952209068', 'doi': None, 'title': 'Complexity Results about Nash Equilibria', 'display_name': 'Complexity Results about Nash Equilibria', 'publication_year': 2002, 'publication_date': '2002-05-28', 'ids': {'openalex': 'https://openalex.org/W2952209068', 'mag': '2952209068'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://arxiv.org/pdf/cs/0205074.pdf', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'type': 'preprint', 'type_crossref': 'posted-content', '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/A5050903632', 'display_name': 'Vincent Conitzer', 'orcid': 'https://orcid.org/0000-0003-1899-7884'}, 'institutions': [{'id': 'https://openalex.org/I74973139', 'display_name': 'Carnegie Mellon University', 'ror': 'https://ror.org/05x2bcf33', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I74973139']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Vincent Conitzer', 'raw_affiliation_strings': ['Carnegie-Mellon University, Computer Science Department, Pittsburgh, PA#TAB#'], 'affiliations': [{'raw_affiliation_string': 'Carnegie-Mellon University, Computer Science Department, Pittsburgh, PA#TAB#', 'institution_ids': ['https://openalex.org/I74973139']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5023571961', 'display_name': 'Tüomas Sandholm', 'orcid': 'https://orcid.org/0000-0001-8861-9366'}, 'institutions': [{'id': 'https://openalex.org/I74973139', 'display_name': 'Carnegie Mellon University', 'ror': 'https://ror.org/05x2bcf33', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I74973139']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Tuomas Sandholm', 'raw_affiliation_strings': ['Carnegie-Mellon University, Computer Science Department, Pittsburgh, PA#TAB#'], 'affiliations': [{'raw_affiliation_string': 'Carnegie-Mellon University, Computer Science Department, Pittsburgh, PA#TAB#', 'institution_ids': ['https://openalex.org/I74973139']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': None, 'has_fulltext': False, 'cited_by_count': 13, 'citation_normalized_percentile': {'value': 0.805175, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 82, 'max': 83}, '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.9997, '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.9997, '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.9971, '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/T12137', 'display_name': 'Economic theories and models', 'score': 0.9916, '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/correlated-equilibrium', 'display_name': 'Correlated equilibrium', 'score': 0.6451972}, {'id': 'https://openalex.org/keywords/bayesian-game', 'display_name': 'Bayesian game', 'score': 0.47866186}, {'id': 'https://openalex.org/keywords/folk-theorem', 'display_name': 'Folk theorem', 'score': 0.47647142}, {'id': 'https://openalex.org/keywords/strategy', 'display_name': 'Strategy', 'score': 0.42310417}, {'id': 'https://openalex.org/keywords/symmetric-game', 'display_name': 'Symmetric game', 'score': 0.41737795}], 'concepts': [{'id': 'https://openalex.org/C46814582', 'wikidata': 'https://www.wikidata.org/wiki/Q23389', 'display_name': 'Nash equilibrium', 'level': 2, 'score': 0.811268}, {'id': 'https://openalex.org/C144237770', 'wikidata': 'https://www.wikidata.org/wiki/Q747534', 'display_name': 'Mathematical economics', 'level': 1, 'score': 0.74868244}, {'id': 'https://openalex.org/C32407928', 'wikidata': 'https://www.wikidata.org/wiki/Q2733833', 'display_name': 'Best response', 'level': 3, 'score': 0.68234456}, {'id': 'https://openalex.org/C155930848', 'wikidata': 'https://www.wikidata.org/wiki/Q1069099', 'display_name': 'Normal-form game', 'level': 4, 'score': 0.65916544}, {'id': 'https://openalex.org/C163630976', 'wikidata': 'https://www.wikidata.org/wiki/Q964667', 'display_name': 'Correlated equilibrium', 'level': 5, 'score': 0.6451972}, {'id': 'https://openalex.org/C164407509', 'wikidata': 'https://www.wikidata.org/wiki/Q5384490', 'display_name': 'Equilibrium selection', 'level': 4, 'score': 0.6423286}, {'id': 'https://openalex.org/C141824439', 'wikidata': 'https://www.wikidata.org/wiki/Q307521', 'display_name': 'Epsilon-equilibrium', 'level': 4, 'score': 0.6381551}, {'id': 'https://openalex.org/C202556891', 'wikidata': 'https://www.wikidata.org/wiki/Q1584646', 'display_name': 'Repeated game', 'level': 3, 'score': 0.5208795}, {'id': 'https://openalex.org/C200594392', 'wikidata': 'https://www.wikidata.org/wiki/Q812529', 'display_name': 'Bayesian game', 'level': 4, 'score': 0.47866186}, {'id': 'https://openalex.org/C21603316', 'wikidata': 'https://www.wikidata.org/wiki/Q650738', 'display_name': 'Folk theorem', 'level': 5, 'score': 0.47647142}, {'id': 'https://openalex.org/C177142836', 'wikidata': 'https://www.wikidata.org/wiki/Q44455', 'display_name': 'Game theory', 'level': 2, 'score': 0.45891652}, {'id': 'https://openalex.org/C73795354', 'wikidata': 'https://www.wikidata.org/wiki/Q287618', 'display_name': 'Sequential game', 'level': 3, 'score': 0.4538024}, {'id': 'https://openalex.org/C88959737', 'wikidata': 'https://www.wikidata.org/wiki/Q1546627', 'display_name': 'Strategy', 'level': 3, 'score': 0.42310417}, {'id': 'https://openalex.org/C93733245', 'wikidata': 'https://www.wikidata.org/wiki/Q3770642', 'display_name': 'Symmetric game', 'level': 5, 'score': 0.41737795}, {'id': 'https://openalex.org/C16946829', 'wikidata': 'https://www.wikidata.org/wiki/Q1039525', 'display_name': 'Trembling hand perfect equilibrium', 'level': 5, 'score': 0.41297007}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.3921952}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://arxiv.org/pdf/cs/0205074.pdf', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 29, 'referenced_works': ['https://openalex.org/W1483936539', 'https://openalex.org/W1619246471', 'https://openalex.org/W1972357512', 'https://openalex.org/W1976179404', 'https://openalex.org/W1989538212', 'https://openalex.org/W1994789681', 'https://openalex.org/W1995892667', 'https://openalex.org/W2006069523', 'https://openalex.org/W2006912660', 'https://openalex.org/W2012634103', 'https://openalex.org/W2013469527', 'https://openalex.org/W20228571', 'https://openalex.org/W2047880045', 'https://openalex.org/W2054951214', 'https://openalex.org/W2067050450', 'https://openalex.org/W2083680012', 'https://openalex.org/W2113147495', 'https://openalex.org/W2125537511', 'https://openalex.org/W2131724520', 'https://openalex.org/W2134628753', 'https://openalex.org/W2134729426', 'https://openalex.org/W2156827107', 'https://openalex.org/W2160135758', 'https://openalex.org/W2292587149', 'https://openalex.org/W2575731723', 'https://openalex.org/W2912008780', 'https://openalex.org/W2962893121', 'https://openalex.org/W3123286829', 'https://openalex.org/W3124716512'], 'related_works': ['https://openalex.org/W614922745', 'https://openalex.org/W282191634', 'https://openalex.org/W2146267939', 'https://openalex.org/W2127182849', 'https://openalex.org/W2125413339', 'https://openalex.org/W2117147908', 'https://openalex.org/W2095746359', 'https://openalex.org/W2077964199', 'https://openalex.org/W2073048734', 'https://openalex.org/W2064768356', 'https://openalex.org/W2013815105', 'https://openalex.org/W1990887241', 'https://openalex.org/W1988732867', 'https://openalex.org/W1899083786', 'https://openalex.org/W1855216217', 'https://openalex.org/W1667857601', 'https://openalex.org/W1589508846', 'https://openalex.org/W1528395754', 'https://openalex.org/W1488939132', 'https://openalex.org/W124742274'], 'abstract_inverted_index': {'Noncooperative': [0], 'game': [1, 92, 98, 106, 124, 130, 135], 'theory': [2], 'provides': [3], 'a': [4, 32, 71, 83, 89], 'normative': [5], 'framework': [6], 'for': [7, 12], 'analyzing': [8], 'strategic': [9], 'interactions.': [10], 'However,': [11], 'the': [13, 18, 52, 97, 105, 123], 'toolbox': [14], 'to': [15, 24], 'be': [16, 25], 'operational,': [17], 'solutions': [19], 'it': [20], 'defines': [21], 'will': [22], 'have': [23], 'computed.': [26], 'In': [27], 'this': [28], 'paper,': [29], 'we': [30], 'provide': [31], 'single': [33], 'reduction': [34], 'that': [35, 67, 79], '1)': [36], 'demonstrates': [37, 51], 'NP-hardness': [38], 'of': [39, 54, 61, 110], 'determining': [40, 69, 81], 'whether': [41, 70, 82], 'Nash': [42, 56, 62, 85, 128], 'equilibria': [43, 57], 'with': [44], 'certain': [45], 'natural': [46], 'properties': [47], 'exist,': [48], 'and': [49, 78, 122], '2)': [50], '#P-hardness': [53], 'counting': [55], '(or': [58], 'connected': [59], 'sets': [60], 'equilibria).': [63], 'We': [64], 'also': [65], 'show': [66], '3)': [68], 'pure-strategy': [72, 84], 'Bayes-Nash': [73, 144], 'equilibrium': [74, 86], 'exists': [75, 87], 'is': [76, 93, 99, 107, 125], 'NP-hard,': [77], '4)': [80], 'in': [88], 'stochastic': [90, 140], '(Markov)': [91], 'PSPACE-hard': [94], 'even': [95, 115], 'if': [96, 104, 116], 'invisible': [100], '(this': [101], 'remains': [102], 'NP-hard': [103], 'finite).': [108], 'All': [109], 'our': [111], 'hardness': [112], 'results': [113], 'hold': [114], 'there': [117], 'are': [118], 'only': [119], 'two': [120], 'players': [121], 'symmetric.': [126], '\r\nKeywords:': [127], 'equilibrium;': [129, 145], 'theory;': [131, 136], 'computational': [132], 'complexity;': [133], 'noncooperative': [134], 'normal': [137], 'form': [138], 'game;': [139, 141, 143], 'Markov': [142], 'multiagent': [146], 'systems.': [147]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2952209068', 'counts_by_year': [{'year': 2019, 'cited_by_count': 1}], 'updated_date': '2024-12-12T10:15:47.276538', 'created_date': '2019-06-27'}