Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities

DSpace/Manakin Repository

Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities

Citable link to this page

 

 
Title: Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities
Author: Parkes, David C.; Procaccia, Ariel; Shah, Nisarg

Note: Order does not necessarily reflect citation order of authors.

Citation: Parkes, David C., Ariel D. Procaccia, and Nisarg Shah. 2012. Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. Proceedings of the 13th ACM Conference on Electronic Commerce (EC ’12), June 4-8, 2012, Valencia, Spain, 808-825. New York, NY: ACM Press.
Full Text & Related Files:
Abstract: We study the problem of allocating multiple resources to agents with heterogeneous demands. Technological advances such as cloud computing and data centers provide a new impetus for investigating this problem under the assumption that agents demand the resources in fixed proportions, known in economics as Leontief preferences. In a recent paper, Ghodsi et al. [2011] introduced the dominant resource fairness (DRF) mechanism, which was shown to possess highly desirable theoretical properties under Leontief preferences. We extend their results in three directions. First, we show that DRF generalizes to more expressive settings, and leverage a new technical framework to formally extend its guarantees. Second, we study the relation between social welfare and properties such as truthfulness; DRF performs poorly in terms of social welfare, but we show that this is an unavoidable shortcoming that is shared by every mechanism that satisfies one of three basic properties. Third, and most importantly, we study a realistic setting that involves indivisibilities. We chart the boundaries of the possible in this setting, contributing a new relaxed notion of fairness and providing both possibility and impossibility results.
Published Version: doi:10.1145/2229012.2229075
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:11956916
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters