Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/37387
Title: Dividing connected chores fairly
Authors: Heydrich, S.
van Stee, Rob
First Published: 9-Jun-2015
Publisher: Elsevier
Citation: Theoretical Computer Science, 2015, 593, pp. 51-61 (11)
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.
DOI Link: 10.1016/j.tcs.2015.05.041
ISSN: 0304-3975
Links: http://www.sciencedirect.com/science/article/pii/S0304397515004958
http://hdl.handle.net/2381/37387
Embargo on file until: 9-Jun-2017
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2015 Elsevier B.V. All rights reserved. This manuscript version is made available after the end of the embargo period under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ 
Description: The file associated with this record is under a 24-month embargo from publication in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper.pdfPost-review (final submitted)363.38 kBUnknownView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.