Publication Information

{'id': 'https://openalex.org/W2145297839', 'doi': 'https://doi.org/10.1145/1007352.1007445', 'title': 'The complexity of pure Nash equilibria', 'display_name': 'The complexity of pure Nash equilibria', 'publication_year': 2004, 'publication_date': '2004-06-13', 'ids': {'openalex': 'https://openalex.org/W2145297839', 'doi': 'https://doi.org/10.1145/1007352.1007445', 'mag': '2145297839'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/1007352.1007445', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': ['crossref'], '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/A5035688187', 'display_name': 'Alex Fabrikant', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I134446601', 'display_name': 'Berkeley College', 'ror': 'https://ror.org/02xewxa75', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I134446601']}, {'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': 'Alex Fabrikant', 'raw_affiliation_strings': ['UC, Berkeley, CA'], 'affiliations': [{'raw_affiliation_string': 'UC, Berkeley, CA', 'institution_ids': ['https://openalex.org/I134446601', 'https://openalex.org/I95457486']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5103200572', 'display_name': 'Christos H. Papadimitriou', 'orcid': 'https://orcid.org/0009-0000-7264-8015'}, 'institutions': [{'id': 'https://openalex.org/I134446601', 'display_name': 'Berkeley College', 'ror': 'https://ror.org/02xewxa75', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I134446601']}, {'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 Papadimitriou', 'raw_affiliation_strings': ['UC, Berkeley, CA'], 'affiliations': [{'raw_affiliation_string': 'UC, Berkeley, CA', 'institution_ids': ['https://openalex.org/I134446601', 'https://openalex.org/I95457486']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5080065269', 'display_name': 'Kunal Talwar', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I134446601', 'display_name': 'Berkeley College', 'ror': 'https://ror.org/02xewxa75', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I134446601']}, {'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': 'Kunal Talwar', 'raw_affiliation_strings': ['UC, Berkeley, CA'], 'affiliations': [{'raw_affiliation_string': 'UC, Berkeley, CA', 'institution_ids': ['https://openalex.org/I134446601', 'https://openalex.org/I95457486']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 2, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 30.159, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 679, 'citation_normalized_percentile': {'value': 0.998424, 'is_in_top_1_percent': True, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 99, 'max': 100}, 'biblio': {'volume': None, 'issue': None, 'first_page': '604', 'last_page': '612'}, '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/T12592', 'display_name': 'Opinion Dynamics and Social Influence', 'score': 0.9867, 'subfield': {'id': 'https://openalex.org/subfields/3109', 'display_name': 'Statistical and Nonlinear Physics'}, 'field': {'id': 'https://openalex.org/fields/31', 'display_name': 'Physics and Astronomy'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10064', 'display_name': 'Complex Network Analysis Techniques', 'score': 0.9838, 'subfield': {'id': 'https://openalex.org/subfields/3109', 'display_name': 'Statistical and Nonlinear Physics'}, 'field': {'id': 'https://openalex.org/fields/31', 'display_name': 'Physics and Astronomy'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/scope', 'display_name': 'Scope (computer science)', 'score': 0.53240687}, {'id': 'https://openalex.org/keywords/risk-dominance', 'display_name': 'Risk dominance', 'score': 0.4870072}, {'id': 'https://openalex.org/keywords/symmetric-equilibrium', 'display_name': 'Symmetric equilibrium', 'score': 0.43002346}], 'concepts': [{'id': 'https://openalex.org/C46814582', 'wikidata': 'https://www.wikidata.org/wiki/Q23389', 'display_name': 'Nash equilibrium', 'level': 2, 'score': 0.89767885}, {'id': 'https://openalex.org/C32407928', 'wikidata': 'https://www.wikidata.org/wiki/Q2733833', 'display_name': 'Best response', 'level': 3, 'score': 0.6920661}, {'id': 'https://openalex.org/C141824439', 'wikidata': 'https://www.wikidata.org/wiki/Q307521', 'display_name': 'Epsilon-equilibrium', 'level': 4, 'score': 0.621599}, {'id': 'https://openalex.org/C144237770', 'wikidata': 'https://www.wikidata.org/wiki/Q747534', 'display_name': 'Mathematical economics', 'level': 1, 'score': 0.5849539}, {'id': 'https://openalex.org/C192209626', 'wikidata': 'https://www.wikidata.org/wiki/Q190909', 'display_name': 'Focus (optics)', 'level': 2, 'score': 0.54994655}, {'id': 'https://openalex.org/C2778012447', 'wikidata': 'https://www.wikidata.org/wiki/Q1034415', 'display_name': 'Scope (computer science)', 'level': 2, 'score': 0.53240687}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.5249229}, {'id': 'https://openalex.org/C22349654', 'wikidata': 'https://www.wikidata.org/wiki/Q2039354', 'display_name': 'Risk dominance', 'level': 5, 'score': 0.4870072}, {'id': 'https://openalex.org/C14036430', 'wikidata': 'https://www.wikidata.org/wiki/Q3736076', 'display_name': 'Function (biology)', 'level': 2, 'score': 0.46094}, {'id': 'https://openalex.org/C126255220', 'wikidata': 'https://www.wikidata.org/wiki/Q141495', 'display_name': 'Mathematical optimization', 'level': 1, 'score': 0.45233747}, {'id': 'https://openalex.org/C93979843', 'wikidata': 'https://www.wikidata.org/wiki/Q7661306', 'display_name': 'Symmetric equilibrium', 'level': 5, 'score': 0.43002346}, {'id': 'https://openalex.org/C177142836', 'wikidata': 'https://www.wikidata.org/wiki/Q44455', 'display_name': 'Game theory', 'level': 2, 'score': 0.4223634}, {'id': 'https://openalex.org/C164407509', 'wikidata': 'https://www.wikidata.org/wiki/Q5384490', 'display_name': 'Equilibrium selection', 'level': 4, 'score': 0.39966565}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.33466208}, {'id': 'https://openalex.org/C202556891', 'wikidata': 'https://www.wikidata.org/wiki/Q1584646', 'display_name': 'Repeated game', 'level': 3, 'score': 0.17657396}, {'id': 'https://openalex.org/C121332964', 'wikidata': 'https://www.wikidata.org/wiki/Q413', 'display_name': 'Physics', 'level': 0, 'score': 0.054562867}, {'id': 'https://openalex.org/C78458016', 'wikidata': 'https://www.wikidata.org/wiki/Q840400', 'display_name': 'Evolutionary biology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C120665830', 'wikidata': 'https://www.wikidata.org/wiki/Q14620', 'display_name': 'Optics', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C86803240', 'wikidata': 'https://www.wikidata.org/wiki/Q420', 'display_name': 'Biology', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/1007352.1007445', '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': [{'score': 0.4, 'id': 'https://metadata.un.org/sdg/10', 'display_name': 'Reduced inequalities'}], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 26, 'referenced_works': ['https://openalex.org/W1753330597', 'https://openalex.org/W1807884544', 'https://openalex.org/W1957147520', 'https://openalex.org/W2006122291', 'https://openalex.org/W2027725119', 'https://openalex.org/W2031636249', 'https://openalex.org/W2046715803', 'https://openalex.org/W2047820376', 'https://openalex.org/W2054129049', 'https://openalex.org/W2061872629', 'https://openalex.org/W2062459871', 'https://openalex.org/W2066883826', 'https://openalex.org/W2067050450', 'https://openalex.org/W2077787105', 'https://openalex.org/W2102736491', 'https://openalex.org/W2103981148', 'https://openalex.org/W2112269231', 'https://openalex.org/W2121956325', 'https://openalex.org/W2131967794', 'https://openalex.org/W2159759087', 'https://openalex.org/W2165956524', 'https://openalex.org/W2169359757', 'https://openalex.org/W2328039855', 'https://openalex.org/W2797415156', 'https://openalex.org/W3022321359', 'https://openalex.org/W3123286829'], 'related_works': ['https://openalex.org/W4301347782', 'https://openalex.org/W4299551322', 'https://openalex.org/W4221157020', 'https://openalex.org/W3125812435', 'https://openalex.org/W2025767136', 'https://openalex.org/W2013767790', 'https://openalex.org/W1853631319', 'https://openalex.org/W1667857601', 'https://openalex.org/W157961742', 'https://openalex.org/W1554758635'], 'abstract_inverted_index': {'We': [0, 16, 46], 'investigate': [1], 'from': [2], 'the': [3, 35, 40, 56, 59], 'computational': [4], 'viewpoint': [5], 'multi-player': [6], 'games': [7], 'that': [8, 23], 'are': [9], 'guaranteed': [10], 'to': [11, 49], 'have': [12], 'pure': [13, 25, 67], 'Nash': [14, 26, 68], 'equilibria.': [15, 69], 'focus': [17], 'on': [18], 'congestion': [19, 51], 'games,': [20, 52], 'and': [21, 53], 'show': [22], 'a': [24], 'equilibrium': [27], 'can': [28], 'be': [29], 'computed': [30], 'in': [31, 34, 44], 'polynomial': [32], 'time': [33], 'symmetric': [36], 'network': [37], 'case,': [38], 'while': [39], 'problem': [41], 'is': [42], 'PLS-complete': [43], 'general.': [45], 'discuss': [47], 'implications': [48], 'non-atomic': [50], 'we': [54], 'explore': [55], 'scope': [57], 'of': [58, 66], 'potential': [60], 'function': [61], 'method': [62], 'for': [63], 'proving': [64], 'existence': [65]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2145297839', 'counts_by_year': [{'year': 2024, 'cited_by_count': 9}, {'year': 2023, 'cited_by_count': 14}, {'year': 2022, 'cited_by_count': 12}, {'year': 2021, 'cited_by_count': 23}, {'year': 2020, 'cited_by_count': 24}, {'year': 2019, 'cited_by_count': 29}, {'year': 2018, 'cited_by_count': 37}, {'year': 2017, 'cited_by_count': 23}, {'year': 2016, 'cited_by_count': 31}, {'year': 2015, 'cited_by_count': 26}, {'year': 2014, 'cited_by_count': 44}, {'year': 2013, 'cited_by_count': 24}, {'year': 2012, 'cited_by_count': 50}], 'updated_date': '2024-12-10T23:30:44.160936', 'created_date': '2016-06-24'}