The Complexity of Games on Highly Regular Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Konstantinos Daskalakis , Christos H. Papadimitriou

ABSTRACT

We present algorithms and complexity results for the problem of finding equilibria (mixed Nash equilibria, pure Nash equilibria and correlated equilibria) in games with extremely succinct description that are defined on highly regular graphs such as the d-dimensional grid; we argue that such games are of interest in the modelling of large systems of interacting agents. We show that mixed Nash equilibria can be found in time exponential in the succinct representation by quantifier elimination, while correlated equilibria can be found in polynomial time by taking advantage of the game’s symmetries. Finally, the complexity of determining whether such a game on the d-dimensional grid has a pure Nash equilibrium depends on d and the dichotomy is remarkably sharp: it is solvable in polynomial time (in fact NL-complete) when d = 1, but it is NEXP-complete for d ≥ 2. More... »

PAGES

71-82

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11561071_9

DOI

http://dx.doi.org/10.1007/11561071_9

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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, Soda Hall, 94720, Berkeley, CA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, UC Berkeley, Soda Hall, 94720, Berkeley, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Daskalakis", 
        "givenName": "Konstantinos", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, UC Berkeley, Soda Hall, 94720, Berkeley, CA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, UC Berkeley, Soda Hall, 94720, Berkeley, CA"
          ], 
          "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": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We present algorithms and complexity results for the problem of finding equilibria (mixed Nash equilibria, pure Nash equilibria and correlated equilibria) in games with extremely succinct description that are defined on highly regular graphs such as the d-dimensional grid; we argue that such games are of interest in the modelling of large systems of interacting agents. We show that mixed Nash equilibria can be found in time exponential in the succinct representation by quantifier elimination, while correlated equilibria can be found in polynomial time by taking advantage of the game\u2019s symmetries. Finally, the complexity of determining whether such a game on the d-dimensional grid has a pure Nash equilibrium depends on d and the dichotomy is remarkably sharp: it is solvable in polynomial time (in fact NL-complete) when d = 1, but it is NEXP-complete for d \u2265 2.", 
    "editor": [
      {
        "familyName": "Brodal", 
        "givenName": "Gerth St\u00f8lting", 
        "type": "Person"
      }, 
      {
        "familyName": "Leonardi", 
        "givenName": "Stefano", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11561071_9", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29118-3", 
        "978-3-540-31951-1"
      ], 
      "name": "Algorithms \u2013 ESA 2005", 
      "type": "Book"
    }, 
    "keywords": [
      "polynomial time", 
      "complexity of games", 
      "dimensional grid", 
      "Nash equilibrium", 
      "pure Nash equilibria", 
      "complexity results", 
      "succinct representation", 
      "correlated equilibrium", 
      "mixed Nash equilibrium", 
      "such games", 
      "large systems", 
      "quantifier elimination", 
      "game symmetry", 
      "game", 
      "graph", 
      "complexity", 
      "succinct description", 
      "grid", 
      "regular graphs", 
      "algorithm", 
      "NEXP", 
      "representation", 
      "system", 
      "advantages", 
      "time", 
      "modelling", 
      "description", 
      "interest", 
      "results", 
      "agents", 
      "symmetry", 
      "equilibrium", 
      "problem", 
      "elimination", 
      "dichotomy", 
      "Highly Regular Graphs"
    ], 
    "name": "The Complexity of Games on Highly Regular Graphs", 
    "pagination": "71-82", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037491442"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11561071_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11561071_9", 
      "https://app.dimensions.ai/details/publication/pub.1037491442"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:56", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_132.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11561071_9"
  }
]
 

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/11561071_9'

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/11561071_9'

Turtle is a human-readable linked data format.

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

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

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


 

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

111 TRIPLES      23 PREDICATES      63 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11561071_9 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0802
4 schema:author Na8acebb7fda145eb809ce3e01aad45fd
5 schema:datePublished 2005
6 schema:datePublishedReg 2005-01-01
7 schema:description We present algorithms and complexity results for the problem of finding equilibria (mixed Nash equilibria, pure Nash equilibria and correlated equilibria) in games with extremely succinct description that are defined on highly regular graphs such as the d-dimensional grid; we argue that such games are of interest in the modelling of large systems of interacting agents. We show that mixed Nash equilibria can be found in time exponential in the succinct representation by quantifier elimination, while correlated equilibria can be found in polynomial time by taking advantage of the game’s symmetries. Finally, the complexity of determining whether such a game on the d-dimensional grid has a pure Nash equilibrium depends on d and the dichotomy is remarkably sharp: it is solvable in polynomial time (in fact NL-complete) when d = 1, but it is NEXP-complete for d ≥ 2.
8 schema:editor Na127f376047e4c3a8830f928491058d8
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf Na9690517ef754944844c5058069c9913
13 schema:keywords Highly Regular Graphs
14 NEXP
15 Nash equilibrium
16 advantages
17 agents
18 algorithm
19 complexity
20 complexity of games
21 complexity results
22 correlated equilibrium
23 description
24 dichotomy
25 dimensional grid
26 elimination
27 equilibrium
28 game
29 game symmetry
30 graph
31 grid
32 interest
33 large systems
34 mixed Nash equilibrium
35 modelling
36 polynomial time
37 problem
38 pure Nash equilibria
39 quantifier elimination
40 regular graphs
41 representation
42 results
43 succinct description
44 succinct representation
45 such games
46 symmetry
47 system
48 time
49 schema:name The Complexity of Games on Highly Regular Graphs
50 schema:pagination 71-82
51 schema:productId N4080c392297b4393b3dbd3fe38d897a3
52 Nde4d44f9a1c74af1aa40bd5269b8eb5e
53 schema:publisher N89d3b13e99a2421d8cdec53dfa257fdf
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037491442
55 https://doi.org/10.1007/11561071_9
56 schema:sdDatePublished 2021-12-01T19:56
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N07f9f0ca996445ff88f22ef5e163e5ad
59 schema:url https://doi.org/10.1007/11561071_9
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N07f9f0ca996445ff88f22ef5e163e5ad schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 N31d039a7f6d84452bdaf49b671af1ceb rdf:first Na09f52db89bc471c898b2d2b08e6d8fb
66 rdf:rest rdf:nil
67 N4080c392297b4393b3dbd3fe38d897a3 schema:name dimensions_id
68 schema:value pub.1037491442
69 rdf:type schema:PropertyValue
70 N7b40f4e66e15492c995d6d06b6440caa schema:familyName Brodal
71 schema:givenName Gerth Stølting
72 rdf:type schema:Person
73 N89d3b13e99a2421d8cdec53dfa257fdf schema:name Springer Nature
74 rdf:type schema:Organisation
75 Na09f52db89bc471c898b2d2b08e6d8fb schema:familyName Leonardi
76 schema:givenName Stefano
77 rdf:type schema:Person
78 Na127f376047e4c3a8830f928491058d8 rdf:first N7b40f4e66e15492c995d6d06b6440caa
79 rdf:rest N31d039a7f6d84452bdaf49b671af1ceb
80 Na8acebb7fda145eb809ce3e01aad45fd rdf:first Nc7b9d779db884b3f9571058d9dbfcab6
81 rdf:rest Naff222a554d743baac58e541a385e15b
82 Na9690517ef754944844c5058069c9913 schema:isbn 978-3-540-29118-3
83 978-3-540-31951-1
84 schema:name Algorithms – ESA 2005
85 rdf:type schema:Book
86 Naff222a554d743baac58e541a385e15b rdf:first sg:person.013233165465.63
87 rdf:rest rdf:nil
88 Nc7b9d779db884b3f9571058d9dbfcab6 schema:affiliation grid-institutes:grid.47840.3f
89 schema:familyName Daskalakis
90 schema:givenName Konstantinos
91 rdf:type schema:Person
92 Nde4d44f9a1c74af1aa40bd5269b8eb5e schema:name doi
93 schema:value 10.1007/11561071_9
94 rdf:type schema:PropertyValue
95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
96 schema:name Information and Computing Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
99 schema:name Artificial Intelligence and Image Processing
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
102 schema:name Computation Theory and Mathematics
103 rdf:type schema:DefinedTerm
104 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
105 schema:familyName Papadimitriou
106 schema:givenName Christos H.
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
108 rdf:type schema:Person
109 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, UC Berkeley, Soda Hall, 94720, Berkeley, CA
110 schema:name Computer Science Division, UC Berkeley, Soda Hall, 94720, Berkeley, CA
111 rdf:type schema:Organization
 




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


...