The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Constantinos Daskalakis , Alex Fabrikant , Christos H. Papadimitriou

ABSTRACT

A recent sequence of results established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players [11,6,4]. By extending these techniques we prove a general theorem, showing that, for a far more general class of families of succinctly representable multiplayer games, the Nash equilibrium problem can also be reduced to the two-player case. In view of empirically successful algorithms available for this problem, this is in essence a positive result — even though, due to the complexity of the reductions, it is of no immediate practical significance. We further extend this conclusion to extensive form games and network congestion games, two classes which do not fall into the same succinct representation framework, and for which no positive algorithmic result had been known. More... »

PAGES

513-524

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-35904-3
978-3-540-35905-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11786986_45

DOI

http://dx.doi.org/10.1007/11786986_45

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1019935315


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Division, UC Berkeley", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Computer Science Division, UC Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Daskalakis", 
        "givenName": "Constantinos", 
        "id": "sg:person.0621125744.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621125744.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, UC Berkeley", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Computer Science Division, UC Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fabrikant", 
        "givenName": "Alex", 
        "id": "sg:person.07731456073.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731456073.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, UC Berkeley", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Computer Science Division, UC Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "A recent sequence of results established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players [11,6,4]. By extending these techniques we prove a general theorem, showing that, for a far more general class of families of succinctly representable multiplayer games, the Nash equilibrium problem can also be reduced to the two-player case. In view of empirically successful algorithms available for this problem, this is in essence a positive result \u2014 even though, due to the complexity of the reductions, it is of no immediate practical significance. We further extend this conclusion to extensive form games and network congestion games, two classes which do not fall into the same succinct representation framework, and for which no positive algorithmic result had been known.", 
    "editor": [
      {
        "familyName": "Bugliesi", 
        "givenName": "Michele", 
        "type": "Person"
      }, 
      {
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "type": "Person"
      }, 
      {
        "familyName": "Sassone", 
        "givenName": "Vladimiro", 
        "type": "Person"
      }, 
      {
        "familyName": "Wegener", 
        "givenName": "Ingo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11786986_45", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-35904-3", 
        "978-3-540-35905-0"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "network congestion games", 
      "PPAD-complete problem", 
      "positive algorithmic results", 
      "succinct games", 
      "Nash equilibrium", 
      "successful algorithms", 
      "multiplayer games", 
      "representation framework", 
      "algorithmic results", 
      "game world", 
      "form games", 
      "congestion games", 
      "extensive form games", 
      "immediate practical significance", 
      "game", 
      "normal form games", 
      "complexity", 
      "Nash equilibrium problem", 
      "two-player case", 
      "algorithm", 
      "practical significance", 
      "recent sequence", 
      "general class", 
      "framework", 
      "class", 
      "technique", 
      "equilibrium problems", 
      "results", 
      "players", 
      "essence", 
      "view", 
      "world", 
      "sequence", 
      "theorem", 
      "cases", 
      "general theorem", 
      "positive results", 
      "reduction", 
      "equilibrium", 
      "significance", 
      "family", 
      "conclusion", 
      "problem", 
      "representable multiplayer games", 
      "same succinct representation framework", 
      "succinct representation framework"
    ], 
    "name": "The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games", 
    "pagination": "513-524", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019935315"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11786986_45"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11786986_45", 
      "https://app.dimensions.ai/details/publication/pub.1019935315"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_125.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11786986_45"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11786986_45'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11786986_45'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11786986_45'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11786986_45'


 

This table displays all metadata directly associated to this object as RDF triples.

135 TRIPLES      23 PREDICATES      72 URIs      65 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11786986_45 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N27474cd270a84a22a8b1c797eb151777
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description A recent sequence of results established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players [11,6,4]. By extending these techniques we prove a general theorem, showing that, for a far more general class of families of succinctly representable multiplayer games, the Nash equilibrium problem can also be reduced to the two-player case. In view of empirically successful algorithms available for this problem, this is in essence a positive result — even though, due to the complexity of the reductions, it is of no immediate practical significance. We further extend this conclusion to extensive form games and network congestion games, two classes which do not fall into the same succinct representation framework, and for which no positive algorithmic result had been known.
7 schema:editor Nc4e0cc391a924f09b8aae62adbe2803e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N14d8686565ff49e9b0760f372bf36fd9
12 schema:keywords Nash equilibrium
13 Nash equilibrium problem
14 PPAD-complete problem
15 algorithm
16 algorithmic results
17 cases
18 class
19 complexity
20 conclusion
21 congestion games
22 equilibrium
23 equilibrium problems
24 essence
25 extensive form games
26 family
27 form games
28 framework
29 game
30 game world
31 general class
32 general theorem
33 immediate practical significance
34 multiplayer games
35 network congestion games
36 normal form games
37 players
38 positive algorithmic results
39 positive results
40 practical significance
41 problem
42 recent sequence
43 reduction
44 representable multiplayer games
45 representation framework
46 results
47 same succinct representation framework
48 sequence
49 significance
50 successful algorithms
51 succinct games
52 succinct representation framework
53 technique
54 theorem
55 two-player case
56 view
57 world
58 schema:name The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
59 schema:pagination 513-524
60 schema:productId N03ad3eac295b4e6fa68a0a80a8fd0955
61 N1eed4bc17f05454499370b4d56570bed
62 schema:publisher Nd0608ff9e80c447abbeadbbc414a9fa7
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019935315
64 https://doi.org/10.1007/11786986_45
65 schema:sdDatePublished 2021-11-01T18:46
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher Nb848495916fd4ec2a1349cc44fd81cd6
68 schema:url https://doi.org/10.1007/11786986_45
69 sgo:license sg:explorer/license/
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N03ad3eac295b4e6fa68a0a80a8fd0955 schema:name doi
73 schema:value 10.1007/11786986_45
74 rdf:type schema:PropertyValue
75 N14d8686565ff49e9b0760f372bf36fd9 schema:isbn 978-3-540-35904-3
76 978-3-540-35905-0
77 schema:name Automata, Languages and Programming
78 rdf:type schema:Book
79 N1b5e7a0ddbb647fd997f79a351e8e259 rdf:first Ne478ffd51ffc4573bb27577003b67834
80 rdf:rest N483853a456c5427096ea4150de7e912a
81 N1eed4bc17f05454499370b4d56570bed schema:name dimensions_id
82 schema:value pub.1019935315
83 rdf:type schema:PropertyValue
84 N27474cd270a84a22a8b1c797eb151777 rdf:first sg:person.0621125744.74
85 rdf:rest Na51383336c044e05a3506b97a2dd1901
86 N2f2904fde2f34357936258ae5154b613 schema:familyName Sassone
87 schema:givenName Vladimiro
88 rdf:type schema:Person
89 N483853a456c5427096ea4150de7e912a rdf:first N2f2904fde2f34357936258ae5154b613
90 rdf:rest Ndf15ede00c6440aaaadde0c8b8ab9852
91 Na51383336c044e05a3506b97a2dd1901 rdf:first sg:person.07731456073.04
92 rdf:rest Nafb44b9cd3d04c6b99bc6739fd58e6b6
93 Nab9eb4f3cc41428385e6af2f2604972e schema:familyName Wegener
94 schema:givenName Ingo
95 rdf:type schema:Person
96 Nafb44b9cd3d04c6b99bc6739fd58e6b6 rdf:first sg:person.013233165465.63
97 rdf:rest rdf:nil
98 Nb848495916fd4ec2a1349cc44fd81cd6 schema:name Springer Nature - SN SciGraph project
99 rdf:type schema:Organization
100 Nc31e0871810747a39a80490988e58df1 schema:familyName Bugliesi
101 schema:givenName Michele
102 rdf:type schema:Person
103 Nc4e0cc391a924f09b8aae62adbe2803e rdf:first Nc31e0871810747a39a80490988e58df1
104 rdf:rest N1b5e7a0ddbb647fd997f79a351e8e259
105 Nd0608ff9e80c447abbeadbbc414a9fa7 schema:name Springer Nature
106 rdf:type schema:Organisation
107 Ndf15ede00c6440aaaadde0c8b8ab9852 rdf:first Nab9eb4f3cc41428385e6af2f2604972e
108 rdf:rest rdf:nil
109 Ne478ffd51ffc4573bb27577003b67834 schema:familyName Preneel
110 schema:givenName Bart
111 rdf:type schema:Person
112 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
113 schema:name Information and Computing Sciences
114 rdf:type schema:DefinedTerm
115 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
116 schema:name Computation Theory and Mathematics
117 rdf:type schema:DefinedTerm
118 sg:person.013233165465.63 schema:affiliation grid-institutes:None
119 schema:familyName Papadimitriou
120 schema:givenName Christos H.
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
122 rdf:type schema:Person
123 sg:person.0621125744.74 schema:affiliation grid-institutes:None
124 schema:familyName Daskalakis
125 schema:givenName Constantinos
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621125744.74
127 rdf:type schema:Person
128 sg:person.07731456073.04 schema:affiliation grid-institutes:None
129 schema:familyName Fabrikant
130 schema:givenName Alex
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731456073.04
132 rdf:type schema:Person
133 grid-institutes:None schema:alternateName Computer Science Division, UC Berkeley
134 schema:name Computer Science Division, UC Berkeley
135 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...