Recent Developments in Equilibria Algorithms View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Christos Papadimitriou

ABSTRACT

Nash proved in 1951 that every game has a mixed Nash equilibrium [6]; whether such an equilibrium can be found in polynomial time has been open since that time. We review here certain recent results which shed some light to this old problem.Even though a mixed Nash equilibrium is a continuous object, the problem is essentially combinatorial, since it suffices to identify the support of a mixed strategy for each player; however, no algorithm better than exponential for doing so is known. For the case of two players we have a simplex-like pivoting algorithm due to Lemke and Howson that is guaranteed to converge to a Nash equilibrium; this algorithm has an exponential worst case [9]. But even such algorithms seem unlikely for three or more players: in his original paper Nash supplied an example of a 3-player game, an abstraction of poker, with only irrational Nash equilibria. More... »

PAGES

1-2

Book

TITLE

Internet and Network Economics

ISBN

978-3-540-30900-0
978-3-540-32293-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11600930_1

DOI

http://dx.doi.org/10.1007/11600930_1

DIMENSIONS

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


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": "Department of EECS, UC Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Department of EECS, UC 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": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Nash proved in 1951 that every game has a mixed Nash equilibrium [6]; whether such an equilibrium can be found in polynomial time has been open since that time. We review here certain recent results which shed some light to this old problem.Even though a mixed Nash equilibrium is a continuous object, the problem is essentially combinatorial, since it suffices to identify the support of a mixed strategy for each player; however, no algorithm better than exponential for doing so is known. For the case of two players we have a simplex-like pivoting algorithm due to Lemke and Howson that is guaranteed to converge to a Nash equilibrium; this algorithm has an exponential worst case [9]. But even such algorithms seem unlikely for three or more players: in his original paper Nash supplied an example of a 3-player game, an abstraction of poker, with only irrational Nash equilibria.", 
    "editor": [
      {
        "familyName": "Deng", 
        "givenName": "Xiaotie", 
        "type": "Person"
      }, 
      {
        "familyName": "Ye", 
        "givenName": "Yinyu", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11600930_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-30900-0", 
        "978-3-540-32293-1"
      ], 
      "name": "Internet and Network Economics", 
      "type": "Book"
    }, 
    "keywords": [
      "mixed Nash equilibrium", 
      "Nash equilibrium", 
      "such algorithms", 
      "continuous objects", 
      "polynomial time", 
      "algorithm", 
      "exponential worst case", 
      "equilibrium algorithm", 
      "worst case", 
      "more players", 
      "game", 
      "mixed strategies", 
      "abstraction", 
      "objects", 
      "poker", 
      "players", 
      "old problem", 
      "recent developments", 
      "time", 
      "example", 
      "support", 
      "recent results", 
      "certain recent results", 
      "strategies", 
      "results", 
      "Lemke", 
      "development", 
      "NASH", 
      "cases", 
      "equilibrium", 
      "light", 
      "problem", 
      "Howson", 
      "original paper Nash", 
      "paper Nash", 
      "abstraction of poker", 
      "irrational Nash equilibria"
    ], 
    "name": "Recent Developments in Equilibria Algorithms", 
    "pagination": "1-2", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043674621"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11600930_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11600930_1", 
      "https://app.dimensions.ai/details/publication/pub.1043674621"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:51", 
    "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_238.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11600930_1"
  }
]
 

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/11600930_1'

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/11600930_1'

Turtle is a human-readable linked data format.

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

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

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


 

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

102 TRIPLES      23 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11600930_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N56d50b904dc945deb6115035931db4d6
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description Nash proved in 1951 that every game has a mixed Nash equilibrium [6]; whether such an equilibrium can be found in polynomial time has been open since that time. We review here certain recent results which shed some light to this old problem.Even though a mixed Nash equilibrium is a continuous object, the problem is essentially combinatorial, since it suffices to identify the support of a mixed strategy for each player; however, no algorithm better than exponential for doing so is known. For the case of two players we have a simplex-like pivoting algorithm due to Lemke and Howson that is guaranteed to converge to a Nash equilibrium; this algorithm has an exponential worst case [9]. But even such algorithms seem unlikely for three or more players: in his original paper Nash supplied an example of a 3-player game, an abstraction of poker, with only irrational Nash equilibria.
7 schema:editor Nc6aaab8ed84b4fe6bdaebaeb599b351d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N7e0bc4de158d471fbcd8ef6f57271e7b
12 schema:keywords Howson
13 Lemke
14 NASH
15 Nash equilibrium
16 abstraction
17 abstraction of poker
18 algorithm
19 cases
20 certain recent results
21 continuous objects
22 development
23 equilibrium
24 equilibrium algorithm
25 example
26 exponential worst case
27 game
28 irrational Nash equilibria
29 light
30 mixed Nash equilibrium
31 mixed strategies
32 more players
33 objects
34 old problem
35 original paper Nash
36 paper Nash
37 players
38 poker
39 polynomial time
40 problem
41 recent developments
42 recent results
43 results
44 strategies
45 such algorithms
46 support
47 time
48 worst case
49 schema:name Recent Developments in Equilibria Algorithms
50 schema:pagination 1-2
51 schema:productId N133842646ba74bbbb53b5568f8f98996
52 N1b62ff1247e84938bd3b920cfb23fe32
53 schema:publisher Ned8bad60ec3549579255a3b60b20a593
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043674621
55 https://doi.org/10.1007/11600930_1
56 schema:sdDatePublished 2021-11-01T18:51
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N3eefbf78d76749ccae5ef3e8b3cd3f9d
59 schema:url https://doi.org/10.1007/11600930_1
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N133842646ba74bbbb53b5568f8f98996 schema:name doi
64 schema:value 10.1007/11600930_1
65 rdf:type schema:PropertyValue
66 N1b62ff1247e84938bd3b920cfb23fe32 schema:name dimensions_id
67 schema:value pub.1043674621
68 rdf:type schema:PropertyValue
69 N3eefbf78d76749ccae5ef3e8b3cd3f9d schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N4dfb0e0ca0c8466689524a84f11d9e76 schema:familyName Ye
72 schema:givenName Yinyu
73 rdf:type schema:Person
74 N56d50b904dc945deb6115035931db4d6 rdf:first sg:person.013233165465.63
75 rdf:rest rdf:nil
76 N56e0dc0f1f1348fab9e872832f78d996 rdf:first N4dfb0e0ca0c8466689524a84f11d9e76
77 rdf:rest rdf:nil
78 N7e0bc4de158d471fbcd8ef6f57271e7b schema:isbn 978-3-540-30900-0
79 978-3-540-32293-1
80 schema:name Internet and Network Economics
81 rdf:type schema:Book
82 N81c529438f9b48f9af5326b839531bcf schema:familyName Deng
83 schema:givenName Xiaotie
84 rdf:type schema:Person
85 Nc6aaab8ed84b4fe6bdaebaeb599b351d rdf:first N81c529438f9b48f9af5326b839531bcf
86 rdf:rest N56e0dc0f1f1348fab9e872832f78d996
87 Ned8bad60ec3549579255a3b60b20a593 schema:name Springer Nature
88 rdf:type schema:Organisation
89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information and Computing Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
93 schema:name Computation Theory and Mathematics
94 rdf:type schema:DefinedTerm
95 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
96 schema:familyName Papadimitriou
97 schema:givenName Christos
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
99 rdf:type schema:Person
100 grid-institutes:grid.47840.3f schema:alternateName Department of EECS, UC Berkeley, USA
101 schema:name Department of EECS, UC Berkeley, USA
102 rdf:type schema:Organization
 




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


...