Some Recent Results in Algorithmic Game Theory View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Christos Papadimitriou

ABSTRACT

There are three major trends in the field of Algorithmic Game Theory: computational mechanism design, the price of anarchy, and the computation of equilibria; this talk describes one recent result in each. We show computational complexity lower bounds on truthful and approximately efficient mechanisms; we revisit the Roughgarden-Tardos result on selfish routing when routing decisions are made by the nodes, not the flows; and we show that Nash equilibria can be approximated well in several broad, unexpected, and useful classes of games. (Joint work with Costis Daskalakis, Michael Schapira, Yaron Singer, and Greg Valiant). More... »

PAGES

17-17

Book

TITLE

Internet and Network Economics

ISBN

978-3-540-92184-4
978-3-540-92185-1

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-92185-1_9

DOI

http://dx.doi.org/10.1007/978-3-540-92185-1_9

DIMENSIONS

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


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/14", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Economics", 
        "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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1401", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Economic Theory", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "UC Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "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": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "There are three major trends in the field of Algorithmic Game Theory: computational mechanism design, the price of anarchy, and the computation of equilibria; this talk describes one recent result in each. We show computational complexity lower bounds on truthful and approximately efficient mechanisms; we revisit the Roughgarden-Tardos result on selfish routing when routing decisions are made by the nodes, not the flows; and we show that Nash equilibria can be approximated well in several broad, unexpected, and useful classes of games. (Joint work with Costis Daskalakis, Michael Schapira, Yaron Singer, and Greg Valiant).", 
    "editor": [
      {
        "familyName": "Papadimitriou", 
        "givenName": "Christos", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhang", 
        "givenName": "Shuzhong", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-92185-1_9", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-92184-4", 
        "978-3-540-92185-1"
      ], 
      "name": "Internet and Network Economics", 
      "type": "Book"
    }, 
    "keywords": [
      "algorithmic game theory", 
      "game theory", 
      "computational mechanism design", 
      "price of anarchy", 
      "computation of equilibria", 
      "Nash equilibrium", 
      "mechanism design", 
      "complexity lower bounds", 
      "recent results", 
      "selfish routing", 
      "lower bounds", 
      "useful class", 
      "major trends", 
      "prices", 
      "equilibrium", 
      "anarchy", 
      "theory", 
      "computational complexity lower bounds", 
      "decisions", 
      "game", 
      "bounds", 
      "efficient mechanism", 
      "computation", 
      "class", 
      "routing", 
      "trends", 
      "nodes", 
      "results", 
      "flow", 
      "design", 
      "field", 
      "talk", 
      "mechanism", 
      "Roughgarden-Tardos result"
    ], 
    "name": "Some Recent Results in Algorithmic Game Theory", 
    "pagination": "17-17", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013152410"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-92185-1_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-92185-1_9", 
      "https://app.dimensions.ai/details/publication/pub.1013152410"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:48", 
    "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_163.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-92185-1_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/978-3-540-92185-1_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/978-3-540-92185-1_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-92185-1_9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-92185-1_9'


 

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

107 TRIPLES      23 PREDICATES      62 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-92185-1_9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:14
4 anzsrc-for:1401
5 schema:author Nb8bf8368b1904a749f36b007f21202cd
6 schema:datePublished 2008
7 schema:datePublishedReg 2008-01-01
8 schema:description There are three major trends in the field of Algorithmic Game Theory: computational mechanism design, the price of anarchy, and the computation of equilibria; this talk describes one recent result in each. We show computational complexity lower bounds on truthful and approximately efficient mechanisms; we revisit the Roughgarden-Tardos result on selfish routing when routing decisions are made by the nodes, not the flows; and we show that Nash equilibria can be approximated well in several broad, unexpected, and useful classes of games. (Joint work with Costis Daskalakis, Michael Schapira, Yaron Singer, and Greg Valiant).
9 schema:editor Nb99a7923e162408ba2ad058b09a33311
10 schema:genre chapter
11 schema:inLanguage en
12 schema:isAccessibleForFree true
13 schema:isPartOf N36d03ac24d01476a91c1ccb157406add
14 schema:keywords Nash equilibrium
15 Roughgarden-Tardos result
16 algorithmic game theory
17 anarchy
18 bounds
19 class
20 complexity lower bounds
21 computation
22 computation of equilibria
23 computational complexity lower bounds
24 computational mechanism design
25 decisions
26 design
27 efficient mechanism
28 equilibrium
29 field
30 flow
31 game
32 game theory
33 lower bounds
34 major trends
35 mechanism
36 mechanism design
37 nodes
38 price of anarchy
39 prices
40 recent results
41 results
42 routing
43 selfish routing
44 talk
45 theory
46 trends
47 useful class
48 schema:name Some Recent Results in Algorithmic Game Theory
49 schema:pagination 17-17
50 schema:productId N44f1a0e5eb1f4ce4aaa107030aa116e8
51 N6d01ba8b7cc542fd9249fd8c0c9c0645
52 schema:publisher Nbe0e0ab426eb4cfa8c89f0a7592dcb73
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013152410
54 https://doi.org/10.1007/978-3-540-92185-1_9
55 schema:sdDatePublished 2021-11-01T18:48
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher N8403f814733d4131aee8db66f82fca35
58 schema:url https://doi.org/10.1007/978-3-540-92185-1_9
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N16c85f2e99db4060afb2c1e8941d8a35 schema:familyName Zhang
63 schema:givenName Shuzhong
64 rdf:type schema:Person
65 N36d03ac24d01476a91c1ccb157406add schema:isbn 978-3-540-92184-4
66 978-3-540-92185-1
67 schema:name Internet and Network Economics
68 rdf:type schema:Book
69 N44f1a0e5eb1f4ce4aaa107030aa116e8 schema:name dimensions_id
70 schema:value pub.1013152410
71 rdf:type schema:PropertyValue
72 N6d01ba8b7cc542fd9249fd8c0c9c0645 schema:name doi
73 schema:value 10.1007/978-3-540-92185-1_9
74 rdf:type schema:PropertyValue
75 N8403f814733d4131aee8db66f82fca35 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Nab3620660faa4932b7bb1ac82ec00d34 rdf:first N16c85f2e99db4060afb2c1e8941d8a35
78 rdf:rest rdf:nil
79 Nb8bf8368b1904a749f36b007f21202cd rdf:first sg:person.013233165465.63
80 rdf:rest rdf:nil
81 Nb99a7923e162408ba2ad058b09a33311 rdf:first Ne2fc24d7c2684e1b9297621af51f60a9
82 rdf:rest Nab3620660faa4932b7bb1ac82ec00d34
83 Nbe0e0ab426eb4cfa8c89f0a7592dcb73 schema:name Springer Nature
84 rdf:type schema:Organisation
85 Ne2fc24d7c2684e1b9297621af51f60a9 schema:familyName Papadimitriou
86 schema:givenName Christos
87 rdf:type schema:Person
88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information and Computing Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
92 schema:name Computation Theory and Mathematics
93 rdf:type schema:DefinedTerm
94 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
95 schema:name Economics
96 rdf:type schema:DefinedTerm
97 anzsrc-for:1401 schema:inDefinedTermSet anzsrc-for:
98 schema:name Economic Theory
99 rdf:type schema:DefinedTerm
100 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
101 schema:familyName Papadimitriou
102 schema:givenName Christos
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
104 rdf:type schema:Person
105 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley, USA
106 schema:name UC Berkeley, USA
107 rdf:type schema:Organization
 




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


...