More Powerful and Simpler Cost-Sharing Methods View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Paolo Penna , Carmine Ventre

ABSTRACT

We provide a new technique to derive group strategyproof mechanisms for the cost-sharing problem. Our technique is simpler and provably more powerful than the existing one based on so called cross-monotonic cost-sharing methods given by Moulin and Shenker [1997]. Indeed, our method yields the first polynomial-time mechanism for the Steiner tree game which is group strategyproof, budget balance and also meets other standard requirements (No Positive Transfer, Voluntary Participation and Consumer Sovereignty). A known result by Megiddo [1978] implies that this result cannot be achieved with cross-monotonic cost-sharing methods, even if using exponential-time mechanisms. More... »

PAGES

97-110

References to SciGraph publications

Book

TITLE

Approximation and Online Algorithms

ISBN

978-3-540-24574-2
978-3-540-31833-0

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-31833-0_10

DOI

http://dx.doi.org/10.1007/978-3-540-31833-0_10

DIMENSIONS

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


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": "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": "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": "https://doi.org/10.1002/net.3230080104", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016573124"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2004.07.033", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025391390"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/380752.380825", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028738557"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/1911055", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069639347"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2003.1238231", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094003635"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We provide a new technique to derive group strategyproof mechanisms for the cost-sharing problem. Our technique is simpler and provably more powerful than the existing one based on so called cross-monotonic cost-sharing methods given by Moulin and Shenker [1997]. Indeed, our method yields the first polynomial-time mechanism for the Steiner tree game which is group strategyproof, budget balance and also meets other standard requirements (No Positive Transfer, Voluntary Participation and Consumer Sovereignty). A known result by Megiddo [1978] implies that this result cannot be achieved with cross-monotonic cost-sharing methods, even if using exponential-time mechanisms.", 
    "editor": [
      {
        "familyName": "Persiano", 
        "givenName": "Giuseppe", 
        "type": "Person"
      }, 
      {
        "familyName": "Solis-Oba", 
        "givenName": "Roberto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-31833-0_10", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24574-2", 
        "978-3-540-31833-0"
      ], 
      "name": "Approximation and Online Algorithms", 
      "type": "Book"
    }, 
    "name": "More Powerful and Simpler Cost-Sharing Methods", 
    "pagination": "97-110", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051520859"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-31833-0_10"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f56c643eb7365745e250b920cce51c1d6258449a4c52272236c62687bd4b775d"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-31833-0_10", 
      "https://app.dimensions.ai/details/publication/pub.1051520859"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:05", 
    "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/0000000359_0000000359/records_29219_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-31833-0_10"
  }
]
 

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-31833-0_10'

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-31833-0_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-31833-0_10'

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-31833-0_10'


 

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

100 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-31833-0_10 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N829c3fd1e4c44e6589ae0e92e8e8e82e
4 schema:citation sg:pub.10.1007/pl00004200
5 sg:pub.10.1007/s003550050145
6 https://doi.org/10.1002/net.3230080104
7 https://doi.org/10.1016/j.tcs.2004.07.033
8 https://doi.org/10.1109/sfcs.2003.1238231
9 https://doi.org/10.1145/380752.380825
10 https://doi.org/10.2307/1911055
11 schema:datePublished 2005
12 schema:datePublishedReg 2005-01-01
13 schema:description We provide a new technique to derive group strategyproof mechanisms for the cost-sharing problem. Our technique is simpler and provably more powerful than the existing one based on so called cross-monotonic cost-sharing methods given by Moulin and Shenker [1997]. Indeed, our method yields the first polynomial-time mechanism for the Steiner tree game which is group strategyproof, budget balance and also meets other standard requirements (No Positive Transfer, Voluntary Participation and Consumer Sovereignty). A known result by Megiddo [1978] implies that this result cannot be achieved with cross-monotonic cost-sharing methods, even if using exponential-time mechanisms.
14 schema:editor Nfb4d4874b0174f52abf3f7c441c325fa
15 schema:genre chapter
16 schema:inLanguage en
17 schema:isAccessibleForFree true
18 schema:isPartOf N4caf4d71da314cceb1423458e92b7d08
19 schema:name More Powerful and Simpler Cost-Sharing Methods
20 schema:pagination 97-110
21 schema:productId N39cc7bf3c7234641aefb98238bc261b3
22 N65523d229a8c4127838fef8f73a68e17
23 Naf673a9905b24c97928adf2a122c366d
24 schema:publisher Ne785c117e0e641b09368c3f05cb2709a
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051520859
26 https://doi.org/10.1007/978-3-540-31833-0_10
27 schema:sdDatePublished 2019-04-16T08:05
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher Nb1d51b5b11174b9ca9e064eb17a88cfa
30 schema:url https://link.springer.com/10.1007%2F978-3-540-31833-0_10
31 sgo:license sg:explorer/license/
32 sgo:sdDataset chapters
33 rdf:type schema:Chapter
34 N19c164bcdb974f5c81a7117aeae7ca54 rdf:first Nb334bdcc9fa849c1b03b0999206d64dc
35 rdf:rest rdf:nil
36 N39cc7bf3c7234641aefb98238bc261b3 schema:name doi
37 schema:value 10.1007/978-3-540-31833-0_10
38 rdf:type schema:PropertyValue
39 N4caf4d71da314cceb1423458e92b7d08 schema:isbn 978-3-540-24574-2
40 978-3-540-31833-0
41 schema:name Approximation and Online Algorithms
42 rdf:type schema:Book
43 N65523d229a8c4127838fef8f73a68e17 schema:name dimensions_id
44 schema:value pub.1051520859
45 rdf:type schema:PropertyValue
46 N829c3fd1e4c44e6589ae0e92e8e8e82e rdf:first sg:person.013624103516.76
47 rdf:rest Nf86920b89b80447f8b0444fb8f811f8c
48 Na7a0f517fab5439b93db1b26ffb64d2b schema:familyName Persiano
49 schema:givenName Giuseppe
50 rdf:type schema:Person
51 Naf673a9905b24c97928adf2a122c366d schema:name readcube_id
52 schema:value f56c643eb7365745e250b920cce51c1d6258449a4c52272236c62687bd4b775d
53 rdf:type schema:PropertyValue
54 Nb1d51b5b11174b9ca9e064eb17a88cfa schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 Nb334bdcc9fa849c1b03b0999206d64dc schema:familyName Solis-Oba
57 schema:givenName Roberto
58 rdf:type schema:Person
59 Ne785c117e0e641b09368c3f05cb2709a schema:location Berlin, Heidelberg
60 schema:name Springer Berlin Heidelberg
61 rdf:type schema:Organisation
62 Nf86920b89b80447f8b0444fb8f811f8c rdf:first sg:person.013762200435.42
63 rdf:rest rdf:nil
64 Nfb4d4874b0174f52abf3f7c441c325fa rdf:first Na7a0f517fab5439b93db1b26ffb64d2b
65 rdf:rest N19c164bcdb974f5c81a7117aeae7ca54
66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
67 schema:name Information and Computing Sciences
68 rdf:type schema:DefinedTerm
69 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
70 schema:name Artificial Intelligence and Image Processing
71 rdf:type schema:DefinedTerm
72 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
73 schema:familyName Penna
74 schema:givenName Paolo
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
76 rdf:type schema:Person
77 sg:person.013762200435.42 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
78 schema:familyName Ventre
79 schema:givenName Carmine
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762200435.42
81 rdf:type schema:Person
82 sg:pub.10.1007/pl00004200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002007481
83 https://doi.org/10.1007/pl00004200
84 rdf:type schema:CreativeWork
85 sg:pub.10.1007/s003550050145 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006921516
86 https://doi.org/10.1007/s003550050145
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1002/net.3230080104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016573124
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1016/j.tcs.2004.07.033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025391390
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1109/sfcs.2003.1238231 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094003635
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1145/380752.380825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028738557
95 rdf:type schema:CreativeWork
96 https://doi.org/10.2307/1911055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069639347
97 rdf:type schema:CreativeWork
98 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
99 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy
100 rdf:type schema:Organization
 




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


...