Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Heydrich, Sandy
van Stee, Rob

dblp
dblp

Not MPG Author(s):

van Stee, Rob

BibTeX cite key*:

Heydrich2015

Title

Title*:

Dividing Connected Chores Fairly

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:

http://www.sciencedirect.com/science/journal/03043975

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

593

Number:


Publishing Date:

August 2015

Pages*:

51-61

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:

10.1016/j.tcs.2015.05.041

Note, Abstract, ©

Note:


(LaTeX) Abstract:

In this paper we consider the fair division of chores (tasks that need to be performed by agents, with negative utility for them), and study the loss in social welfare due to fairness. Previous work has been done on this so-called price of fairness, concerning fair division of cakes and chores with non-connected pieces and of cakes with connected pieces. In this paper, we consider situations where each player has to receive one connected piece of the chores. We provide tight or nearly tight bounds on the price of fairness with respect to the three main fairness criteria proportionality, envy-freeness and equitability and for utilitarian and egalitarian welfare. We also give the first proof of the existence of equitable divisions for chores with connected pieces.

URL for the Abstract:


Categories,
Keywords:

Division of chores, Price of fairness, Cake cutting

HyperLinks / References / URLs:

http://www.sciencedirect.com/science/article/pii/S0304397515004958

Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Heydrich2015,
AUTHOR = {Heydrich, Sandy and van Stee, Rob},
TITLE = {Dividing Connected Chores Fairly},
JOURNAL = {Theoretical Computer Science},
YEAR = {2015},
VOLUME = {593},
PAGES = {51--61},
MONTH = {August},
DOI = {10.1016/j.tcs.2015.05.041},
}


Entry last modified by Sandy Heydrich, 12/01/2016
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Sandy Heydrich
Created
12/01/2016 03:18:35 PM
Revision
0.



Editor
Sandy Heydrich



Edit Date
12/01/2016 03:18:35 PM