Private Capacities in Mechanism Design View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Vincenzo Auletta , Paolo Penna , Giuseppe Persiano

ABSTRACT

Motivated by the applications, we extend the usual one-parameter and multi-parameter settings by considering agents with private capacities: each agent can misreport her cost for “executing” a single unit of work and the maximum amount of work that each agent can actually execute (i.e., the capacity of the agent). We show that truthfulness in this setting is equivalent to a simple condition on the underlying algorithm. By applying this result to various problems considered in the literature (e.g., makespan minimization on related machines) we show that only some of the existing approaches to the case “without capacities” can be adapted to the case with private capacities. This poses new interesting algorithmic challenges. More... »

PAGES

112-123

References to SciGraph publications

Book

TITLE

Mathematical Foundations of Computer Science 2009

ISBN

978-3-642-03815-0
978-3-642-03816-7

Author Affiliations

From Grant

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03816-7_11

DOI

http://dx.doi.org/10.1007/978-3-642-03816-7_11

DIMENSIONS

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


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, Universit\u00e0 di 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 Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni, Universit\u00e0 di 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"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni, Universit\u00e0 di Salerno, 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.1016/0304-4068(87)90007-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007161802"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-006-1316-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009061250", 
          "https://doi.org/10.1007/s00224-006-1316-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_55", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009630558", 
          "https://doi.org/10.1007/11561071_55"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_55", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009630558", 
          "https://doi.org/10.1007/11561071_55"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1064009.1064040", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021789994"
        ], 
        "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": "https://doi.org/10.1006/game.1999.0790", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036056755"
        ], 
        "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.1111/j.1468-0262.2006.00695.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046583996"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/moor.6.1.58", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064724540"
        ], 
        "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.1109/focs.2008.39", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095810864"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Motivated by the applications, we extend the usual one-parameter and multi-parameter settings by considering agents with private capacities: each agent can misreport her cost for \u201cexecuting\u201d a single unit of work and the maximum amount of work that each agent can actually execute (i.e., the capacity of the agent). We show that truthfulness in this setting is equivalent to a simple condition on the underlying algorithm. By applying this result to various problems considered in the literature (e.g., makespan minimization on related machines) we show that only some of the existing approaches to the case \u201cwithout capacities\u201d can be adapted to the case with private capacities. This poses new interesting algorithmic challenges.", 
    "editor": [
      {
        "familyName": "Kr\u00e1lovi\u010d", 
        "givenName": "Rastislav", 
        "type": "Person"
      }, 
      {
        "familyName": "Niwi\u0144ski", 
        "givenName": "Damian", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03816-7_11", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3766914", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-642-03815-0", 
        "978-3-642-03816-7"
      ], 
      "name": "Mathematical Foundations of Computer Science 2009", 
      "type": "Book"
    }, 
    "name": "Private Capacities in Mechanism Design", 
    "pagination": "112-123", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03816-7_11"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0d779c364de5ec9006a0c048ecca4664cf283112d4b331d604e4dac68c6938c0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002827980"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03816-7_11", 
      "https://app.dimensions.ai/details/publication/pub.1002827980"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T11:31", 
    "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_00000244.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-03816-7_11"
  }
]
 

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-642-03816-7_11'

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-642-03816-7_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03816-7_11'

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-642-03816-7_11'


 

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

128 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03816-7_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N537407b9c1d6474a92dc6b7d49c52e36
4 schema:citation sg:pub.10.1007/11561071_55
5 sg:pub.10.1007/bf01726210
6 sg:pub.10.1007/s00224-006-1316-9
7 https://doi.org/10.1006/game.1999.0790
8 https://doi.org/10.1016/0304-4068(87)90007-3
9 https://doi.org/10.1016/j.geb.2008.08.001
10 https://doi.org/10.1109/focs.2008.39
11 https://doi.org/10.1109/sfcs.2001.959924
12 https://doi.org/10.1111/j.1468-0262.2006.00695.x
13 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x
14 https://doi.org/10.1145/1064009.1064040
15 https://doi.org/10.1287/moor.6.1.58
16 https://doi.org/10.2307/1914085
17 schema:datePublished 2009
18 schema:datePublishedReg 2009-01-01
19 schema:description Motivated by the applications, we extend the usual one-parameter and multi-parameter settings by considering agents with private capacities: each agent can misreport her cost for “executing” a single unit of work and the maximum amount of work that each agent can actually execute (i.e., the capacity of the agent). We show that truthfulness in this setting is equivalent to a simple condition on the underlying algorithm. By applying this result to various problems considered in the literature (e.g., makespan minimization on related machines) we show that only some of the existing approaches to the case “without capacities” can be adapted to the case with private capacities. This poses new interesting algorithmic challenges.
20 schema:editor Ned67bca39f65463abc4b1303abd469ec
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf Nc5702d56d9824704a02e099c33e5ce06
25 schema:name Private Capacities in Mechanism Design
26 schema:pagination 112-123
27 schema:productId N0ad9c196d4c544aaaa28832458fd2fd8
28 N70f27e45eed6418cb2eea6944a9efc7e
29 N842478360b8c4ad884ac46aaedcab2bb
30 schema:publisher N1660288188524759a58e83d78ebcf658
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002827980
32 https://doi.org/10.1007/978-3-642-03816-7_11
33 schema:sdDatePublished 2019-04-15T11:31
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N2c9c7d89434042aa97d01b5d1c3d7c06
36 schema:url http://link.springer.com/10.1007/978-3-642-03816-7_11
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N030628b1b78044279cf3865d0407ed8b rdf:first N3fa2c1795ac8413099050e72a99d57be
41 rdf:rest rdf:nil
42 N0ad9c196d4c544aaaa28832458fd2fd8 schema:name doi
43 schema:value 10.1007/978-3-642-03816-7_11
44 rdf:type schema:PropertyValue
45 N14f2eb2234e74169abf1d78d4a2073a2 schema:familyName Královič
46 schema:givenName Rastislav
47 rdf:type schema:Person
48 N1660288188524759a58e83d78ebcf658 schema:location Berlin, Heidelberg
49 schema:name Springer Berlin Heidelberg
50 rdf:type schema:Organisation
51 N2c9c7d89434042aa97d01b5d1c3d7c06 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 N39c78f0b447c437ba6a517ba322c4ad4 rdf:first sg:person.013255374317.27
54 rdf:rest rdf:nil
55 N3fa2c1795ac8413099050e72a99d57be schema:familyName Niwiński
56 schema:givenName Damian
57 rdf:type schema:Person
58 N537407b9c1d6474a92dc6b7d49c52e36 rdf:first sg:person.016327521101.60
59 rdf:rest Nb9f99939b2dd4c9da0d83dd3f3242d65
60 N70f27e45eed6418cb2eea6944a9efc7e schema:name readcube_id
61 schema:value 0d779c364de5ec9006a0c048ecca4664cf283112d4b331d604e4dac68c6938c0
62 rdf:type schema:PropertyValue
63 N842478360b8c4ad884ac46aaedcab2bb schema:name dimensions_id
64 schema:value pub.1002827980
65 rdf:type schema:PropertyValue
66 Nb9f99939b2dd4c9da0d83dd3f3242d65 rdf:first sg:person.013624103516.76
67 rdf:rest N39c78f0b447c437ba6a517ba322c4ad4
68 Nc5702d56d9824704a02e099c33e5ce06 schema:isbn 978-3-642-03815-0
69 978-3-642-03816-7
70 schema:name Mathematical Foundations of Computer Science 2009
71 rdf:type schema:Book
72 Ned67bca39f65463abc4b1303abd469ec rdf:first N14f2eb2234e74169abf1d78d4a2073a2
73 rdf:rest N030628b1b78044279cf3865d0407ed8b
74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
75 schema:name Information and Computing Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
78 schema:name Computation Theory and Mathematics
79 rdf:type schema:DefinedTerm
80 sg:grant.3766914 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-642-03816-7_11
81 rdf:type schema:MonetaryGrant
82 sg:person.013255374317.27 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
83 schema:familyName Persiano
84 schema:givenName Giuseppe
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27
86 rdf:type schema:Person
87 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
88 schema:familyName Penna
89 schema:givenName Paolo
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
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/11561071_55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009630558
98 https://doi.org/10.1007/11561071_55
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/bf01726210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003499590
101 https://doi.org/10.1007/bf01726210
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/s00224-006-1316-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009061250
104 https://doi.org/10.1007/s00224-006-1316-9
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1006/game.1999.0790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036056755
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/0304-4068(87)90007-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007161802
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/j.geb.2008.08.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028346903
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1109/focs.2008.39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095810864
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1109/sfcs.2001.959924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093632931
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1111/j.1468-0262.2006.00695.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046583996
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043120435
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/1064009.1064040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021789994
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1287/moor.6.1.58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064724540
123 rdf:type schema:CreativeWork
124 https://doi.org/10.2307/1914085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069641186
125 rdf:type schema:CreativeWork
126 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
127 schema:name Dipartimento di Informatica ed Applicazioni, Università di Salerno, Italy
128 rdf:type schema:Organization
 




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


...