Controlled Dynamic Fair Division
Controlled Dynamic Fair Division
复制标题
受控动态公平划分
DOI：
10.1145/3033274.3085123
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Shai Vardi
中科院分区：
文献类型：
--
作者：
E. Friedman;Alexandros Psomas;Shai Vardi
在单资源动态公平划分框架中，存在随时间动态到达和离开的代理之间共享的同质资源。当存在n个代理时，只有一个真正“公平”的分配：每个代理接收1/n的资源。在动态世界中实现这种静态解决方案是众所周知的不切实际;现有的分配有太多的中断：对于一个新的代理人来说，为了得到她的公平份额，所有其他代理人都必须放弃一小部分。一个自然的补救措施是简单地限制新代理到达时允许的中断数量。[16]考虑到这种设置，并引入了一个自然的基准-公平性比率-最小份额与理想份额的比率（当系统中有k个代理时为1/k）。他们描述了一种算法，该算法在每个到达代理允许d ≥ 1次中断时获得最佳公平比。然而，在具有高到达率的系统中，即使每次到达一次中断也可能代价太高。我们考虑的情况下，每次到达时少于一个中断是允许的。我们表明，我们可以保持高水平的公平性，即使显着少于一个中断每个到达。特别是，我们提出了一个实例最优算法（该算法的输入是一个向量的允许中断），并表明，该算法的公平性比随c，其中c是连续的时间步长，我们不允许任何中断的最长数量递减。然后，我们考虑动态公平划分多个，异构资源。在这个模型中，代理人以固定的比例要求资源，在经济学中称为Leontief偏好。我们表明，一般的问题是NP难的，即使资源需求是二进制和已知的。我们研究的情况下，公平性标准是主导资源公平性（DRF），需求向量是二进制的。我们设计了一个通用的算法，这种设置使用减少到单资源的情况下。为了证明一个不可能的结果，我们采取一个整数规划的问题，并分析了一个算法，用于构建对偶解决方案的“剩余”的线性规划，这种方法可能是独立的利益。
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.
DOI：
10.1145/2764468.2764490
发表时间：
2015-06
期刊：
Proceedings of the Sixteenth ACM Conference on Economics and Computation
影响因子：
--
作者：
David Kurokawa;Ariel D. Procaccia;Nisarg Shah
通讯作者：
David Kurokawa;Ariel D. Procaccia;Nisarg Shah