A Note on Approximate Nash Equilibria View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Constantinos Daskalakis , Aranyak Mehta , Christos Papadimitriou

ABSTRACT

In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [LMM03], and no approximation better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1\over 4$\end{document} is possible by any algorithm that examines equilibria involving fewer than logn strategies [Alt94]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1\over 2$\end{document}-approximate Nash equilibrium in any 2-player game. For the more demanding notion of well-supported approximate equilibrium due to [DGP06] no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0–1), and that an approximation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$5\over 6$\end{document} is possible contingent upon a graph-theoretic conjecture. More... »

PAGES

297-306

Book

TITLE

Internet and Network Economics

ISBN

978-3-540-68138-0
978-3-540-68141-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11944874_27

DOI

http://dx.doi.org/10.1007/11944874_27

DIMENSIONS

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


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": "University of California, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, Berkeley, USA"
          ], 
          "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": "IBM Almaden Research Center, San Jose, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, San Jose, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehta", 
        "givenName": "Aranyak", 
        "id": "sg:person.010106546671.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos", 
        "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": "In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [LMM03], and no approximation better than \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$1\\over 4$\\end{document} is possible by any algorithm that examines equilibria involving fewer than logn strategies [Alt94]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$1\\over 2$\\end{document}-approximate Nash equilibrium in any 2-player game. For the more demanding notion of well-supported approximate equilibrium due to [DGP06] no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0\u20131), and that an approximation of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$5\\over 6$\\end{document} is possible contingent upon a graph-theoretic conjecture.", 
    "editor": [
      {
        "familyName": "Spirakis", 
        "givenName": "Paul", 
        "type": "Person"
      }, 
      {
        "familyName": "Mavronicolas", 
        "givenName": "Marios", 
        "type": "Person"
      }, 
      {
        "familyName": "Kontogiannis", 
        "givenName": "Spyros", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11944874_27", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-68138-0", 
        "978-3-540-68141-0"
      ], 
      "name": "Internet and Network Economics", 
      "type": "Book"
    }, 
    "keywords": [
      "win-lose games", 
      "game", 
      "contingent", 
      "context", 
      "strategies", 
      "notion", 
      "view", 
      "players", 
      "problem", 
      "intractability", 
      "note", 
      "Nash equilibrium", 
      "algorithm", 
      "cases", 
      "conjecture", 
      "limit", 
      "scheme", 
      "equilibrium", 
      "approximation", 
      "limits of approximation", 
      "approximation scheme", 
      "linear-time algorithm", 
      "approximate equilibrium", 
      "graph-theoretic conjecture", 
      "approximate Nash equilibria", 
      "subexponential approximation scheme", 
      "logn strategies", 
      "demanding notion", 
      "possible contingent"
    ], 
    "name": "A Note on Approximate Nash Equilibria", 
    "pagination": "297-306", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016417682"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11944874_27"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11944874_27", 
      "https://app.dimensions.ai/details/publication/pub.1016417682"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_3.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11944874_27"
  }
]
 

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/11944874_27'

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/11944874_27'

Turtle is a human-readable linked data format.

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

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

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


 

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

116 TRIPLES      23 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11944874_27 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N6187dcf743c347c5a5424176ad0f63a8
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [LMM03], and no approximation better than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1\over 4$\end{document} is possible by any algorithm that examines equilibria involving fewer than logn strategies [Alt94]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1\over 2$\end{document}-approximate Nash equilibrium in any 2-player game. For the more demanding notion of well-supported approximate equilibrium due to [DGP06] no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0–1), and that an approximation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$5\over 6$\end{document} is possible contingent upon a graph-theoretic conjecture.
7 schema:editor N118ba0dca6e942c193c8f7b5ad404e62
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N20d66bc34342418d895bc79a1a849534
12 schema:keywords Nash equilibrium
13 algorithm
14 approximate Nash equilibria
15 approximate equilibrium
16 approximation
17 approximation scheme
18 cases
19 conjecture
20 context
21 contingent
22 demanding notion
23 equilibrium
24 game
25 graph-theoretic conjecture
26 intractability
27 limit
28 limits of approximation
29 linear-time algorithm
30 logn strategies
31 note
32 notion
33 players
34 possible contingent
35 problem
36 scheme
37 strategies
38 subexponential approximation scheme
39 view
40 win-lose games
41 schema:name A Note on Approximate Nash Equilibria
42 schema:pagination 297-306
43 schema:productId N63b6c34fe6ce4478823ed79fdb4a39c6
44 Nd130856a7a4e4d17bb0187c7974771c2
45 schema:publisher N6d23e77da5704665b2daa75799534e78
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016417682
47 https://doi.org/10.1007/11944874_27
48 schema:sdDatePublished 2022-01-01T19:17
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Ne5cdbc5ffe96419da3b32578256bbd55
51 schema:url https://doi.org/10.1007/11944874_27
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N06d9b518db104b84b47187aefbd4065e rdf:first sg:person.010106546671.08
56 rdf:rest N3600e5098b0d481bbc02dbb206fa96dc
57 N118ba0dca6e942c193c8f7b5ad404e62 rdf:first N3fc6daea183e4e67ad96bc627408f104
58 rdf:rest Nee3c5268b75c41e0832cc8ba18def468
59 N20d66bc34342418d895bc79a1a849534 schema:isbn 978-3-540-68138-0
60 978-3-540-68141-0
61 schema:name Internet and Network Economics
62 rdf:type schema:Book
63 N3600e5098b0d481bbc02dbb206fa96dc rdf:first sg:person.013233165465.63
64 rdf:rest rdf:nil
65 N3fc6daea183e4e67ad96bc627408f104 schema:familyName Spirakis
66 schema:givenName Paul
67 rdf:type schema:Person
68 N610ac237287b4e0ba56406a07d498782 schema:familyName Kontogiannis
69 schema:givenName Spyros
70 rdf:type schema:Person
71 N6187dcf743c347c5a5424176ad0f63a8 rdf:first sg:person.0621125744.74
72 rdf:rest N06d9b518db104b84b47187aefbd4065e
73 N63b6c34fe6ce4478823ed79fdb4a39c6 schema:name dimensions_id
74 schema:value pub.1016417682
75 rdf:type schema:PropertyValue
76 N6d23e77da5704665b2daa75799534e78 schema:name Springer Nature
77 rdf:type schema:Organisation
78 N7c9081f1d57e43b08d97eb7314904928 rdf:first N610ac237287b4e0ba56406a07d498782
79 rdf:rest rdf:nil
80 N9cf51a0ee3b8428da3991a2532b52b36 schema:familyName Mavronicolas
81 schema:givenName Marios
82 rdf:type schema:Person
83 Nd130856a7a4e4d17bb0187c7974771c2 schema:name doi
84 schema:value 10.1007/11944874_27
85 rdf:type schema:PropertyValue
86 Ne5cdbc5ffe96419da3b32578256bbd55 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Nee3c5268b75c41e0832cc8ba18def468 rdf:first N9cf51a0ee3b8428da3991a2532b52b36
89 rdf:rest N7c9081f1d57e43b08d97eb7314904928
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.010106546671.08 schema:affiliation grid-institutes:grid.481551.c
97 schema:familyName Mehta
98 schema:givenName Aranyak
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08
100 rdf:type schema:Person
101 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
102 schema:familyName Papadimitriou
103 schema:givenName Christos
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
105 rdf:type schema:Person
106 sg:person.0621125744.74 schema:affiliation grid-institutes:grid.47840.3f
107 schema:familyName Daskalakis
108 schema:givenName Constantinos
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621125744.74
110 rdf:type schema:Person
111 grid-institutes:grid.47840.3f schema:alternateName University of California, Berkeley, USA
112 schema:name University of California, Berkeley, USA
113 rdf:type schema:Organization
114 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, San Jose, USA
115 schema:name IBM Almaden Research Center, San Jose, USA
116 rdf:type schema:Organization
 




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


...