Publication Information

{'id': 'https://openalex.org/W1807884544', 'doi': 'https://doi.org/10.48550/arxiv.cs/0205074', 'title': 'Complexity Results about Nash Equilibria', 'display_name': 'Complexity Results about Nash Equilibria', 'publication_year': 2002, 'publication_date': '2002-01-01', 'ids': {'openalex': 'https://openalex.org/W1807884544', 'doi': 'https://doi.org/10.48550/arxiv.cs/0205074', 'mag': '1807884544'}, 'language': 'en', 'primary_location': {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/cs/0205074', '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': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'preprint', 'type_crossref': 'journal-article', 'indexed_in': ['datacite'], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'https://arxiv.org/abs/cs/0205074', 'any_repository_has_fulltext': True}, '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'], 'affiliations': [{'raw_affiliation_string': 'Carnegie-Mellon University, Computer Science Department, Pittsburgh, PA', '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': 'Tüomas Sandholm', 'raw_affiliation_strings': ['Carnegie-Mellon University, Computer Science Department, Pittsburgh, PA'], 'affiliations': [{'raw_affiliation_string': 'Carnegie-Mellon University, Computer Science Department, Pittsburgh, PA', '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': 232, 'citation_normalized_percentile': {'value': 0.989346, 'is_in_top_1_percent': False, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 98, 'max': 99}, '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.9989, '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.9917, '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': [], 'concepts': [{'id': 'https://openalex.org/C46814582', 'wikidata': 'https://www.wikidata.org/wiki/Q23389', 'display_name': 'Nash equilibrium', 'level': 2, 'score': 0.53214353}, {'id': 'https://openalex.org/C144237770', 'wikidata': 'https://www.wikidata.org/wiki/Q747534', 'display_name': 'Mathematical economics', 'level': 1, 'score': 0.45784113}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.35388708}, {'id': 'https://openalex.org/C162324750', 'wikidata': 'https://www.wikidata.org/wiki/Q8134', 'display_name': 'Economics', 'level': 0, 'score': 0.30072093}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/cs/0205074', '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': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://api.datacite.org/dois/10.48550/arxiv.cs/0205074', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4393179698', 'display_name': 'DataCite API', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I4210145204', 'host_organization_name': 'DataCite', 'host_organization_lineage': ['https://openalex.org/I4210145204'], 'host_organization_lineage_names': ['DataCite'], 'type': 'metadata'}, 'license': None, 'license_id': None, 'version': None}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/cs/0205074', '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': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': None, 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 64, 'referenced_works': ['https://openalex.org/W1483936539', 'https://openalex.org/W1540579334', 'https://openalex.org/W1549469597', 'https://openalex.org/W1578694843', 'https://openalex.org/W1605726653', 'https://openalex.org/W1619246471', 'https://openalex.org/W1680574711', 'https://openalex.org/W1800198041', 'https://openalex.org/W1825000749', 'https://openalex.org/W1826494558', 'https://openalex.org/W1972357512', 'https://openalex.org/W1974597184', 'https://openalex.org/W1976179404', 'https://openalex.org/W1978545668', 'https://openalex.org/W1981698216', 'https://openalex.org/W1989538212', 'https://openalex.org/W1995892667', 'https://openalex.org/W1998084650', 'https://openalex.org/W1998754086', 'https://openalex.org/W2002481951', 'https://openalex.org/W2003296459', 'https://openalex.org/W2006069523', 'https://openalex.org/W2006912660', 'https://openalex.org/W2008519844', 'https://openalex.org/W2009035217', 'https://openalex.org/W2012634103', 'https://openalex.org/W2013327987', 'https://openalex.org/W2013372570', 'https://openalex.org/W2013469527', 'https://openalex.org/W20228571', 'https://openalex.org/W2023373582', 'https://openalex.org/W2032100464', 'https://openalex.org/W2033040247', 'https://openalex.org/W2036265926', 'https://openalex.org/W2039634593', 'https://openalex.org/W2044155094', 'https://openalex.org/W2047880045', 'https://openalex.org/W2049538756', 'https://openalex.org/W2054951214', 'https://openalex.org/W2067050450', 'https://openalex.org/W2073048734', 'https://openalex.org/W2083680012', 'https://openalex.org/W2086386133', 'https://openalex.org/W2087974695', 'https://openalex.org/W2089649903', 'https://openalex.org/W2092183701', 'https://openalex.org/W2113147495', 'https://openalex.org/W2121180068', 'https://openalex.org/W2125537511', 'https://openalex.org/W2129639820', 'https://openalex.org/W2131724520', 'https://openalex.org/W2131967794', 'https://openalex.org/W2134628753', 'https://openalex.org/W2134729426', 'https://openalex.org/W2136427775', 'https://openalex.org/W2156827107', 'https://openalex.org/W2157377553', 'https://openalex.org/W2160135758', 'https://openalex.org/W2160461879', 'https://openalex.org/W2292587149', 'https://openalex.org/W2493238591', 'https://openalex.org/W2575731723', 'https://openalex.org/W2912008780', 'https://openalex.org/W3123286829'], 'related_works': ['https://openalex.org/W4391375266', 'https://openalex.org/W4389370903', 'https://openalex.org/W4302558842', 'https://openalex.org/W2803931294', 'https://openalex.org/W2500870930', 'https://openalex.org/W2468739564', 'https://openalex.org/W2282604764', 'https://openalex.org/W2218535193', 'https://openalex.org/W2171981925', 'https://openalex.org/W1554758635'], '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], 'Keywords:': [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:W1807884544', 'counts_by_year': [{'year': 2023, 'cited_by_count': 2}, {'year': 2022, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 7}, {'year': 2020, 'cited_by_count': 7}, {'year': 2019, 'cited_by_count': 4}, {'year': 2018, 'cited_by_count': 3}, {'year': 2017, 'cited_by_count': 1}, {'year': 2016, 'cited_by_count': 3}, {'year': 2015, 'cited_by_count': 5}, {'year': 2014, 'cited_by_count': 10}, {'year': 2013, 'cited_by_count': 4}, {'year': 2012, 'cited_by_count': 11}], 'updated_date': '2024-12-06T02:51:47.757298', 'created_date': '2016-06-24'}