CaltechAUTHORS
  A Caltech Library Service

Controlled Dynamic Fair Division

Friedman, Eric J. and Psomas, Christos-Alexandros and Vardi, Shai (2017) Controlled Dynamic Fair Division. In: Proceedings of the 2017 ACM Conference on Economics and Computation - EC '17. ACM , New York, NY, pp. 461-478. ISBN 978-1-4503-4527-9. http://resolver.caltech.edu/CaltechAUTHORS:20170718-140444120

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170718-140444120

Abstract

In the single-resource dynamic fair division framework there is a homogeneous resource that is shared between agents dynamically arriving and departing over time. When n agents are present, there is only one truly ``fair'' allocation: each agent receives 1/n of the resource. Implementing this static solution in the dynamic world is notoriously impractical; there are too many disruptions to existing allocations: for a new agent to get her fair share, all other agents must give up a small piece. A natural remedy is simply to restrict the number of allowed disruptions when a new agent arrives. [16] considered this setting, and introduced a natural benchmark - the fairness ratio - the ratio of the minimal share to the ideal share (1/k when there are k agents in the system). They described an algorithm that obtains the optimal fairness ratio when d ≥ 1 disruptions are allowed per arriving agent. However, in systems with high arrival rates even one disruption per arrival can be too costly. We consider the scenario when fewer than one disruption per arrival is allowed. We show that we can maintain high levels of fairness even with significantly fewer than one disruption per arrival. In particular, we present an instance-optimal algorithm (the input to the algorithm is a vector of allowed disruptions) and show that the fairness ratio of this algorithm decays logarithmically with c, where c is the longest number of consecutive time steps in which we are not allowed any disruptions. We then consider dynamic fair division with multiple, heterogeneous resources. In this model, agents demand the resources in fixed proportions, known in economics as Leontief preferences. We show that the general problem is NP-hard, even if the resource demands are binary and known in advance. We study the case where the fairness criterion is Dominant Resource Fairness (DRF), and the demand vectors are binary. We design a generic algorithm for this setting using a reduction to the single-resource case. To prove an impossibility result, we take an integer program for the problem and analyze an algorithm for constructing dual solutions to a "residual" linear program; this approach may be of independent interest.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3033274.3085123DOIArticle
http://dl.acm.org/citation.cfm?doid=3033274.3085123PublisherArticle
Additional Information:© 2017 ACM. This work is supported by the National Science Foundation, under grants NSF-1216073, NSF-1161813, CCF1408635, CCF0964033, Templeton Foundation grant 3966, the Leventis Foundation and by the I-CORE in Algorithms Postdoctoral Fellowship.
Funders:
Funding AgencyGrant Number
NSFNSF-1216073
NSFNSF-1161813
NSFCCF1408635
NSFCCF0964033
Templeton Foundation3966
Leventis Foundation UNSPECIFIED
I-CORE in Algorithms Postdoctoral FellowshipUNSPECIFIED
Subject Keywords:Fair Division; Resource Allocation; Dynamic Fair Division
Record Number:CaltechAUTHORS:20170718-140444120
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170718-140444120
Official Citation:Eric Friedman, Christos-Alexandros Psomas, and Shai Vardi. 2017. Controlled Dynamic Fair Division. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC '17). ACM, New York, NY, USA, 461-478. DOI: https://doi.org/10.1145/3033274.3085123
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:79162
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:18 Jul 2017 22:01
Last Modified:18 Jul 2017 22:01

Repository Staff Only: item control page