The Power of Verification for One-Parameter Agents 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 study combinatorial optimization problems involving one-parameter selfish agents considered by Archer and Tardos [FOCS 2001]. In particular, we show that, if agents can lie in one direction (that is they either overbid or underbid) then any (polynomial-time) c-approximation algorithm, for the optimization problem without selfish agents, can be turned into a (polynomial-time) c(1+ε)-approximation truthful mechanism, for any ε >0. We then look at the Q||C max problem in the case of agents owning machines of different speeds. We consider the model in which payments are given to the agents only after the machines have completed the jobs assigned. This means that for each machine that receives at least one job, the mechanism can verify if the corresponding agent declared a greater speed. For this setting, we characterize the allocation algorithms A that admit a payment function P such that M=(A,P) is a truthful mechanism. In addition, we give a (1+ε)-approximation truthful mechanism for Q||C max when machine speeds are bounded by a constant. Finally, we consider the classical scheduling problem Q|| ∑ wj Cj which does not admit an exact mechanism if verification is not allowed. By contrast, we show that an exact mechanism for Q|| ∑ wj Cj exists when verification is allowed. More... »

PAGES

171-182

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-22849-3
978-3-540-27836-8

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-27836-8_17

DOI

http://dx.doi.org/10.1007/978-3-540-27836-8_17

DIMENSIONS

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


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": "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.1145/7531.7535", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004903970"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1007912.1007942", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018320543"
        ], 
        "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": "https://app.dimensions.ai/details/publication/pub.1026792740", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-58412-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026792740", 
          "https://doi.org/10.1007/978-3-642-58412-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-58412-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026792740", 
          "https://doi.org/10.1007/978-3-642-58412-1"
        ], 
        "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"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "We study combinatorial optimization problems involving one-parameter selfish agents considered by Archer and Tardos [FOCS 2001]. In particular, we show that, if agents can lie in one direction (that is they either overbid or underbid) then any (polynomial-time) c-approximation algorithm, for the optimization problem without selfish agents, can be turned into a (polynomial-time) c(1+\u03b5)-approximation truthful mechanism, for any \u03b5 >0. We then look at the Q||C max problem in the case of agents owning machines of different speeds. We consider the model in which payments are given to the agents only after the machines have completed the jobs assigned. This means that for each machine that receives at least one job, the mechanism can verify if the corresponding agent declared a greater speed. For this setting, we characterize the allocation algorithms A that admit a payment function P such that M=(A,P) is a truthful mechanism. In addition, we give a (1+\u03b5)-approximation truthful mechanism for Q||C max when machine speeds are bounded by a constant. Finally, we consider the classical scheduling problem Q|| \u2211 wj Cj which does not admit an exact mechanism if verification is not allowed. By contrast, we show that an exact mechanism for Q|| \u2211 wj Cj exists when verification is allowed.", 
    "editor": [
      {
        "familyName": "D\u00edaz", 
        "givenName": "Josep", 
        "type": "Person"
      }, 
      {
        "familyName": "Karhum\u00e4ki", 
        "givenName": "Juhani", 
        "type": "Person"
      }, 
      {
        "familyName": "Lepist\u00f6", 
        "givenName": "Arto", 
        "type": "Person"
      }, 
      {
        "familyName": "Sannella", 
        "givenName": "Donald", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-27836-8_17", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-22849-3", 
        "978-3-540-27836-8"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "The Power of Verification for One-Parameter Agents", 
    "pagination": "171-182", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023831388"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-27836-8_17"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "71893f4f39f8c704dea6387c7ebf13a5f22987da275405e8e3ce6d886c29eb7a"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-27836-8_17", 
      "https://app.dimensions.ai/details/publication/pub.1023831388"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:21", 
    "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_70028_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-27836-8_17"
  }
]
 

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-27836-8_17'

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-27836-8_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27836-8_17'

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-27836-8_17'


 

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

130 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-27836-8_17 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N971c969af6a343b1bb55fa0441546760
4 schema:citation sg:pub.10.1007/978-3-540-24749-4_53
5 sg:pub.10.1007/978-3-642-58412-1
6 sg:pub.10.1007/bf01726210
7 https://app.dimensions.ai/details/publication/pub.1026792740
8 https://doi.org/10.1109/sfcs.2001.959924
9 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x
10 https://doi.org/10.1145/1007912.1007942
11 https://doi.org/10.1145/7531.7535
12 https://doi.org/10.2307/1914085
13 schema:datePublished 2004
14 schema:datePublishedReg 2004-01-01
15 schema:description We study combinatorial optimization problems involving one-parameter selfish agents considered by Archer and Tardos [FOCS 2001]. In particular, we show that, if agents can lie in one direction (that is they either overbid or underbid) then any (polynomial-time) c-approximation algorithm, for the optimization problem without selfish agents, can be turned into a (polynomial-time) c(1+ε)-approximation truthful mechanism, for any ε >0. We then look at the Q||C max problem in the case of agents owning machines of different speeds. We consider the model in which payments are given to the agents only after the machines have completed the jobs assigned. This means that for each machine that receives at least one job, the mechanism can verify if the corresponding agent declared a greater speed. For this setting, we characterize the allocation algorithms A that admit a payment function P such that M=(A,P) is a truthful mechanism. In addition, we give a (1+ε)-approximation truthful mechanism for Q||C max when machine speeds are bounded by a constant. Finally, we consider the classical scheduling problem Q|| ∑ wj Cj which does not admit an exact mechanism if verification is not allowed. By contrast, we show that an exact mechanism for Q|| ∑ wj Cj exists when verification is allowed.
16 schema:editor N47f2ae3f8f934649a7bdd804b6c9e1a6
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf Nda979ec8fab9434f960e3867a97de371
21 schema:name The Power of Verification for One-Parameter Agents
22 schema:pagination 171-182
23 schema:productId N804a95606d27400c941ab08d325d030c
24 Nf00d7cd33bb94c3191a9ed448a622720
25 Nf9cb6d09fdff4fcaa2b2f6edc016aee3
26 schema:publisher Naf3628e2345b49ff866c92513fed546f
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023831388
28 https://doi.org/10.1007/978-3-540-27836-8_17
29 schema:sdDatePublished 2019-04-16T08:21
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N70158351a4344f569f4697f9fab47cbd
32 schema:url https://link.springer.com/10.1007%2F978-3-540-27836-8_17
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N16ef6b1f9a3f44928bc1137b1d281cd5 schema:familyName Lepistö
37 schema:givenName Arto
38 rdf:type schema:Person
39 N2657d48330394948bf00b621b073079a rdf:first sg:person.013255374317.27
40 rdf:rest rdf:nil
41 N2cd6d710ac204f71b4699cc98a21522d rdf:first sg:person.015154042177.95
42 rdf:rest N704fc1d67cff4f17a3a6cab44bbeceef
43 N47f2ae3f8f934649a7bdd804b6c9e1a6 rdf:first N96c64f648f154f1ba4b090983050ac61
44 rdf:rest Nbe5c6054749f4f978a130063673d0a4f
45 N70158351a4344f569f4697f9fab47cbd schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 N704fc1d67cff4f17a3a6cab44bbeceef rdf:first sg:person.013624103516.76
48 rdf:rest N2657d48330394948bf00b621b073079a
49 N804a95606d27400c941ab08d325d030c schema:name doi
50 schema:value 10.1007/978-3-540-27836-8_17
51 rdf:type schema:PropertyValue
52 N96c64f648f154f1ba4b090983050ac61 schema:familyName Díaz
53 schema:givenName Josep
54 rdf:type schema:Person
55 N971c969af6a343b1bb55fa0441546760 rdf:first sg:person.016327521101.60
56 rdf:rest N2cd6d710ac204f71b4699cc98a21522d
57 Naf3628e2345b49ff866c92513fed546f schema:location Berlin, Heidelberg
58 schema:name Springer Berlin Heidelberg
59 rdf:type schema:Organisation
60 Nbe5c6054749f4f978a130063673d0a4f rdf:first Ndea5a05069c74919b2085edfe43b4d19
61 rdf:rest Ned37a0a789af46b59787d85802a527c7
62 Nd68f1190311345b0987c8bbba79b8868 rdf:first Ne3048ddca7674ea8b195730dc931f5e6
63 rdf:rest rdf:nil
64 Nda979ec8fab9434f960e3867a97de371 schema:isbn 978-3-540-22849-3
65 978-3-540-27836-8
66 schema:name Automata, Languages and Programming
67 rdf:type schema:Book
68 Ndea5a05069c74919b2085edfe43b4d19 schema:familyName Karhumäki
69 schema:givenName Juhani
70 rdf:type schema:Person
71 Ne3048ddca7674ea8b195730dc931f5e6 schema:familyName Sannella
72 schema:givenName Donald
73 rdf:type schema:Person
74 Ned37a0a789af46b59787d85802a527c7 rdf:first N16ef6b1f9a3f44928bc1137b1d281cd5
75 rdf:rest Nd68f1190311345b0987c8bbba79b8868
76 Nf00d7cd33bb94c3191a9ed448a622720 schema:name dimensions_id
77 schema:value pub.1023831388
78 rdf:type schema:PropertyValue
79 Nf9cb6d09fdff4fcaa2b2f6edc016aee3 schema:name readcube_id
80 schema:value 71893f4f39f8c704dea6387c7ebf13a5f22987da275405e8e3ce6d886c29eb7a
81 rdf:type schema:PropertyValue
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
86 schema:name Artificial Intelligence and Image Processing
87 rdf:type schema:DefinedTerm
88 sg:person.013255374317.27 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
89 schema:familyName Persiano
90 schema:givenName Giuseppe
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27
92 rdf:type schema:Person
93 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
94 schema:familyName Penna
95 schema:givenName Paolo
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
97 rdf:type schema:Person
98 sg:person.015154042177.95 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
99 schema:familyName De Prisco
100 schema:givenName Roberto
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015154042177.95
102 rdf:type schema:Person
103 sg:person.016327521101.60 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
104 schema:familyName Auletta
105 schema:givenName Vincenzo
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60
107 rdf:type schema:Person
108 sg:pub.10.1007/978-3-540-24749-4_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025679830
109 https://doi.org/10.1007/978-3-540-24749-4_53
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/978-3-642-58412-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026792740
112 https://doi.org/10.1007/978-3-642-58412-1
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/bf01726210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003499590
115 https://doi.org/10.1007/bf01726210
116 rdf:type schema:CreativeWork
117 https://app.dimensions.ai/details/publication/pub.1026792740 schema:CreativeWork
118 https://doi.org/10.1109/sfcs.2001.959924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093632931
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043120435
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/1007912.1007942 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018320543
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/7531.7535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004903970
125 rdf:type schema:CreativeWork
126 https://doi.org/10.2307/1914085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069641186
127 rdf:type schema:CreativeWork
128 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
129 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081, Baronissi, (SA), Italy
130 rdf:type schema:Organization
 




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


...