A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007

AUTHORS

Elias Koutsoupias , Angelina Vidali

ABSTRACT

We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in a seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound 1 + φ ≈ 2.618 is a step towards the final resolution of this important problem. More... »

PAGES

454-464

References to SciGraph publications

Book

TITLE

Mathematical Foundations of Computer Science 2007

ISBN

978-3-540-74455-9
978-3-540-74456-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74456-6_41

DOI

http://dx.doi.org/10.1007/978-3-540-74456-6_41

DIMENSIONS

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


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/1401", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Economic Theory", 
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National and Kapodistrian University of Athens", 
          "id": "https://www.grid.ac/institutes/grid.5216.0", 
          "name": [
            "Department of Informatics, University of Athens"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Koutsoupias", 
        "givenName": "Elias", 
        "id": "sg:person.016555647611.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016555647611.20"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National and Kapodistrian University of Athens", 
          "id": "https://www.grid.ac/institutes/grid.5216.0", 
          "name": [
            "Department of Informatics, University of Athens"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vidali", 
        "givenName": "Angelina", 
        "id": "sg:person.010755032053.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010755032053.16"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/301250.301287", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002494864"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01726210", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003499590", 
          "https://doi.org/10.1007/bf01726210"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01726210", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003499590", 
          "https://doi.org/10.1007/bf01726210"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01585745", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006292857", 
          "https://doi.org/10.1007/bf01585745"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_55", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009630558", 
          "https://doi.org/10.1007/11561071_55"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_55", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009630558", 
          "https://doi.org/10.1007/11561071_55"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-008-9165-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015560415", 
          "https://doi.org/10.1007/s00453-008-9165-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-008-9165-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015560415", 
          "https://doi.org/10.1007/s00453-008-9165-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1060590.1060681", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018821540"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1064009.1064040", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021789994"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/15427951.2004.10129086", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026661626"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/846241.846250", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029827197"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-31856-9_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032732750", 
          "https://doi.org/10.1007/978-3-540-31856-9_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-31856-9_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032732750", 
          "https://doi.org/10.1007/978-3-540-31856-9_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1132516.1132607", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033789959"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1250910.1250947", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033988833"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/game.1999.0790", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036056755"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1060590.1060597", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036242952"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-73420-8_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044107492", 
          "https://doi.org/10.1007/978-3-540-73420-8_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-73420-8_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044107492", 
          "https://doi.org/10.1007/978-3-540-73420-8_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321941.321951", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052718373"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/1914085", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069641186"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2003.1238230", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093280231"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2001.959924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093632931"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2001.959924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093632931"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2001.959924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093632931"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2007", 
    "datePublishedReg": "2007-01-01", 
    "description": "We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in a seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound 1 + \u03c6 \u2248 2.618 is a step towards the final resolution of this important problem.", 
    "editor": [
      {
        "familyName": "Ku\u010dera", 
        "givenName": "Lud\u011bk", 
        "type": "Person"
      }, 
      {
        "familyName": "Ku\u010dera", 
        "givenName": "Anton\u00edn", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-74456-6_41", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-74455-9", 
        "978-3-540-74456-6"
      ], 
      "name": "Mathematical Foundations of Computer Science 2007", 
      "type": "Book"
    }, 
    "name": "A Lower Bound of 1 + \u03c6 for Truthful Scheduling Mechanisms", 
    "pagination": "454-464", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-74456-6_41"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9405e7d09c16b2523d552efc9a5c4bcc55fb9a77918f72a50a717f89fe6c2f5b"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031071656"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-74456-6_41", 
      "https://app.dimensions.ai/details/publication/pub.1031071656"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:27", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000345_0000000345/records_64115_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-74456-6_41"
  }
]
 

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-74456-6_41'

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-74456-6_41'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74456-6_41'

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-74456-6_41'


 

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

140 TRIPLES      23 PREDICATES      46 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74456-6_41 schema:about anzsrc-for:14
2 anzsrc-for:1401
3 schema:author Nc1fa0321a43744f18f84285ca399fcf5
4 schema:citation sg:pub.10.1007/11561071_55
5 sg:pub.10.1007/978-3-540-31856-9_6
6 sg:pub.10.1007/978-3-540-73420-8_6
7 sg:pub.10.1007/bf01585745
8 sg:pub.10.1007/bf01726210
9 sg:pub.10.1007/s00453-008-9165-3
10 https://doi.org/10.1006/game.1999.0790
11 https://doi.org/10.1080/15427951.2004.10129086
12 https://doi.org/10.1109/sfcs.2001.959924
13 https://doi.org/10.1109/sfcs.2003.1238230
14 https://doi.org/10.1145/1060590.1060597
15 https://doi.org/10.1145/1060590.1060681
16 https://doi.org/10.1145/1064009.1064040
17 https://doi.org/10.1145/1132516.1132607
18 https://doi.org/10.1145/1250910.1250947
19 https://doi.org/10.1145/301250.301287
20 https://doi.org/10.1145/321941.321951
21 https://doi.org/10.1145/846241.846250
22 https://doi.org/10.2307/1914085
23 schema:datePublished 2007
24 schema:datePublishedReg 2007-01-01
25 schema:description We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in a seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound 1 + φ ≈ 2.618 is a step towards the final resolution of this important problem.
26 schema:editor N75657a42927b4abd8b1fa4673709f9a6
27 schema:genre chapter
28 schema:inLanguage en
29 schema:isAccessibleForFree true
30 schema:isPartOf N883711a3cf4642748d390fbfa524617e
31 schema:name A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
32 schema:pagination 454-464
33 schema:productId N40e17ebbf9984591ab73247276c58743
34 Nb1fbbd58512c4766bc77bdb67854f62d
35 Ne0ce2703c72f4b478ef2c638b922f98a
36 schema:publisher Ne0f3b4708ec34dfa9a38737f22f6e1f9
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031071656
38 https://doi.org/10.1007/978-3-540-74456-6_41
39 schema:sdDatePublished 2019-04-16T05:27
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher Nfa106703540b4809a4dd2443314f3620
42 schema:url https://link.springer.com/10.1007%2F978-3-540-74456-6_41
43 sgo:license sg:explorer/license/
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N0eeca701ca2d47b0b97abf9c70665b07 schema:familyName Kučera
47 schema:givenName Luděk
48 rdf:type schema:Person
49 N40e17ebbf9984591ab73247276c58743 schema:name readcube_id
50 schema:value 9405e7d09c16b2523d552efc9a5c4bcc55fb9a77918f72a50a717f89fe6c2f5b
51 rdf:type schema:PropertyValue
52 N75657a42927b4abd8b1fa4673709f9a6 rdf:first N0eeca701ca2d47b0b97abf9c70665b07
53 rdf:rest Ndaed28ab0c5545d7a6bd58cdd20d1be0
54 N813722a09e9c4fc78baf9b196c363220 rdf:first sg:person.010755032053.16
55 rdf:rest rdf:nil
56 N883711a3cf4642748d390fbfa524617e schema:isbn 978-3-540-74455-9
57 978-3-540-74456-6
58 schema:name Mathematical Foundations of Computer Science 2007
59 rdf:type schema:Book
60 Na23b3e1f55b8406dbae9a0ec49388b25 schema:familyName Kučera
61 schema:givenName Antonín
62 rdf:type schema:Person
63 Nb1fbbd58512c4766bc77bdb67854f62d schema:name doi
64 schema:value 10.1007/978-3-540-74456-6_41
65 rdf:type schema:PropertyValue
66 Nc1fa0321a43744f18f84285ca399fcf5 rdf:first sg:person.016555647611.20
67 rdf:rest N813722a09e9c4fc78baf9b196c363220
68 Ndaed28ab0c5545d7a6bd58cdd20d1be0 rdf:first Na23b3e1f55b8406dbae9a0ec49388b25
69 rdf:rest rdf:nil
70 Ne0ce2703c72f4b478ef2c638b922f98a schema:name dimensions_id
71 schema:value pub.1031071656
72 rdf:type schema:PropertyValue
73 Ne0f3b4708ec34dfa9a38737f22f6e1f9 schema:location Berlin, Heidelberg
74 schema:name Springer Berlin Heidelberg
75 rdf:type schema:Organisation
76 Nfa106703540b4809a4dd2443314f3620 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
79 schema:name Economics
80 rdf:type schema:DefinedTerm
81 anzsrc-for:1401 schema:inDefinedTermSet anzsrc-for:
82 schema:name Economic Theory
83 rdf:type schema:DefinedTerm
84 sg:person.010755032053.16 schema:affiliation https://www.grid.ac/institutes/grid.5216.0
85 schema:familyName Vidali
86 schema:givenName Angelina
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010755032053.16
88 rdf:type schema:Person
89 sg:person.016555647611.20 schema:affiliation https://www.grid.ac/institutes/grid.5216.0
90 schema:familyName Koutsoupias
91 schema:givenName Elias
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016555647611.20
93 rdf:type schema:Person
94 sg:pub.10.1007/11561071_55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009630558
95 https://doi.org/10.1007/11561071_55
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/978-3-540-31856-9_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032732750
98 https://doi.org/10.1007/978-3-540-31856-9_6
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/978-3-540-73420-8_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044107492
101 https://doi.org/10.1007/978-3-540-73420-8_6
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/bf01585745 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006292857
104 https://doi.org/10.1007/bf01585745
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/bf01726210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003499590
107 https://doi.org/10.1007/bf01726210
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/s00453-008-9165-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015560415
110 https://doi.org/10.1007/s00453-008-9165-3
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1006/game.1999.0790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036056755
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1080/15427951.2004.10129086 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026661626
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1109/sfcs.2001.959924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093632931
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/sfcs.2003.1238230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093280231
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/1060590.1060597 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036242952
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/1060590.1060681 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018821540
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/1064009.1064040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021789994
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/1132516.1132607 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033789959
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/1250910.1250947 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033988833
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/301250.301287 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002494864
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1145/321941.321951 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052718373
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1145/846241.846250 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029827197
135 rdf:type schema:CreativeWork
136 https://doi.org/10.2307/1914085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069641186
137 rdf:type schema:CreativeWork
138 https://www.grid.ac/institutes/grid.5216.0 schema:alternateName National and Kapodistrian University of Athens
139 schema:name Department of Informatics, University of Athens
140 rdf:type schema:Organization
 




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


...