Mechanisms for Scheduling with Single-Bit Private Values View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-10

AUTHORS

Vincenzo Auletta, George Christodoulou, Paolo Penna

ABSTRACT

We study the problem of designing truthful mechanisms for makespan minimization in scheduling. In particular, we consider randomized mechanisms for a restriction of the general multi-dimensional domain (i.e., unrelated machines). In a sense, our setting is the simplest multi-dimensional setting, where each machine holds privately only a single-bit of information. Some of the impossibility results for deterministic mechanisms carry over our setting as well. We prove a separation between truthful-in-expectation and universally truthful mechanisms for makespan minimization: We first show how to design an optimal truthful-in-expectation mechanism, and then prove lower bounds on the approximation guarantee of universally truthful mechanisms. More... »

PAGES

523-548

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-015-9625-5

DOI

http://dx.doi.org/10.1007/s00224-015-9625-5

DIMENSIONS

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


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, Universit\u00e0 di Salerno, Salerno, 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 Liverpool", 
          "id": "https://www.grid.ac/institutes/grid.10025.36", 
          "name": [
            "Computer Science Department, University of Liverpool, Liverpool, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Christodoulou", 
        "givenName": "George", 
        "id": "sg:person.015372025055.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015372025055.44"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica, Universit\u00e0 di Salerno, Salerno, 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"
      }
    ], 
    "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.1016/0304-4068(87)90007-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007161802"
        ], 
        "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/1566374.1566399", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027267988"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.geb.2008.08.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028346903"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-92185-1_46", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032192529", 
          "https://doi.org/10.1007/978-3-540-92185-1_46"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-92185-1_46", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032192529", 
          "https://doi.org/10.1007/978-3-540-92185-1_46"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/game.1999.0790", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036056755"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-10841-9_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042645067", 
          "https://doi.org/10.1007/978-3-642-10841-9_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-10841-9_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042645067", 
          "https://doi.org/10.1007/978-3-642-10841-9_5"
        ], 
        "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.1137/080744992", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062855463"
        ], 
        "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.1137/1.9781611973075.81", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088801267"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973105.90", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088801703"
        ], 
        "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.1017/cbo9780511800481", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1108143530"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2015-10", 
    "datePublishedReg": "2015-10-01", 
    "description": "We study the problem of designing truthful mechanisms for makespan minimization in scheduling. In particular, we consider randomized mechanisms for a restriction of the general multi-dimensional domain (i.e., unrelated machines). In a sense, our setting is the simplest multi-dimensional setting, where each machine holds privately only a single-bit of information. Some of the impossibility results for deterministic mechanisms carry over our setting as well. We prove a separation between truthful-in-expectation and universally truthful mechanisms for makespan minimization: We first show how to design an optimal truthful-in-expectation mechanism, and then prove lower bounds on the approximation guarantee of universally truthful mechanisms.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-015-9625-5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.2776074", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "57"
      }
    ], 
    "name": "Mechanisms for Scheduling with Single-Bit Private Values", 
    "pagination": "523-548", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c909567ffa6cb7ae5fdbd47a2fcf3172bc465267cc9f9018a76bfa5887e77c89"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-015-9625-5"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042203527"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-015-9625-5", 
      "https://app.dimensions.ai/details/publication/pub.1042203527"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T14:22", 
    "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/0000000001_0000000264/records_8660_00000592.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00224-015-9625-5"
  }
]
 

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/s00224-015-9625-5'

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/s00224-015-9625-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-015-9625-5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-015-9625-5'


 

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

129 TRIPLES      21 PREDICATES      42 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-015-9625-5 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N2ef89179b8ab4011b4eb7cbe37af48b2
4 schema:citation sg:pub.10.1007/978-3-540-92185-1_46
5 sg:pub.10.1007/978-3-642-10841-9_5
6 sg:pub.10.1007/bf01726210
7 sg:pub.10.1007/s00453-008-9165-3
8 https://doi.org/10.1006/game.1999.0790
9 https://doi.org/10.1016/0304-4068(87)90007-3
10 https://doi.org/10.1016/j.geb.2008.08.001
11 https://doi.org/10.1017/cbo9780511800481
12 https://doi.org/10.1109/sfcs.2001.959924
13 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x
14 https://doi.org/10.1137/080744992
15 https://doi.org/10.1137/1.9781611973075.81
16 https://doi.org/10.1137/1.9781611973105.90
17 https://doi.org/10.1145/1566374.1566399
18 https://doi.org/10.2307/1914085
19 schema:datePublished 2015-10
20 schema:datePublishedReg 2015-10-01
21 schema:description We study the problem of designing truthful mechanisms for makespan minimization in scheduling. In particular, we consider randomized mechanisms for a restriction of the general multi-dimensional domain (i.e., unrelated machines). In a sense, our setting is the simplest multi-dimensional setting, where each machine holds privately only a single-bit of information. Some of the impossibility results for deterministic mechanisms carry over our setting as well. We prove a separation between truthful-in-expectation and universally truthful mechanisms for makespan minimization: We first show how to design an optimal truthful-in-expectation mechanism, and then prove lower bounds on the approximation guarantee of universally truthful mechanisms.
22 schema:genre research_article
23 schema:inLanguage en
24 schema:isAccessibleForFree false
25 schema:isPartOf N479c79aa108142fdbb9cfd917511c755
26 N4cbb388ee99a490fb5f2b2baa807fa89
27 sg:journal.1052098
28 schema:name Mechanisms for Scheduling with Single-Bit Private Values
29 schema:pagination 523-548
30 schema:productId N15fd3fee44d64d4686a6fa94dfb11150
31 N6684d9114a1d439a8859dcf8abc33a1b
32 N780546ab2fca44c19c9767dc2f6c6eaf
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042203527
34 https://doi.org/10.1007/s00224-015-9625-5
35 schema:sdDatePublished 2019-04-10T14:22
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher Naf399b46f9c042f5a7e8e2338a0489dc
38 schema:url http://link.springer.com/10.1007/s00224-015-9625-5
39 sgo:license sg:explorer/license/
40 sgo:sdDataset articles
41 rdf:type schema:ScholarlyArticle
42 N09d42983fb9a42dc93f9362dd1ec311f rdf:first sg:person.015372025055.44
43 rdf:rest Nbfb09880f82949e8bf228eb88e1ce822
44 N15fd3fee44d64d4686a6fa94dfb11150 schema:name readcube_id
45 schema:value c909567ffa6cb7ae5fdbd47a2fcf3172bc465267cc9f9018a76bfa5887e77c89
46 rdf:type schema:PropertyValue
47 N2ef89179b8ab4011b4eb7cbe37af48b2 rdf:first sg:person.016327521101.60
48 rdf:rest N09d42983fb9a42dc93f9362dd1ec311f
49 N479c79aa108142fdbb9cfd917511c755 schema:volumeNumber 57
50 rdf:type schema:PublicationVolume
51 N4cbb388ee99a490fb5f2b2baa807fa89 schema:issueNumber 3
52 rdf:type schema:PublicationIssue
53 N6684d9114a1d439a8859dcf8abc33a1b schema:name dimensions_id
54 schema:value pub.1042203527
55 rdf:type schema:PropertyValue
56 N780546ab2fca44c19c9767dc2f6c6eaf schema:name doi
57 schema:value 10.1007/s00224-015-9625-5
58 rdf:type schema:PropertyValue
59 Naf399b46f9c042f5a7e8e2338a0489dc schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 Nbfb09880f82949e8bf228eb88e1ce822 rdf:first sg:person.013624103516.76
62 rdf:rest rdf:nil
63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
64 schema:name Information and Computing Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
67 schema:name Artificial Intelligence and Image Processing
68 rdf:type schema:DefinedTerm
69 sg:grant.2776074 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-015-9625-5
70 rdf:type schema:MonetaryGrant
71 sg:journal.1052098 schema:issn 1432-4350
72 1433-0490
73 schema:name Theory of Computing Systems
74 rdf:type schema:Periodical
75 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
76 schema:familyName Penna
77 schema:givenName Paolo
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
79 rdf:type schema:Person
80 sg:person.015372025055.44 schema:affiliation https://www.grid.ac/institutes/grid.10025.36
81 schema:familyName Christodoulou
82 schema:givenName George
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015372025055.44
84 rdf:type schema:Person
85 sg:person.016327521101.60 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
86 schema:familyName Auletta
87 schema:givenName Vincenzo
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60
89 rdf:type schema:Person
90 sg:pub.10.1007/978-3-540-92185-1_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032192529
91 https://doi.org/10.1007/978-3-540-92185-1_46
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/978-3-642-10841-9_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042645067
94 https://doi.org/10.1007/978-3-642-10841-9_5
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/bf01726210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003499590
97 https://doi.org/10.1007/bf01726210
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/s00453-008-9165-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015560415
100 https://doi.org/10.1007/s00453-008-9165-3
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1006/game.1999.0790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036056755
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0304-4068(87)90007-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007161802
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/j.geb.2008.08.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028346903
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1017/cbo9780511800481 schema:sameAs https://app.dimensions.ai/details/publication/pub.1108143530
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1109/sfcs.2001.959924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093632931
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043120435
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1137/080744992 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062855463
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1137/1.9781611973075.81 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801267
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1137/1.9781611973105.90 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801703
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/1566374.1566399 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027267988
121 rdf:type schema:CreativeWork
122 https://doi.org/10.2307/1914085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069641186
123 rdf:type schema:CreativeWork
124 https://www.grid.ac/institutes/grid.10025.36 schema:alternateName University of Liverpool
125 schema:name Computer Science Department, University of Liverpool, Liverpool, UK
126 rdf:type schema:Organization
127 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
128 schema:name Dipartimento di Informatica, Università di Salerno, Salerno, Italy
129 rdf:type schema:Organization
 




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


...