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 Ndb75c42991a3449f9a9eadb9200520df
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 N48d3b92f9e15454496bfd17d8ea91a0a
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N0a60059650c44f208fa077c07cec1fdb
21 schema:name The Power of Verification for One-Parameter Agents
22 schema:pagination 171-182
23 schema:productId N0b68227b3cfb4dcd891ce44cff357249
24 N0d94d2c7e02f4c588809f8f7d5ce9cf7
25 Na7e85942d129483eb9b02f83eede5d32
26 schema:publisher Nff2b3e8c781a441d93294183f2e4f4de
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 N7332a9ad48da4e1fb382381c968b3089
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 N007919dff8254ad8ac95557d2c47d42c rdf:first sg:person.013624103516.76
37 rdf:rest N951e79e7d9f5427baa4fd97f856afe11
38 N0a60059650c44f208fa077c07cec1fdb schema:isbn 978-3-540-22849-3
39 978-3-540-27836-8
40 schema:name Automata, Languages and Programming
41 rdf:type schema:Book
42 N0b68227b3cfb4dcd891ce44cff357249 schema:name dimensions_id
43 schema:value pub.1023831388
44 rdf:type schema:PropertyValue
45 N0d94d2c7e02f4c588809f8f7d5ce9cf7 schema:name doi
46 schema:value 10.1007/978-3-540-27836-8_17
47 rdf:type schema:PropertyValue
48 N428aab9a24914dd086529e75d31567bf schema:familyName Díaz
49 schema:givenName Josep
50 rdf:type schema:Person
51 N48d3b92f9e15454496bfd17d8ea91a0a rdf:first N428aab9a24914dd086529e75d31567bf
52 rdf:rest Ne6da90a451ff41c58378d0c21d8661d0
53 N63fe16a5259a4a7fa8b748ff7c2f641e rdf:first N79c51e1dd0de4220be3fe63eb9b1e79c
54 rdf:rest Na884a71f274348a49487b646836e4f88
55 N7332a9ad48da4e1fb382381c968b3089 schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 N79c51e1dd0de4220be3fe63eb9b1e79c schema:familyName Lepistö
58 schema:givenName Arto
59 rdf:type schema:Person
60 N93c9332b7c1a45f78b13f864a434b0ba schema:familyName Sannella
61 schema:givenName Donald
62 rdf:type schema:Person
63 N951e79e7d9f5427baa4fd97f856afe11 rdf:first sg:person.013255374317.27
64 rdf:rest rdf:nil
65 N958408031463429bbbf9c9d897643cdf rdf:first sg:person.015154042177.95
66 rdf:rest N007919dff8254ad8ac95557d2c47d42c
67 Na7e85942d129483eb9b02f83eede5d32 schema:name readcube_id
68 schema:value 71893f4f39f8c704dea6387c7ebf13a5f22987da275405e8e3ce6d886c29eb7a
69 rdf:type schema:PropertyValue
70 Na884a71f274348a49487b646836e4f88 rdf:first N93c9332b7c1a45f78b13f864a434b0ba
71 rdf:rest rdf:nil
72 Nd1edf12f2e784bbebdcf8944a9a1683c schema:familyName Karhumäki
73 schema:givenName Juhani
74 rdf:type schema:Person
75 Ndb75c42991a3449f9a9eadb9200520df rdf:first sg:person.016327521101.60
76 rdf:rest N958408031463429bbbf9c9d897643cdf
77 Ne6da90a451ff41c58378d0c21d8661d0 rdf:first Nd1edf12f2e784bbebdcf8944a9a1683c
78 rdf:rest N63fe16a5259a4a7fa8b748ff7c2f641e
79 Nff2b3e8c781a441d93294183f2e4f4de schema:location Berlin, Heidelberg
80 schema:name Springer Berlin Heidelberg
81 rdf:type schema:Organisation
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)


...