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


...