Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

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

ABSTRACT

We consider the problem of scheduling jobs on related machines owned by selfish agents and provide the first deterministic mechanisms with constant approximation that are truthful; that is, truth-telling is a dominant strategy for all agents. More precisely, we present deterministic polynomial-time (2+ε)-approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Our result also yields a family of deterministic polynomial-time truthful (4+ε)-approximation mechanisms for any fixed number of machines. The only previously-known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is 3-approximated, randomized and truthful under a weaker notion of truthfulness. Up to our knowledge, our mechanisms are the first non-trivial polynomial-time deterministic truthful mechanisms for this NP-hard problem. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism. More... »

PAGES

608-619

References to SciGraph publications

  • 1971-09. Multipart pricing of public goods in PUBLIC CHOICE
  • Book

    TITLE

    STACS 2004

    ISBN

    978-3-540-21236-2
    978-3-540-24749-4

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_53

    DOI

    http://dx.doi.org/10.1007/978-3-540-24749-4_53

    DIMENSIONS

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


    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/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/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": "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": "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": "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": "https://doi.org/10.1002/j.1538-7305.1966.tb01709.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017133205"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/380752.380883", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018290072"
            ], 
            "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.1111/j.1540-6261.1961.tb02789.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043120435"
            ], 
            "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.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"
          }, 
          {
            "id": "https://doi.org/10.1145/352871.352898", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098948611"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "We consider the problem of scheduling jobs on related machines owned by selfish agents and provide the first deterministic mechanisms with constant approximation that are truthful; that is, truth-telling is a dominant strategy for all agents. More precisely, we present deterministic polynomial-time (2+\u03b5)-approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Our result also yields a family of deterministic polynomial-time truthful (4+\u03b5)-approximation mechanisms for any fixed number of machines. The only previously-known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is 3-approximated, randomized and truthful under a weaker notion of truthfulness. Up to our knowledge, our mechanisms are the first non-trivial polynomial-time deterministic truthful mechanisms for this NP-hard problem. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism.", 
        "editor": [
          {
            "familyName": "Diekert", 
            "givenName": "Volker", 
            "type": "Person"
          }, 
          {
            "familyName": "Habib", 
            "givenName": "Michel", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-24749-4_53", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-21236-2", 
            "978-3-540-24749-4"
          ], 
          "name": "STACS 2004", 
          "type": "Book"
        }, 
        "name": "Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines", 
        "pagination": "608-619", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1025679830"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-24749-4_53"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "7a56ff5df616017a741e9edf22bd601e624c6c8e5a0c31ff7a81c5aaa3ccb6d1"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-24749-4_53", 
          "https://app.dimensions.ai/details/publication/pub.1025679830"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:28", 
        "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/0000000363_0000000363/records_70066_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-24749-4_53"
      }
    ]
     

    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-24749-4_53'

    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-24749-4_53'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_53'

    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-24749-4_53'


     

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

    116 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-24749-4_53 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N02185e333ad64c8f85ab869fceb2b179
    4 schema:citation sg:pub.10.1007/bf01726210
    5 https://doi.org/10.1002/j.1538-7305.1966.tb01709.x
    6 https://doi.org/10.1080/15427951.2004.10129086
    7 https://doi.org/10.1109/sfcs.2001.959924
    8 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x
    9 https://doi.org/10.1145/352871.352898
    10 https://doi.org/10.1145/380752.380883
    11 https://doi.org/10.2307/1914085
    12 schema:datePublished 2004
    13 schema:datePublishedReg 2004-01-01
    14 schema:description We consider the problem of scheduling jobs on related machines owned by selfish agents and provide the first deterministic mechanisms with constant approximation that are truthful; that is, truth-telling is a dominant strategy for all agents. More precisely, we present deterministic polynomial-time (2+ε)-approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Our result also yields a family of deterministic polynomial-time truthful (4+ε)-approximation mechanisms for any fixed number of machines. The only previously-known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is 3-approximated, randomized and truthful under a weaker notion of truthfulness. Up to our knowledge, our mechanisms are the first non-trivial polynomial-time deterministic truthful mechanisms for this NP-hard problem. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism.
    15 schema:editor Na97cb6ab2fcb463c915f7abfb02b978a
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree true
    19 schema:isPartOf N07a0ae5ea5894350824fef4b5f2a9df0
    20 schema:name Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines
    21 schema:pagination 608-619
    22 schema:productId N7cb8b3d9fe864a5a9bb76cca0f0a5c98
    23 N9c6f913ef7a04288b0c616fd5555f08c
    24 Nd16b5bad1bcf46299d79ba64c39f89e1
    25 schema:publisher N0a17d4e14cfe4e14af901e2f31cb738b
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025679830
    27 https://doi.org/10.1007/978-3-540-24749-4_53
    28 schema:sdDatePublished 2019-04-16T08:28
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N2660d1859db94407878fdd5107e3f13a
    31 schema:url https://link.springer.com/10.1007%2F978-3-540-24749-4_53
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N02185e333ad64c8f85ab869fceb2b179 rdf:first sg:person.016327521101.60
    36 rdf:rest Ne31bb65211414d8b80e13bd1ef1bff65
    37 N07a0ae5ea5894350824fef4b5f2a9df0 schema:isbn 978-3-540-21236-2
    38 978-3-540-24749-4
    39 schema:name STACS 2004
    40 rdf:type schema:Book
    41 N0a17d4e14cfe4e14af901e2f31cb738b schema:location Berlin, Heidelberg
    42 schema:name Springer Berlin Heidelberg
    43 rdf:type schema:Organisation
    44 N2002b78086fa4a4fa66adda8aa1e12a2 rdf:first sg:person.013255374317.27
    45 rdf:rest rdf:nil
    46 N2660d1859db94407878fdd5107e3f13a schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 N64501ecc49fb4cf7a9e34b97bc5c3443 rdf:first N9895645df9374166ad3a8de650df8bac
    49 rdf:rest rdf:nil
    50 N7a74b8e60033407eb455e04cff4c2461 schema:familyName Diekert
    51 schema:givenName Volker
    52 rdf:type schema:Person
    53 N7cb8b3d9fe864a5a9bb76cca0f0a5c98 schema:name doi
    54 schema:value 10.1007/978-3-540-24749-4_53
    55 rdf:type schema:PropertyValue
    56 N9895645df9374166ad3a8de650df8bac schema:familyName Habib
    57 schema:givenName Michel
    58 rdf:type schema:Person
    59 N9c6f913ef7a04288b0c616fd5555f08c schema:name readcube_id
    60 schema:value 7a56ff5df616017a741e9edf22bd601e624c6c8e5a0c31ff7a81c5aaa3ccb6d1
    61 rdf:type schema:PropertyValue
    62 Na97cb6ab2fcb463c915f7abfb02b978a rdf:first N7a74b8e60033407eb455e04cff4c2461
    63 rdf:rest N64501ecc49fb4cf7a9e34b97bc5c3443
    64 Nd16b5bad1bcf46299d79ba64c39f89e1 schema:name dimensions_id
    65 schema:value pub.1025679830
    66 rdf:type schema:PropertyValue
    67 Ne07b50f6d104441e98b92d50c6bb96a4 rdf:first sg:person.013624103516.76
    68 rdf:rest N2002b78086fa4a4fa66adda8aa1e12a2
    69 Ne31bb65211414d8b80e13bd1ef1bff65 rdf:first sg:person.015154042177.95
    70 rdf:rest Ne07b50f6d104441e98b92d50c6bb96a4
    71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Information and Computing Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Computation Theory and Mathematics
    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.11780.3f
    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/bf01726210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003499590
    98 https://doi.org/10.1007/bf01726210
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1002/j.1538-7305.1966.tb01709.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1017133205
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1080/15427951.2004.10129086 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026661626
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1109/sfcs.2001.959924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093632931
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043120435
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/352871.352898 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098948611
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/380752.380883 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018290072
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.2307/1914085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069641186
    113 rdf:type schema:CreativeWork
    114 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
    115 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy
    116 rdf:type schema:Organization
     




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


    ...