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

Ontology type: schema:ScholarlyArticle

Article Info

DATE

2018-08-14

AUTHORS 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2(n-1)$$\end{document} 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2(n-1)$$\end{document} 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document}). 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

1728-1755

TITLE

Algorithmica

ISSUE

4

VOLUME

81

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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"
},
{
"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"
}
],
"author": [
{
"affiliation": {
"alternateName": "Sharif University of Technology, Tehran, Iran",
"id": "http://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, Tehran, Iran",
"id": "http://www.grid.ac/institutes/grid.412553.4",
"name": [
"Sharif University of Technology, Tehran, Iran"
],
"type": "Organization"
},
"givenName": "Majid",
"id": "sg:person.016273454526.08",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016273454526.08"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "IPM - Institute for Research in Fundamental Sciences, Tehran, Iran",
"id": "http://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",
"id": "sg:person.010044326555.12",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010044326555.12"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Duke university, Durham, USA",
"id": "http://www.grid.ac/institutes/grid.26009.3d",
"name": [
"Duke university, Durham, USA"
],
"type": "Organization"
},
"familyName": "Alijani",
"givenName": "Reza",
"id": "sg:person.012750224100.77",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012750224100.77"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Michigan, Ann Arbor, USA",
"id": "http://www.grid.ac/institutes/grid.214458.e",
"name": [
"University of Michigan, Ann Arbor, USA"
],
"type": "Organization"
},
"familyName": "Tajik",
"id": "sg:person.010067265017.50",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010067265017.50"
],
"type": "Person"
}
],
"citation": [
{
"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": "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"
}
],
"datePublished": "2018-08-14",
"datePublishedReg": "2018-08-14",
"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)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2(n-1)$$\\end{document} 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)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2(n-1)$$\\end{document} 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\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$n-1$$\\end{document}). 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": "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",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "4",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"fair division",
"division",
"heterogeneous resources",
"resources",
"strategic players",
"players",
"player's share",
"share",
"allocation",
"cut",
"different assumptions",
"assumption",
"valuation function",
"expansion process",
"restriction",
"envy-free allocations",
"valuation",
"more shares",
"empirical results",
"optimal solution",
"expansion",
"problem",
"divisible heterogeneous cake",
"heterogeneous cake",
"cake",
"conditions",
"number of cuts",
"number",
"method",
"function",
"single interval",
"intervals",
"special properties",
"properties",
"cases",
"process",
"truthful allocation",
"pieces",
"ordering restriction",
"extended form",
"form",
"unlocking yields",
"yield",
"unlocking",
"complex forms",
"location",
"expansion method",
"practice",
"results",
"solution",
"experiments",
"unlocking process",
"envy-free division",
"piecewise",
"uniform valuation functions",
"envy-free mechanism",
"mechanism",
"small number"
],
"name": "Expand the Shares Together: Envy-Free Mechanisms with a Small Number of Cuts",
"pagination": "1728-1755",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1106158551"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-018-0500-z"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-018-0500-z",
"https://app.dimensions.ai/details/publication/pub.1106158551"
],
"sdDataset": "articles",
"sdDatePublished": "2021-12-01T19:40",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_771.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-018-0500-z"
}
]

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'

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.

163 TRIPLES      22 PREDICATES      86 URIs      76 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1402
3 schema:author Nce4493cbb2194fedb028f860bc08cc24
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 schema:datePublished 2018-08-14
7 schema:datePublishedReg 2018-08-14
8 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2(n-1)$$\end{document} 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2(n-1)$$\end{document} 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document}). 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.
9 schema:genre article
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf Nbd21887eb1e64b29a3c636e4135114c7
13 Nf7da8bfeb0ee43c8b004422feef0dc40
14 sg:journal.1047644
16 allocation
17 assumption
18 cake
19 cases
20 complex forms
21 conditions
22 cut
23 different assumptions
24 divisible heterogeneous cake
25 division
26 empirical results
27 envy-free allocations
28 envy-free division
29 envy-free mechanism
30 expansion
31 expansion method
32 expansion process
33 experiments
34 extended form
35 fair division
36 form
37 function
38 heterogeneous cake
39 heterogeneous resources
40 intervals
41 location
42 mechanism
43 method
44 more shares
45 number
46 number of cuts
47 optimal solution
48 ordering restriction
49 pieces
50 piecewise
51 player's share
52 players
53 practice
54 problem
55 process
56 properties
57 resources
58 restriction
59 results
60 share
61 single interval
62 small number
63 solution
64 special properties
65 strategic players
66 truthful allocation
67 uniform valuation functions
68 unlocking
69 unlocking process
70 unlocking yields
71 valuation
72 valuation function
73 yield
74 schema:name Expand the Shares Together: Envy-Free Mechanisms with a Small Number of Cuts
75 schema:pagination 1728-1755
78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106158551
79 https://doi.org/10.1007/s00453-018-0500-z
80 schema:sdDatePublished 2021-12-01T19:40
82 schema:sdPublisher N754cf5b1f0044675b5364a82a2928b1b
83 schema:url https://doi.org/10.1007/s00453-018-0500-z
85 sgo:sdDataset articles
86 rdf:type schema:ScholarlyArticle
87 N0de3818187e0482ab16b5aed35f21b81 rdf:first sg:person.012750224100.77
88 rdf:rest N2af85ed2f176419bae248d9a2e7c12d7
90 schema:value 10.1007/s00453-018-0500-z
91 rdf:type schema:PropertyValue
92 N2af85ed2f176419bae248d9a2e7c12d7 rdf:first sg:person.010067265017.50
93 rdf:rest rdf:nil
94 N73bc293f61c043ab8cf894947f939609 rdf:first sg:person.016273454526.08
95 rdf:rest Na7c34c40d4634276b216f10402971637
96 N754cf5b1f0044675b5364a82a2928b1b schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
99 schema:value pub.1106158551
100 rdf:type schema:PropertyValue
101 Na7c34c40d4634276b216f10402971637 rdf:first sg:person.010044326555.12
102 rdf:rest N0de3818187e0482ab16b5aed35f21b81
103 Nbd21887eb1e64b29a3c636e4135114c7 schema:issueNumber 4
104 rdf:type schema:PublicationIssue
105 Nce4493cbb2194fedb028f860bc08cc24 rdf:first sg:person.016464362255.29
106 rdf:rest N73bc293f61c043ab8cf894947f939609
108 rdf:type schema:PublicationVolume
109 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
110 schema:name Economics
111 rdf:type schema:DefinedTerm
112 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
113 schema:name Applied Economics
114 rdf:type schema:DefinedTerm
115 sg:journal.1047644 schema:issn 0178-4617
116 1432-0541
117 schema:name Algorithmica
118 schema:publisher Springer Nature
119 rdf:type schema:Periodical
120 sg:person.010044326555.12 schema:affiliation grid-institutes:grid.418744.a
121 schema:familyName Ghodsi
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010044326555.12
124 rdf:type schema:Person
125 sg:person.010067265017.50 schema:affiliation grid-institutes:grid.214458.e
126 schema:familyName Tajik
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010067265017.50
129 rdf:type schema:Person
130 sg:person.012750224100.77 schema:affiliation grid-institutes:grid.26009.3d
131 schema:familyName Alijani
132 schema:givenName Reza
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012750224100.77
134 rdf:type schema:Person
135 sg:person.016273454526.08 schema:affiliation grid-institutes:grid.412553.4
137 schema:givenName Majid
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016273454526.08
139 rdf:type schema:Person
140 sg:person.016464362255.29 schema:affiliation grid-institutes:grid.412553.4
141 schema:familyName Seddighin
142 schema:givenName Masoud
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016464362255.29
144 rdf:type schema:Person
145 sg:pub.10.1007/978-3-319-13129-0_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006219531
146 https://doi.org/10.1007/978-3-319-13129-0_1
147 rdf:type schema:CreativeWork
148 sg:pub.10.1007/978-3-642-35311-6_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036531641
149 https://doi.org/10.1007/978-3-642-35311-6_13
150 rdf:type schema:CreativeWork
151 grid-institutes:grid.214458.e schema:alternateName University of Michigan, Ann Arbor, USA
152 schema:name University of Michigan, Ann Arbor, USA
153 rdf:type schema:Organization
154 grid-institutes:grid.26009.3d schema:alternateName Duke university, Durham, USA
155 schema:name Duke university, Durham, USA
156 rdf:type schema:Organization
157 grid-institutes:grid.412553.4 schema:alternateName Sharif University of Technology, Tehran, Iran
158 schema:name Sharif University of Technology, Tehran, Iran
159 rdf:type schema:Organization
160 grid-institutes:grid.418744.a schema:alternateName IPM - Institute for Research in Fundamental Sciences, Tehran, Iran
161 schema:name IPM - Institute for Research in Fundamental Sciences, Tehran, Iran
162 Sharif University of Technology, Tehran, Iran
163 rdf:type schema:Organization