Expand the Shares Together: Envy-Free Mechanisms with a Small Number of Cuts View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-04

AUTHORS

Masoud Seddighin, Majid Farhadi, Mohammad Ghodsi, Reza Alijani, Ahmad S. Tajik

ABSTRACT

We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players to meet these conditions: (I) every player (weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the allocation is dominant strategy-proof (truthful) (III) the number of cuts made on the cake is small. We provide methods for dividing the cake under different assumptions on the valuation functions of the players. First, we suppose that the valuation function of every player is a single interval with a special property, namely ordering property. For this case, we propose a process called expansion process and show that it results in an envy-free and truthful allocation that cuts the cake into exactly n pieces. Next, we remove the ordering restriction and show that for this case, an extended form of the expansion process, called expansion process with unlocking yields an envy-free allocation of the cake with at most 2(n-1) cuts. Furthermore, we show that in the expansion process with unlocking, the players may misrepresent their valuations to earn more share. In addition, we use a more complex form of the expansion process with unlocking to obtain an envy-free and truthful allocation that cuts the cake in at most 2(n-1) locations. We also, evaluate our expansion method in practice. In the empirical results, we compare the number of cuts made by our method to the number of cuts in the optimal solution (n-1). The experiments reveal that the number of cuts made by the expansion and unlocking process for envy-free division of the cake is very close to the optimal solution. Finally, we study piecewise constant and piecewise uniform valuation functions with m pieces and present the conditions, under which a generalized form of expansion process can allocate the cake via O(nm) cuts. More... »

PAGES

1-28

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-018-0500-z

DOI

http://dx.doi.org/10.1007/s00453-018-0500-z

DIMENSIONS

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


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/1402", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Economics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Sharif University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.412553.4", 
          "name": [
            "Sharif University of Technology, Tehran, Iran"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seddighin", 
        "givenName": "Masoud", 
        "id": "sg:person.016464362255.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016464362255.29"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sharif University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.412553.4", 
          "name": [
            "Sharif University of Technology, Tehran, Iran"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Farhadi", 
        "givenName": "Majid", 
        "id": "sg:person.016273454526.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016273454526.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute for Research in Fundamental Sciences", 
          "id": "https://www.grid.ac/institutes/grid.418744.a", 
          "name": [
            "Sharif University of Technology, Tehran, Iran", 
            "IPM - Institute for Research in Fundamental Sciences, Tehran, Iran"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ghodsi", 
        "givenName": "Mohammad", 
        "id": "sg:person.010044326555.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010044326555.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Duke university, Durham, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alijani", 
        "givenName": "Reza", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Michigan\u2013Ann Arbor", 
          "id": "https://www.grid.ac/institutes/grid.214458.e", 
          "name": [
            "University of Michigan, Ann Arbor, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tajik", 
        "givenName": "Ahmad S.", 
        "id": "sg:person.010067265017.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010067265017.50"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.mathsocsci.2004.03.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004034139"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-13129-0_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006219531", 
          "https://doi.org/10.1007/978-3-319-13129-0_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2483852.2483870", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018237774"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.geb.2012.10.009", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025056911"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-35311-6_13", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036531641", 
          "https://doi.org/10.1007/978-3-642-35311-6_13"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.1120.1116", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064726671"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.2016.52", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093835824"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.24963/ijcai.2017/507", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1096024272"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00029890.1995.11990526", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1103205381"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00029890.1980.11995109", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1103219989"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-04", 
    "datePublishedReg": "2019-04-01", 
    "description": "We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players to meet these conditions: (I) every player (weakly) prefers his allocated cake to any other player\u2019s share (such notion is known as envy-freeness), (II) the allocation is dominant strategy-proof (truthful) (III) the number of cuts made on the cake is small. We provide methods for dividing the cake under different assumptions on the valuation functions of the players. First, we suppose that the valuation function of every player is a single interval with a special property, namely ordering property. For this case, we propose a process called expansion process and show that it results in an envy-free and truthful allocation that cuts the cake into exactly n pieces. Next, we remove the ordering restriction and show that for this case, an extended form of the expansion process, called expansion process with unlocking yields an envy-free allocation of the cake with at most 2(n-1) cuts. Furthermore, we show that in the expansion process with unlocking, the players may misrepresent their valuations to earn more share. In addition, we use a more complex form of the expansion process with unlocking to obtain an envy-free and truthful allocation that cuts the cake in at most 2(n-1) locations. We also, evaluate our expansion method in practice. In the empirical results, we compare the number of cuts made by our method to the number of cuts in the optimal solution (n-1). The experiments reveal that the number of cuts made by the expansion and unlocking process for envy-free division of the cake is very close to the optimal solution. Finally, we study piecewise constant and piecewise uniform valuation functions with m pieces and present the conditions, under which a generalized form of expansion process can allocate the cake via O(nm) cuts.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-018-0500-z", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "81"
      }
    ], 
    "name": "Expand the Shares Together: Envy-Free Mechanisms with a Small Number of Cuts", 
    "pagination": "1-28", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0258b040f214963235bac92a5a49c872a5ae6b800f0ee64ec55f606977409bc3"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-018-0500-z"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1106158551"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-018-0500-z", 
      "https://app.dimensions.ai/details/publication/pub.1106158551"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T14:21", 
    "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/0000000372_0000000372/records_117128_00000003.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00453-018-0500-z"
  }
]
 

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-018-0500-z'

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-018-0500-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-0500-z'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-0500-z'


 

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

130 TRIPLES      21 PREDICATES      37 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-018-0500-z schema:about anzsrc-for:14
2 anzsrc-for:1402
3 schema:author Nad34e20cc1174951877d027bdf728cc0
4 schema:citation sg:pub.10.1007/978-3-319-13129-0_1
5 sg:pub.10.1007/978-3-642-35311-6_13
6 https://doi.org/10.1016/j.geb.2012.10.009
7 https://doi.org/10.1016/j.mathsocsci.2004.03.006
8 https://doi.org/10.1080/00029890.1980.11995109
9 https://doi.org/10.1080/00029890.1995.11990526
10 https://doi.org/10.1109/focs.2016.52
11 https://doi.org/10.1145/2483852.2483870
12 https://doi.org/10.1287/opre.1120.1116
13 https://doi.org/10.24963/ijcai.2017/507
14 schema:datePublished 2019-04
15 schema:datePublishedReg 2019-04-01
16 schema:description We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players to meet these conditions: (I) every player (weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the allocation is dominant strategy-proof (truthful) (III) the number of cuts made on the cake is small. We provide methods for dividing the cake under different assumptions on the valuation functions of the players. First, we suppose that the valuation function of every player is a single interval with a special property, namely ordering property. For this case, we propose a process called expansion process and show that it results in an envy-free and truthful allocation that cuts the cake into exactly n pieces. Next, we remove the ordering restriction and show that for this case, an extended form of the expansion process, called expansion process with unlocking yields an envy-free allocation of the cake with at most 2(n-1) cuts. Furthermore, we show that in the expansion process with unlocking, the players may misrepresent their valuations to earn more share. In addition, we use a more complex form of the expansion process with unlocking to obtain an envy-free and truthful allocation that cuts the cake in at most 2(n-1) locations. We also, evaluate our expansion method in practice. In the empirical results, we compare the number of cuts made by our method to the number of cuts in the optimal solution (n-1). The experiments reveal that the number of cuts made by the expansion and unlocking process for envy-free division of the cake is very close to the optimal solution. Finally, we study piecewise constant and piecewise uniform valuation functions with m pieces and present the conditions, under which a generalized form of expansion process can allocate the cake via O(nm) cuts.
17 schema:genre research_article
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf Nb540a7b42f9d4bda8ed8ac9cbb7c2646
21 Nfc372c0193784b12a2a63c08fd896950
22 sg:journal.1047644
23 schema:name Expand the Shares Together: Envy-Free Mechanisms with a Small Number of Cuts
24 schema:pagination 1-28
25 schema:productId N2d3408e70ff349efa695dbb63778e4ff
26 N55adae82fc024e78819d0684385a928d
27 Nf40197480f7045128d822746718d2270
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106158551
29 https://doi.org/10.1007/s00453-018-0500-z
30 schema:sdDatePublished 2019-04-11T14:21
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N3c1afb7ee93d43a28cb6d966bf46b242
33 schema:url https://link.springer.com/10.1007%2Fs00453-018-0500-z
34 sgo:license sg:explorer/license/
35 sgo:sdDataset articles
36 rdf:type schema:ScholarlyArticle
37 N2d3408e70ff349efa695dbb63778e4ff schema:name readcube_id
38 schema:value 0258b040f214963235bac92a5a49c872a5ae6b800f0ee64ec55f606977409bc3
39 rdf:type schema:PropertyValue
40 N333d1cd69bf34bba9714ce6fcd024fb2 rdf:first sg:person.016273454526.08
41 rdf:rest N8b52cf5c0d2a407597ed3a4d3fd6bc6a
42 N3c1afb7ee93d43a28cb6d966bf46b242 schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N55adae82fc024e78819d0684385a928d schema:name doi
45 schema:value 10.1007/s00453-018-0500-z
46 rdf:type schema:PropertyValue
47 N8b52cf5c0d2a407597ed3a4d3fd6bc6a rdf:first sg:person.010044326555.12
48 rdf:rest N99faebc01c6143db99d31965f51c3efd
49 N8b6f48c1d646486eae1d0b991b75b65a rdf:first sg:person.010067265017.50
50 rdf:rest rdf:nil
51 N99faebc01c6143db99d31965f51c3efd rdf:first Nfeb1fa6b71354adea87f2c4a439c7f34
52 rdf:rest N8b6f48c1d646486eae1d0b991b75b65a
53 Nad34e20cc1174951877d027bdf728cc0 rdf:first sg:person.016464362255.29
54 rdf:rest N333d1cd69bf34bba9714ce6fcd024fb2
55 Nb540a7b42f9d4bda8ed8ac9cbb7c2646 schema:volumeNumber 81
56 rdf:type schema:PublicationVolume
57 Nf40197480f7045128d822746718d2270 schema:name dimensions_id
58 schema:value pub.1106158551
59 rdf:type schema:PropertyValue
60 Nfc372c0193784b12a2a63c08fd896950 schema:issueNumber 4
61 rdf:type schema:PublicationIssue
62 Nfeb1fa6b71354adea87f2c4a439c7f34 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
63 schema:familyName Alijani
64 schema:givenName Reza
65 rdf:type schema:Person
66 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
67 schema:name Economics
68 rdf:type schema:DefinedTerm
69 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
70 schema:name Applied Economics
71 rdf:type schema:DefinedTerm
72 sg:journal.1047644 schema:issn 0178-4617
73 1432-0541
74 schema:name Algorithmica
75 rdf:type schema:Periodical
76 sg:person.010044326555.12 schema:affiliation https://www.grid.ac/institutes/grid.418744.a
77 schema:familyName Ghodsi
78 schema:givenName Mohammad
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010044326555.12
80 rdf:type schema:Person
81 sg:person.010067265017.50 schema:affiliation https://www.grid.ac/institutes/grid.214458.e
82 schema:familyName Tajik
83 schema:givenName Ahmad S.
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010067265017.50
85 rdf:type schema:Person
86 sg:person.016273454526.08 schema:affiliation https://www.grid.ac/institutes/grid.412553.4
87 schema:familyName Farhadi
88 schema:givenName Majid
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016273454526.08
90 rdf:type schema:Person
91 sg:person.016464362255.29 schema:affiliation https://www.grid.ac/institutes/grid.412553.4
92 schema:familyName Seddighin
93 schema:givenName Masoud
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016464362255.29
95 rdf:type schema:Person
96 sg:pub.10.1007/978-3-319-13129-0_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006219531
97 https://doi.org/10.1007/978-3-319-13129-0_1
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/978-3-642-35311-6_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036531641
100 https://doi.org/10.1007/978-3-642-35311-6_13
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/j.geb.2012.10.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025056911
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/j.mathsocsci.2004.03.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004034139
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1080/00029890.1980.11995109 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103219989
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1080/00029890.1995.11990526 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103205381
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1109/focs.2016.52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093835824
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1145/2483852.2483870 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018237774
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1287/opre.1120.1116 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064726671
115 rdf:type schema:CreativeWork
116 https://doi.org/10.24963/ijcai.2017/507 schema:sameAs https://app.dimensions.ai/details/publication/pub.1096024272
117 rdf:type schema:CreativeWork
118 https://www.grid.ac/institutes/grid.214458.e schema:alternateName University of Michigan–Ann Arbor
119 schema:name University of Michigan, Ann Arbor, USA
120 rdf:type schema:Organization
121 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
122 schema:name Duke university, Durham, USA
123 rdf:type schema:Organization
124 https://www.grid.ac/institutes/grid.412553.4 schema:alternateName Sharif University of Technology
125 schema:name Sharif University of Technology, Tehran, Iran
126 rdf:type schema:Organization
127 https://www.grid.ac/institutes/grid.418744.a schema:alternateName Institute for Research in Fundamental Sciences
128 schema:name IPM - Institute for Research in Fundamental Sciences, Tehran, Iran
129 Sharif University of Technology, Tehran, Iran
130 rdf:type schema:Organization
 




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


...