Is Shapley Cost Sharing Optimal? View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Shahar Dobzinski , Aranyak Mehta , Tim Roughgarden , Mukund Sundararajan

ABSTRACT

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 β-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... »

PAGES

327-336

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-79309-0_29

DOI

http://dx.doi.org/10.1007/978-3-540-79309-0_29

DIMENSIONS

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


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/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

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-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

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-79309-0_29 schema:about anzsrc-for:14
2 anzsrc-for:1402
3 schema:author N5e8923f7cc954a1eb4147e1fde98b375
4 schema:datePublished 2008
5 schema:datePublishedReg 2008-01-01
6 schema: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 β-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.
7 schema:editor N7eb6a261a98a470193bc5f5a98867713
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N749102f4d39446e288837eabc106e90f
12 schema:keywords Shapley value mechanism
13 approximation
14 best guarantee
15 cases
16 characterization
17 constant factor
18 cost-sharing mechanisms
19 efficiency guarantees
20 expectations
21 factors
22 good problem
23 guarantees
24 main results
25 mechanism
26 new characterization
27 optimal
28 problem
29 results
30 separation
31 special case
32 subclasses
33 value mechanism
34 schema:name Is Shapley Cost Sharing Optimal?
35 schema:pagination 327-336
36 schema:productId N4cbdde6821354b77b08ffe43f1a0a640
37 Nb7e9e405e1cf47ffa8643c9279617227
38 schema:publisher Na3e3061ba52344bf959cf683b53da3d2
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046685907
40 https://doi.org/10.1007/978-3-540-79309-0_29
41 schema:sdDatePublished 2022-05-10T10:47
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N8ab348fe08584365987608f31176c17d
44 schema:url https://doi.org/10.1007/978-3-540-79309-0_29
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N1ca2dd20a67c4f92bb1b9684251c5233 schema:familyName Monien
49 schema:givenName Burkhard
50 rdf:type schema:Person
51 N4cbdde6821354b77b08ffe43f1a0a640 schema:name doi
52 schema:value 10.1007/978-3-540-79309-0_29
53 rdf:type schema:PropertyValue
54 N5e8923f7cc954a1eb4147e1fde98b375 rdf:first sg:person.014126332137.34
55 rdf:rest N71da82e43417479d877bd74936c15539
56 N71da82e43417479d877bd74936c15539 rdf:first sg:person.010106546671.08
57 rdf:rest Ne08a440533414bca8640682621a33dbd
58 N749102f4d39446e288837eabc106e90f schema:isbn 978-3-540-79308-3
59 978-3-540-79309-0
60 schema:name Algorithmic Game Theory
61 rdf:type schema:Book
62 N7eb6a261a98a470193bc5f5a98867713 rdf:first N1ca2dd20a67c4f92bb1b9684251c5233
63 rdf:rest N7f3bbdbba4ca48b2a4d67b8a163f30f1
64 N7f3bbdbba4ca48b2a4d67b8a163f30f1 rdf:first Na7f57adde9be49d9b96710aec0c9e74e
65 rdf:rest rdf:nil
66 N8ab348fe08584365987608f31176c17d schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 Na3e3061ba52344bf959cf683b53da3d2 schema:name Springer Nature
69 rdf:type schema:Organisation
70 Na7f57adde9be49d9b96710aec0c9e74e schema:familyName Schroeder
71 schema:givenName Ulf-Peter
72 rdf:type schema:Person
73 Nb7e9e405e1cf47ffa8643c9279617227 schema:name dimensions_id
74 schema:value pub.1046685907
75 rdf:type schema:PropertyValue
76 Nc27da926bcfa4ee08a1feac8fae95e73 rdf:first sg:person.010222560615.03
77 rdf:rest rdf:nil
78 Ne08a440533414bca8640682621a33dbd rdf:first sg:person.016435375611.40
79 rdf:rest Nc27da926bcfa4ee08a1feac8fae95e73
80 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
81 schema:name Economics
82 rdf:type schema:DefinedTerm
83 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
84 schema:name Applied Economics
85 rdf:type schema:DefinedTerm
86 sg:person.010106546671.08 schema:affiliation grid-institutes:grid.420451.6
87 schema:familyName Mehta
88 schema:givenName Aranyak
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08
90 rdf:type schema:Person
91 sg:person.010222560615.03 schema:affiliation grid-institutes:grid.168010.e
92 schema:familyName Sundararajan
93 schema:givenName Mukund
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010222560615.03
95 rdf:type schema:Person
96 sg:person.014126332137.34 schema:affiliation grid-institutes:grid.9619.7
97 schema:familyName Dobzinski
98 schema:givenName Shahar
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014126332137.34
100 rdf:type schema:Person
101 sg:person.016435375611.40 schema:affiliation grid-institutes:grid.168010.e
102 schema:familyName Roughgarden
103 schema:givenName Tim
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016435375611.40
105 rdf:type schema:Person
106 grid-institutes:grid.168010.e schema:alternateName Department of Computer Science, Stanford University, 353 Serra Mall, 94305, Stanford, CA, USA
107 schema:name Department of Computer Science, Stanford University, 353 Serra Mall, 94305, Stanford, CA, USA
108 rdf:type schema:Organization
109 grid-institutes:grid.420451.6 schema:alternateName Google, Inc., Mountain View, CA, USA
110 schema:name Google, Inc., Mountain View, CA, USA
111 rdf:type schema:Organization
112 grid-institutes:grid.9619.7 schema:alternateName The School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel
113 schema:name The School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel
114 rdf:type schema:Organization
 




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


...