Free-Riders in Steiner Tree Cost-Sharing Games View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Paolo Penna , Carmine Ventre

ABSTRACT

We consider cost-sharing mechanisms for the Steiner tree game. In this well-studied cooperative game, each selfish user expresses his/her willingness to pay for being connected to a source node s in an underlying graph. A mechanism decides which users will be connected and divides the cost of the corresponding (optimal) Steiner tree among these users (budget balance condition). Since users can form coalitions and misreport their willingness to pay, the mechanism must be group strategyproof: even coalitions of users cannot benefit from lying to the mechanism. We present new polynomial-time mechanisms which satisfy a standard set of axioms considered in the literature (i.e., budget balance, group strategyproofness, voluntary participation, consumer sovereignty, no positive transfer, cost optimality) and consider the free riders issue recently raised by Immorlica et al. [SODA 2005]: it would be desirable to avoid users that are connected for free. We also provide a number of negative results on the existence of polynomial-time mechanisms with certain guarantee on the number of free riders. Finally, we extend our technique and results to a variant considered by Biló et al. [SPAA 2004] with applications to wireless multicast cost sharing. More... »

PAGES

231-245

References to SciGraph publications

Book

TITLE

Structural Information and Communication Complexity

ISBN

978-3-540-26052-3
978-3-540-32073-9

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11429647_19

DOI

http://dx.doi.org/10.1007/11429647_19

DIMENSIONS

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


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/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive 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.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/1022630.1022644", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016626521"
        ], 
        "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.1145/1007912.1007940", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034943805"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcss.2001.1754", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037137868"
        ], 
        "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.1109/wcnc.2003.1200675", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094746071"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We consider cost-sharing mechanisms for the Steiner tree game. In this well-studied cooperative game, each selfish user expresses his/her willingness to pay for being connected to a source node s in an underlying graph. A mechanism decides which users will be connected and divides the cost of the corresponding (optimal) Steiner tree among these users (budget balance condition). Since users can form coalitions and misreport their willingness to pay, the mechanism must be group strategyproof: even coalitions of users cannot benefit from lying to the mechanism. We present new polynomial-time mechanisms which satisfy a standard set of axioms considered in the literature (i.e., budget balance, group strategyproofness, voluntary participation, consumer sovereignty, no positive transfer, cost optimality) and consider the free riders issue recently raised by Immorlica et al. [SODA 2005]: it would be desirable to avoid users that are connected for free. We also provide a number of negative results on the existence of polynomial-time mechanisms with certain guarantee on the number of free riders. Finally, we extend our technique and results to a variant considered by Bil\u00f3 et al. [SPAA 2004] with applications to wireless multicast cost sharing.", 
    "editor": [
      {
        "familyName": "Pelc", 
        "givenName": "Andrzej", 
        "type": "Person"
      }, 
      {
        "familyName": "Raynal", 
        "givenName": "Michel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11429647_19", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-26052-3", 
        "978-3-540-32073-9"
      ], 
      "name": "Structural Information and Communication Complexity", 
      "type": "Book"
    }, 
    "name": "Free-Riders in Steiner Tree Cost-Sharing Games", 
    "pagination": "231-245", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007057281"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11429647_19"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "219e28068d35c1fb987c86decdcdafe965e42af2a428120cdc40a3ed71721452"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11429647_19", 
      "https://app.dimensions.ai/details/publication/pub.1007057281"
    ], 
    "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_29222_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11429647_19"
  }
]
 

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/11429647_19'

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/11429647_19'

Turtle is a human-readable linked data format.

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

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

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


 

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

110 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11429647_19 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N5334dc9344a24e4f999207b745300a0d
4 schema:citation sg:pub.10.1007/978-3-540-31833-0_10
5 sg:pub.10.1007/pl00004200
6 sg:pub.10.1007/s003550050145
7 https://doi.org/10.1002/net.3230080104
8 https://doi.org/10.1006/jcss.2001.1754
9 https://doi.org/10.1109/wcnc.2003.1200675
10 https://doi.org/10.1145/1007912.1007940
11 https://doi.org/10.1145/1022630.1022644
12 https://doi.org/10.1145/380752.380825
13 https://doi.org/10.1145/988772.988814
14 schema:datePublished 2005
15 schema:datePublishedReg 2005-01-01
16 schema:description We consider cost-sharing mechanisms for the Steiner tree game. In this well-studied cooperative game, each selfish user expresses his/her willingness to pay for being connected to a source node s in an underlying graph. A mechanism decides which users will be connected and divides the cost of the corresponding (optimal) Steiner tree among these users (budget balance condition). Since users can form coalitions and misreport their willingness to pay, the mechanism must be group strategyproof: even coalitions of users cannot benefit from lying to the mechanism. We present new polynomial-time mechanisms which satisfy a standard set of axioms considered in the literature (i.e., budget balance, group strategyproofness, voluntary participation, consumer sovereignty, no positive transfer, cost optimality) and consider the free riders issue recently raised by Immorlica et al. [SODA 2005]: it would be desirable to avoid users that are connected for free. We also provide a number of negative results on the existence of polynomial-time mechanisms with certain guarantee on the number of free riders. Finally, we extend our technique and results to a variant considered by Biló et al. [SPAA 2004] with applications to wireless multicast cost sharing.
17 schema:editor N4137a5398be14977be7b777152a44b00
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf Nbbde8d09c1234f6cbc9a0fffbd34335e
22 schema:name Free-Riders in Steiner Tree Cost-Sharing Games
23 schema:pagination 231-245
24 schema:productId N3a81938db7184349a578f7cc46d2e814
25 N6fa927e0d3d4431b8ee95145172f778e
26 Nc32a279877c44c438d2bfa5f03acc17f
27 schema:publisher N320e5b17a5ce469da02b95585d8392dd
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007057281
29 https://doi.org/10.1007/11429647_19
30 schema:sdDatePublished 2019-04-16T08:05
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher Nbdabb6b72e6c4e9b9b201a3c151812fb
33 schema:url https://link.springer.com/10.1007%2F11429647_19
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N24a4b3505a094cbe97b38ac0672ad759 rdf:first N853ceedf55ae4e998453437d6af54bd3
38 rdf:rest rdf:nil
39 N320e5b17a5ce469da02b95585d8392dd schema:location Berlin, Heidelberg
40 schema:name Springer Berlin Heidelberg
41 rdf:type schema:Organisation
42 N3a81938db7184349a578f7cc46d2e814 schema:name doi
43 schema:value 10.1007/11429647_19
44 rdf:type schema:PropertyValue
45 N4137a5398be14977be7b777152a44b00 rdf:first N54dc79cc3f44462897520f0f82f6446a
46 rdf:rest N24a4b3505a094cbe97b38ac0672ad759
47 N5334dc9344a24e4f999207b745300a0d rdf:first sg:person.013624103516.76
48 rdf:rest Nbbb5e075fb484540bf829b7c34c3af45
49 N54dc79cc3f44462897520f0f82f6446a schema:familyName Pelc
50 schema:givenName Andrzej
51 rdf:type schema:Person
52 N6fa927e0d3d4431b8ee95145172f778e schema:name dimensions_id
53 schema:value pub.1007057281
54 rdf:type schema:PropertyValue
55 N853ceedf55ae4e998453437d6af54bd3 schema:familyName Raynal
56 schema:givenName Michel
57 rdf:type schema:Person
58 Nbbb5e075fb484540bf829b7c34c3af45 rdf:first sg:person.013762200435.42
59 rdf:rest rdf:nil
60 Nbbde8d09c1234f6cbc9a0fffbd34335e schema:isbn 978-3-540-26052-3
61 978-3-540-32073-9
62 schema:name Structural Information and Communication Complexity
63 rdf:type schema:Book
64 Nbdabb6b72e6c4e9b9b201a3c151812fb schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 Nc32a279877c44c438d2bfa5f03acc17f schema:name readcube_id
67 schema:value 219e28068d35c1fb987c86decdcdafe965e42af2a428120cdc40a3ed71721452
68 rdf:type schema:PropertyValue
69 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
70 schema:name Psychology and Cognitive Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
73 schema:name Psychology
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/978-3-540-31833-0_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051520859
86 https://doi.org/10.1007/978-3-540-31833-0_10
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/pl00004200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002007481
89 https://doi.org/10.1007/pl00004200
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/s003550050145 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006921516
92 https://doi.org/10.1007/s003550050145
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1002/net.3230080104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016573124
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1006/jcss.2001.1754 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037137868
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1109/wcnc.2003.1200675 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094746071
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1145/1007912.1007940 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034943805
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1145/1022630.1022644 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016626521
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://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
109 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081, Baronissi, (SA), Italy
110 rdf:type schema:Organization
 




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


...