Every computer system -- from schedulers in clouds (e.g. Amazon) to computer networks to operating systems -- performs resource allocation across system users. The defacto allocation policies are max-min fairness (MMF) for single resources and dominant resource fairness (DRF) for multiple resources which guarantee properties like incentive compatibility, envy-freeness, and Pareto efficiency, assuming user demands are static (time-independent). However, in real-world systems, user demands are dynamic, i.e. time-dependant. As a result, there is now a fundamental mismatch between the goals of computer systems and the properties enabled by classic resource allocation policies. We aim to bridge this mismatch. When demands are dynamic, instant-by-instant MMF can be extremely unfair over longer periods of time, i.e. lead to unbalanced user allocations as previous allocations have no effect in the present. We consider a natural generalization of MMF and DRF for multiple resources and users with dynamic demands: this algorithm ensures that user allocations are as max-min fair as possible up to any time instant, given past allocations. This dynamic mechanism remains Pareto optimal and envy-free, but not incentive compatible. However, our results show that the possible increase in utility by misreporting is bounded and, since this can lead to significant decrease in overall useful allocation, this suggests that it is not a useful strategy. Our main result is to show that our dynamic DRF algorithm is $(1+\rho)$-incentive compatible, where $\rho$ quantifies the relative importance of a resource for different users; we show that this factor is tight even with only two resources. We also present a $3/2$ upper bound and a $\sqrt 2$ lower bound for incentive compatibility when there is only one resource. We also offer extensions for the case when users are weighted to prioritize them differently.
翻译:每个计算机系统 -- -- 从云层(如亚马逊)到计算机网络的调度员到操作系统 -- -- 都在系统用户之间进行资源分配。事实上的分配政策是单一资源的最高公平性(MMF),对多种资源的主导性资源公平(DRF),这保证了激励兼容性、无嫉妒和Pareqto效率等特性,假设用户需求是静止的(时间独立),但是,在现实世界系统中,用户需求是动态的,也就是说,用户需求是动态的,也就是说,对于有动态需求的多个资源和用户而言,MMF和DRF的需求是动态的,即时的。因此,计算机系统的目标与经典资源分配政策促成的属性之间现在存在根本的不相匹配性。我们的目标是弥合这种不匹配性。这个动态机制在动态、即时速MFMF值、DRF值1 和DRF值的当前配置结果中显示的是显著的不匹配性,但从整体上看,我们的资源配置的结果是低的。