2008
AUTHORSShahar Dobzinski , Aranyak Mehta , Tim Roughgarden , Mukund Sundararajan
ABSTRACTWe study the best guarantees of efficiency approximation achievable by cost-sharing mechanisms. Our main result is the first quantitative lower bound that applies to all truthful cost-sharing mechanisms, including randomized mechanisms that are only truthful in expectation, and only β-budget-balanced in expectation. Our lower bound is optimal up to constant factors and applies even to the simple and central special case of the public excludable good problem. We also give a stronger lower bound for a subclass of deterministic cost-sharing mechanisms, which is driven by a new characterization of the Shapley value mechanism. Finally, we show a separation between the best-possible efficiency guarantees achievable by deterministic and randomized cost-sharing mechanisms. More... »
PAGES327-336
Algorithmic Game Theory
ISBN
978-3-540-79308-3
978-3-540-79309-0
http://scigraph.springernature.com/pub.10.1007/978-3-540-79309-0_29
DOIhttp://dx.doi.org/10.1007/978-3-540-79309-0_29
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1046685907
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/14",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Economics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1402",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Economics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "The School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel",
"id": "http://www.grid.ac/institutes/grid.9619.7",
"name": [
"The School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel"
],
"type": "Organization"
},
"familyName": "Dobzinski",
"givenName": "Shahar",
"id": "sg:person.014126332137.34",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014126332137.34"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Google, Inc., Mountain View, CA, USA",
"id": "http://www.grid.ac/institutes/grid.420451.6",
"name": [
"Google, Inc., Mountain View, CA, USA"
],
"type": "Organization"
},
"familyName": "Mehta",
"givenName": "Aranyak",
"id": "sg:person.010106546671.08",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, Stanford University, 353 Serra Mall, 94305, Stanford, CA, USA",
"id": "http://www.grid.ac/institutes/grid.168010.e",
"name": [
"Department of Computer Science, Stanford University, 353 Serra Mall, 94305, Stanford, CA, USA"
],
"type": "Organization"
},
"familyName": "Roughgarden",
"givenName": "Tim",
"id": "sg:person.016435375611.40",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016435375611.40"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, Stanford University, 353 Serra Mall, 94305, Stanford, CA, USA",
"id": "http://www.grid.ac/institutes/grid.168010.e",
"name": [
"Department of Computer Science, Stanford University, 353 Serra Mall, 94305, Stanford, CA, USA"
],
"type": "Organization"
},
"familyName": "Sundararajan",
"givenName": "Mukund",
"id": "sg:person.010222560615.03",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010222560615.03"
],
"type": "Person"
}
],
"datePublished": "2008",
"datePublishedReg": "2008-01-01",
"description": "We study the best guarantees of efficiency approximation achievable by cost-sharing mechanisms. Our main result is the first quantitative lower bound that applies to all truthful cost-sharing mechanisms, including randomized mechanisms that are only truthful in expectation, and only \u03b2-budget-balanced in expectation. Our lower bound is optimal up to constant factors and applies even to the simple and central special case of the public excludable good problem. We also give a stronger lower bound for a subclass of deterministic cost-sharing mechanisms, which is driven by a new characterization of the Shapley value mechanism. Finally, we show a separation between the best-possible efficiency guarantees achievable by deterministic and randomized cost-sharing mechanisms.",
"editor": [
{
"familyName": "Monien",
"givenName": "Burkhard",
"type": "Person"
},
{
"familyName": "Schroeder",
"givenName": "Ulf-Peter",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-79309-0_29",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-79308-3",
"978-3-540-79309-0"
],
"name": "Algorithmic Game Theory",
"type": "Book"
},
"keywords": [
"cost-sharing mechanisms",
"Shapley value mechanism",
"good problem",
"value mechanism",
"efficiency guarantees",
"best guarantee",
"main results",
"guarantees",
"expectations",
"special case",
"optimal",
"constant factor",
"mechanism",
"results",
"factors",
"cases",
"problem",
"new characterization",
"approximation",
"subclasses",
"separation",
"characterization"
],
"name": "Is Shapley Cost Sharing Optimal?",
"pagination": "327-336",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1046685907"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-79309-0_29"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-79309-0_29",
"https://app.dimensions.ai/details/publication/pub.1046685907"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:47",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_333.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-79309-0_29"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
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-79309-0_29'
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-79309-0_29'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-79309-0_29'
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-79309-0_29'
This table displays all metadata directly associated to this object as RDF triples.
114 TRIPLES
23 PREDICATES
48 URIs
41 LITERALS
7 BLANK NODES