MPI-INF D1 Publications: Journal Article: Dividing Connected Chores Fairly

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Goto entry point

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:
(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

Edit History (please click the blue arrow to see the details)

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