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": "2021-12-01T19:55", 
    "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_117.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 Nee7e9404528b4d50aeaf16c0684bbe08
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 N2084517c8e2e412c83a1b5073850a084
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nf5dd77cdbb7b48dca981aa8cb2260a11
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 N167822ab5eb743c685a3101cca8d0bca
44 Nb47e332a95be461880d79b33986343a2
45 schema:publisher Na618a1522cbd4f9bbce4d1d261ae79c2
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016417682
47 https://doi.org/10.1007/11944874_27
48 schema:sdDatePublished 2021-12-01T19:55
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher N39cbbc87a2894e00a580e112957be728
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 N0eca9c7c308143cb815537910b83fd88 schema:familyName Spirakis
56 schema:givenName Paul
57 rdf:type schema:Person
58 N167822ab5eb743c685a3101cca8d0bca schema:name doi
59 schema:value 10.1007/11944874_27
60 rdf:type schema:PropertyValue
61 N2084517c8e2e412c83a1b5073850a084 rdf:first N0eca9c7c308143cb815537910b83fd88
62 rdf:rest N387bee26911e4c7d816fd6c8e4258dcb
63 N387bee26911e4c7d816fd6c8e4258dcb rdf:first N4ffa45a8ef3a43f49fcb19fd70428f07
64 rdf:rest N4586d5d1e7a747f0b9f02bbc9c2a9474
65 N39cbbc87a2894e00a580e112957be728 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N4586d5d1e7a747f0b9f02bbc9c2a9474 rdf:first N617f979cc338465f9ceff9e6e14645c7
68 rdf:rest rdf:nil
69 N4ffa45a8ef3a43f49fcb19fd70428f07 schema:familyName Mavronicolas
70 schema:givenName Marios
71 rdf:type schema:Person
72 N617f979cc338465f9ceff9e6e14645c7 schema:familyName Kontogiannis
73 schema:givenName Spyros
74 rdf:type schema:Person
75 N9fdd35e0db014edd8071182bc4b70533 rdf:first sg:person.013233165465.63
76 rdf:rest rdf:nil
77 Na618a1522cbd4f9bbce4d1d261ae79c2 schema:name Springer Nature
78 rdf:type schema:Organisation
79 Nb47e332a95be461880d79b33986343a2 schema:name dimensions_id
80 schema:value pub.1016417682
81 rdf:type schema:PropertyValue
82 Nedeb83b6e77d42cbab302b241cee6107 rdf:first sg:person.010106546671.08
83 rdf:rest N9fdd35e0db014edd8071182bc4b70533
84 Nee7e9404528b4d50aeaf16c0684bbe08 rdf:first sg:person.0621125744.74
85 rdf:rest Nedeb83b6e77d42cbab302b241cee6107
86 Nf5dd77cdbb7b48dca981aa8cb2260a11 schema:isbn 978-3-540-68138-0
87 978-3-540-68141-0
88 schema:name Internet and Network Economics
89 rdf:type schema:Book
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)


...