The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Paolo Penna , Carmine Ventre

ABSTRACT

We study mechanisms for cooperative cost-sharing games satisfying: voluntary participation (i.e., no user is forced to pay more her valuation of the service), consumer sovereignty (i.e, every user can get the service if her valuation is large enough), no positive transfer (i.e., no user receives money from the mechanism), budget balance (i.e., the total amount of money that users pay is equal to the cost of servicing them), and group strategyproofness (i.e., the mechanism is resistant to coalitions). We show that mechanisms satisfying all these requirements must obey certain algorithmic properties (which basically specify how the serviced users are selected). Our results yield a characterization of upper continuous mechanisms (this class is interesting as all known general techniques yield mechanisms of this type). Finally, we extend some of our negative results and obtain the first negative results on the existence of mechanisms satisfying all requirements above. We apply these results to an interesting generalization of cost-sharing games in which the mechanism cannot service certain “forbidden” subsets of users. These generalized cost-sharing games correspond to natural variants of known cost-sharing games and have interesting practical applications (e.g., sharing the cost of multicast transmissions which cannot be encrypted). More... »

PAGES

337-348

References to SciGraph publications

Book

TITLE

STACS 2006

ISBN

978-3-540-32301-3
978-3-540-32288-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11672142_27

DOI

http://dx.doi.org/10.1007/11672142_27

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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, 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, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ventre", 
        "givenName": "Carmine", 
        "id": "sg:person.013762200435.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762200435.42"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/pl00004200", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002007481", 
          "https://doi.org/10.1007/pl00004200"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s003550050145", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006921516", 
          "https://doi.org/10.1007/s003550050145"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11429647_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007057281", 
          "https://doi.org/10.1007/11429647_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11429647_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007057281", 
          "https://doi.org/10.1007/11429647_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/988772.988814", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008077124"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230080104", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016573124"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/380752.380825", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028738557"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-31856-9_18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031816460", 
          "https://doi.org/10.1007/978-3-540-31856-9_18"
        ], 
        "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": "sg:pub.10.1007/978-3-540-31833-0_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051520859", 
          "https://doi.org/10.1007/978-3-540-31833-0_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-31833-0_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051520859", 
          "https://doi.org/10.1007/978-3-540-31833-0_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/moor.6.1.58", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064724540"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "We study mechanisms for cooperative cost-sharing games satisfying: voluntary participation (i.e., no user is forced to pay more her valuation of the service), consumer sovereignty (i.e, every user can get the service if her valuation is large enough), no positive transfer (i.e., no user receives money from the mechanism), budget balance (i.e., the total amount of money that users pay is equal to the cost of servicing them), and group strategyproofness (i.e., the mechanism is resistant to coalitions). We show that mechanisms satisfying all these requirements must obey certain algorithmic properties (which basically specify how the serviced users are selected). Our results yield a characterization of upper continuous mechanisms (this class is interesting as all known general techniques yield mechanisms of this type). Finally, we extend some of our negative results and obtain the first negative results on the existence of mechanisms satisfying all requirements above. We apply these results to an interesting generalization of cost-sharing games in which the mechanism cannot service certain \u201cforbidden\u201d subsets of users. These generalized cost-sharing games correspond to natural variants of known cost-sharing games and have interesting practical applications (e.g., sharing the cost of multicast transmissions which cannot be encrypted).", 
    "editor": [
      {
        "familyName": "Durand", 
        "givenName": "Bruno", 
        "type": "Person"
      }, 
      {
        "familyName": "Thomas", 
        "givenName": "Wolfgang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11672142_27", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-32301-3", 
        "978-3-540-32288-7"
      ], 
      "name": "STACS 2006", 
      "type": "Book"
    }, 
    "name": "The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms", 
    "pagination": "337-348", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008581802"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11672142_27"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "28e2afa42ed7616942e4a0b5424d16664af0f146019523d4af951823e40baa24"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11672142_27", 
      "https://app.dimensions.ai/details/publication/pub.1008581802"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07: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/0000000356_0000000356/records_57894_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11672142_27"
  }
]
 

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/11672142_27'

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/11672142_27'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11672142_27'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11672142_27'


 

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

112 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11672142_27 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N07cf5a11798a4bc3824853b295ecb7b1
4 schema:citation sg:pub.10.1007/11429647_19
5 sg:pub.10.1007/978-3-540-31833-0_10
6 sg:pub.10.1007/978-3-540-31856-9_18
7 sg:pub.10.1007/pl00004200
8 sg:pub.10.1007/s003550050145
9 https://doi.org/10.1002/net.3230080104
10 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x
11 https://doi.org/10.1145/380752.380825
12 https://doi.org/10.1145/988772.988814
13 https://doi.org/10.1287/moor.6.1.58
14 schema:datePublished 2006
15 schema:datePublishedReg 2006-01-01
16 schema:description We study mechanisms for cooperative cost-sharing games satisfying: voluntary participation (i.e., no user is forced to pay more her valuation of the service), consumer sovereignty (i.e, every user can get the service if her valuation is large enough), no positive transfer (i.e., no user receives money from the mechanism), budget balance (i.e., the total amount of money that users pay is equal to the cost of servicing them), and group strategyproofness (i.e., the mechanism is resistant to coalitions). We show that mechanisms satisfying all these requirements must obey certain algorithmic properties (which basically specify how the serviced users are selected). Our results yield a characterization of upper continuous mechanisms (this class is interesting as all known general techniques yield mechanisms of this type). Finally, we extend some of our negative results and obtain the first negative results on the existence of mechanisms satisfying all requirements above. We apply these results to an interesting generalization of cost-sharing games in which the mechanism cannot service certain “forbidden” subsets of users. These generalized cost-sharing games correspond to natural variants of known cost-sharing games and have interesting practical applications (e.g., sharing the cost of multicast transmissions which cannot be encrypted).
17 schema:editor N8a3fb9e96def4fcbabcb2a3615c3d7a0
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf Ndfff71d4e6b04a438fd3b55f67fa6c03
22 schema:name The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms
23 schema:pagination 337-348
24 schema:productId N07b7ef83f18f425c834ad2660844c3a6
25 Nd2b5d4df2f5d4c8da0e58912292eaca0
26 Nd5fd0d3adbd94794be4022502ef59cb7
27 schema:publisher N8da4d207df9c4a51a3cce685129cdf79
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008581802
29 https://doi.org/10.1007/11672142_27
30 schema:sdDatePublished 2019-04-16T07:31
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher Ncbae3bb4ba8f4a9398280a229ccf4c53
33 schema:url https://link.springer.com/10.1007%2F11672142_27
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N07b7ef83f18f425c834ad2660844c3a6 schema:name dimensions_id
38 schema:value pub.1008581802
39 rdf:type schema:PropertyValue
40 N07cf5a11798a4bc3824853b295ecb7b1 rdf:first sg:person.013624103516.76
41 rdf:rest N6e5d10adf8b74e8788016a23ba49c7ac
42 N17e7a5da80fd4c43aed27829dc32613f rdf:first N523b9cb254444c84ae5cbc0847da01ac
43 rdf:rest rdf:nil
44 N523b9cb254444c84ae5cbc0847da01ac schema:familyName Thomas
45 schema:givenName Wolfgang
46 rdf:type schema:Person
47 N6e5d10adf8b74e8788016a23ba49c7ac rdf:first sg:person.013762200435.42
48 rdf:rest rdf:nil
49 N8a3fb9e96def4fcbabcb2a3615c3d7a0 rdf:first Nbb31bfb3d6e44fa2afbcbc0e2c99cdb6
50 rdf:rest N17e7a5da80fd4c43aed27829dc32613f
51 N8da4d207df9c4a51a3cce685129cdf79 schema:location Berlin, Heidelberg
52 schema:name Springer Berlin Heidelberg
53 rdf:type schema:Organisation
54 Nbb31bfb3d6e44fa2afbcbc0e2c99cdb6 schema:familyName Durand
55 schema:givenName Bruno
56 rdf:type schema:Person
57 Ncbae3bb4ba8f4a9398280a229ccf4c53 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 Nd2b5d4df2f5d4c8da0e58912292eaca0 schema:name doi
60 schema:value 10.1007/11672142_27
61 rdf:type schema:PropertyValue
62 Nd5fd0d3adbd94794be4022502ef59cb7 schema:name readcube_id
63 schema:value 28e2afa42ed7616942e4a0b5424d16664af0f146019523d4af951823e40baa24
64 rdf:type schema:PropertyValue
65 Ndfff71d4e6b04a438fd3b55f67fa6c03 schema:isbn 978-3-540-32288-7
66 978-3-540-32301-3
67 schema:name STACS 2006
68 rdf:type schema:Book
69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
70 schema:name Information and Computing Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
73 schema:name Information Systems
74 rdf:type schema:DefinedTerm
75 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
76 schema:familyName Penna
77 schema:givenName Paolo
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
79 rdf:type schema:Person
80 sg:person.013762200435.42 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
81 schema:familyName Ventre
82 schema:givenName Carmine
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762200435.42
84 rdf:type schema:Person
85 sg:pub.10.1007/11429647_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007057281
86 https://doi.org/10.1007/11429647_19
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/978-3-540-31833-0_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051520859
89 https://doi.org/10.1007/978-3-540-31833-0_10
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/978-3-540-31856-9_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031816460
92 https://doi.org/10.1007/978-3-540-31856-9_18
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/pl00004200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002007481
95 https://doi.org/10.1007/pl00004200
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/s003550050145 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006921516
98 https://doi.org/10.1007/s003550050145
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1002/net.3230080104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016573124
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043120435
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1145/380752.380825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028738557
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1145/988772.988814 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008077124
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1287/moor.6.1.58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064724540
109 rdf:type schema:CreativeWork
110 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
111 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, Italy
112 rdf:type schema:Organization
 




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


...