On Designing Truthful Mechanisms for Online Scheduling View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Vincenzo Auletta , Roberto De Prisco , Paolo Penna , Giuseppe Persiano

ABSTRACT

We study the online version of the scheduling problem involving selfish agents considered by Archer and Tardos [FOCS 2001]: jobs must be scheduled on m parallel related machines, each of them owned by a different selfish agent. Our study focuses on general techniques to translate approximation/competitive algorithms into equivalent approximation/competitive truthful mechanisms. Our results show that this translation is more problematic in the online setting than in the offline one.For m = 2, we develop an offline and an online “translation” technique which, given anyρ-approximation/competitive (polynomial-time) algorithm, yields an f(ρ)-approximation/competitive (polynomial-time) mechanism, with f(ρ) = ρ(1 + ε) in the offline case, for every ε > 0. By contrast, one of our lower bounds implies that, in general, online ρ-competitive algorithms cannot be turned into ρ(1 + ε)-competitive mechanisms, for some ε > 0 and every m ≥ 2. We also investigate the issue of designing new online algorithms from scratch so to obtain efficient competitive mechanisms, and prove some lower bounds on a class of “natural” algorithms. Finally, we consider the variant introduced by Nisan and Ronen [STOC 1999] in which machines can be verified. For this model, we give a O(1)-competitive online mechanism for any number of machines and prove that some of the above lower bounds can be broken. More... »

PAGES

3-17

References to SciGraph publications

Book

TITLE

Structural Information and Communication Complexity

ISBN

978-3-540-26052-3
978-3-540-32073-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11429647_3

DOI

http://dx.doi.org/10.1007/11429647_3

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi, (SA), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Auletta", 
        "givenName": "Vincenzo", 
        "id": "sg:person.016327521101.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Akamai (United States)", 
          "id": "https://www.grid.ac/institutes/grid.497049.7", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi, (SA), Italy", 
            "Faculty Group at Akamai Technologies, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "De Prisco", 
        "givenName": "Roberto", 
        "id": "sg:person.015154042177.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015154042177.95"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi, (SA), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi, (SA), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Persiano", 
        "givenName": "Giuseppe", 
        "id": "sg:person.013255374317.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1002/j.1538-7305.1966.tb01709.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017133205"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-27836-8_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023831388", 
          "https://doi.org/10.1007/978-3-540-27836-8_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-27836-8_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023831388", 
          "https://doi.org/10.1007/978-3-540-27836-8_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-24749-4_53", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025679830", 
          "https://doi.org/10.1007/978-3-540-24749-4_53"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-24749-4_53", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025679830", 
          "https://doi.org/10.1007/978-3-540-24749-4_53"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0029569", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032724318", 
          "https://doi.org/10.1007/bfb0029569"
        ], 
        "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.1111/j.1540-6261.1961.tb02789.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043120435"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/258128.258201", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048763327"
        ], 
        "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": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We study the online version of the scheduling problem involving selfish agents considered by Archer and Tardos [FOCS 2001]: jobs must be scheduled on m parallel related machines, each of them owned by a different selfish agent. Our study focuses on general techniques to translate approximation/competitive algorithms into equivalent approximation/competitive truthful mechanisms. Our results show that this translation is more problematic in the online setting than in the offline one.For m = 2, we develop an offline and an online \u201ctranslation\u201d technique which, given any\u03c1-approximation/competitive (polynomial-time) algorithm, yields an f(\u03c1)-approximation/competitive (polynomial-time) mechanism, with f(\u03c1) = \u03c1(1 + \u03b5) in the offline case, for every \u03b5 > 0. By contrast, one of our lower bounds implies that, in general, online \u03c1-competitive algorithms cannot be turned into \u03c1(1 + \u03b5)-competitive mechanisms, for some \u03b5 > 0 and every m \u2265 2. We also investigate the issue of designing new online algorithms from scratch so to obtain efficient competitive mechanisms, and prove some lower bounds on a class of \u201cnatural\u201d algorithms. Finally, we consider the variant introduced by Nisan and Ronen [STOC 1999] in which machines can be verified. For this model, we give a O(1)-competitive online mechanism for any number of machines and prove that some of the above lower bounds can be broken.", 
    "editor": [
      {
        "familyName": "Pelc", 
        "givenName": "Andrzej", 
        "type": "Person"
      }, 
      {
        "familyName": "Raynal", 
        "givenName": "Michel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11429647_3", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-26052-3", 
        "978-3-540-32073-9"
      ], 
      "name": "Structural Information and Communication Complexity", 
      "type": "Book"
    }, 
    "name": "On Designing Truthful Mechanisms for Online Scheduling", 
    "pagination": "3-17", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004827253"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11429647_3"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "17008836f2a6b969da4a09fd80352a89b2be42e2cfc476252ffe8116bca0bd9b"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11429647_3", 
      "https://app.dimensions.ai/details/publication/pub.1004827253"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:58", 
    "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/0000000359_0000000359/records_29181_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11429647_3"
  }
]
 

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/11429647_3'

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/11429647_3'

Turtle is a human-readable linked data format.

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

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

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


 

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

123 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11429647_3 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N9531d0a3fcc8487ea1b2bb70a5da27cb
4 schema:citation sg:pub.10.1007/978-3-540-24749-4_53
5 sg:pub.10.1007/978-3-540-27836-8_17
6 sg:pub.10.1007/978-3-540-31856-9_6
7 sg:pub.10.1007/bfb0029569
8 https://doi.org/10.1002/j.1538-7305.1966.tb01709.x
9 https://doi.org/10.1109/sfcs.2001.959924
10 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x
11 https://doi.org/10.1145/258128.258201
12 schema:datePublished 2005
13 schema:datePublishedReg 2005-01-01
14 schema:description We study the online version of the scheduling problem involving selfish agents considered by Archer and Tardos [FOCS 2001]: jobs must be scheduled on m parallel related machines, each of them owned by a different selfish agent. Our study focuses on general techniques to translate approximation/competitive algorithms into equivalent approximation/competitive truthful mechanisms. Our results show that this translation is more problematic in the online setting than in the offline one.For m = 2, we develop an offline and an online “translation” technique which, given anyρ-approximation/competitive (polynomial-time) algorithm, yields an f(ρ)-approximation/competitive (polynomial-time) mechanism, with f(ρ) = ρ(1 + ε) in the offline case, for every ε > 0. By contrast, one of our lower bounds implies that, in general, online ρ-competitive algorithms cannot be turned into ρ(1 + ε)-competitive mechanisms, for some ε > 0 and every m ≥ 2. We also investigate the issue of designing new online algorithms from scratch so to obtain efficient competitive mechanisms, and prove some lower bounds on a class of “natural” algorithms. Finally, we consider the variant introduced by Nisan and Ronen [STOC 1999] in which machines can be verified. For this model, we give a O(1)-competitive online mechanism for any number of machines and prove that some of the above lower bounds can be broken.
15 schema:editor N2e138b3ac1a344aeb938fea155cf0c9c
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N155028f16d0149ac807f498c834946c4
20 schema:name On Designing Truthful Mechanisms for Online Scheduling
21 schema:pagination 3-17
22 schema:productId N03555f593b234ae48ee99e31eb51dc47
23 N6ae849bce5b14fda978b9c0fc5085505
24 Ndee2c00d126c4df888ae056d8f3b4221
25 schema:publisher N2432f9acdd454b968de8459c225cbf82
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004827253
27 https://doi.org/10.1007/11429647_3
28 schema:sdDatePublished 2019-04-16T07:58
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N8e0640b2818646019ea8695f86728631
31 schema:url https://link.springer.com/10.1007%2F11429647_3
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N03555f593b234ae48ee99e31eb51dc47 schema:name doi
36 schema:value 10.1007/11429647_3
37 rdf:type schema:PropertyValue
38 N05168200aa1a4f4080e7d8672047c0a5 rdf:first sg:person.013624103516.76
39 rdf:rest N829fcb9edda1420d934bda30726e8f7f
40 N155028f16d0149ac807f498c834946c4 schema:isbn 978-3-540-26052-3
41 978-3-540-32073-9
42 schema:name Structural Information and Communication Complexity
43 rdf:type schema:Book
44 N1684785c4fae47a2a52a67a3a5655b6d schema:familyName Raynal
45 schema:givenName Michel
46 rdf:type schema:Person
47 N2432f9acdd454b968de8459c225cbf82 schema:location Berlin, Heidelberg
48 schema:name Springer Berlin Heidelberg
49 rdf:type schema:Organisation
50 N2e138b3ac1a344aeb938fea155cf0c9c rdf:first N9d0853cab0e545d8bf6d9c55d20a6e3f
51 rdf:rest N99ad51f74ac74f4da661cb67d3420491
52 N6ae849bce5b14fda978b9c0fc5085505 schema:name dimensions_id
53 schema:value pub.1004827253
54 rdf:type schema:PropertyValue
55 N829fcb9edda1420d934bda30726e8f7f rdf:first sg:person.013255374317.27
56 rdf:rest rdf:nil
57 N8e0640b2818646019ea8695f86728631 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N9531d0a3fcc8487ea1b2bb70a5da27cb rdf:first sg:person.016327521101.60
60 rdf:rest Nabe576c0123542a8b0f75c2399458de1
61 N99ad51f74ac74f4da661cb67d3420491 rdf:first N1684785c4fae47a2a52a67a3a5655b6d
62 rdf:rest rdf:nil
63 N9d0853cab0e545d8bf6d9c55d20a6e3f schema:familyName Pelc
64 schema:givenName Andrzej
65 rdf:type schema:Person
66 Nabe576c0123542a8b0f75c2399458de1 rdf:first sg:person.015154042177.95
67 rdf:rest N05168200aa1a4f4080e7d8672047c0a5
68 Ndee2c00d126c4df888ae056d8f3b4221 schema:name readcube_id
69 schema:value 17008836f2a6b969da4a09fd80352a89b2be42e2cfc476252ffe8116bca0bd9b
70 rdf:type schema:PropertyValue
71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
72 schema:name Information and Computing Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
75 schema:name Artificial Intelligence and Image Processing
76 rdf:type schema:DefinedTerm
77 sg:person.013255374317.27 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
78 schema:familyName Persiano
79 schema:givenName Giuseppe
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27
81 rdf:type schema:Person
82 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
83 schema:familyName Penna
84 schema:givenName Paolo
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
86 rdf:type schema:Person
87 sg:person.015154042177.95 schema:affiliation https://www.grid.ac/institutes/grid.497049.7
88 schema:familyName De Prisco
89 schema:givenName Roberto
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015154042177.95
91 rdf:type schema:Person
92 sg:person.016327521101.60 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
93 schema:familyName Auletta
94 schema:givenName Vincenzo
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60
96 rdf:type schema:Person
97 sg:pub.10.1007/978-3-540-24749-4_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025679830
98 https://doi.org/10.1007/978-3-540-24749-4_53
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/978-3-540-27836-8_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023831388
101 https://doi.org/10.1007/978-3-540-27836-8_17
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/978-3-540-31856-9_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032732750
104 https://doi.org/10.1007/978-3-540-31856-9_6
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/bfb0029569 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032724318
107 https://doi.org/10.1007/bfb0029569
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1002/j.1538-7305.1966.tb01709.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1017133205
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1109/sfcs.2001.959924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093632931
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043120435
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1145/258128.258201 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048763327
116 rdf:type schema:CreativeWork
117 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
118 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081, Baronissi, (SA), Italy
119 rdf:type schema:Organization
120 https://www.grid.ac/institutes/grid.497049.7 schema:alternateName Akamai (United States)
121 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081, Baronissi, (SA), Italy
122 Faculty Group at Akamai Technologies, Cambridge, MA, USA
123 rdf:type schema:Organization
 




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


...