A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2012-08

AUTHORS

Emmanouil Pountourakis, Angelina Vidali

ABSTRACT

We study the problem of designing group-strategyproof cost-sharing mechanisms. The players report their bids for getting serviced and the mechanism decides a set of players that are going to be serviced and how much each one of them is going to pay. We determine three conditions: Fence Monotonicity, Stability of the allocation and Validity of the tie-breaking rule that are necessary and sufficient for group-strategyproofness, regardless of the cost function. Consequently, Fence Monotonicity characterizes group-strategyproof cost-sharing schemes closing an important open problem. Finally, we use our results to prove that there exist families of cost functions, where any group-strategyproof mechanism has arbitrarily poor budget balance. More... »

PAGES

831-860

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-011-9602-6

DOI

http://dx.doi.org/10.1007/s00453-011-9602-6

DIMENSIONS

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


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/1109", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Neurosciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Medical and Health Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Northwestern University", 
          "id": "https://www.grid.ac/institutes/grid.16753.36", 
          "name": [
            "Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pountourakis", 
        "givenName": "Emmanouil", 
        "id": "sg:person.013011042237.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013011042237.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Vienna", 
          "id": "https://www.grid.ac/institutes/grid.10420.37", 
          "name": [
            "Theory and Applications of Algorithms Research Group, University of Vienna, Vienna, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vidali", 
        "givenName": "Angelina", 
        "id": "sg:person.010755032053.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010755032053.16"
        ], 
        "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": "https://doi.org/10.1145/301250.301287", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002494864"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-77105-0_55", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005742078", 
          "https://doi.org/10.1007/978-3-540-77105-0_55"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-77105-0_55", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005742078", 
          "https://doi.org/10.1007/978-3-540-77105-0_55"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-87744-8_25", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006541558", 
          "https://doi.org/10.1007/978-3-540-87744-8_25"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-87744-8_25", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006541558", 
          "https://doi.org/10.1007/978-3-540-87744-8_25"
        ], 
        "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.1016/0304-4068(87)90007-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007161802"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11672142_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008581802", 
          "https://doi.org/10.1007/11672142_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11672142_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008581802", 
          "https://doi.org/10.1007/11672142_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.geb.2013.07.005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012873483"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-70918-3_57", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013979082", 
          "https://doi.org/10.1007/978-3-540-70918-3_57"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1386790.1386798", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018378930"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1064009.1064040", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021789994"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1361192.1361201", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034008631"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/game.1999.0790", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036056755"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1132516.1132528", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040762969"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4419-0056-2_16", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047401603", 
          "https://doi.org/10.1007/978-1-4419-0056-2_16"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1250910.1250912", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052980101"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2003.1238230", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093280231"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511800481", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1108143530"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2012-08", 
    "datePublishedReg": "2012-08-01", 
    "description": "We study the problem of designing group-strategyproof cost-sharing mechanisms. The players report their bids for getting serviced and the mechanism decides a set of players that are going to be serviced and how much each one of them is going to pay. We determine three conditions: Fence Monotonicity, Stability of the allocation and Validity of the tie-breaking rule that are necessary and sufficient for group-strategyproofness, regardless of the cost function. Consequently, Fence Monotonicity characterizes group-strategyproof cost-sharing schemes closing an important open problem. Finally, we use our results to prove that there exist families of cost functions, where any group-strategyproof mechanism has arbitrarily poor budget balance.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-011-9602-6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "63"
      }
    ], 
    "name": "A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing", 
    "pagination": "831-860", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "bcb60244d87dd1c3d689093bb5e3744595e62586d3432e733a836795154f6f81"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-011-9602-6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039615810"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-011-9602-6", 
      "https://app.dimensions.ai/details/publication/pub.1039615810"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T01:20", 
    "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/0000000001_0000000264/records_8697_00000591.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs00453-011-9602-6"
  }
]
 

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/s00453-011-9602-6'

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/s00453-011-9602-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-011-9602-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-011-9602-6'


 

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

132 TRIPLES      21 PREDICATES      45 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-011-9602-6 schema:about anzsrc-for:11
2 anzsrc-for:1109
3 schema:author N525d0ab9c4de4a6ba5f54d0d0fb0a678
4 schema:citation sg:pub.10.1007/11672142_27
5 sg:pub.10.1007/978-1-4419-0056-2_16
6 sg:pub.10.1007/978-3-540-70918-3_57
7 sg:pub.10.1007/978-3-540-77105-0_55
8 sg:pub.10.1007/978-3-540-87744-8_25
9 sg:pub.10.1007/pl00004200
10 sg:pub.10.1007/s003550050145
11 https://doi.org/10.1006/game.1999.0790
12 https://doi.org/10.1016/0304-4068(87)90007-3
13 https://doi.org/10.1016/j.geb.2013.07.005
14 https://doi.org/10.1017/cbo9780511800481
15 https://doi.org/10.1109/sfcs.2003.1238230
16 https://doi.org/10.1145/1064009.1064040
17 https://doi.org/10.1145/1132516.1132528
18 https://doi.org/10.1145/1250910.1250912
19 https://doi.org/10.1145/1361192.1361201
20 https://doi.org/10.1145/1386790.1386798
21 https://doi.org/10.1145/301250.301287
22 schema:datePublished 2012-08
23 schema:datePublishedReg 2012-08-01
24 schema:description We study the problem of designing group-strategyproof cost-sharing mechanisms. The players report their bids for getting serviced and the mechanism decides a set of players that are going to be serviced and how much each one of them is going to pay. We determine three conditions: Fence Monotonicity, Stability of the allocation and Validity of the tie-breaking rule that are necessary and sufficient for group-strategyproofness, regardless of the cost function. Consequently, Fence Monotonicity characterizes group-strategyproof cost-sharing schemes closing an important open problem. Finally, we use our results to prove that there exist families of cost functions, where any group-strategyproof mechanism has arbitrarily poor budget balance.
25 schema:genre research_article
26 schema:inLanguage en
27 schema:isAccessibleForFree true
28 schema:isPartOf Nabe710c8a0734fe69b8fd09d84651e0f
29 Nb4c9b21942c94dfca6720892073d03ac
30 sg:journal.1047644
31 schema:name A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing
32 schema:pagination 831-860
33 schema:productId N0f4828822f494560a3c57128ed672744
34 N2a596d8166694d28a0231774ac10cb7f
35 Nf3de1db5bf184c25bee7fe440851978f
36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039615810
37 https://doi.org/10.1007/s00453-011-9602-6
38 schema:sdDatePublished 2019-04-11T01:20
39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
40 schema:sdPublisher N5baf5b5c7d52436297fed17c1fc3558b
41 schema:url http://link.springer.com/10.1007%2Fs00453-011-9602-6
42 sgo:license sg:explorer/license/
43 sgo:sdDataset articles
44 rdf:type schema:ScholarlyArticle
45 N0f4828822f494560a3c57128ed672744 schema:name doi
46 schema:value 10.1007/s00453-011-9602-6
47 rdf:type schema:PropertyValue
48 N2a596d8166694d28a0231774ac10cb7f schema:name readcube_id
49 schema:value bcb60244d87dd1c3d689093bb5e3744595e62586d3432e733a836795154f6f81
50 rdf:type schema:PropertyValue
51 N525d0ab9c4de4a6ba5f54d0d0fb0a678 rdf:first sg:person.013011042237.43
52 rdf:rest N632b50aa8eea4e389c0ddde6223ba2fb
53 N5baf5b5c7d52436297fed17c1fc3558b schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 N632b50aa8eea4e389c0ddde6223ba2fb rdf:first sg:person.010755032053.16
56 rdf:rest rdf:nil
57 Nabe710c8a0734fe69b8fd09d84651e0f schema:volumeNumber 63
58 rdf:type schema:PublicationVolume
59 Nb4c9b21942c94dfca6720892073d03ac schema:issueNumber 4
60 rdf:type schema:PublicationIssue
61 Nf3de1db5bf184c25bee7fe440851978f schema:name dimensions_id
62 schema:value pub.1039615810
63 rdf:type schema:PropertyValue
64 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
65 schema:name Medical and Health Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:1109 schema:inDefinedTermSet anzsrc-for:
68 schema:name Neurosciences
69 rdf:type schema:DefinedTerm
70 sg:journal.1047644 schema:issn 0178-4617
71 1432-0541
72 schema:name Algorithmica
73 rdf:type schema:Periodical
74 sg:person.010755032053.16 schema:affiliation https://www.grid.ac/institutes/grid.10420.37
75 schema:familyName Vidali
76 schema:givenName Angelina
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010755032053.16
78 rdf:type schema:Person
79 sg:person.013011042237.43 schema:affiliation https://www.grid.ac/institutes/grid.16753.36
80 schema:familyName Pountourakis
81 schema:givenName Emmanouil
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013011042237.43
83 rdf:type schema:Person
84 sg:pub.10.1007/11672142_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008581802
85 https://doi.org/10.1007/11672142_27
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/978-1-4419-0056-2_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047401603
88 https://doi.org/10.1007/978-1-4419-0056-2_16
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/978-3-540-70918-3_57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013979082
91 https://doi.org/10.1007/978-3-540-70918-3_57
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/978-3-540-77105-0_55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005742078
94 https://doi.org/10.1007/978-3-540-77105-0_55
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/978-3-540-87744-8_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006541558
97 https://doi.org/10.1007/978-3-540-87744-8_25
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/pl00004200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002007481
100 https://doi.org/10.1007/pl00004200
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/s003550050145 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006921516
103 https://doi.org/10.1007/s003550050145
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1006/game.1999.0790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036056755
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/0304-4068(87)90007-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007161802
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/j.geb.2013.07.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012873483
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1017/cbo9780511800481 schema:sameAs https://app.dimensions.ai/details/publication/pub.1108143530
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1109/sfcs.2003.1238230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093280231
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1145/1064009.1064040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021789994
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1145/1132516.1132528 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040762969
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1145/1250910.1250912 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052980101
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1145/1361192.1361201 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034008631
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1145/1386790.1386798 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018378930
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1145/301250.301287 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002494864
126 rdf:type schema:CreativeWork
127 https://www.grid.ac/institutes/grid.10420.37 schema:alternateName University of Vienna
128 schema:name Theory and Applications of Algorithms Research Group, University of Vienna, Vienna, Austria
129 rdf:type schema:Organization
130 https://www.grid.ac/institutes/grid.16753.36 schema:alternateName Northwestern University
131 schema:name Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA
132 rdf:type schema:Organization
 




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


...